基于改进后的地图匹配算法及dijkstra算法的动态路径优化问题的研究

《基于改进后的地图匹配算法及dijkstra算法的动态路径优化问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代码：10255学号：2160873中图法分类号：U491.1基于改进后的地图匹配算法及Dijkstra算法的动态路径优化问题的研究RESEARCHONDYNAMICPATHOPTIMIZATIONPROBLEMBASEDONIMPROVEDMAPMATCHINGAlGORITHMANDDIJKSTRAALGORITHM学科专业：物流工程作者姓名：陈思远指导教师：王文杰答辩日期：2018.05.16东华大学学位论文原创性声明东华大学学位论文原创性声明本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文

2、中已明确注明和引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日东华大学学位论文版权使用授权书东华大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本版权书。本学位论文属于不

3、保密□。学位论文作者签名：指导教师签名：日期：年月日日期：年月日东华大学硕士学位论文答辩委员会成员名单姓名职称职务工作单位备注陈顺华副总裁答辩委员会主席上海物联网投资基金刘峰涛副教授答辩委员会委员东华大学王扶东副教授答辩委员会委员东华大学李庆颖副教授答辩委员会秘书东华大学摘要基于改进后的地图匹配算法及Dijkstra算法的动态路径优化问题的研究摘要近年来，城市物流配送业的需求日益旺盛，这得益于经济及交通技术的高速发展。全面地优化配送模型，提高物流配送效率越来越有必要性。而另一方面，城市交通问题日益严重，ITS（智能交通系统）由此产生，智能交通系统是可以为车辆提供实时有效

4、的信息，实现路线规划，减少车辆的行驶时间，缓解道路拥堵的状况，减少污染，节约能源的利用交通信息系统、定位系统和智[39]能化分析的交通系统的总称。动态路径优化在解决交通拥堵等方面发挥着越来越大的作用，是智能交通系统中必不可少的一部分。如何在规定的时间之内，在克服交通拥堵等困难的情况下，合理地安排物流配送车辆的行驶路径，以最少的行程时间完成配送任务，是当今物流业中的一个重要问题。将高效实用的动态路径优化技术应用于当前的物流配送中，能够缩短配送时间，降低配送成本，提高物流服务水平。本文进行了基于改进后的地图匹配算法及Dijkstra算法的动态路径优化问题的研究，相关研究内容

5、如下：首先，详细阐述了研究动态路径优化的背景及意义，介绍了地图匹配及路径优化的国内外研究现状及其相关理论，强调研究动态路径优化问题的必要性。其次，在详细介绍地图匹配相关知识的基础上，改进了一种利用Frechet距离的应用于物流车辆导航的地图匹配方法，新算法在调整性、实时性、整体性3个方面作了修改，从而提高了匹配的准确率。为了测试地图匹配算法的性能，论文利用收集的车辆的GPS数据在相关软件上进行了相应的实际测试。研究结果表明，新的地图匹配算法在车辆导航中，具有可行性和可操作性，修正了GPS定位信息的偏差，匹配精度更高，体现出了新算法的优势。因此地图匹配算法不仅具有理论上的

6、研究意义，也具有实际应用的价值。这样，获得的准确、实时的动态交通信息为物流车辆路径选择提供了基础条件。再次，研究了图论中图的相关概念，并在此基础上研究分析了经典的I摘要Dijkstra算法。针对经典Dijkstra算法的缺陷提出优化方案，在存储结构、搜索方式、数据队列3个方面作了改进。通过将改进前后的Dijkstra算法的运行结果进行比较，验证了改进后的算法在搜索效率等方面的优势。最后，将城市的道路网络抽象成虚拟路网，在虚拟路网的基础上构建了以路段的行程时间作为权值、以行驶时间最少作为目标函数的动态路网模型。通过仿真实验，可知本文的动态路径优化算法规划出的最优物流配送路

7、径比较符合实际情况，具有较高的实用价值。关键词：动态路径优化问题；地图匹配；Dijkstra算法IIABSTRACTRESEARCHONDYNAMICPATHOPTIMIZATIONPROBLEMBASEDONIMPROVEDMAPMATCHINGAlGORITHMANDDIJKSTRAALGORITHMABSTRACTInrecentyears,withtherapiddevelopmentofsocialeconomyandtransportationtechnology,urbanlogisticsdistributionhaveb