最佳公交线路的实时查询模型及算法
摘要
本文针对查询者的不同需求，为公交查询系统提供了最佳线路查询的模型与算法。
查询者的需求从换乘次数少、时间少和费用少三方面进行考虑。故查询算法从换乘次数（从实际出发，换乘不超过两次）入手：
对直通的任意两站点，可设计出较简单的最佳直通线路查询算法（直通算法）。故对需要查询的两站点，算法先由线路、站点的原始数据判断此两站点是否直通，若是，便可通过直通算法进行查询。
不论是否存在直通线路，算法都考虑对换乘的情形进行查询。考虑到城市公交系统中的站点基数较大，可行的换乘方案数也将较大，故查询算法根据所有可行的一、二换乘点必与起、止站点直通的原则，对可能成为给定两站点的换乘点的站点进行了筛选，得到相关站点集，较大的缩小了查询的范围。
得到相关站点集后，建立了反映站点集中任意两站点直通关系的连通矩阵，并通过矩阵乘法，较快地得出了所有可行的一次、二次换乘点。考虑到所有可行的换乘点可能较多，特别是二次换乘的情形，故查询算法采用分支定界法以较高效率对最佳方案进行了最后的筛选。
在考虑地铁的公交系统时，本文从实际出发，对模型进行了一定的修改。同时，本文考虑了引入站点之间的步行时间的情况，提出了线路选择的模型。
由于筛选算法、矩阵乘法和分支定界法的高效性，整个查询算法具有很高的效率，并能在换乘次数不超过两次的条件下，求得全局最优解，得出满足查询者不同需求的所有最佳方案。并且，从系统设计的角度出发，整个系统需要预存的数据量很小，系统的实用性很强。
对给定的六对站点，采用本算法进行查询，在1.7GHZ的CPU环境下，平均运行时间为：1.27秒，最长运行时间为7.43秒，验证了算法的实时性。同时，对每一对站点，得到了满足不同查询需求的所有最佳线路方案，验证了模型与算法的精确性。
关键词：最佳线路、实时、筛选算法、分支定界
一、问题重述
第29届奥运会将于今年8月在北京举行，届时有大量观众到现场观看比赛，其中大部分人将乘坐公共交通工具（包括公汽、地铁等）出行。北京市的800多条公交线路使得公众面临多条线路选择问题。因此，有必要开发一个解决公交线路选择问题的自主查询计算机系统。
现有如下数据：
1.基本参数设定：包括相邻站点平均行驶时间、换乘时间、票价等信息。
2.公交线路信息：包括公汽和地铁的所有线路、途经站点、票制等信息。
3.公交换乘信息：包括在每个地铁站点可以换乘的所有公汽站点。
从实际情况出发考虑，在满足查询者不同需求的条件下，我们需要完成如下工作：
1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算
法。并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的
最佳线路（要有清晰的评价说明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485
(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676
2.同时考虑公汽与地铁线路，解决以上问题。
3.假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数
学模型。
二、问题分析
对于公交线路查询系统，需设计查询最佳公交线路的模型和算法，满足查询者的各种需求，并使查询系统具有实时性。
对于一般的查询者来说，对线路的选择主要有以下几种需求：换乘次数少、乘车总时间少和乘车总费用少，但不同的查询者对这三个因素有不同的偏好，故查询系统应能提供多种方案供查询者自行选择。
可以先固定换乘次数，求得连通某两个站点的所有方案；再对在该换乘次数下的每一种乘车总费用所对应的方案，筛选出花费时间最少的方案；最后再对换乘次数不同的方案进行比较，淘汰掉劣势方案，得出满足不同查询者需求的最佳线路集。
从实际的城市交通状况出发，交通部门在设置公交站点时会保证整个城市交通网的连通性，以方便人们出行，故可以假设任何两个公汽或地铁站点最多经过2次换乘便可到达。
在查询系统寻找最佳线路集时，若给定的两站点直通，可方便的找出其最佳线路，得到其乘车总费用及总时间。但对于存在换乘点的方案，需要确定途径的线路和换乘点，使得通过这些线路和换乘点可以到达终到站，并需要判断各个方案的优劣。对于目前的城市交通系统，线路和站点的数目都较大，故可能的换乘方案的数目也会较多，特别是对2次换乘的情形。这对各个方案的筛选即最佳线路集的确定将带来一定难度，并对查询算法的效率提出了较高的要求。故问题的关键在于怎样高效的找出最佳方案中的换乘点。
现需要考虑的是有着3957个公汽站点的交通网的最优线路查询问题。为了便于量化交通网中任意两站点的连通关系，先由线路原始数据可建立所有站点的连通矩阵。
在查询给定两站点的最佳线路时，由于查询时间和遍历的站点数目成正相关，故不宜采用直接遍历全部站点的方法，应考虑对可能成为换乘点的站点进行筛选。由于假设的换乘次数不超过两次，故所有可能的换乘点都与起始站或终到站直通，则可考虑将经过起始站和终到站的所有线路上的站点作为可能的换乘点集合。再对该集合中的站点构
成的连通矩阵进行分析，可以得出所有可行的换乘方案。
可行的换乘方案数目也可能很多，特别是对城市中心地带。故在确定最佳方案时，应考虑采用较高效的对比算法。鉴于第一个换乘站点和第二个换乘站点的确定具有先后顺序，两者的层次分明，故可考虑用分支定界算法。
对于公汽地铁混合公交系统，地铁票价与站点数无关、地铁间的换乘和同一地铁站对应的任意两个公汽站之间的换乘均属免费、地铁线的引入增强了整个公交网络的连通性、地铁相对公汽更便捷且无阻塞，这些因素在会对两站点间的连通关系及换乘点的选择产生影响，需要综合考虑。
对于考虑了步行时间的最佳线路选择问题，由于存在在某站下车步行到另一站上车的情况，会对整个公交网络的连通性产生较大影响，具有一定的复杂性。而步行时间无具体数据，故只给出一般模型和求解思路。
三、 变量说明
)520,2,1( =i L i ：已知的520条公汽线路编号
(1,2,3957)i s i =：交通网络中各个公汽站点
)3957,2,1( =i S i ：经过站点i s 的线路集
)3957,2,1( =i N i ：经过站点i s 的线路数量(包括上下行，算两次)
)520,2,1( =i LS i ：线路属性向量，记录该向量为来回、上下行、环行。
(,)(0,1,2)k C i j k =：分别为从站点si 到站点sj 的直通、一次换乘、二次换乘票价 (,)(0,1,2)k t i j k =：分别为从站点si 到站点sj 的直通、一次换乘、二次换乘时间 0s ：起始站点，d s ：终止站点
四、 基本假设
1.
换乘次数不超过两次。 2.
不考虑交通事故等意外情况。 3.
不考虑车辆内部的拥挤情况及交通阻塞。 4.
换乘时间及相邻两站的行驶时间都取为平均值。 5.
若两站点连通且直通线路上的中间站点数不超过3个，则不考虑换乘。
五、 模型建立
先对数据进行处理，缩小搜索范围；然后设计快速算法找出任意两个站点经过直通、换乘一次及换乘两次连通的所有可行线路；最后根据查询者在换乘次数、时间和费用上的不同需求从可行线路中筛选出相应的最佳线路。
5.1公汽最佳线路选择模型
5.1.1建模前的准备
名词解释：
1. 直通：站点i 到站点j 不需要换乘，则称站点i 直通到站点j 。
2. 连通矩阵A ：由n 个站点构成的n n ?的0、1方阵。当i j ≠时，ij a =1表示站点
i 联通到站点j ；反之，ij a =0。当i j =时，规定ij a =0。
3. 单一站点：站点i 只在一条线路上，只考虑来回线及环形线上的站点。 数据处理：
1. 对已有的公汽站点数据进行统计，得到3957个公汽站点。
2. 得到原始连通矩阵0A 。该矩阵为3957阶0、1方阵，反映任何两个站点的直通
关系。
3. 得到单一站点集G 。
4. 得到站点-线路集S 。123957{,...}S S S S =，i S 表示由经过站点i 的所有线路构成的
集合。
5. 线路－站点集L 。12520{,...}L L L L =，i L 表示由线路i 上的所有站点构成的集合。
5.1.2模型的建立
（1）建立连通矩阵A
定义1：前续站点：若站点i 能直通到终点站，则称站点i 为终点站j 的前续站点。由终点站j 的所有前续站点构成的集合称为终点站j 的前续站点集Q 。
定义2：后续站点：若起点站i 能直通到站点j ，则称站点j 为起点站i 的后续站点。由起点站i 的所有后续站点构成的集合称为起点站i 的后续站点集H 。
结合北京公交的实际情况，换乘次数最多为2次，即认为两个站点之间需要经过至少经过三次转车才可达的情况是不存在的。换乘情况如图1所示：
图1
两站点间的各种换乘情况 由单一站点和前、后续站点的定义知：一次换乘点和二次换乘点只可能在Q H 中，
不可能在G 中，由此得到相关站点集合F =()/Q H G ，该集合包含了所有的换乘点。 若在F 外存在一换乘点，则必然至少存在另外两个换乘点，分别与起始站点和终止站点连通，即至少由三次换乘。故若只存在一次换乘或二次换乘，其换乘站点必在F 中。
将集F 中所有元素（假定个数为n ）在原始连通矩阵0A 中对应n 行n 列的2n 个交点提取出来并保持相对位置不变，即得到连通矩阵A 。
一对起止站点0d s s ，就有一个连通矩阵0d A 与之对应。该矩阵反映了与起、止站点直通的所有站点间的连通信息。下面将得到0d A 的算法总结如下:
a) 得到终止站点d s 的前续站点集Q 及起始站点0s 的后续站点集H
b) 得到相关站点集()/F Q H G =
c) 由原始连通矩阵0A 及相关站点集F ，得到连通矩阵0d A
（2）两站点的直通判断及最佳线路选择
对给定的起点站i 和终点站j ，若0ij a =，表示站点i 到站点j 不存在直通线路。若1ij a =，表示站点i 到站点j 存在直通线路。
当站点i 到站点j 存在多条直通线路时，就要从中筛选出最佳线路。由于相邻公汽站的平均行驶时间相同且不经过换乘，站点数最少的线路就是最短时间线路，也是最少费用线路。
从所有直通线路中筛选出站点数最少的线路，就是同时满足时间最短和费用最少的最佳直通线路方案。
（3）两站点的一次换乘及较优线路选择
a) 确定可能换乘点数目
命题：令一次换乘矩阵2B A =，若k b ij =(0,1,2...)k =，则表示从站点i s 到站点j s 存
在k 个一次换乘点。
简要证明如下：
若站点i s 直通到站点j s ，则记为i j s s →
由矩阵乘法，一次换乘矩阵B 的第i 行第j 列的元素ij b 为连通矩阵A 的第i 行元素和第j 列对应元素乘积的和。即可表示为：
()??????
? ??=nj j j in ij i i ij a a a a a a a b 2121,,，0 1 ij i j a i j ?=??站点不能连通到站点站点连通到站点 当i j =时，规定0ij b =；当i j ≠时，若ij b k =，表示n 个乘积项中有k 个为1，其余为0。
下面以111i j a a ?=为例，将其表示的实际意义说明如下：
若111i j a a ?=，则111i j a a ==，表示11,i j s s s s ??→??→，所以，1i j s s s ??→??→表示从站点i s 出发，在站点1s 处经过一次换乘，可以到达站点j s 。
一般地，当k i k j ≠≠且时， 1 ik kj a a ?=时，表示i k j s s s ??→??→。
当k i =时，由于0ii a =，无论ij a 为何值，0ii ij a a ?=，表示即使站点i 与站点j 直通，对ij b k =也没有贡献。即ij b 中不包含站点i 与站点j 的直通信息。 因此，当ij b k =时，表示从站点i s 到站点j s 存在k 个一次换乘点。
b) 确定k 个一次换乘点
令=i b ()in ij i i a a a a ,,21，??????? ??=T
nj j j j a a a c 21， 定义运算符’?’的运算规则如下：
()nj in jj ij j i j i j i ij a a a a a a a a c b f ????=?= ,,,2211 若ij f 中第k 个元素非零，则表示i k j s s s ??→??→，
即可从起点站i s 出发，在站点k s 换乘到达终点站j s 。
c)
图2 两站点间的一次换乘方案示意图 通过a)、b)两步，得到了起点站i s 到终点站j s 经过一次换乘的所有可行换乘点集12{,...}k k k kn S s s s =。然后，采用直通算法分别得到i ki s s →及 (1,2...)ki j s s i n →=的最佳直通线路，由此得到n 条一次换乘线路。
下面从最少费用和最短时间方面得到最佳一次换乘线路。
费用表达式：
100(,)(,)(,)C i j C i k C k j =+
其中，1(,)C i j 表示从站点i s 经过一次换乘到达站点j s 的费用。0(,)C i k 表示从起点站i s 直通到换乘点k s 的费用，0(,)C k j 表示从换乘点k s 直通到终点站j s 的费用。
时间表达式：
100(,)(,)(,)5t i j t i k t k j =++
其中，1(,)t i j 表示从站点i s 经过一次换乘到达站点j s 的时间。0(,)t i k 表示从起点站i s 直通到换乘点i s 的时间，0(,)t k j 表示从换乘点i s 直通到终点站j s 的时间，5分钟表示公汽
之间的换乘时间。
将上述两个计算式代入到n 条一次换乘线路中，便得到了不同费用下的最短时间一次换乘线路。
（4）两站点的二次换乘及较优线路选择
按相似的方法，可以确定从站点i s 经过两次换乘到达站点j s 的两个换乘点。现简要说明如下：
作二次换乘矩阵D A B =?，其中A 为连通矩阵，2B A =为一次换乘矩阵。同样地，规定0 (1,2...)ii d i n ==，根据矩阵乘法：
()1212,, ()j j ij i i ij in nj b b d a a a a i j b ?? ? ?=≠ ? ? ??? 其中，行向量()12,,i i ij in a a a a 反映了起点站i s 与所有相关站点的连通信息，向量12(,....)j j nj b b b '包含了第二次换乘的所有换乘点信息。将这两个向量作?运算，即可得到所有可行的第一次换乘点。
由此，得到了从站点i s 经过两次换乘到达站点j s 的第一次换乘点集合m S 及第二次换乘点集合n S ，如图2所示：
图3
两站点间的二次换乘方案示意图
同样的，可以写出：
总费用表达式：2000(,)(,)(,)(,)C i j C i m C m n C n j =++
总时间表达式：2000(,)(,)(,)(,)10t i j t i m t m n t n j =+++ 其中，m s 为第一次换乘的站点，n s 为第二次换乘的站点。
采用分支定界对二次换乘线路进行搜索，便得到了不同费用下的最短时间二次换乘线路。
（5）两站点的最佳线路选择
通过（2）、（3）、（4），三种换乘次数下的较优线路，现通过制定淘汰规则，去掉劣
解，得到满足不同需求的最佳线路。
方案淘汰规则：
a) 前者费用不小于后者
b) 前者时间不小于后者
c) 前者换乘次数不小于后者
d) 两者的费用、时间、换乘次数不是都相等的
若以上4条规则同时满足，则将前者淘汰。
5.1.3模型的最终确立
对任意的起点站i s 和终点站j s ，得到了不同换乘次数、不同费用下最佳线路选择模
型如下：
001100001010min (,)(,) +(,)(,)(,)(1)5
111=1 (,)=
0,1,2 =1,2,3(1)
k k k k k k k il l l l l l j l t i j t i l t l l t l l t l j k a a a a st C i j u k u k k k --=+++++?===?????=+++，，…，， 其中，01il a =表示站点i s 直通到站点0l s
总乘车费用：00001010(,)=C (,) +C (,)(,)(,)l k k k C i j i l l l C l l C l j -+++
u 表示在换乘次数l 下的各种票价。
最后再根据淘汰规则，得到满足不同需求的最佳线路方案。
5.2公汽地铁混合最佳线路选择模型
由于同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，因此地铁站的引入增强了公汽站点间的连通性。因此，要对原始连通矩阵和相关站点集进行扩充和调整后，再由矩阵分析，确定出所有可行换乘点。
另外，在出行费用方面，要注意到地铁票价和站点数无关及任意两个公汽站之间通过地铁站换乘时免费的情况。
若两公汽站点可对应于同一地铁站，则称这三个站点关联，称某站点为其他站点的关联站点。
于是扩充后起始站点的后续站点集()H 应是起始站点及其全部关联站点的原后续站点集的并集，即i H H =。扩充后的前续站点集应是i Q Q =。再根据()/F H Q G =得出筛选出连通矩阵A 。
再采用公汽系统线路选择相似的算法，可以得到满足不同需求下的公交最佳线路。其中不同之处在于00001010(,)(,) +(,)(,)(,)k k k k t i j t i l t l l t l l t l j t -=++++，t 的取值应根据具体的换乘点来判断，表示换乘时间。并且由于地铁比公汽通畅，在比较有地铁方案跟无地铁方案时，允许前者的票价比后者多，且时间上多于一定值，取为8分钟。
5.3考虑步行情况下的公交线路选择模型
因为不知道两站点的具体地理位置，我们将线路上相连的两个站点视为地理位置上相连，并称这两站点为邻近站点；而线路上不相连的两站点，其在地理位置上也不相连。 考虑到城市交通网络本身的连通性较强，我们只考虑乘客在邻近站点上车、换乘、下车的情况。
若原有的两站点不连通，但考虑步行之后可一次乘车到达，则称这两站点连通。于是考虑步行之后，会修改原始连通矩阵0A 。
考虑步行后起始站点的后续站点集应是该站点及其邻近站点原后续站点集的并集；终止站点的前续站点集应是该站点及其邻近站点原前续站点集的并集。
再得出相关站点集和相关站点的连通矩阵。模型如下所示：
01100001010min (,)(,) +(,)(,)(,)111=1 (,)=
0,1,2 =1,2,3(1)
k k k k k k k il l l l l l j l t i j t i l t l l t l l t l j t
a a a a st C i j u k u k k k --=++++===?????=+++，，…，， 其中，01il a =表示站点i s 直通到站点0l s ，(t 指换乘时间，需根据具体的换乘点确定)
总乘车费用：00001010(,)=C (,) +C (,)(,)(,)l l l l C i j i k k k C k k C k j -+++
在不同的换乘次数l 下，得出一定票价u 下的最少时间方案，最后利用淘汰规则对所有这些方案进行筛选，得出满足不同需求的最佳线路方案。
六、 模型求解的算法设计
在具体的模型求解时，需要一定的数据，这就需要在系统中预存一定的数据。需要预存的数据如下所示：
6.1系统主要预存数据
L ：每条线路依次经过的各个公汽站点
LS ：每条公汽线路的属性(双行线、来回线、环形线)
LN ：每条公汽线路上的站点数
C ：每条公汽站点线路的计费方式(单一费制1元、分段)
N ：经过每个公汽站点的线路(公汽、地铁)数目
A 0：所有公汽站点的连通矩阵
DS ：对每个地铁站点，可换乘的公汽站点
LT ：每条地铁线路途径的地铁站点
总预存数据大小：662K 。由此可见，总预存数据较少，从系统设计的实际出发，这对系统的开发有很大的好处。
6.2总体算法设计
6.2.1算法功能描述：
给定站点12(,)s s ，在已知原始的线路和站点数据的条件下，求出满足查询者对换乘次数、乘车时间和乘车费用的各种不同需求的最佳线路方案。
6.2.2算法步骤：
1. 输入：需要查询的站点12(,)s s ，其中1s 为起点站，2s 为终到站。
2. 零次换乘方案的确定：由所有站点的原始连通矩阵A 0，判断12s s 和是否直通，
若可以，则由直通算法进行求解，得出零次换乘方案的结果。
3. 若12s s 和不直通或12s s 和的直通时间不超过12分钟，转4。
4. 对数据进行预处理：由筛选算法得到可能成为12s s 和的一次、二次换乘点的候选
站点集H ，再生成H 中所有站点的连通矩阵A 。
5. 一次换乘方案的确定：
1) 对连通矩阵A 进行矩阵分析，确定出所有的可以作为一次换乘点的站点k s 。
2) 对每个k s ，由直通算法确定出1(,)k s s 和2(,)k s s 两对站点之间的最佳线路，得
到所有可行的一次换乘方案。
3) 由淘汰规则确定出最佳的一次换乘方案集。
6. 二次换乘方案的确定：
1) 再对连通矩阵A 进行矩阵分析，确定出所有的可以作为二次换乘点的站点
对(,)i j sa sb 。
2) 结合直通算法，由分支定界算法对所有的(,)i j sa sb 站点对进行比较、筛选，
得到最佳二次换乘方案的候选集H2。
3) 对候选集H2由淘汰规则进行筛选，确定出最佳的二次换乘方案集。
7. 对三种换乘次数对应的最佳方案集，再由淘汰规则进行筛选，得出最终的最佳
方案集。
6.3直通算法设计
6.3.1算法功能描述：
在已知给定站点对12(,)s s 存在直通线路的情况下，求出12(,)s s 之间最佳线路集和对应的乘车时间和乘车费用。
6.3.2算法说明：
直通线路中，乘车时间与途径的站点数成正比，而费用也与站点数成正相关关系，故采用途径站点数最少的线路作为最佳线路。
算法步骤：
1. 由经过每一站点的线路集S （系统预存）确定出同时经过12s s 和的线路集合L 。
2. 对L 中的每一条线路，确定12s s 、在其上的位置，再根据该线路的属性（双行、
来回、环行），得出由此线路从12s s 到经过的站点数。
3. 在L 中选出途径站点数最少的线路，作为最佳线路，并算出对应的时间和费用。
若最佳线路不唯一（即对应的时间和费用均相同），则将线路全部输出。
6.4筛选算法设计
6.4.1算法功能描述：
给定两站定12(,)s s ，筛选出可能作为12s s 和中的一次、二次换乘点的候选站点集H 。
6.4.2算法步骤：
1. 初始化候选集H 为空。
2. 对起始站点1s （终到站点2s ）：
1) 由经过每一站点的线路集S （系统预存）确定出经过1s （2s ）的线路集合L 。
2) 对L 中的每一条线路，若该线路为来回线或环行线，则将该线路上的所有
站点加入到候选集H 中；若该线路为双行线，则将该线路中在1s 后面（2s 前
面）的所有站点加入到候选集H 中。
3) 对候选集H 遍历，删掉重复的站点。
4) 对候选集H 再进行二次筛选：若对H 中的每一站点，经过该站点的线路只
有一条且该线路不为双行线，责任将该点淘汰掉。
6.5分支定界算法设计
6.5.1算法功能描述：
已得出所有的可以作为二次换乘点的站点对(,)i j sa sb ，对每一站点对(,)i j sa sb 对应的二次换乘方案通过分支定界进行筛选，得出包含方案个数较少的最佳二次换乘方案候选集。
二次换乘的分支定界的示意图如图4所示：
图4 二次换乘的分支定界示意图
2
6.5.2算法步骤：
1. 初始化候选方案集LH 为空。
2. 对第一对站点11(,)sa sb ，由直通算法确定11(,)s sa 、11(,)sa sb 、12(,)sb s 三对站点
的最佳线路，并得到在此二次换乘方案下的总乘车时间和总乘车费用。再将此方案加入到LH 中。
3. 初始化分支定界的界限：将上一步得到的总乘车时间设为time ，得到的总乘车
费用设为cost 。
4. 对以后的每一站点对(,)i j sa sb ：
1) 由直通算法确定站点对1(,)i s sa 之间的最佳线路，并得到这两个站点的直达
时间t1和直达费用c1。
若该方案的最小总乘车时间t1+16不大于当前的最优总时间time ，或者该方
案的最小总乘车费用c1+2不大于当前的最优总费用cost ，转2)，否则，转
4。
2) 由直通算法确定站点对(,)i j sa sb 之间的最佳线路，并得到这两个站点的直达
时间t2和直达费用c2。
若该方案的最小总乘车时间t1+t2+13不大于当前的最优总时间time ，或该
方案的最小总乘车费用c1+c2+1不大于当前的最优总费用cost ，转3)，否则，转4。
3) 由直通算法确定站点对2(,)j sb s 之间的最佳线路，并得到这两个站点的直达
时间t3和直达费用c3。
若该方案的最小总乘车时间t1+t2+t3+10不大于当前的最优总时间time ，或
者该方案的最小总乘车费用c1+c2+c3不大于当前的最优总费用cost ，将该
方案加入到候选方案集LH 中。
对于公汽系统，综合以上各个模型求解的算法，可得MATLAB 程序，见【附件5】。 对于公汽地铁的混合公交系统，算法大体一致，只需对原始站点的连通矩阵进行修改，具体程序见【附件8】。
在MATLAB 7.4上实现，对所给6对站点进行最佳线路的查询，得到以下结果：