2007数学建模乘公交 - 看奥运（含代码）

乘公交 看奥运

摘 要

本设计要解决的是合理给出两站点间的最佳路线选择问题，即给出一条经济且省时的路线。在处理此问题之前，我们根据调查和分析，对影响线路选择的因素进行筛选，最终确定了以下三个影响较大的因素：第一是换乘次数；第二是乘车时间；第三是乘车费用。依据各因素对路线选择的影响程度,我们按不同的权重对它们进行考虑。从实际情况分析，人们通常宁愿多乘坐几站地也不愿换车，所以我们赋予换乘次数较大的权重。为了解决换乘次数最少，乘车时间相对较短、乘车费用相对较少的问题，经过尝试与探索，我们采用了现代分析的方法，对起始站和终点站有无相交站点进行分类讨论，归纳出直达，换乘一次，换乘两次的情况（三次以上的情形可以类推），并通过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、同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费。

三、符号的说明

符号 表示意义 第i条包含初始站点的线路，i?1,2,?,m 2

LAi

符号 表示意义 第j条包含目标站点的线路，j?1,2,?,s 第k条中间线路，k?1,2,?,w LBj LCk ail bjr LAi上的第l个站点，l?1,2,?,m LBj上的第r个站点，r?1,2,?,t LCk上的第u个站点，u?1,2,?,v 乘客在第i段线路上乘坐的站数 乘客在一次地铁线路上乘坐的总站数 公汽换乘公汽的次数 地铁换乘地铁的次数 地铁换乘公汽的次数 公汽换乘地铁的次数 cku xi y z1 z2 z3 z4

四、问题的分析、模型的建立及求解

4.1 问题一 4.1.1 问题一的分析

已知相邻公汽站平均行驶时间(包括停站时间)：3分钟；公汽换乘公汽平均 耗时：5分钟(其中步行时间2分钟)。

公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段估计票 价为：0～20站：1元；21～40站：2元；40站以上：3元。

题目要求设计任意两公汽站点之间线路选择问题的数学模型与算法。 对于附录中的1.1 公汽线路信息.txt中的数据进行处理后，以文本文件形式导入Matlab中，找到了站点与站点之间的关系。进一步发现表明无论试图产生邻接矩阵或边权矩阵因数据太庞大而可行性极低，其运行时间长达50分钟，故考虑按题目给的路线来建立站点矩阵并对此矩阵进行处理后能够清晰有效地应用此矩阵。

3

4.1.2 模型的建立及求解 模型一

设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,?,LAm建成一个集合S，1?l0?n，

i?1,2,?,m，所有包含目标站点bjr0的线路LB1,LB2,?,LBs建成一个集合G，

1?r0?t，j?1,2,?,s。

S??LA1,LA2,?,LAm?， G??LB1,LB2,?,LBs?，

LAi?ai1?ai2???ain，i?1,2,?,m，

LBj?bj1?bj2???bjt，j?1,2,?,s。

1、直达的线路。

1?i?m，1?j?s，当S?G??时，存在LAi、LBj，使得LAi?LBj，即LAi、

LBj为同一线路。此线路既包含初始站点ail0又包含目标站点bjr0。

4

若l0?r0，那么，此线路为所求直达线路。

若l0?r0，或者当S?G??时，考虑换乘一次的线路。 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??LBj??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??LBj??bjr0

若不满足l0?l?n，或者，当不存在满足条件的LCk1?u1?u2?v，1?r?r0，

5

??

时，说明需要换乘三次才能够到达目标站点。换乘三次的线路的模型建立原理是相同的。由于几乎没有这样的情况，故我们不作考虑。

通过考虑花费的时间或金钱，在得出的多条结果中进行筛选。

4.1.3 问题一的结果

由于公交线路的固定性、重叠性和可选择性,使得公交乘客出行线路选择行为具有相当的复杂性。由公交乘客的路径选择特性可知,乘客总是根据个人偏好选择出行路线(或希望出行时间最少,或希望换乘次数最少,或希望出行费用最低),可称之为最短路因素。同时,由于公交网络的复杂性,使得最短路判断出现差异,而个人选择行为带有一定的随机性,所以多路径选择较为符合乘客的行为特点。另外一个方面，当乘客要进行一次换乘时，他会考虑到时间或者费用等问题，但当乘客必须二次换乘时，时间是决定乘客选择路线的唯一因素，所以在这种情况下我们只考虑途经站点最少的二次转乘路线。基于以上考虑,我们对每道小题都给出了多种乘车路线，以供乘客根据自己的需要选择。

（程序见附录8.1、附录8.2、附录8.3） （1）S3359→S1828

线路（条）金钱（元）公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数时间（分） 2 3 4 5

3 S3359错误！未找到引用源。错误！未找到引用源。L217下行L436下行??????S1784?????? S1828 131101 S3359错误！未找到引用源。错误！未找到引用源。L167下行L436下行??????S1784?????? S1828 131101 3 94 3 S3359错误！未找到引用源。错误！未找到引用源。L105上行L217下行L011下行??????S3515??????S1784??????S1828 12115S3359错误！未找到引用源。错误！未找到引用源。L015上行L217下行L011下行??????S0359??????S1784??????S1828 1111694 3 3359错误！未找到引用源。错误！未找到引用源。94 3 6

L015上行L167下行L011下行??????S3515??????S1784??????S1828 12115评价说明：经Matlab运行程序，得出了5条优化线路。其中，1、2条换乘一次，3、4、5条换乘两次， 3、4、5条线路比1、2条线路多换乘一次，所花的金钱相同，但是节省了7分钟时间。

乘客根据自己的需要进行选择。

（2）S1557→S0481

线路（条）时间（分）金钱（元）公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数 2 3 4 5 6 7

S1错误！未找到引用源。557错误！未找到引用源。L363下行L417上行L254上行??????S1919??????S2424??????S0481 12175112 S1错误！未找到引用源。557错误！未找到引用源。L363下行L417上行L447上行??????S1919??????S2424??????S0481 12175112 S1错误！未找到引用源。557错误！未找到引用源。L363下行L417上行L460??????S1919??????S2424?????S0481 12175112 S1错误！未找到引用源。557错误！未找到引用源。L363下行L417上行L516上行??????S1919??????S2424??????S0481 12175112 S1错误！未找到引用源。557错误！未找到引用源。L363下行L417上行L312下行??????S1919??????S2424??????S0481 12175112 S1错误！未找到引用源。557错误！未找到引用源。L084下行L417上行L254上行??????S1919??????S2424??????S0481 12175112 S1错误！未找到引用源。557错误！未找到引用源。L084下行L417上行L447上行??????S1919??????S2424??????S0481 121757

112 3 3 3 3 3 3 3 8 S1错误！未找到引用源。557错误！未找到引用源。L084下行L417上行L516上行??????S1919??????S2424??????S0481 12175112 3 9 S1错误！未找到引用源。557错误！未找到引用源。L084下行L417上行L321下行??????S1919??????S2424??????S0481 12175112 3 评价说明：经Matlab运行程序，得出了9条优化线路。乘坐这9条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。

乘客可以选择任意一条线路。

（3）S0971→S0485

线路时间（分）金钱（元）公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数 ?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数 128 L417下行L013下行S0971错误！未找到引用源。??????S2184?????? 21203 S0485 2 L013下行L417下行S0971错误！未找到引用源。??????S0992?????? 2220131 3 S0485 3 S0971错误！未找到引用源。L007上行L417下行L013下行??????S3405??????S2515??????S0485 1221594 3 4 S0971错误！未找到引用源。L119上行L008下行L469上行??????S1520??????S2265??????S0485 8171394 3 5 S0971错误！未找到引用源。L469上行L119上行L008下行??????S1520??????S2654??????S0485 1181994 3 6 S0971错误！未找到引用源。L119上行L008下行L469上行??????S1520??????S1729??????S0485 8201094 3 8

7 S0971错误！未找到引用源。L008下行L119上行L469上行??????S1520??????S3766??????S0485 218994 3 8 S0971错误！未找到引用源。L469上行L013下行L008下行??????S1520??????S2265??????S0485 1291794 3 9 S0971错误！未找到引用源。L469上行L094下行L008下行??????S1520??????S2265??????S0485 1291794 3 评价说明：经Matlab运行程序，得出了9条优化线路。其中，1条换乘一次，3~9条换乘两次， 3~9条线路比1条线路多换乘一次，所花的金钱相同，但是节省了37分钟时间。

乘客根据自己的需要进行选择。

（4）S0008→S0073

公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数线路时间（分）金钱（元）?????? (换乘站??????)目标站 L463下行L057上行S0008错误！未找到引用源。??????S2083?????? 141283 2 公汽线路途经站数公汽线路途经站数 1 2 3 4 5

S0073 L355下行L354上行S0008错误！未找到引用源。??????S2263?????? 71983 2 S0073 L159下行L058下行?S2683?????? S0008错误！未找到引用源。?????17983 2 S0073 L159下行L474上行?S0400?????? S0008错误！未找到引用源。?????101683 2 S0073 L159下行L464上行?S2559?????? S0008错误！未找到引用源。?????2159

83 3 S0073 6 S0008错误！未找到引用源。L198上行L002上行L345上行??????S1383??????S2833??????S0073 1101382 3 7 S0008错误！未找到引用源。L198上行L002上行L345上行??????S1691??????S2833??????S0073 291382 3 8 S0008错误！未找到引用源。L198上行L002上行L345上行??????S3766??????S2833??????S0073 381382 3 9 S0008错误！未找到引用源。L463下行L002上行L345上行??????S1383??????S2833??????S0073 1101382 3 10 S0008错误！未找到引用源。L043下行L002上行L345上行??????S1383??????S2833??????S0073 1101382 3 评价说明：经Matlab运行程序，得出了10条优化线路。其中，1~5条换乘一次，所花费的时间相同，但是1~4条比5条节省了1元钱。6~10条换乘两次，所花的金钱比1~4条多1元，只节省了1分钟时间。

所以建议乘客选择1~4条。

（5）S0148→S0485

线路时间（分）金钱（元）公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数 ?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数S0148错误！未找到引用源。L308上行L156上行L417下行??????S0036??????S2210??????S0485 14153106 3 2 S0148错误！未找到引用源。L308上行L417下行L156上行??????S0036??????S3332??????S0485 14216106 3 10

3 S0148错误！未找到引用源。L308上行L417下行L156上行??????S0036??????S3351??????S0485 14117106 3 评价说明：经Matlab运行程序，得出了3条优化线路。乘坐这3条线路所花费的时间和金钱都相同，且均需要换乘两次。不存在换乘一次的线路。

乘客可以选择任意一条线路。

（6）S0087→S3676

线路（条）时间（分）金钱（元）公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数 2 3 4 65 L454上行L209下行S0087错误！未找到引用源。??????S3496?????? 1192 S3676 L454上行L209下行S0087错误！未找到引用源。??????S1893?????? 121071 2 S3676 S0087错误！未找到引用源。L120上行L454上行L462上行?S0236??????S3676 ??????S0541?????25752 3 S0087错误！未找到引用源。L454上行L120上行L462上行??????S0541??????S2336??????S3676 53652 3 评价说明：经Matlab运行程序，得出了4条优化线路。其中，1、2条换乘一次，所花费的金钱相同，但是1条比2条节省了6分钟。3、4条换乘两次，所花的金钱相同，且比1、2条多1元，但节省了时间。

所以建议乘客选择1、3、4条。 4.2

问题二

4.2.1 问题二的分析

已知相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟；

11

地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)； 地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)； 公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；

地铁票价：3元（无论地铁线路间是否换乘）；其它的公汽时间信息与问题一相同。

题目要求同时考虑公汽与地铁线路，设计任意两公汽站点之间线路选择问题的数学模型与算法。在此，我们考虑了总时间和总费用两个函数，讨论方法与一题类似，只是加入了地铁，分为乘坐地铁和完全不坐地铁两种。

4.2.2 模型的建立及求解 模型二

设f，g分别为乘坐公交和地铁线路的费用函数：

xi?0;?0,?1, 0?xi?20;?0,?f(xi)?? g(y)???3,?2, 20?xi?40;?xi?40?3,y?0; y?0总时间函数：

T?3?xi?2.5y?5z1?4z2?7z3?6z4 （0?zi?2，?zi?2） （3）

i?1i?134总费用函数：

F??f(xi)?g(y) （4）

i?13其中xi表示乘客在公交线路Li上乘坐的站数；y表示乘客在一次地铁线路上乘坐的总站数；z1,z2,z3,z4分别表示公汽换乘公汽，地铁换乘地铁，地铁换乘公汽，公汽换乘地铁的次数。

目标：找出任意给定的两站点的乘车线路，使T和F相对最小。

算法思路：由于假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费，那么不妨把同一地铁站所对应的几个公汽站合并成一个站。

地铁线路

T1?D01?D02???D23， T2?D24?D25???D39?D24。

1、可以乘坐地铁的线路。

12

（1）若初始站点和目标站点都在地铁线路T1或者T2上，那么，只乘坐地铁T1或者T2便可以直达。其中，若都在线路T2上，就选择经过站数最少的方向。

若初始站点和目标站点分别在地铁线路T1和T2上，那么，需要进行一次地铁换乘地铁才能到达。

（2）若只有初始站点或只有目标站点在地铁线路上，则需要换乘公汽才能到达目标站点。

①初始站点ail0?Tp，p?1,2，目标站点bjr0?T1且bjr0?T2，bjr0?LBj。 当有LBj和地铁相交时，即存在LBj，有bjr?LBj，使得bjr?Ty，q?1或2。

1?i?m，1?j?s。

若1?r?r0，那么，从初始站点ail0（记为Da） 乘坐地铁线路，行驶至站点bjr（记为Db），换乘公汽线路LBj至目标站点bjr0。1?a?39，1?b?39。即

ail0??Da?????Tp???bjr??Db?????LBj???bjr0 （q?p） ail0??Da?????Tp???Tq???bjr??Db?????LBj???bjr0 （q?p）

其中， q?p时需要地铁换乘地铁。

若不满足1?r?r0，或者当没有这样的LBj时，说明在地铁换乘公汽后，还需要进行公汽换乘公汽。由于这样的情况几乎不存在，故不作考虑。

②目标站点bjr0?Tp，初始站点ail0?T1且ail0?T2，p?1,2 同理可得结论。

（3）若初始站点和目标站点都不在地铁线路上，则先乘坐公汽，换乘地铁，再由地铁换乘公汽。

地铁线路既和LAi相交又和LBj相交时，即

地铁线路既不包含初始站点ail0又不包含目标站点bjr0。但是存在LAi、LBj，

1?i?m，1?j?s，有

ail?LAi，使得ail?Tp，记ail为Da，

bjr?LBj，使得bjr?Tq，记bjr为Db，

p?1,2，q?1或2，1?a?39，1?b?39。

13

若l0?l?n，那么，从初始站点ail0乘坐LAi线路，行驶至站点ail（记1?r?r0，为Da），换乘地铁线路至站点bjr（记为Db），换乘LBj线路至目标站点bjr0。即

ail0???LAi???ail?Da????Tp???bjr?Db????LBj???bjr0 （q?p） ail0???LAi???ail?Da????Tp???Tq???bjr?Db????LBj???bjr0（q?p）

其中， q?p时需要地铁换乘地铁。

若不满足l0?l?n，1?r?r0，或者不存在LAi、LBj都与地铁线路相交，说明需要在地铁线路前或后进行公汽与公汽的换乘。由于这样的情况几乎不存在，故不作考虑。

2、只乘坐公汽的线路。

完全排除地铁线路，与解决问题一的方法相同。

4.1.3 问题二的结果

（程序见附录8.4） （1）S3359→S1828

应用Matlab编出的程序显示出没有在地铁站附近车站转站的的转站台，所以此时不坐地铁的结果完全和“问题一”中的第一小题的结果相同。

因此在这种情况下，建议在这些站点乘客应当首先考虑坐公汽。具体情况请参照“问题一”的的结果。

（2）S1557→S0481

同（1）的结论。

14

图1 北京地铁图

（3）S0971→S0485

通过S0971的路线同时又能够到达地铁站的线路分别为：L160上行，L263下行，L119上行，L024下行，L119下行，L013上行，分别到达地铁的D01，D02，D26；另外一方面，与终点站S0485相连并能够到达地铁站的公交线路分别是L375上，L469下行，L051上行，L417下行，L395下行，分别到达地铁站的D21，D22和D20。

可以乘坐地铁：

线路（条）时间（分）金钱（元）线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数?????? (换乘站??????)目标站 1 线路途经站数线路途经站数 2 3

138.5 138.5 138.5 L160上行T2?T1?（D21）S0971错误！未找到引用源。??????（D26）?????289L051上行??????S0485 5L160上行T2?T1?（D21）S0971错误！未找到引用源。??????（D26）?????289L469下行??????S0485 5L160上行T2?T1?（D21）S0971错误！未找到引用源。??????（D26）?????289L395下行??????S0485 56 6 6 只乘坐公汽：

15

线路公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数时间（分）金钱（元） 128 L417下行L013下行S0971错误！未找到引用源。??????S2184?????? 21203 S0485 2 L013下行L417下行S0971错误！未找到引用源。??????S0992?????? 2220131 3 S0485 3 S0971错误！未找到引用源。L007上行L417下行L013下行??????S3405??????S2515??????S0485 1221594 3 4 S0971错误！未找到引用源。L119上行L008下行L469上行??????S1520??????S2265??????S0485 8171394 3 5 S0971错误！未找到引用源。L469上行L119上行L008下行??????S1520??????S2654??????S0485 1181994 3 6 S0971错误！未找到引用源。L119上行L008下行L469上行??????S1520??????S1729??????S0485 8201094 3 7 S0971错误！未找到引用源。L008下行L119上行L469上行??????S1520??????S3766??????S0485 218994 3 8 S0971错误！未找到引用源。L469上行L013下行L008下行??????S1520??????S2265??????S0485 1291794 3 9 S0971错误！未找到引用源。L469上行L094下行L008下行??????S1520??????S2265??????S0485 1291794 3 评价说明：经Matlab运行程序，得出了3 条乘坐地铁的优化线路。但与乘坐公汽对比，如果要坐地铁，不仅需要换乘多次，还会花费大量时间。

16

建议乘客乘坐公汽。

（4）S0008→S0073

同（1）的结论。

（5）S0148→S0485

可以乘坐地铁：

线路（条）时间（分）金钱（元）线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数?????? (换乘站??????)目标站 L024下行T1S0148错误！未找到引用源。??????S3045（D02）???（D21）419L051上行??????S0485 5L024下行T1S0148错误！未找到引用源。??????S3045（D02）???（D21）419L104上行??????S0485 5L024下行T1S0148错误！未找到引用源。??????S3045（D02）???（D21）419L395下行??????S0485 5L024下行T1S0148错误！未找到引用源。??????S3045（D02）???（D21）419L450下行??????S0485 5只乘坐公汽：

公汽线路?换乘站初始站错误！未找到引用源。错误！未找到引用源。?????途经站数87.5 5 线路途经站数线路途经站数 1 2 3 4 87.5 5 87.5 5 87.5 5 线路?????? (换乘站??????)目标站 1 公汽线路途经站数公汽线路途经站数时间（分）金钱（元） S0148错误！未找到引用源。L308上行L156上行L417下行??????S0036??????S2210??????S0485 14153106 3 2 S0148错误！未找到引用源。17

106 3

L308上行L417下行L156上行??????S0036??????S3332??????S0485 142163 S0148错误！未找到引用源。L308上行L417下行L156上行??????S0036??????S3351??????S0485 14117106 3 评价说明：经Matlab运行程序，得出了4条乘坐地铁的优化线路。与乘坐公汽对比，节省的时间较多。

乘客根据自己的需要进行选择。

（6）S0087→S3676

抽象出T1和T2的模型，如图1所示。由于S0087和S3676这两个站点都对应地铁站，又由2.2 地铁T2线换乘公汽信息.txt，故把S0087合并到地铁站点D27，把S3676合并到地铁站点D36。又由图1所知，当乘客在S0087时，他有两种很快捷，方便的乘车路线到达S3676，即

D27?D28?D29?D30?D31?D32?D12?D33?D34?D35?D36，

D27?D12?D26?D25?D24?D39?D38?D37?D36。

两条路线都只花3元钱，而第一条线路耗时25分钟，第二条只耗时20分钟。相比于“问题一”中的第六个小题，在花费均相等的前提下，建议乘客选乘地铁，因为这在很大程度上节约了时间，同时也免去了转车带来的麻烦。 4.3

问题三

4.3.1 问题三的分析

已知所有站点间的步行时间，其余信息与问题二相同，题目要求建立任意两站点间路线选择问题的数学模型。

问题三在问题二的基础上又增加了步行这种情况，在适当站点步行，可以节省交通费用而且不会消耗过多时间，比如某些乘客在一段分段计价线路上欲乘坐21或41个站点，则可以选择在第20站或第40站下车，步行一站即到达目的地，这样做可以节省1元。

4.3.2 模型的建立 模型三

设f,g分别为乘坐公交和地铁线路的费用函数：

18

?0,?1,?f(xi?ni)???2,??3,xi?ni?0;0?xi?ni?20;?0, g(y)??20?xi?ni?40;?3,xi?ni?40.y?0; y?0.根据实际情况，在地铁线路上不考虑步行。我们可以在初始站点、目标站点或换乘站点的附近考虑步行，即在任意公交线路Li,1?i?3上最多下车一次。否则，若在某个Li,1?i?3上下车步行两次，则在Li上需要多购买车票一次，同时消耗的时间更多，此做法既违反常理，又不经济实惠。

设在线路Li，i?1,2,3上步行的站数为ni，0?ni?xi，相邻公汽站步行时间为t，那么 总时间函数：

T?3?(xi?ni)?t?ni?2.5y?5z1?4z2?7z3?6z4， （5）

i?1i?133总费用函数：

F??f(xi?ni)?g(y)， （6）

i?13目标：找出任意给定的两站点的乘车线路，使T和F相对最小。

五、模型的评价

5.1 模型的优点：

1、型简单易懂，操作简单，涵盖了所有路线的选择情况。

2、此模型的设计完全符合“乘公交，看奥运”的主题，解决了公交线路的选择问题，使公众的出行更加通畅便利。 5.2 模型的缺点：

忽略了人流、车流拥挤的状况。

六、模型的改进和推广

6.1 对于若干条从某一初始站点到目标站点的线路，我们可以设计一种带记忆功能的系统，即乘客选择某路径的次数越多，说明此路径是比较优的路径，为以后选择路径提供必要的信息。系统使用的时间越长，为乘客提供的信息越全面，越准确，系统也越智能化。这样就可以为乘客需求量最大的一条增加班次，以满足

19

更多人的需要。

6.2 在假设中提到，所有线路的开班、收班时间相同，但事实并非如此。那么可以在模型的设计中加入线路运行的时间元素，使乘客查询时只显示正在运行的线路。

七、参考文献

[1] 姜启源，邢文训，谢金星,杨顶辉，大学数学实验，北京：清华大学出版社，2000

[2] 傅鹂，龚劬，刘琼荪，何中市编著,数学实验，北京:科学出版社，2000 [3] 王树禾，图论，北京：科学出版社，2004 [4] 苏金明等编，MATLAB工具箱应用

八、 附录

8. 1 问题一的程序代码（直达的线路）

x1=input('please input starting station:'); y1=input('please input the terminal :'); [i1,j1]=find(a==x1); [i2,j2]=find(a==y1); [m,n]=size(i1); [p,q]=size(i2); r=0; for i=1:m for j=1:p

if i1(i,n)==i2(j,q) % 厉害呢！找出出发站和终点站在一条线路上的 nv=find(x1==a(i1(i,n),:)); nu=find(y1==a(i2(j,q),:)); if nv

if r~=0

20

disp(t) else t=0 end j1 j2

%直达的输出说明 t是线路 j1是起点站在该线路的第几个站 j2是终点站在该线路的第几个站

8. 2 问题一的程序代码（换乘一次的线路）

x1=input('请输入起点站:'); y1=input('请输入终点站:');

W=input('输入最多经过站点的个数:');

[i1,j1]=find(a==x1); %记录行和列 [i2,j2]=find(a==y1); [m,n]=size(i1); [p,q]=size(i2);

for i=1:m for j=1:p ro=0;

if i1(i,n)~=i2(j,q) mv=a(i1(i,n),:); mu=a(i2(j,q),:); [mo,no]=size(mv); [po,qo]=size(mu); for io=1:no for jo=1:qo

if mv(mo,io)==mu(po,jo)

ad=find(a(i1(i,n),:)==x1); %x1所在的位置 bd=find(a(i2(j,q),:)==y1); %y1所在的位置

ao=find(mv(mo,io)==a(i1(i,n),:)); %转站点在x1所在列的位置 bo=find(mv(mo,io)==a(i2(j,q),:)); %转站点在y1所在列的位置 if ad

to(ro)=mv(mo,io);

21

tka(ro)=ao-1; tji(ro)=bo-1; end end end end

if ro~=0

disp('中转站点') disp(to)

disp('中转站点在始发线上的位置') disp(tka)

disp('中转站点在抵达线上的位置') disp(tji)

vo(1)=i1(i,n);vo(2)=i2(j,q); disp('始发线和抵达线') a(vo,1)

disp('起点站位置') ad-1

disp('终点站位置') bd-1 end end end end

8. 3 问题一的程序代码（换乘两次的线路）

x1=input('请输入起点站:'); y1=input('请输入终点站:');

W=input('输入最多经过站点的个数:'); [i1,j1]=find(a==x1); [i2,j2]=find(a==y1); [m,n]=size(i1); [p,q]=size(i2); [vp,vb]=size(a); tto=0;

22

%寻找不包含起点和终点的线路 for iu=1:vp vc=a(iu,:); rpp=find(x1==vc); rpq=isempty(rpp); tpp=find(y1==vc); tpq=isempty(tpp); if rpq==1&tpq==1 tto=tto+1; uu(tto)=iu; end end

for ey=1:size(uu,2) eyy=a(uu(1,ey),:); for ex=1:m

exx=a(i1(ex,n),:); for ez=1:p

ezz=a(i2(ez,q),:); mn=size(exx,2); iq=0; ih=0;

%寻找exx和eyy的相同元素，赋值到tq for i=1:mn for ig=1:mn

if exx(i)==eyy(ig) iq=iq+1; tq(iq)=exx(i); end end end

%寻找eyy和ezz的相同元素，赋值到tn for i=1:mn for ig=1:mn

if ezz(i)==eyy(ig) ih=ih+1;

23

tn(ih)=ezz(i); end end end

if iq~=0&ih~=0 %eyy与exx，ezz都有交点 for di=1:iq

wq=find(tq(di)==eyy); %exx与eyy的相交元素在eyy中的位置 for dh=1:ih

wh=find(tn(dh)==eyy); %ezz与eyy的相交元素在eyy中的位置 if wq

%第二个转站点和终点站在第三线路上的位置 if Le

disp('起点站第一个转站点第二个转站点终点站在所在线的位置') weizhi=[Le,Lf,Lg,Lh,Lj,Lk] disp('转两次站经过的路线');

L=[a(i1(ex,n),1),a(uu(1,ey),1),a(i2(ez,q),1)] disp('中转站点');

zhongzhuan=[eyy(wq),eyy(wh)] end end end end end end end end

24

8.4 问题二的程序代码

y1=input('finish'); [i1,i2]=find(x1==a) tt=0; t=size(i1,1); for p=1:t

mv=a(i1(p,1),:); n=size(mv,2); for tp=1:n

if(mv(tp)>5000&mv(tp)<6000) tt=tt+1;

mm(tt)=a(i1(p,1),1); break end end end

disp('起点经过地铁的线路') disp(mm) ttt=0

[i1,i2]=find(y1==a); t=size(i1,1); for p=1:t

mv=a(i1(p,1),:); n=size(mv,2); for tp=1:n

if(mv(tp)>5000&mv(tp)<6000) ttt=ttt+1;

mmm(ttt)=a(i1(p,1),1); break end end end

disp('终点经过地铁的线路') disp(mmm)

25

26

本文来源：https://www.bwwdw.com/article/mxka.html