07年数学建模论文cumcm0719

数学建模优秀论文

公交路线的最优化选择

摘 要

本文讨论了求解交通网络中乘车方案的路线选择问题。考虑到题中站点间距离的邻接矩阵为一个大规模的稀疏矩阵，本文将整个公交网络抽象为“结点―弧段―有向线”的网络模型，再通过广度优先算法求解出不同换乘次数的最佳线路设计方案，从而大幅度的提高程序运行效率.

针对问题一，兼顾不同乘客的需求，本文分别从三个方面（乘车便利性、最短耗时、费用最小化）建立了单因素最优化模型，并通过广度优先算法，求解出题中六组起始点的最佳乘车方案。考虑到实际情况，某些乘客可能并不偏重于考虑单一因素（比如只考虑节约时间而忽略费用的多少），因此本文建立了多因素模糊综合评价模型。

问题二中，本文建立了三阶段动态规划模型，先求出地铁相邻各车站到起点和终点所需的时间，并算出地铁各站间通行最短时间矩阵，再基于动态规划的算法，得到了乘坐地铁情况下公交网络任意两点间最优路线的选择方案，并将其与第一问中的方案进行对比，从而得到考虑地铁通行情况下的最优方案。

对于问题三，在给出一些合理假设后，本文分别以换乘次数最少、总时间最短、费用最低为目标，在定义步行矩阵后，通过动态规划求解出包含步行、乘公交、乘地铁三种方式在内的任意两站点间最优路线的选取方法，并加以推广，在模型扩展中讨论了可包含多种交通方式的两点间最优路线的解决方法。同时，还讨论了蚁群算法在公交网络设计中的应用。

关键词：公交查询 广度优先算法 动态规划 模糊评价

数学建模优秀论文

一． 问题重述

我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时将有大量观众到

现场观看奥运比赛，其中大部分人将会乘坐公共交通工具出行。这些年来，城市的公共交通系统有了很大的发展，使得公众的出行更加通畅，便利，但同时也面临多条公交线路的选还能择问题。

要求设计一个查询系统，从实际情况出发考虑，满足公共交通线路查询者的各种不同要求，包括换乘复杂程度，时间，交通费用等不同因素，为乘客提供最佳乘车路线。

二． 模型假设

1.题目中所给定有关行驶时间与换乘时间的数据与现实相吻合，不考虑由于车辆拥堵程

度等原因造成的时间误差；

2.所有车辆在起点处的发车间隔均为换乘车时的等待时间；

3.北京市交通网络设计合理，各个站点附近交通网络密度基本均匀；

4.若行车路线经过其所在公交车次的终点，则必须在终点处换乘另一辆车，对于公交环线也是如此。但在地铁环线T2的D24站，不考虑换乘问题。 5.公交环形线路车辆只沿一个方向运行。 6.地铁可沿环形线路的两个方向运行。 7.乘车时间军不包含第一次候车时间。

三． 符号说明

Li….……第i条公交线路；

Si…….…第i个公交站点；

wLi,j……表述公交线路Li是否经过公交站Sj的参量，它的值为1表示经过，为0表示不经过；

U………..可以与一个地铁站对应的公交站的集合；

LrTij…..…公交经由线路Lr从Si站行驶到Sj站所需要的时间；

DTij………在Si站与Sj站都与地铁站对应的情况下，通过换乘地铁从Si站达到Sj站所需要的

最短时间；

DMij…..…在Si站与Sj站都与地铁站对应的情况下，通过换乘地铁从Si站达到Sj站所需要的

最少金钱；

Tij…….…在所有公交与公交之间的换乘方式中，从Si站行驶到Sj站所需要的最短时间；

数学建模优秀论文

Mij…….…在所有公交与公交之间的换乘方式中，从Si站行驶到Sj站所需要的最少金钱； CiLr…….…公交经由线路Lr到达Si站时已经经过的站数，若CiLr>CjLr，说明在线路Lr上的

公交车先经过Sj站，后经过Si站。

四． 问题分析

题目要求给出最优路线查询结果，面向着社会大众的“最优”对报有不同目的，不

同偏爱的人来说并不完全相同，但核心问题是找到对路经的一种或多种不同的加权方案，求该方案对应的最短路算法。

解决道路选择问题的常规思路是建立“站点到站点”的赋权有向图模型，通过Dijkstra算法求解。在公交查询中要求的是从某点到另一点的最短路径,而Dijkstra算法求出的是从某点到其余各点的最短路径,而题中所给的站点多至几千,这无疑会降低了求解效率.用Dijkstra算法计算公交路线最短路径,在大数据量的情况下,计算速度会慢得让人难以忍受,而查询系统需要在短时间内给出最佳乘车路线，这一点用Dijkstra算法难以实现. 据统计乘客出行要以最短的时间到达目的地,首先考虑的是转车次数的多少,其次考虑的才是路径的长度.而用Dijkstra算法算出来的结果可能是:从A站到B站需要转几次甚至十几次车才能到达,这样的计算结果是没有意义的.因此我们认为 Dijkstra算法不适合复杂交通网络的最短路径查询，需要寻找一种改进的路径搜索算法。

考虑到题中站点间距离的邻接矩阵为一个大规模的稀疏矩阵，我们将整个公交网络抽象为“结点―弧段―有向线”的网络模型，再通过广度优先算法求解出不同换乘次数的最佳线路设计方案，可大幅度的提高程序运行效率。

五． 模型建立与求解

模型一：公汽换乘模型

模型建立：设换乘次数为k，分别以换乘次数最少、时间最省和交通花费最小化为目标，仅考虑公汽线路，建立最优化模型： 假定从Si到Sj,Sz1Sz2 ,……,Szk为中转站。 （1） 换乘次数最小化模型：

Min k s.t. wLr

1

,i

=wLr

1

,z1＝wLr2,z1

=wLr

2

,z2＝wLr3,z2

= ＝wLr

k+1

,zk

=wLr

k+1

,j

=1；

约束条件表明所选择路线依次经过公交站点SiSz1Sz2 ,……,SzkSj. （2） 时间最小化模型：

数学建模优秀论文

L

Tij= Min Tizr1

1

,i

+

LrLr3Lr2

Tz1z2＋Tz2z3＋…+Tzjk+1

k

+5 k

k+1

s.t. wLr Tz

LrpL

1

=wLr

1

,z1＝wLr2,z1

Lrp

p

=wLr

2

,z2＝wLr3,z2

= ＝wLr

,zk

=wLr

k+1

,j

=1；

p 1zp

=3 (Cz

L

1

Cz

L

Lrp

p 1

); p=1,2……,k

Tizr1=3 (Czr1 C1r1)

1

Tz

Lr

kj

k+1

=3 (Cj

Lr

k+1

Czkk+1)

Lr

LrLrCz为公交经由线路Lr到达Sz站时已经经过的站数:Cz= zt=1wLr,t-1

（3） 花费最省模型：

LMij= Min Mizr1

1

+

LrLr3Lr2+1

Mz1z2＋Mz2z3＋…+Mzk

kj

s.t. wLr

1

,i

=wLr

1

,z1＝wLr2,z1

=wLr

2

,z2＝wLr3,z2

Lr

= ＝wLr

Lr

k+1

,zk

=wLr

k+1

,j

=1；

Mzp 1zp

Lrp

pp

1 Lrp采用单一票制或Czp Czp 1≤20 LL

=2 20<Czrp Czrp≤40

pp 1

3 CLrp CLrp>40 zpzp 1

Mizr1，Mz

1

L

Lr

kj

k+1

的计算方法同上

模型求解：

将各路线抽象为有向弧线(L1L2……Lm)(区分上下行)，站点抽象为弧线上的节点(S1S2……Sn)， wij表述公交线路Li是否经过公交站Sj的参量,值为1表示经过，为0表示不经过。

基于广度优先算法的最短路径求法：

首先搜索合理的方案。公交线路的设计应该满足至多乘车3次就到达目的地，否则就说明公交线路的设计存在问题。用以下步骤搜索3次乘车次数以内的线路选择方案：

1)看是否存在Lk∈ L1,L2…Lm 使得wk,i=wk,j=1如果存在，则说明有可能只要乘

数学建模优秀论文

车一次就可到达目的地．乘车路线为：

Si Sj

2)两次乘车的情况：搜索集合

SS1= L1,L2…Lm ，SS2= S1,S2…Sn 看是否存在Sz1∈SS2; Li1,Li2∈SS1,满足：

wLi

1

Lk

,i

=wLi

1

,z1

=1,wLi

Li1

2

,z1

=wLi

2

,z2

==1

如果存在，则说明需乘车两次(换车一次)，即可到达目的地．乘车路线为：

Si Sz1 Sj

3)三次乘车的情况：搜索集合

SS1= L1,L2…Lm ，SS2= S1,S2…Sn 看是否存在Sz1,Sz2∈SS2;Li1,Li2,Li3∈SS1，满足：

wLi

1

Li2

,i

=wLi

1

,z1

=1,wLi

2

,z1

=wLi

Li2

2

,z2

=1,wLi

3

,z2

=wLi

3

,j

=1

如果存在，则说明只需乘车三次(换车两次)即可达到目的地．乘车路线为：

Si Sz1 Sz2 Sj

根据所查资料，合理的公交线路网可以通过三次以内乘车的线路连接任意两个公交

站点。[1]

但由于以上的算法没有考虑公车上下行站点的不同，所以需要对上述过程的结果进行检验。通过对可行解的检验，剔除掉一些不符合要求的方案（如下图：可以看出，虽然公交路线经过 A，B两点，但由于上行路线没有从A有向到B的路径，所以在本公交班次上不存在从A点到B点的直接走法）。

然后从可行的策略中挑选出换乘次数分别为0，1，2的情况下，最少乘车时间所对应的乘车策略与最少花费所对应的乘车策略。

Li1

Li3

程序流程图如下

数学建模优秀论文

对于题目所给的六个线路，得出分别对应于三种目标的最优策略均包含于如下结果中：

S3359 S1828： 方案1.1：S3359 S1784 S1828, 换乘1次，101分钟，3元； 方案1.2：S3359 S2903 S1784 S1828, 换乘2次，73分钟，3元；

箭头左右为在乘车方案该线路上的始末站点,箭头上方为路线, 路线后括号内为该路线经过的站点数(不包括末端站点).

S1557 S0481： 方案1.1：S1557 S1919 S3186 S0481, 换乘2次，106分钟，3元；

L084(下)（12）

L189(下)(3)

L460(下)(17)

L123（1）

L027(19)

L217或L167(1)

L436（31）

L217或L167(1)

L084(下)表示下行路线,若无括号注明,默认为上行路线 .

S0971 S0485：

方案1.1：S0971 S2184 S0485,换乘1次，128分钟，3元； 方案1.2：S0971 S1609 S2654 S0485,换乘2次，106分钟，3元；

L013(下)（20）L417(下)(21)

L013（2）

L140(下)(19)

L469(11)

数学建模优秀论文

S0008 S0073：

方案1.1：S0008 S0291 S0073, 换乘1次，83分钟，2元；

方案1.2：S0008 S3766 S2184 S0073, 换乘2次，67分钟，3元；

S0148 S0485： 方案1.1：S0148 S0036 S2210 S0485, 换乘1次，106分钟，3元；

S0087 S3676： 方案1.1：S0087 S3496 S3676, 换乘1次，65分钟，2元；

方案1.2：S0087 S0088 S0427 S3676, 换乘2次，46分钟，3元；

查询者可以在上述表中寻找最符合自己目的的乘车方案。如换乘次数最少，耗时最短，花费最低等均可通过简单的查找来满足。为了便于查询，我们给出下表：

L159(下)（18）

L058(8)

L198（3）L296(13)L345(3)

L308（14）L156(15)

L417(下)(3)

L454（11）

L209 下 (9)

L206（1）L231(10)L097(1)

模型二：公汽与地铁混合策略模型

模型建立：分别以换乘次数最少、时间最省和交通花费最小化为目标，考虑借助地铁换乘的情况，建立三阶段动态规划模型：

Si是初始位置，也是动态规划的初态；Sza与Szb分别表示第二个与第三个状态，即换乘地铁的站点，Sza与Szb之间需要换乘地铁，故Sza,Szb∈H；Sj为终点站，也是动态规划的末态。

中间状态只与其位置有关，与之前的行走路线无关。

H中的任意一个元素都对应一种中间状态，特别的，当且仅当Sza与Szb与同一个地铁站对应时，表示两地铁站直接通过地铁站换乘。

构造有向图G如下图：

数学建模优秀论文

分别用某一过程乘车的次数，花费时间，花费金钱对图G的边赋权。我们需要从与地铁两邻的119个公交站中，选择两站za，zb作为公交换地铁，地铁换公交的中转站，使得目标函数值最小。

于是，分别对应换乘次数最少、时间最省和交通花费最小化三个目标建立三阶段动态规划模型。

设n为换乘总次数，Dα,Dβ分别为与Sza与Szb相邻的地铁站。nα,β为从Dα到Dβ的最

D

少换乘次数，TzD为从z到z的最短耗时，M为从za到zb的最少费用。 zabzabazb

（4） 换乘次数最小化模型：

Min n s.t. wLr

1

,i

=wLr

1

,z1＝wLr2,z1

=wLr

2

,z2＝wLr3,z2,zk

= =wLra,za 1=wLra,za=

,j

wLr

b

,zb＝wLr,zb+1

b

= =wLr

k+1

=wLr

k+1

=1；

n=a-b+k+2+nα,β Sza,Szb∈H；

（5） 时间最小化模型：

Min Tiza+TzD+Tzbj azbs.t. wLr wLr

1

,i

=wLr

1

,z1＝wLr2,z1

=wLr

2

,z2＝wLr3,z2,zk

= =wLra,za 1=wLra,za=

,j

b

,zb＝wLr,zb+1

b

= =wLr

k+1

=wLr

k+1

=1；

Sza,Szb∈H （6） 花费最省模型：

数学建模优秀论文

D

Min Miza+Mz+Mzbj azb

s.t. wLr wLr

1

,i

=wLr

1

,z1＝wLr2,z1

=wLr

2

,z2＝wLr3,z2,zk

= =wLra,za 1=wLra,za=

,j

b

,zb＝wLr,zb+1

b

= =wLr

k+1

=wLr

k+1

=1；

Sza,Szb∈H

模型解释:

显然由于地铁站之间较好的连通特性，如果借助地铁的话只需一次公交------地铁------公交的换乘过程。

D

花费在地铁乘坐上的钱只有Mz=3元。花费的时间应该比模型一多考虑公交转地azb

铁,地铁转公交，地铁转地铁这三种情况。

Sza,Szb∈U说明公交站点Sza,Szb在地铁的沿线，选取路线经由这两个公交站与其附近的地铁站实现公交与地铁线路之间的转乘。

Tiza表示从公交站到的最短时间（包括可能出现的公交转乘时间），它可以由模型一提供的算法求出。

公交换乘地铁，地铁换乘公交，以及地铁行驶，地铁转乘的时间均包含于TzD中。 azb

模型求解：

可以运用动态规划问题的求解算法求解。 程序流程图如下：

数学建模优秀论文

对于题目所给的六个线路，得出分别对应于三种目标的最优策略均包含于如下结果中：(路线后括号内数字表示经过的站数,不包括末端站点)

S3359 S1828： 方案2.1：S3359 S3068 D08 D12 D38 S3262

L041(10)

L015（5）

换乘地铁

T1（4）

T2（5）

换乘公交

S1828,换乘3次，84.5分钟，5元；

方案2.2：S3359 S2903 S0609 D12 D37

L123（1）L201（4）

换乘地铁

T2（6）

数学建模优秀论文

换乘公交

S1961 S1671 S1828,换乘4次，62分钟，7元；

S1557 S0481：

方案2.1： S1557 S0978 D32 D24

换乘公交

L

84（下）

L428(2)L041(1)

（14）

换乘地铁

T2（9）

S0537 S0481,换乘2次，116.5分钟，5元；

方案2.2： S1557 S0978 D32 D25

换乘公交

L

084（下）

L516(13)

（14）

换乘地铁

T2（9）

S0525 S0872 S0481, 换乘3次，116分钟，6元；

S0917 S0485：

方案2.1：S0971 S0567 D01 D21 S0466 S0485,换乘2次，96分钟，5元；

方案2.2：S0917 S0567 D01 D15 S2534 S2210

L417下(3)

L094（6）

换乘地铁

T1（14）

换乘公交

L156(5)

L094（6）

换乘地铁

T1（20）

换乘公交

L051（5）

L103(11)L072(1)

S0485,换乘3次，95分钟，6元；

S0008 S0073：

方案2.1：S0008 S2534 D15 D12 D25 S0525

L103(2)

L200（6）

换乘地铁

T1（3）

T2（2）

换乘公交

S0073,换乘3次，53.5分钟，5元；

S0148 S0485：

方案2.1：S0148 S1487 D02 D21 S0466

L051(5)

L

024（下）

（4）

换乘地铁

T1（19）

换乘公交

S0485, 换乘2次，87.5分钟，5元；

方案2.2：S0148 S1487 D2 D15 S2534

L156(5)

L

024（下）

（4）

换乘地铁

T1（13）

换乘公交

S2210 S0485, 换乘3次，86.5分钟，6元；

S0087 S3676：

方案2.1：S0087 D27 D36 S3676, 换乘0次，33分钟，3元；

综合上述结果与模型一中不借助地铁的情况下得出的方案，再次给出针对不同目的

L417（下）(3)

直接到

T2（8）

直接到

数学建模优秀论文

模型三：步行，公汽，地铁的混合策略模型 针对模型三的模型假设：

1．步行路线均在公交线路网中。

2．步行路线的总长度不超过2站，乘车最多次数不超过2。（如果违反了第一点，行人就会由于步行距离过长而不满意，如果违反第二点，则一定存在乘车次数为3次以内的非步行方案优于该步行方案）。

3.从任意一个站点步行至其相邻站点耗时均为15分钟。 模型准备：

基于针对模型三的假设，步行方案中的可行方案包括以下几种类型： 步行------交通工具； 交通工具------步行；

步行------交通工具------步行；

交通工具------步行------交通工具；

交通工具 交通工具------步行； 步行------交通工具 交通工具；

步行------交通工具------步行------交通工具； 步行------交通工具 交通工具------步行；

交通工具------步行------交通工具------步行；

任意一种类型中步行的站数可以为0站，但总和不能超过两站。

针对模型三的符号约定：

A(Si,Sj)……..表述公交站Si是否与公交站Sj距离在两站以内的参量，距离在两站以内时它的值为1，否则值为0；

Ri………………只借助交通工具，或者步行两站路以内的一段有向路径； kRi………….…交通工具在路径Ri上的换乘次数；

iSbegin……..…有向路径Ri的起点；

换乘

换乘

换乘

R

RiS………..…有向路径Ri的终点；

数学建模优秀论文

Ti………………路径Ri上的最短时间(若乘车包括换乘时间,若步行Ti=15); Mi………….…路径Ri上的最少费用(若Mi=0) 模型建立：

分别针对每一种类型的情况仿照模型二建立“a” 阶段动态规划模型 (a≤4)： （7） 换乘次数最小化模型：

Min ai=1kRi

R1Ras.t. Sbegin=Si,Send=Sj,

且任取1<i≤a, A(Si 1,Si)=1；

（8） 时间最小化模型：

Min T1+T2+ +Ta

R1Ra

s.t. Sbegin=Si,Send=Sj,

且任取1<i≤a, A(Si 1,Si)=1；

（9） 花费最省模型：

Min M1+M2+ +Ma

Ra1

s.t. Sbegin=Si,Send=Sj,

R

且任取1<i≤a, A(Si 1,Si)=1；

模型求解：

模型三采用基于广度优先算法与动态规划结合的方法，寻找出“有价值的”步行线路方案，即在某种评价标准下为最优解的方案。

算法流程图如下：

数学建模优秀论文

得出分别对应于三种目标的最优策略均包含于如下结果中：

S3359 S1828：

方案3.1：S3359 S2903 S1671 S1828, 换乘0次，87分钟，1元； 方案3.2：S3359 S1784 S1828, 换乘0次，108分钟，2元；

S1557 S0481： 方案3.1：S1557 S1919 S3919 S0481, 换乘1次，131分钟，3

元；

S0971 S0485： 方案3.1：S0971 S2184 S0992 S0485, 换乘1次，138分钟，

2元； 方案3.2：S0971 S3405 S2515 S0485，换乘1次,129分钟，3元；

S0008 S0073：

方案3.1：S0008 S3729 S0073, 换乘0次，93分钟，2元；

L159(下)（26）

步行(1)

L013(下)（15）

步行(1)

L417(下)(22)

步行（1）L

L201(19)

步行（1）

436（下）

（31）

步行(1)

L

084(下)

（12）

L417(25)

步行(1)

L

013(下)

（20）

步行(1)

L

417(下)

(20)

数学建模优秀论文

方案3.2：S0008 S2743 S3729 S0073, 换乘0次，102分钟，2元；

S0148 S0485：

方案3.1：S0148 S0036 S3351 S0485, 换乘1次，113分钟，2

元；

S0087 S3676： 方案3.1：S0087 S0630 S0427 S3676, 换乘2次，63分钟，1元；

模糊综合评价模型：

1．设由单因素最优化模型给出的方案组成论域U={方案1，方案2……方案n}，，因素集为V={乘车次数，总时间，费用},模糊集A为满意的乘车方案，ek为方案k对A的隶属度，rij表示方案j关于因素i的满意度指标（r1j:方案j乘车次数满意度指标，r2j:方案j乘车时间满意度指标，r3j:方案j所需费用满意度指标。） 2．隶属函数的确定

换乘因素满意度指标：r1k=

vMinvk

步行（1）

L159（下）(24)

步行 (1)

L308（14）L156(17)

步行(1)

步行（1）

L381(11)

步行(1)

.(1)

（1）式中vk为换乘次数。

由于乘车时间越大，乘客的满意度越低，当换乘次数为所有方案中最小值时，可认为满意度为1，即r2k=1。考虑到实际情况，乘车时间超过最小值30分钟的方案在大多数乘客并不会采用，可认为满意度为0。

时间因素满意度指标：r2k=1 费用因素满意度指标：r3k=

tk tMin

30

………………….(2)

cMax ckcMax cMin

……….…………….(3)

由以上公式（1）（2）（3），可计算出满意度矩阵R= rij

3．模糊合成

为了全面提高评判结果，并简化计算，这里进一步选取加权平均模糊合成模型。

ek= 3i=1pi rik…………………………………………(4)i=1,2,...,n

这里pi 表示第i 个影响因子的权系数, ek反应了方案k综合满意度的大小。结合实际，确定各因素的权重为0.5，0.35，0.15。

再运用公式（4）得出综合评判向量： E={e1,e2,……,en},根据隶属度最大化原则， ek值最大者为最佳方案。

综合模型一、二、三给出的结果及模糊评价模型，再次给出针对不同目的的查询表：

数学建模优秀论文

六． 灵敏度稳定性分析

换乘时间有时会有微小变动，并且公交车和地铁的票价也会随着政策的不同而改变，

所以对这两方面可能产生的波动进行讨论就变得很有必要：

1．时间的波动。

与公交车和地铁行驶相关的时间有两个，分别是相邻两站间的平均行驶时间和换车所需时间，由于最优路线的选择仅与这两个时间的比值相关，我们不妨固定相邻两站间公交车和地铁的平均行驶时间，变动换车时间，研究它对最优路线的影响。

从问题一我们得知，我们针对不同换乘次数存在不同方案的4个算例，给出了在固定公交在相邻两站间的平均行驶时间的情况下，换车时间的改变对乘车时间的影响。

当换车时间为20分钟以上时，才有可能改变最优路径的选择方案，因此，问题一中换车时间对方案的选择影响不大。

在问题二里，存在着有很多换乘策略，但总时间花费却差不多的现象，以S01三8到S0485为例，我们首先固定公交车和地铁的两站间的平均行驶时间，研究公汽换公汽的时间对最优路线的影响。

图6.1 图6.2

从图6.1中可以看出，这次公汽换公汽的时间对最优路线的影响就非常大，当公汽

数学建模优秀论文

换公汽的时间多于6分钟时，最优策略就发生改变。因此，此时应尽量选择少换车的方案，以减小换车时的等待造成的时间开销。

在现实生活中，公交与地铁的行驶时间比也会影响到策略的选择，我们仍以S0148到S0485为例，研究这个比例的变化对乘车方案的影响，从图6.2中可以看到，比值在0.8附近就对最优乘车路线产生了影响，为了避免这样的影响，我们建议出行时还是尽量选择两站间行驶时间比较稳定的地铁以减少行驶时间的变动造成的影响。

2．价格的变动。

就在我们讨论这个问题的同时，从网上得知，地铁的价格将由3元/次调整到2元/次。其实价格的变动对偏重时间的最优路线没有影响，在讨论它对偏重价格的最优路线的影响中，我们不妨固定公交车的价格，讨论地铁价格的变化对偏重价格路线的影响。

地铁价格变动之前，地铁，公交价格比为3，相当于坐一次地铁的钱可以坐3次公交，这对于偏重出行费用的乘客来说，他们一般不会坐地铁。通过编程可知，地铁站相邻的共117个车站间共13689条线路均可通过不超过2次换乘到达，具体乘车次数见下图：

也就是说他们乘公交在这117个车站间的花费不会超过3元，因此除了要乘3次车才能到达的那1644条线路的乘客外，其余乘客也就用不着坐地铁以增加出行费用。然而，当地铁价格调整为2元/次后，两站间乘地铁的费用也许会和乘公交的费用一样，甚至少于乘公交的费用，而乘地铁一般是比乘公交节省时间的，所以这必将导致许多乘客改变他们的出行方案。我们假定，如果一条路线乘地铁的费用小于或等于乘公交的费用，那么乘客会选择乘地铁，于是由上图可知，地铁价格调整到2元/次后，将有11344条路线的乘客选择乘地铁（未调整前为1644条），所以，地铁价格调整后将分流大部分乘客，从而大大缓解了公交车运营的压力。

在研究过程中我们还发现：乘公交的人之所以比乘地铁的人多出很多，是因为公交车站点覆盖十分广泛，有将近4000个，而地铁仅覆盖了117个公交站点，所以，加强地铁线路建设力度，建造更多的地铁线路，是使公交车压力得到缓解，公交地铁出行人数进一步平衡，乘客总出行时间减少的有效方案。

数学建模优秀论文

七． 模型评价

优点：

1．模型很好地解决了三个问题，并且用强制搜索的方法给出了每个问题对应的最优解，具有良好的推广意义。

2．我们的模型充分考虑到了实际情况，从金钱，换乘次数和时间3方面衡量一个方案的好坏，能够全面对一种方案进行评价。

3．我们的模型可扩展性强，将来如果有别的出行方式可轻松加入到我们的模型中进行计算。 缺点：

模型只考虑到了两次换乘以内的情形，对于三次以上的换乘计算效率低下。

八． 模型扩展

1.拓展一:多种交通方式情况下两站点间最优路线的选择方法：

在第三问里，乘客的出行方式已经包括步行、乘地铁和乘公交三种情况，其实，现实生活中还可能有骑自行车、骑摩托等别的出行方式，因此，找到一种可包含所有这些出行方法的最优路线选择方案是很必要的。

通过对这三个问题的研究，我们发现：不同出行方式的数据处理方式有两种，一种给出路线—站点矩阵，表述某条路线是否经过某一站点，以及经过的顺序；另一种是给出两站点间步行所需时间的点对点矩阵。这样，无论增加多少出行方式，我们都可以把它们归到上述两种数据处理方法里。

然后是将对应站点联系起来，首先我们要考虑不同出行方式对应的站点是否相同，若相同，则无需处理；若不同，可按照地铁站点转化到相邻的公交站点的方法将其转化为已知站点，方法是动态规划法。最后，将所有数据合并成以上两种方式的矩阵，如果有重复数据，则取其耗费时间较小者。在数据处理过程中，要注意记录数据是出于哪种出行方式。这样，我们就把众多出行方式划归为两种。

最后就是计算，由于两种出行方式的转换不会太多，可列出所有类型，然后利用解决动态问题的方法求出不同出行方式情况下对应的最优路线，再将它们进行比较，从而可以得到最优路线。（由于不同方式间转换花费的时间相对于总出行时间较少，因此可先近似忽略，待求出最优路线后再加上）

2.拓展二:蚁群算法模型：

本模型的显著特点之一就是将换乘次数作为最重要的因素加以考虑。若存在部分人更重视时间而不介意经常换乘车辆（如在途中观光，购物等），则针对他们，可以提出允许较多换乘次数，且以最短时间为目标的蚂蚁算法。

城市的公交线网可用连通的赋权有向图G(S,L,E)表示。V={(si,lj)|1≤i≤n,1≤j≤m }为车辆的状态集, si为公交站点, lj表示车辆行至si时所在的公交路线;站点之间的有向连线(单向、双向)集E表示公交线路及其走向;连线上对应的权值表示蚂蚁出行路径的激素强度。

已知起、迄点的城市公交出行线网可简化为图2形式。假设任一公交站点k的出度

数学建模优秀论文

为n(即从公交站点k可乘坐n条公交线路,即站点k有n个目标站点)。其中起点代表蚁穴,终点

代表食物源。

蚂蚁在出行选择路径时,从起点开始,根据状态vj以及可乘坐的m条公交线路的激素强度,用旋轮方法随机选择第i条继续前进达到下一状态vk,并判断是否达到食物源。若达到则出行成功,并修改公交线网的激素强度(使蚂蚁按原路返回,增加经过的线路的激素强度,反之则减少);若否,则出行时间单位加1,并继续向前查找,直到搜寻到食物源为止。

产生大量蚂蚁，不断地更新各条路线的信息素，以最后一只蚂蚁选择的路径为算法所得的最优路径。[2]

九.参考文献

[1]马良河，刘信斌，廖大庆，《城市公交线路网络图的最短路与乘车路线问题》，《数学的实践与认识》第34卷第6期：第38页，2004年。 [2] 李文勇，王 炜，陈学武，《公交出行路径蚂蚁算法》，《交通运输工程学报》第4卷第4期：第102页，2004年。 [3]苏爱华，施法中，《公交网络换乘问题的一种实现》，《工程图学学报》2005年第4期：第55页，2005年。

[4]陈箫枫，蔡秀云，唐德强，《最短路径算法分析及其仔公交查询中的应用》，《工程图学学报》2001年第3期：第20页，2001年。

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