乘公交 看奥运
摘 要
本设计要解决的是合理给出两站点间的最佳路线选择问题，即给出一条经济且省时的路线。在处理此问题之前，我们根据调查和分析，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是乘车时间；第三是乘车费用。问题一，对于附录中的1.1 公汽线路信息.TXT中的数据进行处理后，以文本文件形式导入MATLAB中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50min，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。六对站台间考虑只乘坐公共汽车需要的最短时间分别为94min、112min、94min、82min、106min、52min。
针对问题二,要求同时考虑公汽与地铁线路，设计任意两公汽站点之间线路选择问题的数学模型与算法。在此，我们考虑了总时间和总费用两个函数，讨论方法与一题类似，只是加入了地铁，分为乘坐地铁和完全不坐地铁两种。于假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费,那么不妨把同一地铁站所对应的几个公汽站合并成一个站。
针对问题三，问题三在问题二的基础上又增加了步行这种情况，在适当站点步行，可以节省交通费用而且不会消耗过多时间，比如某些乘客在一段分段计价线路上欲乘坐21或41个站点，则可以选择在第20站或第40站下车，步行一站即到达目的地，这样做可以节省1元。
从实际情况分析，人们通常宁愿多乘坐几站地也不愿换车，所以我们赋予换乘次数较大的权重。为了解决换乘次数最少，乘车时间相对较短、乘车费用相对较少的问题，经过尝试与探索，我们采用了现代分析的方法，对起始站和终点站有无相交站点进行分类讨论，归纳出直达，换乘一次，换乘两次的情况（三次以上的情形可以类推），并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的地点，最后还提出了进一步的意见和建议。
关键词： 最佳路线 换乘次数 乘车时间 乘车费用
1
一、问题的重述与分析
第29届奥运会明年8月将在北京举行，作为城市枢纽的公共交通承担着非常重的运输任务。如何在短时间、换乘次数最少、成本最低的情况到达目的地，是人们所关注的问题。
因此，我们通过建立线路选择的模型与算法，设计一套自主查询计算机系统，查询到出行时所需的最佳公交路线及换乘方法，给人们出行节约更多的时间和金钱。
要求：
1、仅考虑公汽线路，建立任意两公汽站点之间线路选择问题的数学模型与算法。并求出以下6对起始站→终到站之间的最佳路线。
（1）S3359→S1828 （2）S1557→S0481 （3）S0971→S0485 （4）S0008→S0073 （5）S0148→S0485 （6）S0087→S3676 2、同时考虑公汽与地铁线路，解决1中问题。
3、如果所有站点间的步行时间已知，建立任意两站点间路线选择问题的数学模型。
分析：问题中包含了三个小问，但实质上讨论的都是建立算法解决奥运期间观众的出行问题。而问题一仅考虑乘坐公汽的情况；问题二在问题一的基础上考虑了添加了乘地铁的情况；问题三则在前两个问题上将步行考虑进模型的情况。三个问题步步深入，环环相扣。作为观众都希望能找到一种既满足转车次数最少，满足花费时间最短，并且车费最省的出行方式。公交查询系统一种较好的解决方案是当用户输入起始站和终点站时，系统只负责分别给出转车次数最少、花费时间最短、车费最省的出行方式，具体路线由乘客根据实际情况选择。最后给出一个较为主观的三目标综合评价指标，给乘客做出最终决定提供一个参考。
二、模型的假设
1、所有公交线路的开班、收班时间相同。 2、公车不会因为堵车等因素延长行驶时间。 3、各条线路不会有新的调整与变化。
4、环线可以以任意站作为起点站和终点站，并且是双向的。 5、除环线以外的线路，到达终点站后，所有的人都必须下车。
6、人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度。
7、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费。
2
三、符号的说明
符号 表示意义 第i条包含初始站点的线路，i?1,2,第j条包含目标站点的线路，j?1,2,第k条中间线路，k?1,2,,w ,m ,s LAi LBj LCk ail bjr LAi上的第l个站点，l?1,2,,m ,t ,v LBj上的第r个站点，r?1,2,cku xi y LCk上的第u个站点，u?1,2,乘客在第i段线路上乘坐的站数 乘客在一次地铁线路上乘坐的总站数 公汽换乘公汽的次数 地铁换乘地铁的次数 地铁换乘公汽的次数 公汽换乘地铁的次数 z1 z2 z3 z4
四、模型的建立及求解
4.1.1 模型的建立及求解：
已知相邻公汽站平均行驶时间(包括停站时间)：3分钟；公汽换乘公汽平均 耗时：5分钟(其中步行时间2分钟)。
公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段估计票 价为：0～20站：1元；21～40站：2元；40站以上：3元。
题目要求设计任意两公汽站点之间线路选择问题的数学模型与算法。
对于附录中的1.1 公汽线路信息.TXT中的数据进行处理后，以文本文件形式导入MATLAB中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50分钟，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。
3
模型一
设f为乘坐公交线路的费用函数：
xi?0;?0,?1, 0?xi?20;?f(xi)??，
2, 20?x?40;i??xi?40?3,总时间函数：
T?3?xi?5z1 (0?z1?2 ) （1）
i?13总费用函数：
F??f(xi) （2）
i?13其中xi表示乘客在公交线路Li上乘坐的站数； z1表示公汽换乘公汽的次数。 目标：找出任意给定的两站点的乘车线路，使T和F相对最小。
算法思路：由于人们的对换乘车次数尽量少的偏好程度总是大于对花费时间和金钱相对少的偏好程度，我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费金钱相对少，对得出的所有结果中进行筛选。换乘次数的大概思路及步骤如下：
将所有包含初始站点ail0的线路LA1,LA2,i?1,2,,LAm建成一个集合S，1?l0?n，
,LBs建成一个集合G，
,m，所有包含目标站点bjr0的线路LB1,LB2,1?r0?t，j?1,2,,s。
S??LA1,LA2,,LAm?， G??LB1,LB2,?ain，i?1,2,,LBs?，
,m， ,s。
LAi?ai1?ai2?LBj?bj1?bj2?1、直达的线路。
当S?bjt，j?1,2,1?i?m，G??时，1?j?s，存在LAi、LBj，使得LAi?LBj，即LAi、
LBj为同一线路。此线路既包含初始站点ail0又包含目标站点bjr0。
若l0?r0，那么，此线路为所求直达线路。 若l0?r0，或者当S
G??时，考虑换乘一次的线路。
4
2、换乘一次的线路。
当有LAi和LBj相交时，存在LAi、LBj，1?i?m，1?j?s，有ail?LAi及
bjr?LBj，1?l?n，1?r?t。使得ail?bjr，即ail、bjr为同一站点。
若l0?l?n，1?r?r0，那么，从初始站点ail0乘坐线路LAi，行驶至站点ail，即在站点bjr，换乘线路LBj至目标站点bjr0。即
ail0??LAi??ail?bjr??LB?j?bjr0
若不满足l0?l?n，1?r?r0，或者，当无任何LAi和LBj相交时，考虑换乘两次的线路。
3、换乘两次的线路。
记LC1,LC2,,LCw，LCk?ck1?ck2??ckv，k?1,2,,w，有LCk?S，
LCk?G，k?1,2,,w，且满足LCk与LAi、LBj都相交时，即
线路LCk既不包含初始站点ail0又不包含目标站点bjr0，1?l0?n，1?r0?t。但是
存在cku1?LCk及ail?LAi，使得cku1?ail， 存在cku2?LCk及bjr?LBj，使得cku2?bjr，
即cku1、ail为同一站点，且cku2、bjr为同一站点。1?k?w，1?i?m，1?j?s，
1?u1?v，1?u2?v，1?l?n，1?r?t。
若l0?l?n，1?u1?u2?v，1?r?r0，那么，从初始站点ail0乘坐LAi线路，行驶至站点ail，即在站点cku1，换乘LCk线路至站点cku2，即在站点bjr，换乘LBj线路至目标站点bjr0。即
ail0??LAi??ail?cku1??LCk??cku2?bjr??LB?j?bjr0
若不满足l0?l?n，或者，当不存在满足条件的LCk1?u1?u2?v，1?r?r0，时，说明需要换乘三次才能够到达目标站点。换乘三次的线路的模型建立原理是相同的。由于几乎没有这样的情况，故我们不作考虑。
通过考虑花费的时间或金钱，在得出的多条结果中进行筛选。
5