资源描述：
《以最小换乘次数和站数为目标公交出行算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第24卷第12期计算机应用Vol.24No.122004年12月ComputerApplicationsDec.2004文章编号:1001-9081(2004)12-0136-02以最小换乘次数和站数为目标的公交出行算法112赵巧霞,马志强,张发(1.空军工程大学电讯学院,陕西西安710077;2.西安交通大学管理学院,陕西西安710049)(richter@pub.xaonline.com)摘要:提供两点乘车的最优公交路径是ATIS的核心功能。文中建立了以最小换乘次数为第一目标,最小途经站数为第二目标的公交出行最优路径模型。提出了可行路径的最小换
2、乘次数动态规划算法,依此确定换乘次数上界;设计了搜索算法确定最优公交线路序列,分析了线路相交的四种情况,给出了换乘点选择方法,由公交线路序列和换乘点共同组成最优路径。关键词:最优路径;换乘;途经站数;公共交通中图分类号:U491.2;O157.5文献标识码:AAlgorithmsforpublictransittripwithminimaltransfertimesandstops112ZHAOQiao2xia,MAZhi2qiang,ZHANGFa(1.Tele2CommunicationSchool,AirForceUniversityofEn
3、gineering,XipanShaanxi710077,China;2.SchoolofManagement,XipanJiaoTongUniversity,XipanShaanxi710049,China)Abstract:ProvidingoptimumrouteforpublictransittripisacorefunctionofATIS.Amodelofoptimumroutewiththeminimaltransfertimesasprimarygoalandtheminimalstopsassecondgoalwasbuilt.B
4、asedontheprincipleofoptimality,adynamicprogrammingalgorithmofminimaltransfertimesforaviableroutewasdesignedandthiscouldbeusedtodeterminetheupperbound.ABFSalgorithmwasdesignedtofindthelinesserialoftheoptimumroute.Transferwasdeterminedbasedontheanalysisoffourclassofinterconnecti
5、vityoflines.Theoptimumroutewascomprisedoflinesserialandtransfers.Keywords:optimumroute,transfer,stopsinroute,publictransit0引言1公交乘车模型随着ATIS(先进的出行者信息系统)的发展,为出行者提选择公交方式出行时,可行的乘车方案一般有多个,出行[2]供公交出行计划成为可能。其中一个核心问题是两点乘车者必须做出选择。而出行者考虑的因素很多,如换乘次数、旅[6]问题,即对公交出行者给出的任意一对起讫点,如何确定最优途时间、费用等,
6、不能简单的抽象为最短路问题。研究表明[7]乘车方案。所谓乘车方案是一个站点、线路的交替序列,该序一般出行者以换乘次数为优先考虑的目标,公交网络的设[10]列说明从起点出发乘坐何线路,途中如何换乘,直至到达讫点。计也以减少平均换乘次数为重要目标,因此本文以最小换对公交出行最优乘车问题的理论研究包括公交网络的数乘次数为第一目标。另外,旅途时间具有随机性,而旅行费用[9]学描述和设计最优路径算法。在公交网络描述方面,Anez等的计算方式较多,但一般而言所需时间、费用都与途经的站用对偶图描述能够涵盖公交线路的交通网络[3],Choi等讨论数正相关,为避免过
7、于复杂,本文选择最小途经站数为第二目了利用GIS技术从街道的地理数据产生公交线路和站点的标。即:在所有可行路径中选择换乘次数最小,且在满足此目问题[4],黄正东研究了在GIS中公交实体与基础路网的关标条件下使途经站数最少的路径为最优路径。联[5],这些为公交网络的数学描述提供了基础。在最优路径这样,公交乘车问题的一般模型为:设给定起点v0和讫点vd,可行的公交路径集合为TR={TRi
8、TRi=},TRi表示在起点v0选择线路同的角度提出了算法,
9、如严寒冰等研究了城市交通中的最短[6]pi1到达vi1,换乘pi2到达vi2,⋯,最终到达vd,该路径换乘次路算法,杨新苗
