基于换乘次数最少的公交网络最优路径模型研究new

《基于换乘次数最少的公交网络最优路径模型研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、维普资讯http://www.cqvip.com第l8卷第!期计算机技术与发展vo12008年．1月．．18NlCOMPUTERTECHNoL()(YANDDEVELOPMENTJan．2008基于换乘次数最少的公交网络最优路径模型研究侯刚，周宽久，2(1．大连理工大学软件学院，辽宁大连116620；2．大连理工大学系统工程研究所，辽宁大连116024)摘要：结合乘客出行心理分析，提出以换乘次数最少为目标的公交乘车模型。在公交网络建模方面，综合考虑公交站点空间关系，提出空间数据到拓扑模型再到搜索模型的公交网络双层建模方案。通过搜

2、索模型的建立，将最小换乘次数问题转化为两点间的最短路径问题进行求解。在搜索算法的设计上，首先提出改造的边权为1的Dijktra算法，以此为基础设计前驱节点算法。并以前驱节点算法为前提，设计所有最短路径算法，能够高效地求解两点间的所有换乘次数最小的乘车方案。最后，以大连市公交数据为例，验证了建模方案和算法的可行性。关键词：换乘次数；公交网络；所有最短路径算法中图分类号：U491；O189文献标识码：A文章编号：1673—629x(20o8)01—0o44—04ResearchforPublicTrafficNetworkModel

3、ofOptimumRoutewithMinimalTransferTimesHOUGang，ZHOUKuan-jiu，(1．SoftwareSdx~ol，DalianUniversityofTechnology，Dalian116620，China；2．InstituteofSyst~asEngineering，DalianUniversityofTechnology，Dalian116024，China)：Consideringp{ISs朗gers’travelpsychoanalysis，thepublictrafficmo

4、delofoptimumrouteisproposed，whichgoalisminimaltransfertimes．Ontheintegratedanalysisofthespacerelationshipbetweenstations．thetwice—projectofhowtOfoundthepublictrafficnetwork’smodelispropc~l，whichisfromthespacedatatothetopologymodelandfinallytothesearchingmode1．Basingo

5、nthesearch·ingmodel。theleasttransfertimesproblemissolvedbytranslatingtOtheproblemoftheshortestroutebetweentwos~tions．n·provedI~jkstraalgorithmwithedgevalueisoneispropo~l。andtheprior—nodealgorithmisdesignedbasingonit．Thentheall—short·est—routealgorithmisconstructedoft

6、heor—nodealgorithm，whichcanefficientlysolvethetrav~lproiectofalltheleasttransfertimbetweentwospots．Rnally，DalianpublictrafficdataisusedaSanexampletoprovethatmoddingofpublictrafficnetworkandthesearchingalgorithm&refeasible．KeyM岫rds：transfertimes；publictrafficnetwork；w

7、holeshortestroutealgorithmO引言于“最优”的指标选取因人而异，一些研究者从不同的对公交出行最优乘车问题的理论研究包括公交网角度提出了算法。张国伍等结合公交网络的特点，在络的数学描述和设计最优路径算法。在公交网络描述推广Floyd算法的基础上提出了一种公交网络多条最短路径算法r；Koncz等提出了一种以换乘次数少为方面。Anez等用对偶图描述能够涵盖公交线路的交通网络[；Choi等讨论了利用GIS技术从街道的地理数首要目标，以出行距离短为次要目标的公交网络静态多路径选择算法[5]；Qiujinwu等利用图

8、论中的K最短据产生公交线路和站点的问题-2；黄正东研究了在GIS中公交实体与基础路网的关联L3J。这些为公交网路径算法求解公交网络中的多路径优化问题【6；严寒络的数学描述提供了基础。在最优路径算法方面，由冰等研究了城市交通中的最短路算法-7；杨新苗等设计了以换乘