第 31 卷第 2 期
唐山师范学院学报
以直达，不需要换乘。如图 1 所示。 （2） 起点 且存在
2009 年 3 月
它车走的距离以及下车后到终点行走的距离， 车上距离指的 是所乘公交车所走的距离。 出行时间也同样包括车外时间和 车上时间。 车外时间指乘客的车外路程消耗的时间以及站台 等车时间，车上时间指乘坐公交车所消耗的时间。出行消费 指乘公交车所消费的费用。 乘客的目的就是在较短的时间内 以较少的代价到达目的地，而一般情况下如果转车次数越 多，由此引起问题的可能就越多。如等车时间，道路状况， 上下班高峰期等情况都会引起车外时间延长。 由于唐山市大 多数公交线路，均为无人售票的单一票价的公交车线路，所 以转车次数越多则乘车代价越高。 因此在实际乘车过程中换 乘次数越少，也就实现了乘车费用越少，且出行消耗时间越 短。在转车次数相同，即乘车消费相同的情况下，再选择路 径最短。假设相邻两站点之间的距离大致相等，路径越短也 就是起点与终点之间的公交站点越少。 当乘客所选择的起点 和终点的直线距离小于 300 米时， 当没有公交车可以直接到 达时，则可建议乘客步行。通过以上分析，将换乘次数最少 定为选择乘坐公交车的最佳路径的首要目标， 在此基础上以 出行距离最短定为最佳路径的第二目标。 这样可使乘客乘坐 公交车费用最少、出行时间最短，符合乘客的出行心理。 3 公交车最佳路径算法设计及优化 对城市公交线路进行最佳路径分析， 需要将现实中的城 市公交网络的实际情况抽象为图论中的网络图， 常用的几种 网络最短路径算法有：Dijkstra 算法、Floyd 算法等，目前被 公认为最好的算法是 1959 年迪杰斯特拉提出的 Dijkstra 算 法，不仅能求出起点到各个点的最短路径，而且能求出任意 两点间的最短路径。 虽然 Dijkstra 算法能算出一条最短路径， 但根据公交路线的特点，我们需要计算的是换乘次数最少， 或换乘次数相同，所经过的站点最少（相邻两站点之间距离 大致相等） 。所以最短路径并非最佳路径，故此 Dijkstra 算 法不适合找到我们需要的最佳路径。 3.1 最佳路径算法 1 将唐山市所有的公交线路设为 P，记为
之间的公交车站点数最小，即 选择的最佳路径。
m j 的值最小的线路为所
（2）对于情况（2） ，遍历 P ，只要存在 p (i ) ， p ( h) ， 使得 pij p (i ) ， p hk p (h) ，且 p (i ) p ( h) ，则 存在换车站点 p ef p ef p (i ) p ( h) ， 设 p ef 在 p (i ) 中 的对应站点为 piq ， p ef 在 p ( h) 中的对应站点为 p hr ， 则乘 q j r k p ( i ) p ( h )中 车总站数 N 为 N 。遍历 的每一个 p ef ， n minN 为最少乘车站数，那么此时 p ef 为最佳换乘站点，最佳路径为 pij → p ef ， p ef → p hk ， 其中
目前公交车最佳路径的算法有很多种， 算法的区别在于数据存储的结构， 各个数据存储结构有各自的优点与不足， 基于唐山市公交基础信息和实际生活中公交乘客出行的特点，设计了合乎乘客需求的最佳路径查询的算法。提出 以换乘次数最少为首要目标， 在此基础上以出行距离最短为第二目标的算法。 可将其用于公交公司的管理系统中， 也可以用于公交公司查询服务系统中。 关键词：公交查询；最佳路径；算法；数据结构；优化 中图分类号： TP301.6 文献标识码：A 文章编号： 1009-9115(2009)02-0079-04
p ef
为换乘站点。
p(i ) ， p(h) ， 使得 pij p (i ) ， p hk p (h) ，且 p (i ) p ( h) ，遍历 p(i ) 中 所 有 站 点 ， 若 存 在 换 车 站 点 p ef ， p ef p(i ) p (e) ，ptu p(h) p(e) ， 则说明 p ef ，ptu 为乘车路径中的两个换车站点， i 、 e 、 h 为乘车线路，同 样 p ef ， ptu 及 i, e, h 也存在很多，必须要对所有方案进行

p1n p 2n p sn
每个站点信息可以有两部分组成，站名和本站编号。 对于任意的起点 下几种： （1）起点 p ij 与终点 p hk 在同一线路上，即 i h ，可 -80-
pij 与终点 p hk ，可能存在的情况有以
图 4 换乘两次以内无法到达 算法过程也根据以上的分析分为四个层次：
第 31 卷第 2 期 V学报 Journal of Tangshan Teachers College
2009 年 3 月 Mar. 2009
计算机与自动化技术
公交车最佳乘车路径优化算法
王 祥
（北京交通大学 计算机学院，北京 100044） 摘 要： 公交乘客出行路径选择是公交乘客信息系统的关键技术， 而公交车最佳路径算法是路径选择的基础，
pij 与终点 p hk 不在同一线路上，通过换车
三次和三次以上，乘车不易到达，提示乘客没有最佳路径。 换乘三次的情况。如图 4 所示。
P= ( p(0), p (1), p (2),, p (i ),, p( s ))T 其中 p (i ) 表示第 i 号线路所有公交车站点的名称，记为
图 3 换乘两次示意图
Optimization Algorithm of Best Travel Path
WANG Xiang
(School of Computer, Beijing Jiaotong University, Beijing 100044, China) Abstract: Bus travel path selection is the key technology of passenger information system, and the optimization algorithm of the best travel path is the basis for the current path selection. There are many algorithms of the best travel path, and some of them are different in the structures of data storage. Data storage structures all have their own advantages and disadvantages. Based on the characteristics of basic Tangshan city bus information and passengers travel in actual life, an algorithm of the best path query is designed to satisfy the requirements of passengers, and an algorithm is proposed, taking the least change as the first target, the shortest travel distance as the second target. Key words: bus inquiries; best path; algorithm; data structure; optimization 1 引言 车出行的乘客的心理行为进行调查研究， 确定优化的目标和 条件， 通过对公交乘客的随机问卷调查得知公交乘客选择乘 车路径的心理过程，主要受到以下因素的影响，换乘次数， 出行距离，出行时间和出行消费。如表 1 所示。 表 1 出行影响因素比例表 影响因素 所占比例 换乘次数 45% 出行距离 30% 出行时间 20% 出行消费 5%
p(i ) ( pi 0 , pi1 , pi 2 , , pij ,, pin ) 其中 p ij 表示第 i 路公交车行使线路上的第 j 个站点信息 （假
设公交车的往返是相同的站点） 。因此 P 也可以记为
p11 P p 21 p s1
p12 p 22 p s2
s11 s S 21 sn1
s12 s22 sn 2

s1k s2 k snk
sij （ 1 i n ，1 j k ， k 为任意站点最多的车次
数）为经过 s i 的所有行车路线。每个数据有信息：①路线 编号，②路线名称，③此站在此线路上的位序。 查找 s i 站到 s j 站的最佳路径的具体步骤如下： ，则进行 （1）如果∣ s i - s j ∣< d ,（ d 在 300 米左右） 步行分析，如果存在合适步行的路线则建议乘客步行。 否则转（2） 。 （2）经过站点 s i 的所有车的集合为 PASS A ，经过 站点 s j 的所有车的集合为 PASS B ，如果 PASS A ∩
其中换乘次数指的是乘客完成一次由起点到达终点的 出行过程中所换乘公交车的次数。 出行距离分为车外距离和 车上距离。 车外距离指的是乘客为乘坐某路公交车而行走的 距离，其中包括从起点到上车地点步行的距离，中途换乘其
────────── 收稿日期：2009-01-14 作者简介：王祥（1965-） ，男，河北唐山人，北京交通大学硕士研究生，唐山师范学院高级工程师，研究方向为计算机网络 安全及软件工程。 -79-
王
（1）对于情况（1） ，只要遍历 P 中
祥：公交车最佳乘车路径优化算法
乘三次到达终点视为无最佳路径。 欲查找从起始站点 A 到目的地站点 B 的最佳路径，可 以从 A 点出发，以公交车路线为基础进行广度优先搜索， 到 B 站点即告终止，找到 B 站点时，一定是转车次数最少 的。若从站点 A 到站点 B 的可接受换乘次数最多为两次， 则出行的最佳路径还可用如下算法给出： 数据以数组的形式存储， S 为所有站点的集合记作 S s (1), s (2),, s (n) T 即