以最小换乘次数和站数为目标的公交线路选择

摘要 一、问题重述

我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：

1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。

(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485

(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路，解决以上问题。

3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

二、问题分析

这是一个公交线路选择的自主查询系统设计问题。为了设计这样一个系统，其核心是线路选择的模型与算法设计。路线是指：

L2 L1 Ln-1

S 2Sn S S 13 其中S1起点，Sn是终点，Si是转站点，Li乘车线路。即是告诉查询者从起点到终点坐哪列车到哪个站点换乘最终到达终点。

对于问题一，仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。一般情况下，选择公交线路时,可行的乘车方案一般有多个。而出行者考虑的因素很多,如换乘次数、旅途时间、费用等,不能简单的抽象为最

[2]

短路问题。所以可以建立多目标分层最优模型。算法设计方面，考虑将线路进行抽象处理，将分上下行的线路、双向行驶的线路和环行线路抽象为一条，即将上下行的线路和双向行驶的线路连接成一条。而算法设计中确定输出乘车路线和换乘点到查询界面是难点和重点，针对本题数据庞大的特点，如何克服庞大数据给计算机运行带来的重大负荷是有效解决问题的关键。考虑到时间复杂度和空间复杂度的影响，本文的最少换乘算法考虑采用图论中广度优先搜索思想。本算法

[5]

得出的解一定是最少换乘次数的路径，但可能解并不唯一。得到最少换乘路径——路线序列(r1,r2,rn1,rn)，再分情况讨论相邻两线路的关系，以最少站为目

标求出换乘点。综上即可求出乘车路线和换乘点。在此基础上，将出题目给出的六对起始点到终点的最优路线，并作出详细评价。

对于问题二，同时考虑公汽与地铁的线路线路选择问题。考虑到题目给出相同地铁对应的公交站点通过地铁站换乘无需支付地铁费，且这些公交站点在地理位置上非常接近，所以可以抽象为一个新的公交站点，由问题一的模型和算法求解。

对于问题三，考虑现实生活中公交及地铁站点的实际分布情况，有时会出现步行小段距离再转车的情况更能节省时间或转车次数。因此，研究此种情况下的出行方案对节省出行时间具有重要的实际意义。

三、问题假设与符号说明

（一）问题假设

1．假设各路车发车频率相同。

2．不考虑路途中遇到红灯时间的拖延。

3．假设任一行驶路段行驶时间交通顺畅，不出现交通堵塞的情形。

4．假设任一乘客的换乘耗时相同，即不考虑换乘车辆到达却因乘客过满等原因无法上车的情形。

5．同一地铁站对应的公交站点地理位置非常接近，假设任意两站点间步行时间近似为0。

（二）符号说明 重要符号 S6 四、模型的建立与求解

4.1 问题一：公汽线路选择模型的建立及求解

4.1.1 数据处理——线路抽象处理

由已给数据可知，公交线路一共可分为三种：上、下行线重合线路，环形线路，上下行线不重合线路。

① 考虑到一般情况下，上、下行线终点需乘客全部下车换乘（可以再次乘坐本辆车次，但必须重新收费），为方便统一对数据进行处理，我们将上、下行线重合线路拆分为两条线路，即：

SS3 S4 S5 S6 S

S2 S3 S4 S5 S1 S6 SS4 S3 S2 S1 S 图1 ② 将环形线路抽象成一条线路

符号含义 重要符号 符号含义 S1 S1 图2

③ 上、下行线线路不重合不变

4.1.2 模型分析

一般情况下，选择公交线路时,可行的乘车方案一般有多个。而出行者考虑的因素很多,如换乘次数、旅途时间、费用等,不能简单的抽象为最短路问题[2]。研究表明一般出行者以换乘次数为优先考虑的目标[3] ,公交网络的设计也以减少

[4]

平均换乘次数为重要目标 。考虑到实际情况，奥运会期间正直炎热夏天，并有大量观众乘坐公共交通工具，换乘麻烦不为大多数人能接受。因此本文考虑以最小换乘次数为第一目标。另外,题目信息已给出的旅途时间,和乘车计费方式。不失一般性，乘车所需时间、费用都与途经的站数正相关,并且考虑到公交站点及公交路线数据过去庞大，计算机在有限时间内实现耗时较长，为避免过于复杂,本文选择最小途经站数为第二目标。即:在所有可行路径中选择换乘次数最小,且在满足此目标条件下使途经站数最少的路径为最优路径（不唯一）。在确定最优路径前提下计算乘车时间与乘车费用，让出行者全面了解线路信息以做出选择。

4.1.2 模型的建立

设起点v0，终点vd的可行路径集合为TRTRiTRiv0,pi1,v1,pi2,,vdTRi表示起点为v0S1

，

，乘坐线路pi1到达站点v1换乘pi2到达v2，最终到达终点vd。

设该线路中换乘次数为Ni，途径总站点数Si，总费用为Mi，总耗时Ti。则： 1) 目标函数

我们的目标是希望换乘次数、途径总站数、总费用、总耗时越少越好，即

目标一：minNi

TRi目标二：minSi

TRi目标三：minMi

TRi目标四：minTi

TRi目标三、四在目标一、二实现前提下实现，即找到起点到终点的最少换乘次数N及途径最少站数S路线的前提下求乘车费用M及乘车时间T。则

N1Mm

kk1TStst0

以换乘为结点，其中mk为每段路的乘车费用；ts3min为相邻公汽站平均行驶时间(包括停站时间)，t05min为公汽换乘公汽平均耗时。 2) 约束条件

Ni0,1,2,3Si0,1,2,3Mi0T0i

3) 综上，公汽线路选择模型为

minTRiNi Si

minTRist.N1Mmkk1TStst0Nt3minst05minN0,1,2,3iSi0,1,2,3M0iTi0

4.1.3 算法设计

由模型可知，需设计算法找出最优换乘路径。 （一）公交网络描述

对公交网络的数学描述是算法设计的基础，本文用四元组(V,P,R,L)来表示。其中：

① Vvii1,2,,n，为节点的集合，包括交通网络中所有的公交站点或可能的出行起始点和终点[1]，节点有唯一编号（题目已给出）。

② Ppii1,2,,K，为公交线路集合，各线路有唯一编号（题目已给出）。

③ Rrkk1,2,,K，为线路-节点关系集合，假设线路是无方向的。由所该线路包含的站点按通过顺序构成的节点有序序列表示。如第k条线路：

rkvk1,vk2,,vkmk，其中vk1,vkm是该线路的始发、终点站。

④ L(ljj1,2,,K)，为节点-线路关系集合。如ljpj1,pj2,,pjm，为所有经过的节点vj线路编号的集合。特别的，若lj，表示无线路经过该节点。

（二）算法准备

1o 为判断两条线路的相交情况，定义线路相交矩阵C[5]:

CcijKK

其中

1,cij0,若线路ri,rj有公共站点若线路ri,rj没有公共站点

2o 确定换乘上界矩阵H

可由Floyd算法求得任意两站点间最少站点数，组成矩阵H'。H'矩阵代表当任意给定的始点、终点vi,vj经过最少站点到达时，最多可换乘H'ij次。而实际路线经过的站点数大于等于H'ij，即可换乘次数可能会大于或等于H'ij。考虑到实际情况中，一般情况下，出行者所能接受的换乘次数将十分有限。所以，我们考虑将任意两站点间换乘次数构成的换乘上界矩阵等于两站点到达时的最少站点数矩阵，即

HH'

o

3公交线路集合的扩展 a. 建立起公交线路集合Ak和AD， b. 根据相交矩阵C

（三）最优乘车路径的搜索算法

设在公交查询网络上，出行者任给定始点、终点v0,vd可达，需要确定最优乘车方案输出到终端。首先需要确定换乘次数上界TN，然后根据(V,P,R,L)按换乘次数递增进行搜索，算法必在不大于TN次换乘的某此循环中找到可行路径。若可行路径有多条，则寻找总站数最小的为最优路径并输出。

算法步骤：

Step 1 输入始点、终点v0,vd，确定换乘次数上界TNHod Step 2 判断直达线路是否存在

l0pjv0pj,j1,2,，Kldpjvdpj,j1,2,，K, 

若l0ld，则由直达路线。计算各路线站数，最小者即最优路径，转step

5。否则，需要换乘，继续。 Step 3 令A0l0,i0

Step 4 若不存在i次换乘的可行路径，则搜索i1次换乘的可行路径。 1o 扩充Ai到Ai1

即寻找所有的路别单元pk(k1,2,,K)

st.pkpi

 Ai1Aipkpkpi,piAi,k1,2,,K

即将所有满足与Ai中路线pi相交的路别并到Ai中构成新的集合Ai1。

2o if Ai1ld，则有可行路径。对每条可行路径回溯确定线路序号，计算每一条可行路径的总站数，总站数最小的为最优路径。转step 5。

否则，i:i1，重复执行step 4。

Step 5 根据最优路径上的路线序列确定换乘方案，输出到终端，结束。

算法补充：

上述算法中的换乘方案确定的算法设计。 由上述算法可确定线路序列（不唯一），选择不同的换乘方案可能导致总站数不同，因此需确定换乘点以保证总站数最少。不是一般性，设上述算法中回溯确定的从起点到终点的线路序列为p1,p2,,pm，其中相邻的两线路pi,pi1的相交关系可能存在以下四种，而相交关系的不同将影响换乘点的度额定，进而影响总站数。

a. 单交叉点 b. 重合区段

c. 多个分离交叉点

d. 多个分离交叉点和重合区段 由图3所示，实粗线表示线路ri，虚线表示线路ri1。

(a) (b) 图6

(c) (d) 对四种情形换乘点的确定如下： 情形(a)：换乘点唯一，即交叉点[1]。

情形(b)：重合区段中的任一节点都是换乘点，且对站数无影响[1]。

情形(d)归类到情形(c)：在换站次数为1的前提下，利用穷取法对换乘点进行搜索。

五、模型评价及改进 六、参考文献

[1] 赵巧霞，马志强，张发. 以最小换乘次数和站数为目标的公交出行算法. 计算机应用，24（12）：136-137，146. 2004.

[2] 严寒冰, 刘迎春. 基于GIS 的城市道路网最短路径算法探讨[J]. 计算机学报, 25(3) ,2000 .

[3] 杨新苗, 王炜, 马文腾. 基于GIS 的公交乘客出行路径选择模型[J] . 东南大学学报(自然科学版),30(6):87-91,2000.

[4] 韩传峰, 胡志伟. 城市公交路网性能评估的网络图方法[J]. 系统工程, 21(3):58-61,2003.

[5] 傅东绵. 交通系统中最少换乘算法及其实现. 华侨大学学报（自然科学版）.22(4): 348-350,2001. []

七、及其附录