乘公交,看奥运--历年数学建模大全.doc

乘公交，看奥运

【摘要】本文要解决的问题是以即将举行的08年北京奥运会为背景而提出的。人们为了能现场观看奥运会，必然会面对出行方式与路线选择的问题。因此如何快速、高效地从众多可行路线中选出最优路线成为了解决此问题的关键。

鉴于公交系统网络的复杂性，我们没有采用常规的Dijkstr算法，而采用了高效的广度优先算法。其基本思想是从经过起（始）点的路线出发，搜寻出转乘次数不超过两次的可行路线，然后对可行解进行进一步处理。为满足不同查询者要求，我们对三个问题都分别建立了以时间、转乘次数、费用最小为目标的优化模型。

针对问题一（只考虑公汽系统），我们建立了模型一并通过VC++编程得到了任意两个站点间的多种最优路线，并得出所求站点间最优路线的最优值，如下表所示：

出发站

终点站

S3359

S1828

S1557

S0481

S0971

S0485

S0008

S0073

S0148

S0485

S0087

S3676

最短耗时（min）

64

106

106

67

106

46

最少转乘次数（次）

1

2

1

1

2

2

最少费用（元）

3

3

3

2

3

3

模型二是根据问题二（同时考虑公汽和地铁系统）建立的，同样用VC++编程得到所求站点间的最优路线，如下表所示：

出发站

终点站

S3359

S1828

S1557

S0481

S0971

S0485

S0008

S0073

S0148

S0485

S0087

S3676

最短耗时（min）

64

106

96

55

87.5

33

最少转乘次数（次）

1

2

1

1

2

0

最少费用（元）

3

3

3

2

3

3

对问题三（将步行考虑在内）我们建立了模型三的优化模型，然后在模型改进里又建立了图论模型。

本文的主要特点在于，所用算法的效率十分显著。在对原始数据仅做简单预处理的条件下，搜索任意站点间的最优路线所需的平均时间不超过0.5秒。另外，本文所建立的模型简单、所用算法比较清晰，易于程序实现，对公交线路自主查询计算机系统的实现具有现实指导作用。

关键字：转乘次数广度优先算法查询效率实时系统

一问题的重述

传承华夏五千年的文明，梦圆十三亿华夏儿女的畅想，2008年8月8日这个不平凡的日子终于离我们越来越近了！在观看奥运的众多方式之中，现场观看无疑是最激动人心的。为了迎接2008年奥运会，北京公交做了充分的准备，首都的公交车大都焕然一新，增强了交通的安全性和舒适性，公交线路已达800条以上，使得公众的出行更加通畅、便利。但同时也面临多条线路的选择问题。为满足公众查询公交线路的选择问题，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。

这个系统的核心是线路选择的模型与算法，另外还应该从实际情况出发考虑，满足查询者的各种不同需求。需要解决的问题有：

1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型算法，求出以下6对起始站到终到站最佳路线。

(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485

(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S3676

2、同时考虑公汽与地铁线路，解决以上问题。

3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。

二符号说明

：第i条公汽线路标号,i=1,2…10400,当时,表示上行公汽路线,当时,表示与上行路线相对应的下行公汽路线；

：经过第i条公汽路线的第g个公汽站点标号；

：第j条地铁路线标号,j=1,2；

：经过第j条地铁线路的第h个地铁站点标号；

：转乘n次的路线；

：选择第k种路线的总时间；

：选择第k种路线公汽换乘公汽的换乘次数；

：选择第k种路线地铁换乘地铁的换乘次数；

：选择第k种路线地铁换乘公汽的换乘次数；

：选择第k种路线公汽换乘地铁的换乘次数；

：第k种路线、乘坐第m辆公汽的计费方式，其中：

表示实行单一票价，表示实行分段计价；

：第k种路线，乘坐第m辆公汽的费用；

：选择第k种路线的总费用；

：选择第k种路线，乘坐第m辆公汽需要经过的公汽站个点数；

：选择第k种路线，乘坐第n路地铁需要经过的地铁站个点数；

：表示对于第k种路线的第m路公汽的路线是否选择步行，为0-1变量，表示不选择步行，表示选择步行；

：对于第k种路线的第n路地铁的路线是否选择步行，为0-1变量，表示不选择步行，表示选择步行；

三模型假设

3.1基本假设

1、相邻公汽站平均行驶时间(包括停站时间)：3分钟

2、相邻地铁站平均行驶时间(包括停站时间)：2.5分钟

3、公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)

4、地铁