【摘 要】
:
随着物流业务的快速发展,物流企业越来越依赖精确快速的路径规划算法。多个节点间距离矩阵的计算在仓储设施选址、车辆路径规划等问题中都有着重要的作用,而精确的路径规划依
论文部分内容阅读
随着物流业务的快速发展,物流企业越来越依赖精确快速的路径规划算法。多个节点间距离矩阵的计算在仓储设施选址、车辆路径规划等问题中都有着重要的作用,而精确的路径规划依赖于精确的最短路算法。然而,由于普通的最短路算法只考虑行驶时间而无法处理路段之间的转向限制,故而无法搜索到符合实际情形的最短路径,无法应用于实际问题。除此之外,在求解多点对多点的最短路径时,多次调用单点对单点算法的方法时间复杂度极高,并不实用。本文对考虑转向限制的单源点单汇点最短路径问题和考虑转向限制的多源点多汇点最短路径问题进行了研究。针对考虑转向限制的单源点单汇点最短路径问题,本文不仅完成了基于弧标号的改进Dijkstra算法的高效实现,而且通过应用双向搜索的思想,提出了考虑转向限制的双向弧标号算法,使搜索效率进一步提高。另外,本文还通过使用邻接表存储地图数据和利用最小优先队列、哈希映射表对算法进行加速,大幅提升了算法的执行效率。针对考虑转向限制的多源点多汇点最短路径问题,本文应用了双向搜索的算法思想,提出了在考虑转向限制条件下的多点到多点的最短路径算法,即一种先对终点集合进行反向搜索,再对起点集合进行正向搜索的算法。这种搜索方式与多次调用基于弧标号的改进Dijkstra算法相比,在中等规模的交通路网中,效率提升明显。本文使用真实路网数据与模拟路网数据对以上算法进行了模拟实验。实验结果表明,在单源点单汇点最短路问题中,本文所提出的双向弧标号算法有着更好的搜索效率;在多源点多汇点最短路问题中,在规模适中的交通路网中,本文所提出的双向搜索算法性能提升明显,更具有实用性。
其他文献
大气污染不仅会直接导致空气质量恶化,还会导致水体和土壤污染,对生态平衡、人类健康和社会经济的可持续发展构成严重危害,因而受到普遍关注。大气污染物包括微尘、有毒有害
嗅鞘细胞(OECs)是存在于嗅觉系统中的一种特殊类型的胶质细胞,它起源于嗅基底膜,分布在嗅球、嗅神经并可伴随嗅束迁徙入脑。它不同于星形胶质细胞和雪旺细胞,但同时具有这两种细胞
任何文化都存在于一定的时间中,文化安全在时间驱动下发生变化,时间因素对文化安全产生何种影响,它是否会侵蚀、威胁文化安全,文章围绕三个问题展开了递进的分析。首先,时间通过对
目的:探讨“简式”经皮椎间孔内窥镜技术治疗中老年单节段腰椎间盘突出症的可靠性及临床效果,评价运用“简式”技术治疗中老年单节段腰椎间盘突出症术中、术后临床疗效,及分析数据,为中老年单节段腰椎间盘突出症的治疗提供指导从而使“简式”技术更好的应用于临床。方法:应用回顾性研究手法抽取2015年2月至2018年2月来我院就诊的中老年(50岁-80岁)单节段腰椎间盘突出患者60例,随机分为试验组(A组)(“简
煤基粗油是指原煤经各种热化学反应、化工过程加工处理后得到的初级液体产物,包括煤焦油、煤直接液化油和煤间接液化油等。以生产过程全流程物料衡算为约束条件,对煤基粗油全
在快速磁共振成像领域,传统的基于压缩感知的快速成像算法(CS-MRI)研究遇到了三个瓶颈:1)稀疏变换过于简单,无法捕获与生物组织相关的复杂图像内容;2)参数选取困难,且通用性
目的尿蛋白不仅是临床诊断肾脏疾病的标志,其也能加重肾损伤。白蛋白作为尿蛋白中最主要的成分,已经被证明能够引起肾小管细胞凋亡、线粒体功能障碍和氧化应激等。前期研究已
学校承担着人才培养的重要任务,向社会输送大量优秀人才,为我国现代化社会的建设提供了重要的力量,而近年来人们对于人才的评价标准逐渐发生变化,其中人才是否具备良好的心理
背景:冻结肩是临床常见疾病,治疗方法较多,大部分患者可以通过保守治疗治愈。而对于保守治疗无效的患者,目前有文献报道应用关节镜下松解结合麻醉下手法松解治疗,效果满意。目