奥运会公交线路查询系统最优方案研究
朱惠雅，梁培艳，秦江星
指导教师：刘平
摘要：本论文针对2008年北京奥运会期间乘客对于公交线路的选择问题进行了分析，以乘客最短交通时间为首要目标，综合考虑了转乘次数、出行费用、出行距离等其他次要因素，建立了公交线路查询系统的网络优化模型。首先，我们对其换乘次数进行约束，规定乘客的换乘次数不得超过3次。对于问题一，仅考虑公汽站点之间的最佳线路选择问题。对于给定的起始点A与终到点B，利用广度优先算法搜索出这两点间所有连通的线路，用这些线路建立起讫点网络，通过对网络中的线路赋权值，得到最终的目标函数。问题二中，同时考虑地铁线路和公汽线路组成的网络。当任意两个站点间同时存在这两种交通方式时，优先选择乘坐地铁出行。以最短交通时间为首要目标，建立优化模型目标函数。问题三中，假设已知所有站点之间的步行时间，则所给站点和路线组成一个以最短交通时间为权值的全连通有向网络图。针对该交通网络图，建立了两种模型。一为最短初等链模型，在建立该模型过程中，未考虑换乘次数对算法的限制，仅达到时间最优即可；二为广度优先搜索模型，在建立该模型过程中，考虑了乘次数对算法的限制，对路线进行了综合处理。
关键词：广度优先搜索；优化模型 ；最短出行时间；转乘次数；MATLAB
基本假设
公交线路顺畅，忽略外界客观因素引起的交通阻塞对公交车运行时间的影响。公交网络中的所有线路均为“无迂回线路”。假设转车的上限定为3次， 鉴于3次以上的转车次数多，不予考虑。当任意两站点间同时存在公汽线路和地铁线路这两种交通方式时，优先选择乘坐地铁出行。
问题分析
问题一，只考虑公汽出行的情况下确定任意两公汽站点之间线路选择问题的模型。首先考虑任意两站点之间的连通性，确定出任意两站点之间转车次数在三次以内的路线。以乘车时间最短为首要目标，以换乘次数少、乘车费用低为次要目标，确定最优线路。问题二，将地铁线路与公共汽车线路结合考虑。基本思路与问题一相似，只是在考虑任意两站点之间的连通性时，需要检验这两个站点间所涉及到路线上是否有公汽站点与地铁站点可以换乘。如果有，则将地铁站点计入线路中。再根据问题一中的标准分别确定不同乘客理想中的不同路线。问题三中，假设已知所有站点之间的步行时间，那么任意两站点之间都连接，则所给站点和路线组成的交通网络成为一个全连通的有向网络图，且该网络图以相邻站点间的最短到达时间为权值，建立数学模型。
模型的建立与求解
问题一
本问题要讨论公交网络中任意两个公汽站点之间的最佳线路选择问题。我们建立了一个起讫点网络数学规划模型对问题一进行求解。
在这里，最佳并不一定意味着最短。最佳线路是指在通达出行者目的的多条线路中，能最好的满足出行者愿望的线路，即是出行效用最大的线路。
本文参照了在南京市做的一个公交乘客出行心理调查统计结果,它主要对三个因素做了调查：换乘次数、出行距离、出行耗时。调查结果显示，有%的乘客在选择出行路径时首先考虑的是“换乘最少”,其次考虑“时间最短”的乘客占％，而将“路程最短”作为出行时考虑的首要条件的乘客只占%，最后考虑其他因素的乘客占％。鉴于北京即将进入奥运会的特殊时期，大批奥运观众涌入京城，为保证奥运观众能正常地观看赛事，避免将时间无谓的浪费在出行过程中，大部分公交乘客在选择出行路径时会首先考虑以满足“出行时间最短”为标准，其次以“步行”、“换乘次数最少”、“所经过公交站点最少”相结合作为判断标准。
设A、B为公交网络中的任意两点，现在欲查找起始站点A到目的站点B的最优路线，为使最终得到的线路出行时间最短，建立了一个起讫点网络数学模型，需要分以下两步进行：
(1) 初始起讫点网络的建立
起讫点网络是一个由任意起始点A和终点B组成的节点集合，以及描述这些起始点和终点之间配对关系的线路组成的网络。起讫点可以作为一条线路的始终点，也可同时作为其它线路的过路点。
利用广度优先搜索和深度优先搜索方法搜索出A、B两点之间的所有“无迂回线路”，包括A、B之间得以实现连通的所有方案，即直达方案、换乘一次、换乘二次、换乘二次等三种方案的所有集合，建立初始起讫点网络。
(2) 赋权值
将以上初始起讫点网络中的所有线路赋上时间权值。由题目中的“相邻公汽站平均行驶时间(包括停站时间)： 3分钟；公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)”可知，在一条公交线路上，行进一站地需要3分钟，起讫点网络中任意两相邻站点边权值为3，全程行驶时间为（站点个数－1）×3分钟。又因为，每转乘一次，平均消耗5分钟，故转乘时间为：转乘次数×5分钟。将以上两种时间相加便得到全过程交通时间。
设初始起讫点网络中起讫点A、B之间“无迂回线路”上的结点共为m个，其中转乘了n（n=0，1，2，3，）次，则这条线路的行车时间为
表示从站点到站点的沿公交网络所需花费的最短时间。
(3) 建立起讫点数学规划优化模型
在起讫点网络后，便可以对其进行优化。以服务区内乘客总乘车时间最短为主要目标建立数学模型，得到构成最终每条奥运会交通线路的任意两站点之间的最短行驶时间路径。建立起讫点配对问题的数学规划模型如下：
目标函数： ()
约束条件：
m、n均为整数
对于问题一中给定的六组数据，在MATLAB中编制程序，求出最终结果。
问题二
本问题在问题一的基础上，又涉及到了另一种交通工具：地铁，即考虑乘坐地铁和公汽出行，选择最佳线路，使乘坐时间达到最短。建模过程中，仍以最短出行时间为第一目标，同时综合考虑出行费用和转乘次数，从而确定出最佳路线。
对所给数据的处理：
（1）从所给地铁线路信息及其换乘公汽信息文档可以看出，地铁线路T2是一个环形线路，而且与线路T1相交于地铁站点D12和D18。
（2）用MATLAB软件对地铁线路换乘公汽信息进行处理，可分别得到起始站点和终点站点与公汽线路Li以及地铁站点Dj间的对应关系。
为避免数据的繁琐，在此，我们只选取一组较简单的数据举例说明，例如第一问中的第二组站点(2)、S1557→S0481的相关信息进行处理可得到以下关系：
公汽线路转乘地铁处所在公汽站点
公汽线路
公汽线路转乘地铁处所在地铁站点
起始站点
S1919
下行L084
D20
S1919
上行L363
D20
S1919
下行L 363
D20
S1921
上行L 084
D20
S1920
上行L 457
D20
S1920
下行L 457
D20
S0978
上行L 084
D32
S0978
下行L 084
D32
对两条地铁线路关系进行简单模拟，如下图所示：
在上图中，椭圆表示线路T2, 上方的箭头表示本路线运行方向为逆向行驶。其中，地铁站点D24、D25、D26、......D38、D39依次按照顺序逆向排列在线路T2中，站点D12、D18穿插其中，作为线路T1与T2的交点。横贯左右的近似直线即为地铁线路T1。各个地铁站点D1、D2、D3、……、D22、D23从左至右依次排列在线路T1上。其中，线路T1应该包括从D1——D23的上行路线以及从D23——D1的下行路线。
(1) 起讫点网络的建立
a、从起始站点A乘坐公汽至最近的地铁站点阶段。
此过程为：首先从起始站点乘坐公共汽车到达可以与地铁站点直接换乘的公汽站点。对于任意起始点A从A点开始进行广度优先搜索， 找出经过A点的所有公共汽车线路，这些线路上的所有公汽站点集合记为，如果与地铁站点相连的公汽站点在集合中，则输出站点与，并且输出连接与的公汽线路。
b、从地下的地铁线路转乘回至公汽线路最后到达终止点B。
这一过程可以看成是第一阶段的反过程，算法步骤基本相同。对于任意起始点B，从B点开始进行广度优先搜索，找出经过B点的所有公共汽车线路，这些线路上的所有公汽站点集合记为，如果与地铁站点相连的公汽站点在集合中，则输出站点与，并且输出连接与的公汽线路。
c、从公汽站点转乘至地铁路线后的地铁线路
在a、b的基础上，连接起地铁站点与的地铁线路即为所求。
(2) 赋权值：
将以上初始起讫点网络中的所有线路赋上时间权值
设初始起讫点网络中起讫点A、B之间“无迂回线路”上的公交站点共为m个，其中转乘了次，则这条线路的地上行车时间为。设在地铁线路上经过地铁站点数目为p个，在地铁线路转乘次，则在地下运行时间为。那么整个过程的交通时间为
T＝Min表示从站点到站点的沿公交网络所需花费的最短时间。
(3) 建立起讫点数学规划优化模型
在确定了起讫点网络后，便可以对其进行优化。以服务区内乘客总乘车时间最短为主要目标建立数学模型，得到构成最终每条奥运会交通线路的任意两站点之间的最短行驶时间路径。建立起讫点配对问题的数学规划优化模型如下：
目标函数：
约束条件：
m、n、 p、q均为整数
问题三
模型一：最短初等链法
本模型主要运用网络图的权映射的概念 ，并通过它把所有求解图的最短路问题转化为最简单的分阶段单向动态规划问题，并在此基础上提出了一种求解图的最短路问题的通用算法——最短初等链法。
设所给公汽线路，地铁线路和步行线路及其各个站点构造的网络图 G=(V，W )(其中 ，为起点，为终点)的一等效作业图是一个 m阶段的动态规划图。是其 m+1个状态集。那么此时的寻优函数方程为：
其中即从初始站点到达终到站点所用时间，表示题目中的各个站点，作为权值，即为任意两相邻站点交通所用时间，当两站点间可通过多种交通工具到达时，的值即为所有交通工具中用时最短的一种所对应的时间。当两点间不存在公汽和地铁线路时，可选择步行到达，步行所需时间已在题目中得到假设。
模型二：基于广度优先算法的最优路线求法。
步骤a： 如果，则进行步行分析，如果存在合适的步行路线则建议乘客步行。
步骤b： 经过站点A的所有车的集合为P（A1），经过站点B的所有车的集合为P（B），如果P（A1）与P（B）的交集非空，则找出此交集，即乘一次车即可到达。若可以一次到达，则计算出A，B之间公共站点最少的线路为最优路线，算法结束。否则转步骤3。
步骤c：找出P（A）中车的所有能转乘车次的集合P（A2），（假设共有转车n1车次）如果P（A2）与P（B）的交集非空，则找出此交集，并按顺序找出这个交集中的车由哪些车转来。即知经一次转车即可到达目的站点。
5 模型的结果分析
在本题中建立的模型，给出了任意两公汽站点之间线路选择问题的一般数学模型与算法。通过对结果进行分析，得到以下：
问题一中，求得的最终结果为如下所示：(1)、S3359→S1828： 67mins；(2)、S1557→S0481：106mins； (3)、S0971→S0485：115mins；(4)、S0008→S0073 64mins ；(5)、S0148→S0485 ：111mins；(6)、S0087→S3676 ：46mins。
可见，为得到两点之间的最佳路线，需要适当增加转乘次数，可以获得相对更短出行时间。例如在第三组数据中(3)、S0971→S0485中，转乘一次的交通时间为128mins，转乘二次降低为115mins。
问题二中，我们做了如此假设：鉴于地铁线路的高速低价等优点，当两点间同时存在这两种交通方式时，优先选择乘坐地铁出行。得到最佳线路的用时分别为如下所示：(1)、S3359→S1828：76mins；(2)、S1557→S0481： 86mins；(3)、S0971→S0485： 78mins；(4)、S0008→S0073：50mins；(5)、S0148→S0485： 79mins (6)、S0087→S3676：30mins。
将问题一与问题二的结果进行比较，绘制折线图，发现两点间同时存在这两种交通方式，优先选择乘坐地铁线路的出行时间确实低于公汽线路所需时间，证明了我们假设是非常合理的。
6 模型的推广与探讨
模型的推广：本文中我们建立了公交线路查询系统的网络优化模型。该模型可以用于辅助设计电子地图，用于地理信息系统或其他信息检索系统。
同时，在解决本类问题时，除了利用Matlab这一常见软件进行编程求解。我们还可以尝试利用数据库加VB实现，或者其他诸如mathematica、spss等软件进行求解。
进一步探讨：在确定最佳路线时，我们以出行时间最短作为首要考虑目标，对乘客的乘车心理统一按照一种思路考虑，这种方法可能并不能使所有的乘客满意，因此进一步研究要设计出合乎不同用户乘车心理的线路选择标准；可以考虑对出行时间、出行费用、出行距离、换乘次数等目标加权，对不同需求的乘客设置不同的权值，从而可以满足所有乘客各种不同的要求。
