[航空航天]乘公交_看奥运方案设计

承诺书

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

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电

话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、

讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的

成果或其他公开的资料（包括网上查到的资料），必须按照规定的参

考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）：

所属学校（请填写完整的全名）黔南民族师范学院

参赛队员 (打印并签名) ：1. 曹龙

2. 彭开连

3. 陈勇

指导教师或指导教师组负责人 (打印并签名)：薛先贵

日期： 2011年 8 月 15 日

乘公交,看奥运

摘要:本文将公交线路（3957个公汽站点和520条公汽线路、39个地铁站点和2条地铁线路、地铁与公汽间转换关系）关系抽象为有向赋权图，并建立时间直达矩阵、费用直达矩阵、换乘直达线路数矩阵，利用最短路模型、搜索法及0-1整数规划模型进行解答。对于问题一，在只考虑公汽的情况下，我们用修改floyd算法求出最小转乘次数、最少费用、最少时间，并由搜索法得出最优线路；对于问题二，在考虑公汽和地铁的情况下，同样，我们也用修改floyd算法求出最小转乘次数、最少费用、最少时间，并由搜索法得出最优线路；对于第三问题，我们则需要考虑步行时间进去，在问题二的基础上并利用0-1整数规划模型进行优化组合取得最优线路。

关键字:线路选择有向赋权图修改floyd算法搜索法优化模型

一、问题重述:

奥运会是世界上举行的一项重大的赛事活动.第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、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

道）→公汽站.换乘耗时11分钟：步行4+4=8分钟, 等车3分钟.

二、问题分析:

本论文主要研究公交线路选择的问题，即要求:

a 如何换车...

b 车与车之间的关系...

c 满足乘车人关心的问题：

1）换乘次数最少；

2）费用最低；

3）时间最短（初始等车时间2(3)min也不包括在内，最后结果可加上。）； ......

在众多的条件中，为了切合人们的实际需要，优先考虑是否有直达,若无直达公汽,则我们主要从最方便、最经济、最快捷等出发，建立以换乘次数、费用、时间为最优的数学模型。

三、模型假设:

1、所有公交线路的每天的工作始末时间相同;

2、公汽、地铁均到站停车;

3、各公交车都运行正常，不会发生堵车现象;

4、环线可以看作以任意站作为起点站和终点站，并且是双向的,并且经过终点后要重新收费;

5、假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘，且无需支付地铁费；

6、人们对换乘车次数尽量少的偏好程度总是大于对花费时间相对短和花费金钱相对少的偏好程度;

7 初始等车时间2(或3)min也不包括在内;

8、同一公交线的往返路线视为两条单行线;

9、考虑两地铁之间不通过公汽乘换（即只：公汽站→地铁站（通道）→公汽站）。

四、模型建立:

对于公交线路选择，我们主要考、虑乘换次数、费用、时间各因素最优。

在线路选择问题中，将公交路线关系抽象成一个有向赋权图，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为：

(0)0ij ij ij i j d i j l d ?=?==∞

???站点往站点无直达车否则。

ij l 表示由i 直达j 付出的代价，可以为时间或费用 (不包括换乘代价；多条线路可达时只保留最小代价)；

公交乘换方式：公汽——公汽，公汽——地铁，地铁——公汽，地铁——地铁，公汽——地铁——公汽。

A ） i 站点是公汽站点，j 站点为地铁站点：

（1）若j 站点对应的所有换乘(公汽)站点k ，均不能从i 直达(不在i 站点所在公汽线路L 上)，则(0)ij d =∞;

（2）若j 站点对应的换乘（公汽）站点k, 可从i 站点直达k ，则费用为(0)ij d =(0)

kj d ；

注：对于时间则需要加上k 到j 的步行时间. (若有多种选择，取最小成本者即可)

B ） j 站点是公汽站点，i 站点为地铁站点： （1）若从i 站点对应的任何换乘(公汽)站点k ，均不能直达j 站点，则(0)ij d =∞.

（2）若从i 站点对应的换乘(公汽)站点k ，能直达j 站点， 则费用为(0)ij d =(0)kj d ；

注：对于时间则需要加上i 到k 的步行时间.

定义：矩阵算子“⊙”如下：设D （k-1）、D 均为n 阶方阵， D(k) = D （k-1）⊙ D (考虑换乘代价)

{}11,,min ,1,2,,k k k ij ij ik kj i j k k n d d d d δ--=++=

当考虑费用矩阵间的运算时，,,i j k δ=0；

当考虑时间矩阵间的运算时，,,i j k δ表示在k 的换乘时间。

D(k)= D(k-1)⊙D 表示k 次换乘的最低代价(费用或时间)，即通

过修改floyd算法求解。

δi,j,k表示换乘时间：

i = j 或k = i，j时，δi,j,k = 0

其他情形：

若不可换乘(当i ，j为公汽站点而k为地铁站点，或者i ，j 为地铁站点而k为公汽站点时)，则δi,j,k = 0

若可换乘，则：

,,

5,

4,

3,

2,

i j k

δ

?

?

?

=?

?

??

若公汽换乘公汽

若地铁换乘地铁

（只考虑换乘时间）若地铁换乘公汽

（只考虑换乘时间）若公汽换乘地铁

问题一模型：

因为仅考虑公汽线路，为了能得到两站点之间的最好选择线路，将题中所提供的公汽网络抽象成一个有向赋权图,建立直达矩阵 D

=

)

()0(

)0(d

D ij

nxn

=

。

当D为时间直达矩阵时，按D(k)= D(k-1) ⊙ D式重复地进行⊙

运算得到

()k

D，当1k

ij

d-=∞，k ij d≠∞时，表示从 i站点到 j站点最少

换乘k次能够到达，且即()k ij d表示换乘k次到达所需的最短时间。

当D为费用直达矩阵时，按D(k)= D(k-1) ⊙ D重复地进行⊙

运算得到

()k

D，运算适当次数后若 D(k)= D(k-1)，则表示已得到所有

站点间的最小费用，()k ij d即表示从i站点到j站点所需的最少费用。

根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。

问题二模型：

当还需要考虑地铁时，为了能得到两站点之间的最好选择线路，同样，将题中所提供的公汽（含地铁转换的公汽）网络抽象成一个有

向赋权图,建立直达矩阵 D =

)

()0(

)0(d

D ij

nxn

=

。算法设计基本与模型一

相当。

当D为时间直达矩阵时，按D(k)= D(k-1) ⊙ D式重复地进行

⊙运算得到

()k

D，当1k

ij

d-=∞，k ij d≠∞时，表示从 i站点到 j站点最

少换乘k次能够到达，且即()k ij d表示换乘k次到达所需的最短时间。

当D为费用直达矩阵时，按D(k)= D(k-1) ⊙ D重复地进行⊙

运算得到

()k

D，运算适当次数后若 D(k)= D(k-1)，则表示已得到所有

站点间的最小费用，()k ij d即表示从i站点到j站点所需的最少费用。

根据最少乘换次数等约束条件，再利用图的邻接搜索法可得出两站点之间的选择线路。

问题三模型：

问题三是在模型二的基础上添加步行时间进行考虑。

优先考虑乘换次数。对直达时间矩阵

()

(0)(0)

ij n n

D D

?

=

按D(k)=

D(k-1) ⊙ D式重复地进行⊙运算得到

()k

D，当1k

ij

d-=∞，k ij d≠∞时，

表示从 i站点到 j站点最少换乘k次能够到达。在运算过程中可记录下换乘站点信息，随之可得到相关线路信息。若有若干条最小换乘路线，则比较另外两个目标选择最佳线路（即建立0-1整数规划模型）。

设共有m条单行公交线，构造一个m+2个点构成的完全图。

点：a 为起点（出发点），b 为终点（目的地），此外每条公交线也视为一个点。

边：边表示两点之间的步行关系。

边权：步行时间为边权。针对不同的边可分为上车前、下车后和换车时步行时间，构成步行时间矩阵()(1)(1)ij m m s S +?+= 。行：依次表示的是m 条公交线与起点，列：依次表示的是m 条公交线与终点。 点权：第个公交线点还有三个信息为点权。

1）公交线名称及上行或下行；

2）类型

,,,,L E T ?=??公汽地铁及票价方式； 3）乘车站数表矩阵 ()(1)(1),1,2,,i i cd m m G g i m +?+== ，其中 i cd g 表示从

c 到

d 经过i 号公交线时需要乘车的站数,c 到d 利用不上i 时

i cd g 取

无穷大。这个矩阵的行列表示用S 。

于是原问题转化为在这个图上求a 到b 的最短路。 最短的可以理解为换乘车数最少、乘车的总站数最少、总的步行时间最少、总车费最少这样几个目标的各种组合方式。

可以用0-1整数规划解决这个问题，方法是分出恰乘一次公交车，恰乘两次公交车，恰乘三次公交车等等情况分别求出下列模型解然后比较得出最优解。

优化模型：

恰乘一次公交车的模型如下：

变量全部是0-1变量，共有3*(m)个。

,1,2,,i x i m = 表示选不选择去第i 条公交线的路；