考虑转向限制的路网中最短路径算法研究

发布时间：2020-09-21 20:41

　　 随着物流业务的快速发展,物流企业越来越依赖精确快速的路径规划算法。多个节点间距离矩阵的计算在仓储设施选址、车辆路径规划等问题中都有着重要的作用,而精确的路径规划依赖于精确的最短路算法。然而,由于普通的最短路算法只考虑行驶时间而无法处理路段之间的转向限制,故而无法搜索到符合实际情形的最短路径,无法应用于实际问题。除此之外,在求解多点对多点的最短路径时,多次调用单点对单点算法的方法时间复杂度极高,并不实用。本文对考虑转向限制的单源点单汇点最短路径问题和考虑转向限制的多源点多汇点最短路径问题进行了研究。针对考虑转向限制的单源点单汇点最短路径问题,本文不仅完成了基于弧标号的改进Dijkstra算法的高效实现,而且通过应用双向搜索的思想,提出了考虑转向限制的双向弧标号算法,使搜索效率进一步提高。另外,本文还通过使用邻接表存储地图数据和利用最小优先队列、哈希映射表对算法进行加速,大幅提升了算法的执行效率。针对考虑转向限制的多源点多汇点最短路径问题,本文应用了双向搜索的算法思想,提出了在考虑转向限制条件下的多点到多点的最短路径算法,即一种先对终点集合进行反向搜索,再对起点集合进行正向搜索的算法。这种搜索方式与多次调用基于弧标号的改进Dijkstra算法相比,在中等规模的交通路网中,效率提升明显。本文使用真实路网数据与模拟路网数据对以上算法进行了模拟实验。实验结果表明,在单源点单汇点最短路问题中,本文所提出的双向弧标号算法有着更好的搜索效率;在多源点多汇点最短路问题中,在规模适中的交通路网中,本文所提出的双向搜索算法性能提升明显,更具有实用性。
【学位单位】：清华大学
【学位级别】：硕士
【学位年份】：2015
【中图分类】：O157.5

【相似文献】

相关期刊论文 前10条

1 肖金声;;关于最短路径算法[J];中山大学学报(自然科学版);1987年03期

2 马东岭;;城市公交网络的最短路径算法研究[J];科技信息;2008年26期

3 胡于杰;李响;;利用最短路径算法确定地理网络中心服务范围[J];地理与地理信息科学;2010年03期

4 郑年波;陆锋;李清泉;段滢滢;;顾及转向延误的时间依赖A~*最短路径算法[J];测绘学报;2010年05期

5 涂海丽;;最短路径算法及其应用探讨[J];科技广场;2011年09期

6 毛少武;张焕国;黄崇超;吴万青;;改进的K最短路径算法在通信网络中的应用[J];武汉大学学报(理学版);2013年06期

7 张效贤;最短路径算法的应用[J];甘肃高师学报;1999年02期

8 冯晓辉;;交通网络中的最短路径算法探索[J];计算机光盘软件与应用;2013年21期

9 窦桂琴;杨青;黄祖锋;王雪萍;;一种基于城市应急系统的最短路径算法[J];广西师范大学学报(自然科学版);2007年04期

10 欧福军;刘萍;涂亚平;吴海兵;;大规模网络最短路径算法的优化及实现[J];海南大学学报(自然科学版);2008年02期

相关会议论文 前9条

1 王闯;董志江;;最短路径算法[A];吉林省测绘学会2008年学术年会论文集（下）[C];2008年

2 唐小勇;程琳;徐上;;考虑转向延误最短路径算法及实现[A];2007第三届中国智能交通年会论文集[C];2007年

3 陈再春;张云青;潘伯鸣;;最短路径算法在公交查询中的实现[A];首届长三角科技论坛数字区域建设与地理空间技术论坛优秀论文集[C];2004年

4 罗飞;魏开平;万润泽;;复杂网络中最短路径算法的研究及应用[A];2006全国复杂网络学术会议论文集[C];2006年

5 王明福;彭群生;;基于编码图的求解最短路径算法[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

6 孙绍河;朱瑞艳;;GIS中最短路径算法的研究[A];第二届“测绘科学前沿技术论坛”论文精选[C];2010年

7 张惠谦;;电信规划最短路径算法的Excel宏实现[A];中国通信学会信息通信网络技术委员会2005年年会论文集[C];2005年

8 王冬;张丽果;杜慧敏;韩俊刚;;基于R-Torus结构和最短路径算法的NoC建模[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（上册）[C];2008年

9 冯盼盼;蔺宏伟;于金辉;;投影法生成网格上的路径[A];第六届全国几何设计与计算学术会议论文集[C];2013年

相关博士学位论文 前1条

1 廖远;一对一最短路径算法研究及车载导航系统设计[D];南昌大学;2012年

相关硕士学位论文 前10条

1 罗丽虹;考虑转向限制的路网中最短路径算法研究[D];清华大学;2015年

2 郭东;基于Virtools的煤矿井下逃生系统的研究[D];太原理工大学;2016年

3 邓礼礼;求图中受限制的所有最短路径算法的分析与研究[D];华东师范大学;2009年

4 杨蔓;最短路径算法在煤矿安全分区分析中的应用研究[D];西安科技大学;2009年

5 张志敏;手机导航系统中最短路径算法的优化与实现[D];西北大学;2011年

6 王世明;典型城市路网中最短路径算法研究及实现[D];山东大学;2012年

7 杨争;武警警力调配系统研究与实现[D];国防科学技术大学;2010年

8 赵艳丽;实际路网最短路径算法优化与实现[D];华南理工大学;2015年

9 张波良;动态路网上最短路径算法研究[D];复旦大学;2013年

10 李洪扬;配网最佳抢修路径算法的研究[D];重庆大学;2002年

本文编号：2823967