年全国大学生数学建模一等奖获奖论文.doc
《年全国大学生数学建模一等奖获奖论文.doc》由会员分享，可在线阅读，更多相关《年全国大学生数学建模一等奖获奖论文.doc（16页珍藏版）》请在冰点文库上搜索。
2007高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
B
我们的电子文件名：
B0302
所属学校（请填写完整的全名）：
广西师范学院
参赛队员（打印并签名）：
1.钟兴智
2.尹海军
3.斯婷
指导教师或指导教师组负责人（打印并签名）：
韦程东
日期：
2007年9月24日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2007高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
乘公交，看奥运
摘要
我们基于最小换乘次数算法，设计了公交查询系统，能够分别从时间和花费出发考虑，选择最优路径，以满足查询者的各种不同需求。
问题一：
采用最小换乘次数算法，求出任意两站的最小换乘次数，在次数一定的情况下，分别选取花费最少和时间最少作为优化目标，建立两种模型：
最少时间模型：
；最少花费模型：
；利用两种模型求出6组数局的最佳路线如下（两种模型求出的最优结果是一样的）；
起始站→终点站
乘车路线
时间
费用
S3359→S1828
L436下行（S1784）→L167下行
101
3
S1557→S0481
L084下行（S1919）→L189下行（S3186）→L460下行……（有2条最优路线）
106
3
S0485→S0971
L013下行（S0992）→L417下行
128
3
S0008→S0073
L159下行（S0491）→L058下行
……（有5条最优路线）
83
2
S0148→S0485
L308上行（S0036）→L156上行（S3351）→L417下行
101
3
S0087→S3676
L454上行（S3496）→L209下行
65
2
问题二：
把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题，改进问题一中的模型求出此问题的最少时间模型+
得到6组数据的最优路线如下：
起始站→终点站
乘车路线
所需
费用
S3359→S1828
L436下行（S1784）→L167下行
101分
3元
S1557→S0481
L363下行（S1919）→L189下行（S3186）→L460下行……（有两条）
106分
3元
S0485→S0971
L013下行（S0992）→L417下行
128分
3元
S0008→S0073
L159下行（S0491）→L058下行
……（有5条）
83分
2元
S0148→S0485
L308上行（S0036）→L156上行（S3351）→L417下行
101分
3元
S0087→S3676
T2（D27→D36）
33分
3元
问题三：
考虑到会存在紧邻站点与终点站的直达线路，所以我们对问题一的最小换乘算法进行了改进。
关键词：
最小换乘次数，算法，紧邻点，数据库，路线集
问题重述
第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。
这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。
针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。
现需解决以下问题：
1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。
并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线。
（1）、S3359→S1828
（2）、S1557→S0481（3）、S0971→S0485
（4）、S0008→S0073（5）、S0148→S0485（6）、S0087→S3676
2、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。
模型假设
1.相邻两站公汽站距离和所需行驶时间相同。
2.公汽与地铁线路都畅通无阻，即没有堵车。
3.人们考虑换乘次数不超过两次。
4.在有直达车的情况下，人们首选直达车。
5.同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘（无需支付地铁费）。
6.人们选择坐地铁都是出于省时考虑，暂不考虑花费。
模型建立与求解
问题一
1.问题分析
人们在选择公交出行路线时考虑的因素很多，如出行耗时是否最少，线路是否最短，换乘次数是否最少，花费是否最少。
资料调查显示，大多数乘客在选择公汽线路时，首先考虑的是乘车是否方便，就换乘次数而言，一般不大于两次[3]。
所以我们采用最小换乘次数算法[1]，求出最少换乘次数。
然后在最少换乘次数一定的情况下，我们再针对个人偏好，分别选取花费最少和时间最少作为优化目标。
最小换乘次数最少算法的基本思想是从起始站点（任意的），终止站点（任意的）出发，通过比较公交网络上各车站的可换乘车站，追索到的可能路径，然后比较各可能路径的时间或花费，来确定最优路线。
12
2．模型算法与求解
2.1符号说明：
为经过的线路集。
为经过B的线路集。
为线路上的站点。
其中可表示为线路上各站点的序号。
为线路上的站点。
其中可表示为线路上各站点的序号。
为经过的线路集。
为经过的线路集。
2.2算法步骤及流程图：
（1）输入乘车的起始站点及终止站点；
（2）求出经过站点的所有线路集和经过站点的所有线路集；
（3）判断是否等于，如果相等再判断是否为环行线路，如果是则为站点到站点的直达线路，如果不是环行线路但线路上结束的序号大于开始的序号则仍是直达线路；输出结果，结束运算；如果没有则进行下一步。
（4）求线路上的站点以及线路上的站点；
（5）判断是否存在相同站点，即是否有存在=的情况，如果有再判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，线路，即为一次转车的线路，即为转车站点。
如果没有相同站点再执行下面。
（6）求出经过的线路集，经过的线路集；
（7）判断是否等于。
如果相等再判断是否为环行线路，如果是则线路，，为两次换车的线路，换车站点为和；如果不是环行线路但线路上结束的序号大于开始的序号则仍可实现二次转车。
输出结果，结束运算。
开始
直达
进入下组数据
是
获得起点A和终点B
获得经过A的线路集合S（K）和B的线路集合T（L）
S（K）与T（L）是否有交集
交集中的线路类型是否为环形
用一转的方法解决
线路上结束的序号是否大于开始的序号
是
否
否得经过A的线路集合S（K）和B的线路集合T（L）
是
否
最少换乘次数算法流程图：
（图一）
一次转乘算法流程图：
S（K）与T（L）路线是否存在交点
相交路线类型是否为环行
用二转算法解决
线路上结束的序号是否小于结束站序号
经过终点的路线是否为环行
线路上结束的序号是否小于结束站序号
一转可到达
进入下一组数据
是
否
否
是
否
否
否
是
是
（图二）
2.3模型建立：
对于所求转车线路可能不止一条，我们根据最少时间或最少花费为目标函数求出个人所需最优线路。
记为线路上的站点，其序号为；线路上的站点，其序号为。
记,,,
自起三条路线的总站数分别为
；
若线路为上下行或单行，则从站点到转车站点的站点数为，从到的站点数为，从转车站点到站点的站点数为。
若线路为环行，当<，，<时，站点到，到，到站点的站点数为，，。
当>,>时，站点到，到，到站点的站点数为，，
（1）最少时间模型：
（1.1）
s.t.,
（1）
（2）
，（3）
（2）最少花费模型：
（1.2）
s.t.，
（1）
，
（2）
（3）
2.4模型求解
我们将所给文本1.1公路线路信息.txt中的数据作处理，用替换的方法使得文本利于导入数据库，利用C#将文本文件的内容一次导入SQL数据库，接着利用C#编写程序（见附件1），数据库代码见附件2。
利用算法实现的代码与数据库连接求得最优解。
2.5模型结果及分析：
最少时间和最少花费的线路结果表：
起始站→终点站
乘车路线
时间
费用
S3359→S1828
L436下行（S1784）→L167下行
101分
3元
S1557→S0481
L363下行（S1919）→L189下行（S3186）→L460下行
106分
3元
L084下行（S1919）→L189下行（S3186）→L460下行
106分
3元
S0485→S0971
L013下行（S0992）→L417下行
128分
3元
S0008→S0073
L159下行（S0491）→L058下行
83分
2元
L159下行（S3053）→L474上行
83分
2元
L355下行（S2303）→L345上行
83分
2元
L463下行（S2083）→L057上行
83分
2元
L159下行（S0491）→L058下行
83分
2元
S0148→S0485
L308上行（S0036）→L156上行（S3351）→L417下行
101分
3元
S0087→S3676
L454上行（S3496）→L209下行
65分
3元
我们发现在这6组数据里面，时间最少和花费最少的最佳路线是一样的。
这也是符合常情的。
但也存在站数和时间少但花费多的情况。
这时人们就可以根据自己实际情况选择路线。
2.6模型评价
优点：
采用最小换乘次数算法，既符合人们一般想法，又把问题及模型简单化。
能够分别从时间和花费考虑建立两种模型，满足查询者的不同需求。
模型结构简单，条理清晰，易于实施，对于编程来说是比较容易的
缺点：
采用地毯式的遍历搜索，使得程序运行的复杂度过高，运行时间长，不适合于大量数据的应用。
问题二
1.问题分析
如果同时考虑汽车和地铁换乘，虽然花费可能会增加，但很有可能减少路径时间，这对赶时间的人来说是十分必要的。
所以此问只考虑最小换乘次数的最少时间模型。
我们依然规定最小换乘次数为2次。
我们建立了两个模型。
2.模型一的算法与求解
2.1符号说明
为开始站点对应地铁站点的车次，为终止站点对应站点的车次
为地铁站点对应的公汽站点的集合，为地铁站点对应的公汽站点的集合
2.2算法步骤
（1）输入乘车的起始站点及终止站点
（2）分别判断，是否属于，，若都不属于则回到问题一的算法；若,则进行第（3），（4）步；若，则进行第（5）步；若，则进行第（6）步。
（3）判断是否等于，若则可以通过转到。
若，则进行下一步。
（4）若，，则可从乘T1直达；若，，则先从乘T1在D12下车，然后坐T2到达；若，，则先从乘T1在D18下车，然后坐T2到达；若，，则先从乘T2在D18下车，然后坐T1到达判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，；若，，则先从乘T2在D12下车，然后坐T1到达；若，，则从可乘T2直达。
（5），，判断能否找到和中某公汽站点的直达线路。
若没有则退出运算；若有则根据第（3），（4）步求出和的地铁转乘路线。
这样就可求出到的公汽——地铁的转乘路线。
（6），，类似第（5）步求出到的地铁——公汽的转乘路线。
2.3模型建立
当到的路线为通过地铁站点直接转到时，所需时间为公汽与地铁站点的步行时间，即=8
当从乘T1直达时，所需时间为
当从乘T1在D12下车，然后乘T2到达时，所需时间为
当从乘T1在D18下车，然后乘T2到达时，所需时间为
当从乘T2在D18下车，然后坐T1到达时，所需时间为
当从乘T2在D12下车，然后坐T1到达时，所需时间为
当从可乘T2直达时，所需时间为
当为公汽——地铁或地铁——公汽路线时，所需时间为
当不能通过地铁转乘时，所需时间为问题一的最短时间
综上所述，模型一可归纳如下：
（1.3）
s.t.=8，
，，
，，
，，
，，
，，
为环形直达所需时间，，
为公汽与地铁换乘所需时间，或，
为问题一中情况所需时间，
2.4模型评价
此模型算法复杂，且求解各段时间较为困难，很难编程解出结果。
所以我们考虑了第二种模型
3.模型二的建立与求解
3.1模型建立
把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题，然后利用求出的公交站点求出地铁的站台号。
这样可以回归到问题的模型求解。
记：
为原公汽线路上的站点；
为由地铁改编成的公汽线路的站点；
为原公汽线路上的站点；
为由地铁改编成的公汽线路上的站点；
，，
，，
乘坐改编成的公汽线路时的时间为
地铁与公汽换乘时间为
公汽与地铁换乘时间为
综上所述最少时间模型：
+（1.4）
s.t.,
（1）
（2）
，（3）
（4）
（5）
3.2模型求解
把地铁线路转换成公交线路，进行问题中的运算。
运算结果如下表：
起始站→终点站
乘车路线
时间
费用
S3359→S1828
L436下行（S1784）→L167下行
101分
3元
S1557→S0481
L363下行（S1919）→L189下行（S3186）→L460下行
106分
3元
S1557→S0481
L084下行（S1919）→L189下行（S3186）→L460下行
106分
3元
S0485→S0971
L013下行（S0992）→L417下行
128分
3元
S0008→S0073
L159下行（S0491）→L058下行
83分
2元
L159下行（S3053）→L474上行
83分
2元
L355下行（S2303）→L345上行
83分
2元
L463下行（S2083）→L057上行
83分
2元
L159下行（S0491）→L058下行
83分
2元
S0148→S0485
L308上行（S0036）→L156上行（S3351）→L417下行
101分
3元
S0087→S3676
T2（D27→D36）
33分
3元
3.3模型评价：
此模型引用的是问题一中的模型，对时间最短模型进行改进。
只是增加了条件，程序运行复杂度更高。
问题三
1.问题分析
考虑站点之间步行时间后，就有可能存在与终止站点直达线路的紧邻站点，只要先步行到紧邻站点，再由紧邻站点乘直达车到终止站点，就有可能减少时间。
所以要对问题一的算法进行改进[2]。
2.改进的算法
2.1符号说明：
为经过的线路集。
为经过B的线路集。
为线路上的站点。
其中可表示为线路上各站点的序号。
为线路上的站点。
其中可表示为线路上各站点的序号。
为经过或其附近的线路集。
为经过或其附近的线路集。
表示站点与站点之间步行的时间，T表示乘客在换车时步行时间的最大心理承受值。
对于站点与站点之间的紧邻关系，可以用一个不等式表示：
2.2算法步骤：
（1）输入乘车的起始站点及终止站点；
（2）求出经过站点的所有线路集和经过站点的所有线路集；
（3）判断是否等于，如果相等再判断是否为环行线路，如果是则为站点到站点的直达线路，如果不是环行线路但线路上结束的序号大于开始的序号则仍是直达线路；输出结果，结束运算；如果没有则进行下一步。
（4）求线路上的站点以及线路上的站点；
（5）判断是否存在相同站点，即是否有存在=的情况，或者存在紧邻站点，即满足；如果存在=，判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，则线路，即为一次转车的线路，即为转车站点，而且换车时不用更换站点；如果满足，但满足，则线路，仍为一次转车的线路，即为转车站点，但换车时要步行到紧邻站点；如果没有再执行下面。
（6）求出经过的线路集，经过的线路集；
（7）判断是否等于。
如果相等再判断是否为环行线路，如果是则线路，，为两次换车的线路，换车站点为和；如果不是环行线路但线路上结束的序号大于开始的序号则仍可实现二次转车。
输出结果，结束运算。
2.3模型建立：
由于时间关系，我们没能给出基于改进算法的模型，但参照问题一模型的求法，也容易将其求出。
参考文献
[1]李丹等，城市公交出行系统中最优路线算法研究，交通与安全，No.11：
122-124，2005
[2]朱江云等，基于最小换乘次数的最优路径算法，福建电脑，No.3：
121-122，2007
[3]唐德强等，最短路径算法分析及其在公交查询的应用，工程图学学报，No.3：
20-24，2001
[4]姜启源等，数学模型，北京：
高等教育出版社，2003
升级会员 