2007优秀论文 - 图文

公交最优路线换乘模型

摘

要

本文主要针对大量观众到 2008 年奥运会现场观看奥运比赛的出行问题进行 分析，对出行面临的多条公交线路的选择问题进行剖析，对公交的转乘情况进行 了尽可能的详尽研究。在对人们的出行行为习惯和心理因素进行统计分析的基础 上，并结合实际建立可行的模型与算法。为公司开发解决公交线路选择问题的自 主查询计算机系统提供理论依据。

首先，我们对附件中的公交信息数据进行处理，把数据换成统一的形式，即 每条线路均有上行线和下行线。然后，对各个问题分别进行建立模型和算法。

针对问题一，我们采用了基于最小转乘次数和最短出行时间的公交网络拓扑 模型，本模型根据实际的调查分析，考虑两种判断标准：

（1）建立一个以转乘次数最小为第一目标、以出行时间最短为第二目标和 以出行费用最少作为第三目标的模型与算法。在所有可到达的线路中选择转乘次 数最小值 N，再选出满足条件的各条途经总站数 M ij 。并在此情况下找到出行时 间 t 最短的目标函数:

（2）在第一目标条件下考虑以出行费用最少为第二目标和以出行时间最短 作为第三目标的模型。模型的算法采用了结构体的存储方式，便于数据的调用。 最后，根据算法编写程序并在计算机中运行，得出相应的结果。

针对问题二：我们采用与问题一同样的思想来建立模型和算法，但由于地铁 信息数据与公交的不统一，模型和算法更加复杂。我们采用把相近的各公交车站 （地铁站附近）看作一点来考虑。另外我们将地铁线路图绘制出来后，利用网络 拓扑和图论的相关知识进行求解，我们设计了此种情况的算法。

针对问题三：我们主要考虑相近的不同站点间的步行时间，采用时间阻抗函 数最小为转乘的选择标准。

问题一结果：

转乘次数 最短时间 费用 (1)、S3359—S1828 1 106 3 2 112 3 (2)、S1557—S0481

1 128 3 (3)、S0971—S0485

1 83 2 (4)、S0008—S0073

2 120 3 (5)、S0148—S0485

1 65 2 (6)、S0087—S3676

t = min{t j / t j = 5* N + 3*(Mij ?1)，j=1,2L k)} (分钟)。

关键字：换乘次数 拓扑模型 数学描述 最优公交路径 时间阻抗函数

Dijkstra 改进模型

1

一、 问题的重述

随着城市建设的飞速发展及公交系统的不断完善，公交车已成为城市居民出

行的主要交通工具。但由于城市公交线路四通八达，且随着城市扩建而快速发展， 新的公交线路在不断延伸和开辟，再加上单行道、禁左等道路交通约束，即使是 当地居民也不一定能找到到达目的地的最佳线路，外地游客更是难以获取公交出 行的路径信息。因此，在2008年奥运会来临之际，北京应建立适合于公交线路查 询特点的公交数据模型，开发操作直观、便捷、快速、准确的城市公交查询系统， 为出行者提供全面、准确的公交信息，帮助出行者快速地选择出行路径、换乘路 线等,提升出行者的效率,优化公交资源的配置,提高交通运输的效率和城市的信 息服务化水平。

针对这种情况要求我们设计一个系统，其核心是线路选择的模型与算法，能 够从实际情况出发，满足查询者的各种不同需求。并解决以下三个问题：

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 分钟； 3. 相邻地铁站的行驶时间相等(包括停站时间)： 2.5 分钟； 4. 公汽换乘公汽耗时相等： 5 分钟(其中步行时间 2 分钟)； 5. 地铁换乘地铁耗时相等： 4 分钟(其中步行时间 2 分钟)； 6. 地铁换乘公汽耗时相等： 7 分钟(其中步行时间 4 分钟)； 7. 公汽换乘地铁耗时相等： 6 分钟(其中步行时间 4 分钟)；

8. 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的 票价为：0～20 站：1 元；21～40 站：2 元；40 站以上：3 元

9. 顾客在车站等候各站车的时间相等，且仅考虑从起始站出发后开始计时，直 到到达终点站所需时间；

10.只考虑至多二次换乘的情况。 注：上述是模型假设讨论过程中的全局性假设，在后面的分布讨论中我们可能引 入新的全局性假设。

2

三、 符号说明

1. V（G）表示所有公交站点的集合；

2. TR = {TRi TRi ≤ (s0 , li1 , si1 , li 2 , si 2 ,L , sd )}(i = 1, 2, 3L , n) ，是包含起点 s0 和终点 sd

的可行公交路径集合；

3. L = {l j j = 1, 2,L , 520} 为公交线路集合，各线路具有唯一编号； 4. vij 表示第 i 线路上的第 j 站点；

5. E(G)是所有道路边的集合； 6. Z 表示出行区域的集合， Z = {z1 , z2 ,L , zm m为区域数} ；

7. li 表示一条公交线路；

8. Pxy 表示一条公交路径，可记为 Pxy = {i1 , l1 , i2 , l2 , i3 ,

i4 ,L

, lk , i2 k ?1}

；

9. R = {lk k = 1, 2,L , K} 为线路--节点关系集合，称之为线路--节点描述； 10. N i (自然数）：第 i 条途经换乘次数； 11. M i (正整数）：第 i 条途经总站数；

12. Wi 表示路段阻抗，即平均换乘所需时间。

注：此处的符号变量说明为全局性变量，具体的模型中设定的变量符号只具有局 部性。

3

四、 问题分析

1 公交网络描述

公交网络是由公交道路网络和相应的公交车线路网络组合而成。一般的公交 道路网络包括出行区域（起始站点和目标站点）、步行边、道路边和结点。当发 生换乘时，步行边是指从下车站点到另一上车站点间步行的一段。公交道路网络 中的结点一般指道路交叉口和车站，在此为研究方便，结点仅指公交站点，而道 路边指有某条公交线经过的相邻站点间道路，是一个经抽象简化的概念。公交道 路网用简单图 G 表示，而结点集 V（G）是所有公交站点的集合，边集 E（G）

V (G) = n ，表示有 n 个不同的公是所有道路边的集合。V（G）的基数为 n，即

交站点。出行区域的集合定义为:

Z = {z1 , z2 ,L , zm m为区域数} 步行边的集合用 E 0 = {e i ≠ j} 来表示。 ij i, j ∈ (Z UV (G)),

公交车线：

Ri = {k , n1 , n2 ,L , nvi nvi ∈V (G), vi为Ri 上的站点数, k ∈ (0,1, 2)}

(1)

式(1)表示公交车线可从n1点出发依次经过n2，n3,?，nvi-1，到达nvi点。如果 是环线，k=2；如非环线，双向，k=1；如非环线，单向，k=0。而由所有的公交 车线形成公交车线网络X：X = {Ri i = 1, 2,L , N R , N R为网络中车线数}，而对公 交网络中的一条公交路径，可记为：

(2) Pxy = {i1 , l1 , i2 , l2 , i3 , , lk , i2 k ?1}

i1 , i2 k ?1 ? ?出行区域

i4 ,L 式中：

l1 , l2 ,L , lk ? ?车线

有了以上的表述,再给出两条定义： 定义 1 设 I ∈V (G) ，称 I 为基结点，由 I 出发经 k 次换乘可以到达的结点为 I

k

的第 k 层点。I 的第 k 层点的全体记为W ；特殊的，若 I 到 j 有直达公交线路， l 则称 j 为 I 的第 0 层点(或直达点)。 定义 2 称结点 I 到结点 j( j ∈W lk k 次换乘的时间最短公交路径，为 I 到 j 的 ) 经

第 k 阶公交最短路径，其时间称为 I 到 j 的第 k 阶公交最短行程时间， 记为: t k (I , j) 。 2 问题背景的理解与解决思想：

公交乘务问题的实质就是给出起始点、目标点后，给用户提供乘车方案。所 谓乘车方案是一个站点、线路的交替序列，该序列说明从起点出发乘坐何线路， 可以直接到达目标点，或途中如何换乘，到达终点。在大部分的城市公交网络模 型中，公交线路的选择通常受到以下几个因素的作用：

(1)换乘次数：是指乘客在完成一次出行过程中所换公交车的次数；

(2)出行距离：则包括车上距离和车外距离，车外距离指的是乘客为了乘车 而步行的距离；

(3)出行耗时：指乘客在一次出行过程中所需的时间，它也包括车上和车外 部分，车外耗时除了在车外距离部分所耗的时间外还包括在车站等车的时间；

(4)出行费用：指的是乘客在完成一次出行过程中所花的车费。 不同乘客对于各项因素的要求都是不同的。经调查，表明大多数乘客在选择公交 线路出行时, 首先考虑的是乘车是否方便, 就换乘次数而言, 一般不大于两次；

4

其次是乘车所花费的时间是否最少， 由于各相邻站点间的行驶时间是相同的， 所以存在直达线路时，时间主要是通过公交线路的站点来衡量, 站点越少越好。 同时，由于换乘耗时的存在，当不存在直达线路时，要求换乘次数越少越好。因 此, 将“换乘次数最少”和“沿途站点最少”这两点作为设计最短路径数学模型 的优化目标。

3 仅考虑公汽线路时的最佳路线选择

根据人们的出行习惯，首先，看 A 站是否有公交车直接到 B 站。如果有一 条或多条直达公交线路，则从中优先输出线路距离最短的公交车，如图（1（a））。 如果没有，则看经过 A 站的公交车和经过 B 站的公交车有没有交叉点，若有交 叉点 C，则选择在交叉点 C 转车到达 B 站，如图（1（b））。如果经过 A 站的公 交车和经过 B 站的公交车没有交叉点，则先乘经过 A 站的某一路公交车到达某 一站 C，看经过 C 站的公交车与经过 B 站的公交车有没有交叉点 D，若有，则 在 D 站转车到达 B 站，如图（1（c））。另外，有可能存在多种两次换乘的方案， 如图（1（d））所示。此时，需要判断哪种方案距离最短，然后优先输出距离最 短方案。如果经过 C 站的公交车与经过 B 站的公交车没有交叉点，说明经过两 次换乘还不能从 A 站到达 B 站，则需要三次换乘或三次以上才可到达目的地。 考虑到方案的实用性，我们认为转乘超过两次，即为失败方案，则停止搜索。

C B

B A （b） C A D B E （d）

F

A （a）

C A

D B （c）

图 1 公交线路换乘示意图

4 同时考虑公汽与地铁线路的最佳路线选择 在问题一条件的基础上，加入了地

铁的线路信息，虽然我们已经通过 matlab 将最优结果已经计算出来了，我们原以为只要将地铁的线路信息加到问题一的模 型和程序中，就可以计算出结果，但由于地铁线路信息的数据结构与公汽线路信 息的数据结构并不兼容，因此很难利用问题一的程序将起实现。为此，我们将地 铁线路图绘制出来后，发现可以利用网络拓扑和图论的相关知识进行求解，来得 出结果。

5 考虑步行时间的公汽、地铁最佳路线选择

第一种方案：由于 Dijkstra 算法本身虽然是计算最短路径的最优算法，但当 我们的网络比较大时，其处理的速度则大大降低，我们通过改进 Dijkstra 算法， 以换乘次数最少为主要目标，同时将路径进行优化，以实现我们的目标。

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2007优秀论文 - 图文在线全文阅读。