基于实时道路的路径优化算法设计与实现

《基于实时道路的路径优化算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、申请上海交通大学工程硕士学位论文基于实时道路的路径优化算法设计与实现学校：上海交通大学院系：软件学院班级：Z0703793学号：1070379109工程硕士生：丁玥工程领域：软件工程导师I：王东（副教授）上海交通大学软件学院2010年1月ADissertationSubmittedtoShanghaiJiaoTongUniversityfortheMasterDegreeofEngineeringTHEDESIGNANDREALIZATIONOFROUTEOPTIMIZATIONALGORITHMBASEDONREAL-TIMEPATHINFORMATIONAuthor：Ding

2、YueSpecialty:SoftwareEngineeringAdvisorI:Prof.WangDongSchoolofSoftwareShanghaiJiaoTongUniversityShanghai,P.R.ChinaJanuary,2010基于实时道路的路径优化算法设计与实现摘要随着对物流配送路径优化问题研究的不断深入，各种路径优化算法在物流领域已经有了广泛且成熟的应用。但是传统的路径优化算法都是基于静态信息的计算，现今城市路面交通状况每况愈下，传统的路径优化算法已经无法满足目前路径优化的需求。随着全球定位系统GPS的发展以及各种路况采集技术的成熟，以往无法收集到的实

3、时交通数据现在已经完全可以作为路径优化的全新计算参数,为基于实时道路的路径优化提供了可能。今后随着3G网络和WiFi的普及，信息的传递将更加便捷，在这样的背景下如何利用城市实时道路信息来进一步规划合理的行驶路径已经成为目前物流领域急需解决的课题。本文提出了将传统的解决车辆路径问题（VehicleRoutingProblem，VRP）的蚁群算法与解决最短路径问题的A*算法结合成为两阶段算法，以求解“次优快速解”的思想对蚁群算法进行了高效实现，将蚁群算法的输出作为A*算法的输入，对A*算法进行了重点改进，将实时道路信息作为一个新的计算维度融入A*算法，提出了基于时间换算和基于路程换算

4、的A*算法，同时也提出了A*算法结点的预处理方法。本文开发了一套基于实时道路信息的路径优化系统，能够适用于指定配送模型下的路径优化，使用真实的上海市道路交通实时路况数据对算法进行了验证并得到比较满意的优化结果。本文首先分析了相关的路径优化算法和城市实时路况采集技术；接着，本文提出了基于实时道路的路径优化解决框架，详细阐述了该模型-第I页-的各个关键部分；然后，本文设计了高效的蚁群算法和改进的A*算法作为核心算法，同时在后台数据库存放了真实的道路路况数据作为计算参数；最后在系统的实现部分，本文使用J2EE相关技术和ORACLE10g数据库完成了基于MVC架构的系统实现，并使用上海市

5、电子地图与MapXtreme完成了基于GIS的结果显示。关键词：实时道路，改进的A*算法，GIS-第II页-DesignandRealizationofRouteOptimizationbasedonReal-TimePathInformationABSTRACTWiththein-depthstudyoflogisticsdistributionrouteoptimization,avarietyofrouteoptimizationalgorithmsinlogisticsfieldhavehadextensiveandsophisticatedapplication.But

6、traditionalrouteoptimizationalgorithmsarebasedonstaticinformation,thecurrenttrafficsituationinthecityisdeteriorating;traditionalrouteoptimizationalgorithmscannotmeettheneedsofcurrentrouteoptimization.WiththedevelopmentofGPSandmatureapplicationofvarioustrafficcollectiontechnologies,thetrafficd

7、atawhichisunabletocollectinthepastcanbefullyusedasanewcalculatingparameter,thus,itprovidethepossibilitytocalculaterouteoptimizationbasedonreal-timepathinformation.Withthepopularityof3GnetworksandWiFiinthefuture,thetransmissionofdatawillbemore