基于换乘次数最少的城市公交网络最优路径算法

《基于换乘次数最少的城市公交网络最优路径算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第25卷第5期经济地理Vol.25，No.52005年9月ECONOMICGEOGRAPHYSep.，2005文章编号：1000-8462（2005）05-0673-04基于换乘次数最少的城市公交网络最优路径算法*王建林（浙江交通职业技术学院，中国浙江杭州311112）摘要：依据对公交乘客出行心理调查的统计结果，指出换乘次数最少是乘客出行时考虑的首要因素。描述了传统的Dijkstra算法，并分析了Dijkstra算法不适合公交网络最优路径选择的原因。最后根据公交乘客可以步行小段距离再转车的实际情况，提出一种基于换乘次数最少的公交最

2、短路径改进算法。关键词：公交网络；换乘次数；最优路径算法中图分类号：F294.3文献标识码：A点处具有连通性。但在公交网络中，如果将公交站点视为结1公交乘客出行心理研究点的话，那么同路公交线路在该点的连通性与不同公交线路在城市电子地图中，公共交通信息模块是必不可少的，它在该点的连通性是有差别的，这是因为不同路的公交线在同为各种交通信息的查询、统计提供方便直观的手段，为市民的一站点上的连通是需要换车而增加时间消耗的。另外多条公出行提供了方便。在研究公交网络模型和最优路径算法时，交线路虽然可以相交于空间上的同一个点，但是该点不一定有必

3、要先了解公交乘客出行时所考虑的因素，通过对公交乘是公交停靠站点，或者不是同时有停靠点，在这种情况下不同客出行心理、行为的研究来确定模型的优化目标和约束条件。公交线路在这一点也不是连通的。通常乘客选择出行路线时受到以下几个因素的作用：“换乘次数”、“出行距离”、“出行耗时”、“出行费用”。换乘次数是指乘客在完成一次出行过程中所换车的次数。出行距离则包括车上距离和车外距离，车外距离指的是乘客为了乘车而步行的距离，比如说从起点到上车站台的距离、中途换车所步行的距离以及从下车站台到终点的距离。出行耗时指乘客在一次出行过程中所需的时间，它也

4、包括车上和车外部分，车外耗时除了在车外距离部分所耗的时间外还包括在车站等车的时间。出行费用指的是乘客在完成一次出行过程中所花的车费。实际上这几个出行因素是相互影响的，如换乘次数和出行费用就是相关联的，特别是在一些实行一票制的城市中，这两个因图1公交乘客出行心理分析图Fig.1Psychologyanalysisofpassengerstrip素可以说是一致的。2.2公交站点的特性本文参照了在南京市做的一个公交乘客出行心理调查在公交线路网中，不同的公交线路在行程上一定会有重统计结果［1］，它主要对三个因素做了调查：换乘次数、出行距叠

5、，也就是说不同的线路上一定会有同名站点，但在公交站点离、出行耗时。从图1中可以看到有41.16%的乘客在选择出分布的实际情况中，即使是同名站点也存在空间位置相异的行路径时首先考虑的是换乘最少，其次考虑时间最短，而将路情况。如果将一个公交站点视为一个结点，在进行网络分析程最短作为出行时考虑的首要条件的乘客只占18.60%。时，就要求把空间上相近的异线同名站点合理抽象成一个结2城市公交网络的特点点。也就是在相应的网络图上不同属性的边在结点上连通，这样才能模拟不同公交线之间的可换车情况。城市中公交汽车沿着道路运行，形成的公交线路网是建2

6、.3公交网络中最短路径的意义立在道路网之上，依据道路建立的网络模型并不能直接应用公交乘客出行和汽车司机运货所考虑的因素是不同的，于公交网络，这是因为公交网络与道路网络相比有它的一些汽车司机运货关心的是如何选择最近距离，最大程度的省时特点。省油；而公交乘客出行更多考虑的是出门的方便性和舒适性，2.1连通性所以道路网络中的最短路径和公交线路的最短路径的意义是在道路网络模型中，通常是将道路交叉点抽象成一个结不同的。道路网络中的最短路径只要找出两点之间路径距离点，也就是说该结点连接着多条路段，路段与路段之间在该结*收稿日期：2005-03

7、-12；修回日期：2005-06-10674经济地理25卷为最短即可。但是在公交网络中，乘客不会为了寻找距离最S=SU｛j｝短路径而随意换车。因为从一条线路换乘到另一条线路是费3.2.3修改从v出发到集合V-S上任一顶点vk可达的最短时又费力的，在很多情况下，换乘另一趟车需要到另一个站路径长度。如果台，这就有一段的步行距离，而且在站台等车也是要消费时间D［j］+arc［sj］［k］

8、3.2.4重复操作（2）（、3）共n-1次，由此求得从v到图上其3传统的Dijkstra最优路径算法它各顶点的最短路径是依路径长度递增的序列。3.1最优路径概念3.3传统的Dijkstra算法不适合公交线路查询的原因地理网络的最优路径是指在地理网络