07年全国大学生数学建模一等奖获奖论文

2024年2月3日发(作者：数学试卷题组分析报告总结)

2007高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B

我们的电子文件名： B0302

所属学校（请填写完整的全名）： 广西师范学院

参赛队员 (打印并签名) ：1. 钟兴智

2. 尹海军

3. 斯 婷

指导教师或指导教师组负责人 (打印并签名)： 韦程东

日期： 2007 年 9 月 24 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2007高教社杯全国大学生数学建模竞赛

编 号 专 用 页

评

阅

人

评

分

备

注

赛区评阅编号（由赛区组委会评阅前进行编号）：

赛区评阅记录（可供赛区评阅时使用）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

乘公交，看奥运

摘要

我们基于最小换乘次数算法，设计了公交查询系统，能够分别从时间和花费出发考虑，选择最优路径，以满足查询者的各种不同需求。

问题一：采用最小换乘次数算法，求出任意两站的最小换乘次数，在次数一定的情况下，分别选取花费最少和时间最少作为优化目标，建立两种模型：最少时间模型：minf(A,B)3((xini(1xi)qi))5xi；最少花费模型：i1i133ming(A,B)(xi\'(1xi\')yi\')；利用两种模型求出6组数局的最佳路线如下（两13种模型求出的最优结果是一样的）；

起始站→终点站 乘车路线 时间 费用

S3359→S1828 L436下行（S1784）→L167下行 101 3

S1557→S0481 L084下行（S1919）→L189下行（S3186）106 3

→L460下行……（有2条最优路线）

S0485→S0971 L013下行（S0992）→L417下行 128 3

S0008→S0073 L159下行（S0491）→L058下行 83 2

……(有5条最优路线)

S0148→S0485 L308上行（S0036）→L156上行（S3351）101 3

→L417下行

S0087→S3676 L454上行（S3496）→ L209下行 65 2

问题二：把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题，改进问题一中的模型求出此问题的最少时间模型minf(A,B)(yi(3((xini(1xi)qi))5xi)))i1i1i1333

3((1yi)(2.5((xini(1xi)qi)))4xi)7(1zi)yi+6ziyi

\'i1i1i1i1i13333 得到6组数据的最优路线如下：

起始站→终点站 乘车路线 所需

S3359→S1828 L436下行（S1784）→L167下行 101分

S1557→S0481 L363下行（S1919）→L189下行（S3186）106分

→L460下行……（有两条）

S0485→S0971

S0008→S0073

费用

3元

3元

L013下行（S0992）→L417下行 128分 3元

L159下行（S0491）→L058下行 83分 2元

……（有5条）

S0148→S0485 L308上行（S0036）→L156上行（S3351）101分 3元

→L417下行

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]，求出最少换乘次数。然后在最少换乘次数一定的情况下，我们再针对个人偏好，分别选取花费最少和时间最少作为优化目标。

最小换乘次数最少算法的基本思想是从起始站点A（任意的），终止站点B（任意的）出发，通过比较公交网络上各车站的可换乘车站，追索A到B的可能路径，然后比较各可能路径的时间或花费，来确定最优路线。

1

2．模型算法与求解

2.1 符号说明：

S(K)T(L)的序号。

K1,2,,m为经过A的线路集。

L1,2,,n为经过B的线路集。

E(K,U)(U1,2,pi)为线路S(K)上的站点。其中U可表示为线路S(K)上各站点F(L,V)(V1,2,pj)为线路T(L)上的站点。其中V可表示为线路T(L)上各站点的序号。

R(M)(M1,2,,g)为经过E(K,U)的线路集。

Y(N)(N1,2,,z)为经过F(L,V)的线路集。

2.2 算法步骤及流程图：

(1)输入乘车的起始站点A及终止站点B；

(2)求出经过站点A的所有线路集S(K)和经过站点B的所有线路集T(L)；

(3)判断S(K)是否等于T(L)，如果相等再判断S(K)是否为环行线路，如果是则S(K)为站点A到站点B的直达线路，如果不是环行线路但线路上结束的序号大于开始的序号则仍是直达线路；输出结果，结束运算；如果没有则进行下一步。

(4)求线路S(K)上的站点E(K,U)以及线路T(L)上的站点F(L,V)；

(5)判断是否存在相同站点，即是否有存在E(K,U)=F(L,V)的情况，如果有再判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，线路S(K)，T(L)即为一次转车的线路，E(K,U)即为转车站点。如果没有相同站点再执行下面。

(6)求出经过E(K,U)的线路集R(M)，经过F(L,V)的线路集Y(N)；

(7)判断R(M)是否等于Y(N) 。如果相等再判断R(M)是否为环行线路，如果是则线路S(K)，R(M)，T(L)为两次换车的线路，换车站点为E(K,U)和F(L,V)；如果不是环行线路但线路上结束的序号大于开始的序号则仍可实现二次转车。输出结果，结束运算。

2

最少换乘次数算法流程图：

开始

获得起点A和终点B

获得经过A的线路集合S（K）和B的线路集合T（L）

是

S(K)与T(L)是否有交集

否

交集中的线路类型是否为环形

否用一转的方法解决

是

线路上结束的序号是否大于开始的序号

否

直达

是

进入下组数据

（图一）

3

一次转乘算法流程图：

是

S（K）与T（L）路线是否存在交点

否

否

相交路线类型是否为环行

线路上结束的序号是否小于结束站序号

是

否

用二转算法解决

经过终点的路线是否为环行

否

是

是

一转可到达

线路上结束的序号是否小于结束

站序号

进入下一组数据

否

（图二）

2.3模型建立：

对于所求转车线路可能不止一条，我们根据最少时间或最少花费为目标函数求出个人所需最优线路。

记E(K,UA)为线路S(K)上的A站点，其序号为UA；F(L,VB)线路T(L)上的B站点，其序号为VB。

记n1UUA,

n2VU,n3VBV,

自A起三条路线的总站数分别为p1,p2,p3

1U,UAp1；1U,Vp21V,VBp3

4

若线路为上下行或单行，则从A站点E(K,UA)到转车站点E(K,U)的站点数为从E(K,U)到F(L,V)的站点数为n2VU，从转车站点F(L,V)到B站n1UUA，点的站点数为n3VBV。

若线路为环行，当UAU,V>VB时，A站点到E(K,U)，E(K,U)到F(L,V)，F(L,V)到B站点的站点数为p1n1，p2n2，p3n3

（1）最少时间模型：

minf(A,B)3((xini(1xi)qi))5xi （1.1）

i1i133

xi0,3线路为上下行或单行,

(i1,2,3) （1）

线路为环行

1xi3 （2）

i1

qi(nipi)modp(,2,3) （3）

i)，0qipi

(i1（2）最少花费模型：

ming(A,B)(xi\'(1xi\')yi\') （1.2）

130,\'i线路为单一票制，(i1,2,3) （1）

线路为分段计价1ni2021ni40 ，(j1,2,3) （2）

41ni1,y\'j2,3,31xi3 （3）

i12.4模型求解

我们将所给文本1.1公路线路信息.txt中的数据作处理，用替换的方法使得文本利于导入数据库，利用C#将文本文件的内容一次导入SQL数据库，接着利用C#编写程序（见附件1），数据库代码见附件2。利用算法实现的代码与数据库连接求得最优解。

5

2.5模型结果及分析：

最少时间和最少花费的线路结果表：

起始站→终点站 乘车路线

S3359→S1828 L436下行（S1784）→L167下行

时间

101分

费用

3元

3元

3元

3元

2元

2元

2元

2元

2元

3元

3元

S1557→S0481

S0485→S0971

L363下行（S1919）→L189下行（S3186）106分

→L460下行

L084下行（S1919）→L189下行（S3186）106分

→L460下行

L013下行（S0992）→L417下行 128分

83分

L159下行（S0491）→L058下行

L159下行(S3053) →L474上行

83分

83分

83分

83分

S0008→S0073

L355下行(S2303) →L345上行

L463下行（S2083）→L057上行

L159下行（S0491）→L058下行

S0148→S0485

S0087→S3676

L308上行（S0036）→L156上行（S3351）101分

→L417下行

65分

L454上行（S3496）→ L209下行

我们发现在这6组数据里面，时间最少和花费最少的最佳路线是一样的。这也是符合常情的。但也存在站数和时间少但花费多的情况。这时人们就可以根据自己实际情况选择路线。

2.6模型评价

优点：采用最小换乘次数算法，既符合人们一般想法，又把问题及模型简单化。能够分别从时间和花费考虑建立两种模型，满足查询者的不同需求。模型结构简单，条理清晰，易于实施，对于编程来说是比较容易的

缺点：采用地毯式的遍历搜索，使得程序运行的复杂度过高，运行时间长，不适合于大量数据的应用。

6

问题二

1.问题分析

如果同时考虑汽车和地铁换乘，虽然花费可能会增加，但很有可能减少路径时间，这对赶时间的人来说是十分必要的。所以此问只考虑最小换乘次数的最少时间模型。我们依然规定最小换乘次数为2次。我们建立了两个模型。

2.模型一的算法与求解

2.1符号说明

Di(i1,2,...,39)为开始站点A对应地铁站点的车次，Dj(j1,2,...,39)为终止站点B对应站点的车次

Mi为地铁站点Di对应的公汽站点的集合，Mj为地铁站点Dj对应的公汽站点的集合

2.2 算法步骤

（1）输入乘车的起始站点A及终止站点B

（2）分别判断A，B是否属于Mi，Mj，若都不属于则回到问题一的算法；若，（4）步；若AMi，BMj则进行第（5）步；若AMi，AMi,BMj则进行第（3）BMj则进行第（6）步。

（3）判断i是否等于j，若ij则A可以通过Di转到B。若ij，则进行下一步。

（4）若1i23，1j23，则可从Di乘T1直达Dj；若1i23，27j32，则先从Di乘T1在D12下车，然后坐T2到达Dj；若1i23，33j39或24j26，则先从Di乘T1在D18下车，然后坐T2到达Dj；若27i32，1j23，则先从Di乘T2在D18下车，然后坐T1到达判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，Dj；若33i39或24i32，1j23，则先从Di乘T2在D12下车，然后坐T1到达Dj；若24i39或i12,18，24j39或者j12.18，则从Di可乘T2直达Dj。

（5）AMi，BMj，判断能否找到A和Mi中某公汽站点A\'的直达线路。若没有则退出运算；若有则根据第（3），（4）步求出A\'和B的地铁转乘路线。这样就可求出A到B的公汽——地铁的转乘路线。

（6）AMi，BMj，类似第（5）步求出A到B的地铁——公汽的转乘路线。

2.3 模型建立

7

当A到B的路线为通过地铁站点Di直接转到时，所需时间为公汽与地铁站点的步行时间，即t144=8

当从Di乘T1直达Dj时，所需时间为t28(ji)2.5

当从Di乘T1在D12下车，然后乘T2到达Dj时，所需时间为t384(18ij32)2.5

当从Di乘T1在D18下车，然后乘T2到达Dj时，所需时间为t484(18i(j1733)mod(17))

当从Di乘T2在D18下车，然后坐T1到达Dj时，所需时间为t584((33i)18j)2.5

当从Di乘T2在D12下车，然后坐T1到达Dj时，所需时间为t684((i1733)mod(17)12j)2.5

当从Di可乘T2直达Dj时，所需时间为t7

当为公汽——地铁或地铁——公汽路线时，所需时间为t8

当不能通过地铁转乘时，所需时间为问题一的最短时间t9

综上所述，模型一可归纳如下：

minf(A,B)min(t1,t2,...t9) （1.3）

s.t.

t1=8，

ij

t28(ji)2.5，

1i23，1j23

t384(18ij32)2.5，1i23，27j32

t484(18i(j1733)mod(17))，1i23，33j39或24j26

t584((33i)18j)2.5，27i32，1j23

t684((i1733)mod(17)12j)2.5，33i39或24i32，1j23

t7为环形直达所需时间，

24i39或i12,18，24j39或者j12.18

8

t8,为公汽与地铁换乘所需时间

AMi，BMj或AMi，BMj

t9为问题一中情况所需时间

AMi，BMj

2.4 模型评价

此模型算法复杂，且求解各段时间较为困难，很难编程解出结果。所以我们考虑了第二种模型

3.模型二的建立与求解

3.1模型建立

把两条地铁的任意站点的附近公交站点以相同的序号表示，因此将地铁的线路转化成公交的问题，然后利用求出的公交站点求出地铁的站台号。这样可以回归到问题的模型求解。

记：

E(K,U)(U1,2,pi)为原公汽线路S(K)上的站点；

E(K\',U)(U1,2,pi)为由地铁改编成的公汽线路S(K\')的站点；

F(L,V)(V1,2,pj)为原公汽线路T(L)上的站点；

F(L\',V)(V1,2,p\'j)为由地铁改编成的公汽线路

T(L\')上的站点；

n1UUA，n2VU，n3VBV

n1UUA，n2VU，n3VBV

1,yi0乘坐原公汽线路

乘坐改编成的公汽线路3\'3\'\'\'乘坐改编成的公汽线路时的时间为2.5((xini(1xi)qi))4xi

i1i1地铁与公汽换乘时间为7yi

i133公汽与地铁换乘时间为6yi

i11,zi0公汽地铁换乘

地铁-公汽换乘

综上所述最少时间模型：

9

minf(A,B)(yi(3((xini(1xi)qi))5xi)))i1i1i1333

3((1y)(2.5((xniii1i133\'i(1xi)qi)))4xi)7(1zi)yi+6ziyi （1.4）

i1i1i133

xi0,3线路为上下行或单行,

(i1,2,3) （1）

线路为环行

1xi3 （2）

i1

qi(nipi)modp(,2,3) （3）

i)，0qipi

(i11,

yi01,

zi0乘坐原公汽线路 （4）

乘坐改编成的公汽线公汽地铁换乘 （5）

地铁-公汽换乘3.2模型求解

把地铁线路转换成公交线路，进行问题中的运算。运算结果如下表：

起始站→终点站 乘车路线 时间 费用

101分 3元

S3359→S1828

L436下行（S1784）→L167下行

S1557→S0481

S1557→S0481

S0485→S0971

L363下行（S1919）→L189下行（S3186）106分

→L460下行

L084下行（S1919）→L189下行（S3186）106分

→L460下行

L013下行（S0992）→L417下行 128分

L159下行（S0491）→L058下行 83分

L159下行(S3053) →L474上行

S0008→S0073

L355下行(S2303) →L345上行

L463下行（S2083）→L057上行

L159下行（S0491）→L058下行

S0148→S0485

83分

83分

83分

83分

3元

3元

3元

2元

2元

2元

2元

2元

L308上行（S0036）→L156上行（S3351）101分 3元

→L417下行

S0087→S3676 T2（D27→D36） 33分 3元

3.3模型评价：

此模型引用的是问题一中的模型，对时间最短模型进行改进。只是增加了条件，程序运行复杂度更高。

10

问题三

1.问题分析

考虑站点之间步行时间后，就有可能存在与终止站点直达线路的紧邻站点，只要先步行到紧邻站点，再由紧邻站点乘直达车到终止站点，就有可能减少时间。所以要对问题一的算法进行改进[2]。

2.改进的算法

2.1符号说明：

S(K)T(L)的序号。

K1,2,,m为经过A的线路集。

L1,2,,n为经过B的线路集。

E(K,U)(U1,2,pi)为线路S(K)上的站点。其中U可表示为线路S(K)上各站点F(L,V)(V1,2,pj)为线路T(L)上的站点。其中V可表示为线路T(L)上各站点的序号。

R(M)(M1,2,,g)为经过E(K,U)或其附近的线路集。

Y(N)(N1,2,,z)为经过F(L,V)或其附近的线路集。

t(m,n)表示站点m与站点n之间步行的时间，T表示乘客在换车时步行时间的最大心理承受值。对于站点m与站点n之间的紧邻关系，可以用一个不等式表示：t(m,n)T

2.2算法步骤：

(1)输入乘车的起始站点A及终止站点B；

(2)求出经过站点A的所有线路集S(K)和经过站点B的所有线路集T(L)；

(3)判断S(K)是否等于T(L)，如果相等再判断S(K)是否为环行线路，如果是则S(K)为站点A到站点B的直达线路，如果不是环行线路但线路上结束的序号大于开始的序号则仍是直达线路；输出结果，结束运算；如果没有则进行下一步。

(4)求线路S(K)上的站点E(K,U)以及线路T(L)上的站点F(L,V)；

(5)判断是否存在相同站点，即是否有存在E(K,U)=F(L,V)的情况，或者存在紧邻站点，即满足t(m,n)T；如果存在E(K,U)=F(L,V)，判断相交路线是否为环行，如果是且经过终点的路线也为环行，则可一次转车；如果相交路线不是环行，但线路上结束的序号小于结束站序号，仍可一次转车，则线路S(K)，T(L)即为一次转车的线路，E(K,U)即为转车站点，而且换车时不用更换站点；如果满足E(K,U)F(L,V)，但满

11

足t(m,n)T，则线路S(K)，T(L)仍为一次转车的线路，E(K,U)即为转车站点，但换车时要步行到紧邻站点F(L,V)；如果没有再执行下面。

(6)求出经过E(K,U)的线路集R(M)，经过F(L,V)的线路集Y(N)；

(7)判断R(M)是否等于Y(N) 。如果相等再判断R(M)是否为环行线路，如果是则线路S(K)，R(M)，T(L)为两次换车的线路，换车站点为E(K,U)和F(L,V)；如果不是环行线路但线路上结束的序号大于开始的序号则仍可实现二次转车。输出结果，结束运算。

2.3 模型建立：

由于时间关系，我们没能给出基于改进算法的模型，但参照问题一模型的求法，也容易将其求出。

参考文献

[1]李丹等，城市公交出行系统中最优路线算法研究，交通与安全，No.11：122-124，2005

[2]朱江云等，基于最小换乘次数的最优路径算法，福建电脑，No.3：121-122，2007

[3]唐德强等，最短路径算法分析及其在公交查询的应用，工程图学学报，No.3：20-24，2001

[4]姜启源等，数学模型，北京：高等教育出版社，2003

12