乘公交看奥运
摘要
本文将运用图论知识，以站点抽象为顶点，站点与站点间的线路抽象为图的边，最后采用图论的最短路用0-1整数规划描述，建立直达矩阵Q作为数据基库，根据用户的不同需求为目标建0-1整数规划模型用邻接算法查找最优线路。
问题 (只考虑公汽）：在用户查询时首先考虑直达方案，在无直达方案时，针对不同用户需求，考虑目标：总耗时、转乘次数、总费用，在以不同目标的有向
x边为决策变量，以用户需求赋权图建立权矩阵。以顶点i到j的路径是否包含
ij
为目标，始、终点连通为约束建立0-1规划模型。
一、问题重述：
我国人民翘首企盼的第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、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
二、问题分析
本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。所以我们根据公众实际的需求，考虑公众乘车的主要因素有乘车时间、转乘次数、乘车费用对本题进行讨论。
在问题一仅考虑公汽线路的情形下，根据题目所给公汽线路数据，对每条线
路进行抽象处理，上下行线、双向行线、环行线各抽象为两条，主要以转乘次数最少的基础上，再以乘车时间、乘车费用最少为建立模型，给出以各因素最优的多条线路供乘客参考。
此问题可以看作多目标优化问题（至少考虑三方面：换乘次数最少， 在考虑问题二时，根据题目所给信息，同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，既可把每个地铁站点与相邻的公汽站点抽象为一个站点，对地铁线路的抽象处理同样把每条线路处理为两条，并与问题一同样的方法建立模型。
在我们的实际生活中，可能会出现先步行一段距离后再乘车，这样会对节省乘车时间，并能减少转乘次数和乘车费用，所以考虑这一因素是必要的。主要先考虑步行时间与候车时间。
三、问题假设
3.1、假设车站不同名；
3.2、假设各车在相邻站点间的行车时间相等； 3.3、假设交通顺畅，不发生交通事故； 3.4、假设公交车准时出发并准时到达站点； 3.5、假设不考虑过红绿灯时间； 3.6、假设不考虑其它交通工具；
3.7、假设只考虑转乘次数小于等于2；
四、符号约定
4.1、问题I ：
A —表示直达矩阵；
ij l —表示从站点i 到站点j 所付出的时间代价；
G —表示汽车公交网络抽象的有向赋权图；
v —表示图的顶点，即公汽站点； ij e —表示弧),(j i v v 是否在图G 上； ij t —表示从i v 到j v 的乘车总时间；
ij p —表示从i v 到j v 的乘车总费用；
n —表示公汽站点个数，既为图的顶点个数；
C —表示转乘次数； 4.2、问题II ：
ij y —— 弧(i , j )是否在该路径上；
ijk Y —— 站点i → j → k 间是否地铁换乘地铁；
'ij t —— 站点i → j 的乘车时间； 'ij p —— 站点i → j 的乘车总费用；
c —— 人为设定参数，表示乘客可接受的最多换乘次数； T 1,T 2 —— 总等待时间，总步行时间；
ij z =3 表示i →j 最短直达为公汽（也表示乘始发坐公汽等待3 分钟）， 等于2 为地铁（也表示始发乘坐地铁等待2 分钟）。
五、模型建立与求解
5.1、问题I ：
本小问只考虑公汽站点的线路选择建立数学模型与算法设计，分别以乘客不同的需求下给出最佳线路。建立模型所考虑的目标因素有：
?第一目标：转乘次数最少
?第二目标：乘车需总时间最少 ?第三目标：乘车需总费用最少
（1）用以上三个目标建立模型需解决如下问题：
5.1.1、对三种汽车路线进行图论的抽象处理； 5.1.2、建立公汽的直达矩阵A ；
5.1.3、以图论的最短路理论的整数规划建立模型； 5.1.1、对三种汽车路线进行图论的抽象处理；
根据题中所给数据，公汽线路共分为三种，分别进行处理。 1）上、下行线原路返回
这种路线的行驶车所经站点完全相同，并以两个相同的站点作为起点或终点，所以抽象为有向图时由于方向不同而抽象为两条线路；
???????876521s s s s s s
2）上、下行线经过有不同的站点
很显然这样的线路应抽象为两条线路；
876s s s ???
12s 1011s
3）环行线路
和1）是同样的抽象处理，只是环行线只有一个站点，既为起点也为终点，→a →A
或''''A B a A →→→
5.1.2
1）直达线路数矩阵的建立
引入直达线路数矩阵A=()ij N N a ?，其矩阵元素ij a 表示第i 个站点到第j 个站点直达线路数n ，其中，i=j 时是无效线路，设定值为0，即：
0 (i= j) (i j)ij a n ?=?≠?
以N 表示所有公汽所经过的站点总数，则直达线路数矩阵可表示为：
111212122212
a a a a a a a a a a n n ij nn n n A ?? ? ?= ? ? ?? 2）换乘线路数矩阵的建立
直达矩阵A 为N × N 阶方阵，矩阵A 的2次幂中元素表示任两站点间通过1次转乘的路线数，即：2A A A =?
其中，2ij A 表示第i 个站点到第j 个站点通过1次转乘的线路数， 5.1.3、以图论的最短路理论的整数规划建立模型
引用图论知识将公交网络抽象为一有向赋权图),,(W E V G =，G 中的每个顶点为一不同的站点，如在G 中的两个顶点i v 到j v 有直达路线，则图中这两顶点间就有一有向过相连，方向为i v 到j v ，且E v v j i ∈),(。其中 s 为起点， e 为讫点，),(j i v v w 为相应的权值，可以是i v 到j v 所用时间或费用等。
时间：n n ij t t w ?=)(，其中????
?=无直达的直达时间到0
),(j i v v ij v v t t j
i
费用：n n ij p p w ?=)(，其中????
?=无直达
的直达费用到0
)
,(j i v v ij v v p p j
i
5.2、目标与约束分析：
5.2.1、第一目标：转乘次数最少
在6.1.3中建立的有向赋权图，引入0-1决策变量ij x ，则：
??
?=否则
的线路上
到在以弧0),(1j i j i ij v v v v x 若i v 与j v 没有直接相连的弧，则需在每个站点都转乘，那么i v 到j v 所经过的站点数为：
1),(-∑∈E
v v ij
j i x
即i v 到j v 转乘次数最小表示为：
1min
),(-∑∈E
v v ij
j i x
根据实际，在生活中人们所能接受的转乘次数，本模型取2≤c ； 所以转乘次数的约束为：
???
?
???∈≤≤≤-∑∈z c c c x E v v ij j
i
2
01),( 在系统查询时，c 的值由本人自己选择，有以下几种情形：
1、c=0时，表示直达；
2、c=1时，表示转乘一次；
3、c=2时，表示转乘二次； 5.2.2、第二目标：行程总时间最短
根据时间权值n n ij t t w ?=)(，乘车时间为：
(,)i j ij ij v v E
t x ∈∑
由题目知，转车时间为固定5分钟，在起始站点等待3分钟，所以， 行程总时间=乘车时间+换乘时间+起始站等待时间
3)1(5min ),(),(+-+∑∑∈∈E
v v ij E
v v ij ij j i j i x x t
5.2.3、目标三：行程总费用最少
直达费用权()p ij n n W P ?=， min ,()i j ij ij v v E
P x ∈∑
5.2.4、最短路起讫点约束
由于G 为有向图，则其中顶点分为“起点”、“中间点”、“讫点”三类，对于起点只有出的边而无入的边，对于中间点既有入的也有出的边，对于讫点只有入的无出的边。对有向图而言，若求顶点s → e 的最短路径，以ij x 表示进入第j 个顶点的边，以ji x 表示出第j 个顶点的边，则s → e 中的三类点约束可表示为：
11(,)(,) 1 (i=s)1 (i=e)0 (i s,e)n
n
ij ji j j i j E i j E x x ==∈∈??
-=-??≠?
∑∑ 根据多目标的优化问题建立模型如下：
1min ),(-∑∈E
v v ij j i x
3)1(
5min ),(),(+-+∑∑∈∈E
v v ij
E
v v ij
ij
j i j i x x
t
,()min i j ij ij v v E
P x ∈∑
}{(,)11(,)(,)1 1 (i=s)1 (i=e)0 (i s,e).0,1,i j ij v v E n n
ij ji j j i j E i j E ij x c x x s t x i j E
∈==∈∈?-≤??
????-=-????≠????
∈????∈?∑∑∑
5.3、模型的求解（程序见附录）
5.3.1、模型求解的2种方法
方法一、修正Floyd-Warshall 算法
在线路选择问题中，当从i 可直达j 时,定义弧(i,j)；其上的权为
0 i=j j ij ij
d l ??
=∞??? i 站点到站点无直达车否则
ij l 表示由i 直达j 付出的时间代价(多条线路可达时只保留最短时间) 初始等车时间2(3)min 也不包括在内，最后结果可加上. 最短时间
定义矩阵算子“⊙”如下：设A 、B 均为n 阶方阵， C = A ⊙ B (考虑换乘代价)
{},,min }|1,2,,ij ik kj i j k c a b k n =++δ=
当考虑时间矩阵之间的运算时，
,,i j k
δ表示在第k 站的换乘时间。
D(k)= D(k-1) ⊙ D 表示k 次换乘的最短时间， 该算法大体相当于求最短路的Floyd-Warshall 算法，但考虑了换乘因素
方法二、基于数据库Q 与Dijkstra 算法的“邻接算法”求解 Step 1：输入乘车始点i 终点j ，（注： ()ij n n C c ? 为最少换乘次数矩阵，） 若 ij C =0 则有直达线路，输出Q 中所有直达信息，结束程序， 若 ij C =1 则有转乘1次线路，转Step 2， 若 ij C =2 则有转乘2次线路，转Step 4，
若 ij C >2 则存在转乘 c ij 次线路，但全局计算时间复杂度较高，终止邻接算法， 采用Lingo 求解；
Step 2：求线路s(i)的直达站点E(i,U),及线路t(j)的直达站点F(j,V)；
Step 3：若存在E(i,U)=F(j,V)，线路s(i)、t(i)可能不止一种，即为一次转车的线路,保存队列U1，转Step6；
Step 4：求经过E(i,U)的线路r(K)求线路r(K)的站点G(K,W)；
Step 5：若存在G(K,W)=F(j,V)，线路s(i)、t(j)、r(K)可能不止一种，即为两次转车的线路，保存队列U2，转Step6;
Step 6：修改队列U1、U2 中的成员，按其属性(路过的站点数，乘坐的车辆)根据不同目标计算总行程时间、费用等；
方案结果
5.4．1、根据程序计算得到如下结果： 程序见附录