2007高教社杯全国大学生数学建模竞赛B题论文
公***交通网络模型
摘 要：
明年8月第29届奥运会将在北京举行，届时有大量观众到现场观看奥运比赛，这将对北京的交通带来巨大的影响。本文以给出的北京地区公交路线为参考资料，根据公交网络换乘问题构建了公***交通网络模型。对三个问题的解决方案如下：
（1）针对问题1，本文首先利用MATLAB编程将公交线路读出，求出各站点间的邻接矩阵。再根据所求的邻接矩阵。对求得的邻接矩阵进行处理；判断起点和终点之间有没有直达的线路，如有就确定为最优线路，没有就在通过程序寻找一个合适的数值（记为M）作为限制（即找出邻接点最多的那部分站点），找出通过次数超过这个数值的站点。
下一步则寻找换乘站点。通过把求得的站点与要求的起点和终点，建立循环逐个修改开始站点与最终站点的值可求出通过各站点的路线，再将经过所求得的站点的路线与经过起点和终点的路线进行比较，寻找相同的路线，若存在，则这个站点可以作为所给的这对起点与终点的中转站（但根据人们乘车的习惯，假设中转的次数不超过2次）。如果的站点中无法找到中转站，则调整M的值，直到可以找到可行的乘车路线为止。
根据得到的可行乘车线路，利用路过分别与费用和时间的函数关系，计算出按照吸收较小转车次数的原则，比较用钱少、费时少的线路，最终得到最优的乘车方案。
（2）针对问题2，将换乘地铁站和公汽站视为对等的，与问题1相似，利用相同的方法求出最优线路，但是情况比问题1更复杂，特别是地铁与地铁之间还可以换乘，这需要单独进行考虑。此时，站点数、费用和时间的函数发生了变化，因此，利用新的函数表达式求解再比较得到最优线路。
（3）针对问题3，考虑步行时，可先利用图论中的Floyd算法求出任意两站点间的最短道路，并在此基础上求出这段路步行所需要的时间。再在第二问的基础上，对时间加一个阈值T。当计算出的两点间最短路的步行时间<阈值T时，就选择步行，否则，选择问题2中求得的最优线路。
本文所考虑的算法，可以查询任意两个站点间的乘车最优路径。
关键词：MATLAB程序、公交换乘、限制求解、Floyd算法、最优线路
一、问题重述
北京申奥的成功，对北京市的交通系统提出了更高的要求。依据国外举办奥运会的经验教训来看，奥运期间交通状况是否良好，交通管理是否高效，是关系奥运盛会能否圆满成功举办的举足轻重的条件之一。因此，必须在全面调研基础上，制定切实可行的交通规划及管理策略，为奥运会的成功保驾护航。
在观众的交通行为中，轨道站点、外围停车场和专用巴士的换乘，是整个交通链的重要环节，一旦出现交通瓶颈，其向上游反馈形成的阻塞波(或者称为交通扰动)会溯源而上并且影响加剧，最终造成主会场人员疏散的延误和交通设施服务水平的降低以及一定程度上的混乱和连带的不可估量的经济损失、负面的社会影响。因此应从系统全局考虑进行换乘系统规划，保证观众出行全过程的流畅。
二、模型假设
1、乘客到起始站可以直接选择公汽或地铁班次上车，即不记在起始站的等待时间。
2、在实际过程中，对于公交（包括公汽与地铁）可能要换车2次以上，用户已无法容忍，视为无法到达。（因为如果他们之间换乘就使得费用增大了很多，这是人们不愿意看到的，且一般只坐地铁是无法到达终点站的，所以还要再换乘其他的工具，换乘次数太大我们也不再将其纳入考虑的范围）。
3、相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟。
4、相邻公汽站平均行驶时间(包括停站时间)： 3分钟。
5、公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)。
6、地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)。
7、地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)。
8、公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)。
9、公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价票价为：0～20站：1元；21～40站：2元；40站以上：3元。
10、地铁票价：3元（无论地铁线路间是否换乘）。
11、已知所有站点之间的步行时间。
12、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。
13、郊县和繁华地区公交车站的间隔大概一致。
三、符号说明
1、 表示第一问中从起点站到终点站所用的总时间。
2、 表示表示第一问中从起点站到终点站经过的总站点数。
3、M表示求取局部最优解的限制值。
4、T表示判断是坐车还是步行的阈值，但这个值因人而易。
四、问题的分析
文献[2]对公交乘客的出行心理进行了研究，其结果表明，“换乘次数”是大部分公交乘客在选择出行路线时首先考虑的因素，其次是出行耗时和距离长短。而出行耗费的时间与换乘的次数，及等车的时间以及距离的长短密切相关。因此，对于出行耗时和距离长短，转化为换乘次数最少的基础上出行距离最短的问题。对公交换乘的问题进行
研究，首先就是要解决公***交通网络模型如何合理地表述；其次是公交换乘问题的解决思想。
公***交通网络不同于一般的道路交通网络，在许多书籍文献中都对公***交通网络的特点进行了阐述，如网络的连通性不同于普通道路网，结点有其空间位置特性和一对多的属性等，并分析了弧段的特性及有向线的性质。对于公交网络的特点不再赘述。
在GIS网络分析中，公***交通网络可以映射为一个有向图。根据公***交通网络的特点，把公交网络模型映射为，其中，G为有向赋权图；V表示网络上所有结点即公交站点的集合，一个公交站点可能是多条公交线路的上下客站点；表示网络边(连接公交线路上两个公交站点之间的弧段)的集合，若A站点与B站点是n条线路的相邻上下客站点，那么A与B之间至多有2n条连接边：R表示网络上连接起始点和目标点间所有结点的公交线路的集合； 是结点的非负权值；是边的非负权值[4]。最优出行路径就是指乘客从起始点到目标点所选择的一系列连通结点组成的距离最短的路段及最少换乘的公交线路的集合。[3]