B题：乘公交，看奥运
摘要
针对题目所给的北京市部分公交线路，建立了多种不同目标规划下的优化模型，以满足不同类型的人们对于公交线路的不同需求。如乘车耗时短、换乘次数少、乘车耗时短以及乘车花费少。
针对上述多种情况，主要考虑了三种优化模型，首先，从公交线路的图论性质着手，建立传统的最短路径问题的模型，以最短路径为约束条件，以最小换乘次数为目标函数，求得在满足路径最短的情况下，换乘次数最少的最佳乘车方案；接着，从乘客自身的心理出发，认为换乘次数是乘客选择乘车路线的第一考虑因素，以此为出发点，以最小换乘次数为约束条件，分别以乘车耗时最短和乘车花费最少为目标函数，建立优化模型，求得在满足换乘次数最小的情况下，耗时最短或花费最少的最佳乘车方案。
对于上述不同的模型，我们采用了不同的算法，对于第一种模型，我们采用了改进的Dijkstra算法求得最短路径，再通过将该路径上相邻两站点的线路进行合并删除，求得换乘次数最小的乘车方案。对于后两种模型，首先我们认为乘客所能接受的最大换乘次数为no，接着引入直达矩阵T以及最小换乘矩阵Q，利用结论：矩阵Tn中对应的元素aij表示通过（n-1）次换乘从节点i?j的路径数。求得两站点之间满足最小换乘次数的路径，从这些路径中求得耗时最短或花费最少的乘车方案。其中对于题目所给的六个站点，同时满足乘车耗时最短和乘车花费最少的最佳路径数分别为2，1，1，9，3，1，最短耗时分别为101，106，128，83，106，65 min
接着在此基础上，引入地铁系统，因为同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)，我们将地铁站附近的公交站点连同相应的地铁站近似同化为同一个站点，通过一定的修改站名的工作，将地铁系统并入到了公汽系统中，得到新的公交路径，在修改后的直达矩阵T的基础上求得不同目标下的最佳乘车方案。而在此种情况下，对于题目所给的六个站点，同时满足乘车耗时最短和乘车花费最少的最佳路径数分别为1，1，2，3，0，1，最短耗时分别为98，101，09，77，88，25 min
而在问题3中，将步行作为一种出行方式，由步行方式把一些相距较近的站点连接起来。我们采用建立某站点邻集的方法，将站点联通矩阵R进行扩充，使R中记录有与每一站点相邻的结点的信息。再利用第2问的模型和方法求解相应的直达矩阵和一次及二次转乘矩阵，对于一次及二次的转乘矩阵里路径中含有步行段（即未转乘相应次数）的信息，转存至较低转乘次数的矩阵中。
最后在模型推广中，我们进行了换乘次数对乘车耗时的敏感度分析，考虑增加一次换乘次数有时可有效减少乘车耗时。
关键词 Dijkstra算法 最小换乘次数 直达矩阵T
1
1问题重述
明年8月第29届奥运会在北京举行时，会有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的计算机自主查询系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。必须解决如下问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用建立好的模型与算法，求出以下6对起始站→终到站之间的最佳路线，同时对所建立的模型进行评价。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485
(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676
2、将交通线路进行扩大，加入二条地铁线路，进一步扩大了交通网络，在此基础上解决以上问题。
3、进一步考虑所有站点之间的步行时间，建立任意两站点之间线路选择问题的数学模型。
2基本假设
1假设两站点之间的换乘次数最多为2次，超过2次认为两站点之间在公交网络中不连通。
2假设在问题1中，公车换乘只发生在同一站点，即乘客在某一站点下车，同时在相同站点上另外一辆车，进行换乘，不考虑距离较近的站点之间乘客通过步行换乘问题。 3假设问题2中同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费).。
4假设问题2中，地铁站附近的公交站点连同相应的地铁站近似同化为同一个站点。 5假设在问题3中，相邻的两站点之间步行平均耗时为常数t_unit（由于相邻公汽站间行驶时间认为是平均的）。
6假设在问题3中，人们可以接受的最大合理步行时间tm。
3符号说明
T——直达矩阵 R——路径矩阵
n——任意两站点i，j的最小换乘次数
m——任意两站点i，j满足最小换乘次数的路径数 r——任意两站点i，j耗时最少的最佳路径数 s——任意两站点i，j花费最小的最佳路径数
4问题分析
在城市的公共交通网络中，公交换乘是乘客出行的一个重要的问题。随着城市公交规模的不断扩大，尤其是像北京这样的国际大都市，有相当多的站点之间不能直达，乘客必须换乘才可到达目的地。
2
一般来说，乘客总是选择从起始点到终止点的最短路径，但事实上，在大部分的城市公交网络模型中，最短距离并不是决定公交线路选择的主要因素，其它因素在乘客出行中也是十分重要的影响因素，在本题中，主要考虑以下几点因素：
⑴换乘次数：是指乘客在完成一次出行过程中所换公交车的次数；
⑵出行耗时：指乘客在一次出行过程中所需的时间，包括公汽行驶路线上站点之间的行驶时间和地铁行驶路线上站点之间的行驶时间，这是第一、二问主要考虑的时间因素问题，在第三问时，还要新引入公汽换乘公汽，地铁换成地铁，地铁换成公汽和公汽换成地铁的耗时，综合考虑多种时间因素建立模型；
⑶出行费用：指的是乘客在完成一次出行过程中所花费的车费。在本题中公车按收费类型分为单一票价与分段计价两种计价类型，与之相对应的是关于公交车收费的分段函数[1]。
不同的乘客对各项因素的要求是不一样的，有些人想方便（换乘次数少），有些人想省时间（出行耗时少），有些人想省钱（出行费用少）。在理论计算上，往往采用最短路径的算法求出经过站点最少的路径，而在实际中，人们的心理往往是寻求最小换乘次数的乘车方案。
在上述思想基础上，我们建立了下述模型与算法。
5模型建立
本题为一个典型的优化问题，为了满足不同人群对于公交路线的不同需求，以换乘次数、乘车耗时和乘车花费为目标构建优化模型，将多目标问题转化为三个满足人们不同需求的单目标规划优化模型。
模型一：改进Dijkstra 算法的最短路径优化模型
把各站点看作图中的各顶点，从起点x开始进行编号，每一轮标号修正各临时标号(T）,确定一个标号（P）,按路径长度递增找下一个顶点，直至终点y 标上标号，最后反向追踪，得一条x?y的最短路径。这种模型下，只要两节点间有连接就可以进行搜索，没有考虑换乘次数。而对于换成次数较大的路线是没有实际的应用意义的。因此考虑采用以换乘次数为条件
模型二：乘车耗时最短的单目标规划优化模型
公交线路上两站点i，j在满足换乘次数最小时，设乘车耗时为t，
已知相邻两站点之间的平均行驶时间为一定值t0，站点换乘时间为tr，路径经历的站点间隔数为p则
t?t0p?trn 式 1
1对于任意两点i，j，集合V 为从i?j到的各种路径下的换乘次数的集合，则从i?j最小换成次数n满足：
n?V 式 2
2在乘车问题中，人们有一个心理所能接受的最大换乘次数n0，换乘次数超过n0时，
两站点之间在公交网络中不连通，故：
n?no
故以乘车耗时最小为目标函数的单目标规划优化模型为：
min t?t0p?trn
3
式 3
?n?n0??s.t.?n?V ???n,p?N
式 4
同理可建立如下模型三：
模型三：乘车花费最小的单目标规划优化模型
乘车花费是关于站点间隔数p与换乘次数t的函数，记为
d?f(p,t) 考虑最小换乘次数引入约束条件式2和3，同样得，
n?V
式 5
n?no
故以乘车耗时最小为目标函数的单目标规划优化模型为： min d?f(p,t)
?n?n0??s.t.?n?V ???n,p?N式 6
在上述所提出的模型的基础上，通过进一步分析、简化模型，提出以下几种的算法：
5.1最短路径算法——改进的Dijkstra算法[2]
由上述问题分析知，首先考虑最短路径算法，即经典的Dijkstra算法，由于题目中并未给出相邻两站之间的距离，所以以两站之间公汽行驶的时间为权重，计算满足最短路径的情况下的最小换乘次数。
1 根据输入的起点和终点在存储矩阵中找到匹配的记录；
2 利用Dijkstra算法计算出两点的最短路径，得到最短路径经过的站点； 3 计算换乘方案
按顺序取出两个站点间连接线路，并逐个进行比较，合并与前面记录相同的线路，删除不同的线路，当没有相同的线路以合并是说明在该线路需要换乘，将该点记为换乘点，直到比较到终点为止。这样不但求出了2个公交站点之间的最短路径，而且还给出了最短路径条件下的最小换乘方案。
5.2最少换乘算法
5.2.1直达矩阵（T 矩阵）[3]
引入直达矩阵T
?a11?a?21T???????a?n1a12a22??an2????????a1n??a2n??? ???ann??其中aij为节点i?j直达线路数m, 即
4
m i ?j aij?? ? ?j?0 i推论：矩阵Tn中的对应的元素aij表示通过（n-1）次换乘从节点i?j的路径数。
?a11?a?21证明：对于矩阵T???????a?n1a12a22??an2????????a1n??a2n??? ???ann??nI.a(i,j)表示由节点i?j直达路径的数量，那么当a(i,j)?0时，i?j有直达路径。 II．T?T?T，且对于任意的i,j??1，2，3，?，n?，bij?T，其中，bij?22?ak?1ikakj
若bij?0，则表示至少存在一个k，使aik和akj不同时为0，
即从i?j可通过在k点转乘一次到达。而bij表示从i?j转乘一次的路径数量。
33cij?T，III．对于二次转乘的情况，且对于任意的i,j??1，2，3，?，n?，T?T?T?T，
mnik其中，cij???ak?1m?1akmamj
若cij?0，则表示至少存在这样一组k, m，使aik,akm,amj同时不为0，即从i?j可通过k，m两处转乘到达。而cij表示从i?j转乘两次的路径数量。
IV．对于（n-1）次转乘矩阵Tn中元素的意义可由I?III的方法依次导出。
5.2.2最少换乘矩阵（Q矩阵）[2]
引入Q矩阵，Qi,j为使得Ti,nj?0的n的最小值，n??1,??。Qi,j?1表示从节点i?j必要的最小换乘次数。?表示两个节点间不存在有效路径。
利用Q矩阵可以确定最小换乘次数，还可用于评价公交网络。若计算所得Qi,j很大，说明从i?j需多次换乘，方便性较差。 5.2.3算法思路
设x, y为起止点
⑴若x?y，则为无效路径；
⑵若在直达矩阵T中axy?0，则x, y之间存在直达路径，记录此时所对应的线路值；
⑶若在直达矩阵T中axy?0且在一次转乘矩阵T2中bxy?0，则x，y之间通过一次转乘可到达：
n①其中使得bxy??ak?1xkaky?0的对应的k值即为一次转乘的转乘站点，即
值；
②此时可将上述一次转乘问题转化为两个直达线路问题，起止点分别为(x,k)和(k,y)，重复⑵，可得两对站点之间的直达路径，记录下对应的两条线路值；
⑷若在直达矩阵T和一次转乘矩阵T2中，axy?0且bxy?0，而在二次转乘矩阵T3中
cxy?0，则
x?k?y，记录此时的中转站点的k
x，y之间通过两次转乘可到达：
5
16222-数学建模-培训课件-B20004018中南大学_崔蕾_吴林_孙种夷
