Floyd算法在公交线路优化中的应用

《Floyd算法在公交线路优化中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第3期武汉工业学院学报Vol．30No．32011年9月JournalofWuhanPolytechnicUniversitySep．2011文章编号:1009-4881(2011)03-0037-06DOI:10．3969/j．issn．1009-4881．2011．03．010Floyd算法在公交线路优化中的应用王防修，周康，同小军(武汉工业学院数理科学系，湖北武汉430023)摘要:以城市交通优化问题为例，研究了网络交通优化问题的数学模型。在已有Floyd算法的基础上提出了改进的Floyd算法，该算法能够有效地解

2、决多权网络交通优化问题。以北京市公交为例，建立了多权交通网，讨论了从出发点A站到目的地B站的最优路线查询问题，运用Floyd算法建立该问题的数学模型。通过实例应用，进一步证明了该算法和模型的可行性和合理性。关键词:最优线路;赋权有向图;Floyd算法;多权交通网;交通优化中图分类号:TP301．6文献标识码:AApplyingFloydalgorithmtooptimizebuslinesWANGFang-xiu，ZHOUKang，TONGXiao-jun(DepartmentofMathematicsandPhysics，W

3、uhanPolytechnicUniversity，Wuhan430023，China)Abstract:Urbantrafficoptimizationproblemisputforwardandthenetworktrafficoptimizationmathematicalmodelisstudied．ThepaperproposestheimprovementonFloydalgorithm．Thealgorithmcaneffectivelysolvethenetworktrafficoptimizationprob

4、lem．Finally，withBeijingtrafficasanexample，thispapersetsupamulti－weighttrafficnetwork．TheoptimalrouteisdiscussedfromthepointstationAtothedestinationstationB．Atthesametime，ites-tablishsthemathematicalmodeloftheproblemthroughFloydalgorithm．Further，itprovesthefeasibilit

5、yandra-tionalityofthemodelandthealgorithmbyanapplicationexample．Keywords:bestroutes;empoweringdirectedgraph;Floydalgorithm;multi－weighttrafficnetwork;trafficoptimiza-tion随着社会的发展，最优线路问题成为研究交通常活动提供参考有很大的价值，是一个值得研究的问题中的一个重要问题，在解决公交最佳出行线路、课题。城市援救最佳线路、物流配送、高速公路联网收费等建立交通中

6、最优线路问题数学模型的目的就是与人们日常生活密切相关问题中发挥着重要的作寻找最优路径，为公众做出出行决策提供参考。目用。这些年来，城市的交通系统有了很大发展，为公前关于最佳出行线路问题的研究主要是一些传统算众的出行以及进行各项日常活动带来了很大的便法和根据问题的特点对传统算法进行改造。具有代利，但同时也面临着多条线路的选择问题。所以建表性的有Dijkstra算法、Floyd算法、Bellman算［1］［2］立交通中最优线路问题的数学模型，为人们进行日法;AngelicaLozano研究了标号修正技术在综收稿日期:2011-01

7、-13作者简介:王防修(1973－)，男，硕士，讲师，E－mail:wfx323@126．com．基金项目:国家自然科学基金资助项目(60574041)．38武汉工业学院学报2011年合运输网络中求解起点到终点的最短可行路径;Pa-Dk0=min{Dij}．i，j［3］olaModesti等针对最小出行时间研究了求解综合其中，k0为从Si到Sj所有可能线路中按最短距离所运输网络最短路径问题，使用多标记图构建运输网选的最优线路。络和对应的数据，并提出了求解算法。但这些已有2．2最少换乘次数的量化的算法都不能解决出行线路双向选择、

8、环形出行线对乘客而言，从起始点Si到目的地Sj可乘坐的路和多权问题，因此需要一种新的算法来建立交通主要交通工具是公汽，而公汽又包括一票制和分段中最优线路问题的数学模型。计价两种不同方式。设从起始站Si到目的地Sj所有的可能线路有k条;用I、II表示乘坐单一票价、分1最优线路的