07年全国数学建模竞赛试题解答（由于懒得将图⽚依次贴出，
需要者可以下载相关附件）
乘公交看奥运
摘要
本设计要解决的是合理给出两站点间的最佳路线选择问题，即给出⼀条经济且省时的路线。在处理此问题之前，我们根据调查和分析，对影响线路选择的因素进⾏筛选，最终确定了以下三个影响较⼤的因素：第⼀是换乘次数；第⼆是乘车时间；第三是乘车费⽤。依据各因素对路线选择的影响程度，我们按不同的权重对它们进⾏考虑。从实际情况分析，⼈们通常宁愿多乘坐⼏站地也不愿换车，所以我们赋予换乘次数较⼤的权重。为了解决换乘次数最少，乘车时间相对较短、乘车费⽤相对较少的问题，经过尝试与探索，我们采⽤了现代分析的⽅法，对起始站和终点站有⽆相交站点进⾏分类讨论，归纳出直达，换乘⼀次，换乘两次的情况（三次以上的情形可以类推），并通过Matlab编制程序，给出了任意两站点间的最佳乘车路线以及换车的地点，最后还提出了进⼀步的意见和建议。
关键词：最佳路线换乘次数乘车时间乘车费⽤
⼀、问题的重述
第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、同⼀地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且⽆需⽀付地铁费。
三、符号的说明
符号表⽰意义
第条包含初始站点的线路，
第条包含初始站点的线路，
符号表⽰意义
第条包含⽬标站点的线路，
第条中间线路，
上的第个站点，
上的第个站点，
上的第个站点，
乘客在第段线路上乘坐的站数
乘客在⼀次地铁线路上乘坐的总站数
公汽换乘公汽的次数
地铁换乘地铁的次数
地铁换乘公汽的次数
公汽换乘地铁的次数
四、问题的分析、模型的建⽴及求解
4.1 问题⼀
4.1.1 问题⼀的分析
已知相邻公汽站平均⾏驶时间(包括停站时间)：3分钟；公汽换乘公汽平均
耗时：5分钟(其中步⾏时间2分钟)。
公汽票价：分为单⼀票价与分段计价两种，标记于线路后；其中分段估计票
价为：0～20站：1元；21～40站：2元；40站以上：3元。
题⽬要求设计任意两公汽站点之间线路选择问题的数学模型与算法。
对于附录中的1.1 公汽线路信息.txt中的数据进⾏处理后，以⽂本⽂件形式导⼊Matlab中，到了站点与
站点之间的关系。进⼀步发现表明⽆论试图产⽣邻接矩阵或边权矩阵因数据太庞⼤⽽可⾏性极低，其运⾏时间长达50分钟，故考虑按题⽬给的路线来建⽴站点矩阵并对此矩阵进⾏处理后能够清晰有效地应⽤此矩阵。
4.1.2 模型的建⽴及求解
模型⼀
设为乘坐公交线路的费⽤函数：
，
总时间函数：
（1）总费⽤函数：
（2）其中表⽰乘客在公交线路上乘坐的站数；表⽰公汽换乘公汽的次数。
⽬标：出任意给定的两站点的乘车线路，使和相对最⼩。
算法思路：由于⼈们的对换乘车次数尽量少的偏好程度总是⼤于对花费时间和⾦钱相对少的偏好程度，
我们将优先考虑换乘车次数尽量少，然后再考虑花费时间相对短、花费⾦钱相对少，对得出的所有结果中进⾏筛选。换乘次数的⼤概思路及步骤如下：将所有包含初始站点的线路建成⼀个集合S，，，所有包含⽬标站点的线路建成⼀个集合G，，。
，，
，，
，。
1、直达的线路。
当时，存在、，，，使得，即、为同⼀线路。此线路既包含初始站点⼜包含⽬标站点。
若，那么，此线路为所求直达线路。
若，或者当时，考虑换乘⼀次的线路。
2、换乘⼀次的线路。
当有和相交时，存在、，，，有及，，。使得，即、为同⼀站点。
若，，那么，从初始站点乘坐线路，⾏驶⾄站点，即在站点，换乘线路⾄⽬标站点。即
若不满⾜，，或者，当⽆任何和相交时，考虑换乘两次的线路。
3、换乘两次的线路。
记，，，有，，，且满⾜与、都相交时，即
线路既不包含初始站点⼜不包含⽬标站点，，。但是
存在及，使得，
存在及，使得，
即、为同⼀站点，且、为同⼀站点。，，，，，，。
若，，，那么，从初始站点乘坐线路，⾏驶⾄站点，即在站点，换乘线路⾄站点，即在站点，换乘线路⾄⽬标站点。即
若不满⾜，，，或者，当不存在满⾜条件的时，说明需要换乘三次才能够到达⽬标站点。换乘三次的线路的模型建⽴原理是相同的。由于⼏乎没有这样的情况，故我们不作考虑。
通过考虑花费的时间或⾦钱，在得出的多条结果中进⾏筛选。
4.1.3 问题⼀的结果
由于公交线路的固定性、重叠性和可选择性，使得公交乘客出⾏线路选择⾏为具有相当的复杂性。由公交乘客的路径选择特性可知，乘客总是根据个⼈偏好选择出⾏路线(或希望出⾏时间最少，或希望换乘次数最少，或希望出⾏费⽤最低)，可称之为最短路因素。同时，由于公交⽹络的复杂性，使得最短路判断出现差异,⽽个⼈选择⾏为带有⼀定的随机性，所以多路径选择较为符合乘客的⾏为特点。另外⼀个⽅⾯，当乘客要进⾏⼀次换乘时，他会考虑到时间或者费⽤等问题，但当乘客必须⼆次换乘时，时间是决定乘客选择路线的唯⼀因素，所以在这种情况下我们只考虑途经站点最少的⼆次转乘路线。基于以上考虑，我们对每道⼩题都给出了多种乘车路线，以供乘客根据⾃⼰的需要选择。
（程序见附录8.1、附录8.2、附录8.3）
（1）S3359→S1828
线路（条）初始站换乘站 (换乘站)⽬标站时间
（分）
⾦钱
（元）
1S3359S1784 S1*******
2S3359S1784 S1*******
3S3359S3515S1784S1828943
4S3359S0359S1784S1828943
53359S3515S1784S1828943
评价说明：经Matlab运⾏程序，得出了5条优化线路。其中，1、2条换乘⼀次，3、4、5条换乘两次， 3、4、5条线路⽐1、2条线路多换乘⼀次，所花的⾦钱相同，但是节省了7分钟时间。
乘客根据⾃⼰的需要进⾏选择。
（2）S1557→S0481
线路（条）初始站换乘站 (换乘站)⽬标站时间
（分）
⾦钱
（元）
1S1557S1919S2424S04811123 2S1557S1919S2424S04811123
S1557S1919S2424S0481
2S1557S1919S2424S04811123
3S1557S1919S2424S04811123
4S1557S1919S2424S04811123
5S1557S1919S2424S04811123
6S1557S1919S2424S04811123
7S1557S1919S2424S04811123
8S1557S1919S2424S04811123
9S1557S1919S2424S04811123
评价说明：经Matlab运⾏程序，得出了9条优化线路。乘坐这9条线路所花费的时间和⾦钱都相同，且均需要换乘两次。不存在换乘⼀次的线路。
乘客可以选择任意⼀条线路。
（3）S0971→S0485
线路初始站换乘站 (换乘站)⽬标站时间
（分）
⾦钱
（元）
1S0971S2184 S0*******
2S0971S0992 S0*******
3S0971S3405S2515S0485943
4S0971S1520S2265S0485943
5S0971S1520S2654S0485943
6S0971S1520S1729S0485943
7S0971S1520S3766S0485943
8S0971S1520S2265S0485943
9S0971S1520S2265S0485943
评价说明：经Matlab运⾏程序，得出了9条优化线路。其中，1条换乘⼀次，3~9条换乘两次， 3~9条线路⽐1条线路多换乘⼀次，所花的⾦钱相同，但是节省了37分钟时间。
乘客根据⾃⼰的需要进⾏选择。
（4）S0008→S0073
线路初始站换乘站 (换乘站)⽬标站时间
（分）
⾦钱
（元）
1S0008S2083 S0073832
2S0008S2263 S0073832
3S0008S2683 S0073832
4S0008S0400 S0073832
5S0008S2559 S0073833
6S0008S1383S2833S0073823
7S0008S1691S2833S0073823
8S0008S3766S2833S0073823
9S0008S1383S2833S0073823
10S0008S1383S2833S0073823
评价说明：经Matlab运⾏程序，得出了10条优化线路。其中，1~5条换乘⼀次，所花费的时间相同，但是1~4条⽐5条节省了1元钱。6~10条换乘两次，所花的⾦钱⽐1~4条多1元，只节省了1分钟时间。
所以建议乘客选择1~4条。
（5）S0148→S0485
线路初始站换乘站 (换乘站)⽬标站时间
（分）
⾦钱
（元）
1S0148S0036S2210S04851063
2S0148S0036S3332S04851063
3S0148S0036S3351S04851063
评价说明：经Matlab运⾏程序，得出了3条优化线路。乘坐这3条线路所花费的时间和⾦钱都相同，且均需要换乘两次。不存在换乘⼀次的线路。matlab 下载
乘客可以选择任意⼀条线路。
（6）S0087→S3676
线路（条）初始站换乘站 (换乘站)⽬标站时间
（分）
⾦钱
（元）
1S0087S3496 S3676652
2S0087S1893 S3676712
3S0087S0541S0236S3676523
4S0087S0541S2336S3676523
评价说明：经Matlab运⾏程序，得出了4条优化线路。其中，1、2条换乘⼀次，所花费的⾦钱相同，但是1条⽐2条节省了6分
钟。3、4条换乘两次，所花的⾦钱相同，且⽐1、2条多1元，但节省了时间。
所以建议乘客选择1、3、4条。
4.2问题⼆
4.2.1 问题⼆的分析
已知相邻地铁站平均⾏驶时间(包括停站时间)： 2.5分钟；
地铁换乘地铁平均耗时：4分钟(其中步⾏时间2分钟)；
地铁换乘公汽平均耗时：7分钟(其中步⾏时间4分钟)；
公汽换乘地铁平均耗时：6分钟(其中步⾏时间4分钟)；
地铁票价：3元（⽆论地铁线路间是否换乘）；其它的公汽时间信息与问题⼀相同。
题⽬要求同时考虑公汽与地铁线路，设计任意两公汽站点之间线路选择问题的数学模型与算法。在此，我们考虑了总时间和总费⽤两个函数，讨论⽅法与⼀题类似，只是加⼊了地铁，分为乘坐地铁和完全不坐地铁两种。
4.2.2模型的建⽴及求解
模型⼆
设，分别为乘坐公交和地铁线路的费⽤函数：
总时间函数：
（，）（3）总费⽤函数：
（4）
其中表⽰乘客在公交线路上乘坐的站数；表⽰乘客在⼀次地铁线路上乘坐的总站数；分别表⽰公汽换乘公汽，地铁换乘地铁，地铁换乘公汽，公汽换乘地铁的次数。
⽬标：出任意给定的两站点的乘车线路，使和相对最⼩。
算法思路：由于假设同⼀地铁站对应的任意两个公汽站之间可以通过地铁站换乘且⽆需⽀付地铁费，那么不妨把同⼀地铁站所对应的⼏个公汽站合并成⼀个站。
地铁线路
，
。
1、可以乘坐地铁的线路。
（1）若初始站点和⽬标站点都在地铁线路或者上，那么，只乘坐地铁或者便可以直达。其中，若都在线路上，就选择经过站数最少的⽅向。
若初始站点和⽬标站点分别在地铁线路和上，那么，需要进⾏⼀次地铁换乘地铁才能到达。
（2）若只有初始站点或只有⽬标站点在地铁线路上，则需要换乘公汽才能到达⽬标站点。
①初始站点，，⽬标站点且，。