公路交通中车辆路径A＊算法优化的研究.pdf

《公路交通中车辆路径A＊算法优化的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、总第294期计算机与数字工程Vo1．42No．42014年第4期Computer&DigitalEngineering609公路交通中车辆路径A*算法优化的研究顾保磊吴云(中国地质大学江城学院武汉430200)摘要公路交通管理中，最短路径是进行车辆路径优化的基础。论文在简单分析了一些经典的最短路径算法和这些最短路径算法单独应用于车辆路径优化存在的局限性的基础上，提出了一种改进A*算法的方法口]，并用它来解决城市间道路网中实时最短路径问题，并以实例加以阐述。关键词最短路径；车辆路径优化；A*中图分类号TP312DOI：

2、10．3969／j．issn1672—9722．2014．04．017OptimizationofA*AlgorithmaboutVehicleRouteinHighwayTraficGUBaoleiWUYun(JiangchengCollege，ChinaUniversityofGeosciences，Wuhan430200)AbstractInmanagementofhighwaytraffic，theshortestroutealgorithmisthebasisofvehiclerouteoptimizati

3、on．Inthispaper，someclassicsalgorithmofshortestrouteandthelimitationofthesealgorithmsseparatelyappliedtOthevehiclerouteoptimizationareanalyzed．Basedonsuchalgorithm，amodifiedmethodofA*algorithmisproposedsolvetheproblemofreal—timeshortestrouteininter-cityroadnetwo

4、rk．KeyWordsshortestroute，vehiclerouteoptimization，A*CIassNumberTP312两个算法。1引言2．1Dijkstra算法随着公路交通管理技术的应用和发展，车辆路最短路径的算法中经典的算法是kstra算径优化问题已成为现代公路交通管理过程中研究法l_4J，主要思想是：路线抽象为网络中的边，边的权值的一个热点3]。众多因素影响着车辆路径优化问为道路的相关参数，算法确定了网络中从某点到其它题，各种因素之间关系十分复杂。在城市与城市间节点的最小权值的路径。该算法忽略了

5、网络模型中道路网络模型的路径寻优问题中，具有顶点数多和个体特眭；按路径长度递增的次序产生最短路径，实现对网络模型中的路线查询一般需要一定的动态性从某个源点到其余各个节点的最短路径，时间复杂度的特点。随着全国城市规模的发展，城市间的交通较高，为O(n2)。受计算机硬件水平等限制，如果直接系统变得越来越复杂。用于解决实际问题，在一定程度上不能满足要求。2．2Floyd算法2传统的最短路径算法Floyd算法是一种穷举型算法，按路径搜索试由于问题具有纷繁复杂的特征、网络特性等，探产生最短路径，可以一次性求出所有顶点间的最最短

6、路径算法表现出一定的多样性，但可以按问题短路径，时间复杂度也是O(2)。如果需要计算任的类型、网络特征和求解技术的不同进行分类。通意两个节点之间的最短路径，Floyd算法比较合常，传统的最短路径算法主要有Dijkstra和Floyd适，如果对具有成千上万个顶点的城市间道路网来+收稿日期：2013年1O月9日，修回日期：2013年l1月21日作者简介：顾保磊，男，教授，研究方向：程序设计理论与方法、计算机网络、软件工程。吴云，女，讲师，研究方向：程序设计理论与方法、物联网。2014年第4期计算机与数字工程651验得到的

7、命名实体进行分类处理。traction：BoostingandtheVotedPerception[C]／／Pro—ceedingsofthe40thAnnualMeetingoftheACL，2002：参考文献489-496．[1]张晓艳，王挺，陈火旺．命名实体识别研究[J]．计算机[1O]MCollins．RankingAlgorithmsforNamed-EntityEx—科学，2005(4)：44—48．traction：BoostingandtheVotedPerception[C]／／Pro—ZHANGX

8、iaoyan，WANGTing，CHENHuowang．ceedingsofthe40thAnnualMeetingoftheACL，StudyofNamedEntityrecognition[J]．ComputerSci—2002：489—496．ence，2005(4)：44—48．[11]MJansche．NamedEntityExtra