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

第 25 卷第 5 期 经 　　济 　　地 　　理 Vol. 25 , No. 5 2005 年 9 月 　　　　　　　　　　　　　　ECONOMIC GEOGRAPHY　　　　　　　　　　 　　　　 Sep. , 2005 ( ) 文章编号 :1000 - 8462 2005 05 - 0673 - 04 基于换乘次数最少的城市公交网络最优路径算法 王 　建 　林 (浙江交通职业技术学院 ,中国浙江 杭州 　311112) 摘 　要 :依据对公交乘客出行心理调查的统计结果 ,指出换乘次数最少是乘客出行时考虑的首要因素。描述了传 统的 Dijkstra 算法 ,并分析了 Dijkstra 算法不适合公交网络最优路径选择的原因。最后根据公交乘客可以步行小段 距离再转车的实际情况 ,提出一种基于换乘次数最少的公交最短路径改进算法。 关键词 :公交网络 ;换乘次数 ;最优路径算法 中图分类号:F294. 3 文献标识码 :A 点处具有连通性。但在公交网络中 ,如果将公交站点视为结 1 　公交乘客出行心理研究 点的话 ,那么同路公交线路在该点的连通性与不同公交线路 在城市电子地图中 ,公共交通信息模块是必不可少的 ,它 在该点的连通性是有差别的 ,这是因为不同路的公交线在同 为各种交通信息的查询、统计提供方便直观的手段 ,为市民的 一站点上的连通是需要换车而增加时间消耗的。另外多条公 出行提供了方便。在研究公交网络模型和最优路径算法时 , 交线路虽然可以相交于空间上的同一个点 ,但是该点不一定 有必要先了解公交乘客出行时所考虑的因素 ,通过对公交乘 是公交停靠站点 ,或者不是同时有停靠点 ,在这种情况下不同 客出行心理、行为的研究来确定模型的优化目标和约束条件。 公交线路在这一点也不是连通的。 通常乘客选择出行路线时受到以下几个因素的作用 :“换乘次 数”、“出行距离”、“出行耗时”、“出行费用”。换乘次数是指乘 客在完成一次出行过程中所换车的次数。出行距离则包括车 上距离和车外距离 ,车外距离指的是乘客为了乘车而步行的 距离 , 比如说从起点到上车站台的距离、中途换车所步行的距 离以及从下车站台到终点的距离。出行耗时指乘客在一次出 行过程中所需的时间 ,它也包括车上和车外部分 ,车外耗时除 了在车外距离部分所耗的时间外还包括在车站等车的时间。 出行费用指的是乘客在完成一次出行过程中所花的车费。实 际上这几个出行因素是相互影响的 ,如换乘次数和出行费用 就是相关联的 ,特别是在一些实行一票制的城市中 ,这两个因 图 1 　公交乘客出行心理分析图 Fig. 1 　Psychology analysis of passengers trip 素可以说是一致的。 2. 2 　公交站点的特性 本文参照了在南京市做的一个公交乘客出行心理调查 [1 ] 在公交线路网中 ,不同的公交线路在行程上一定会有重 统计结果 ,它主要对三个因素做了调查 :换乘次数、出行距 叠 ,也就是说不同的线路上一定会有同名站点 ,但在公交站点 离、出行耗时。从图 1 中可以看到有41. 16 %的乘客在选择出 分布的实际情况中 ,即使是同名站点也存在空间位置相异的 行路径时首先考虑的是换乘最少 ,其次考虑时间最短 ,而将路 情况。如果将一个公交站点视为一个结点 ,在进行网络分析 程最短作为出行