2007优秀论文 - 图文(3)

1、我们只考虑线路最短为主要目标； 2、此线路图形处在整个城市的中间位置；

3、图形以内的任意两站点，不考虑换乘的情况； 5.2.2 模型实现算法：

第一步：将每个站点看作图形中的一个点，将处在多边形 ABCDEF 中（包 括线段上）的所有站点存入集合 V 中，即：

V = {vij | v 存在于多边形ABCDEF之中} ij 第二步：对于要求的任意两点 a、b 之间的线路,

a) 首先判断 a、b 是否属于集合 V，如果 a、b 两点同时属于集合 V，那么 我们就无需考虑换乘的情况，只要利用问题一中的求解算法找出它们之间的线路 信息；

b) 如果 a 属于集合 V，而 b 不属于集合 V，那么找出从 a 到最近的地铁站 点 c 的线路信息，找出从 b 到最近的地铁站点 d 的线路信息，那么 c、d 之间的 地铁线路也就相应的得到了，综合几条线路即可得出线路信息；

c) 如果 b 属于集合 V，而 a 不属于集合 V，那么找出从 a 到最近的地铁站 点 e 的线路信息，找出从 b 到最近的地铁站点 f 的线路信息，那么 e、f 之间的地 铁线路也就相应的得到了，综合几条线路即可得出线路信息；

d) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线没有交点，那么此问题就可以利用问题一中的算法求出最短线 路信息；

e) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 1 个交点时，同样无需考虑换乘地铁，求解算法与 d)相同；

f) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 2 个交点时且连线处于 AD 之上，我们也可以得出无需考虑 换乘地铁，求解算法与 d)相同；

g) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 2 个交点时且连线处于 AD 之下，那么我们就要求解与 a、b 最 近的地铁站点和地铁站点之间的线路信息最短；

h) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 3 个交点时且没有超过 BC 边与 EF 边，可以算出同样无需换 乘地铁，计算它们之间的最短线路信息；

i) 如果 a 不属于集合 V，b 也不属于集合 V，同时 a 与 b 的连线与多边形 ABCDEF 的实线有 3 个交点时且没有超过 BC 边，但超出了 EF 边，那么就要考 虑换乘地铁，算法同 g)；

j) 其它情况不做考虑，算法结束。 5.3 问题三

5.3.1、 路径优化准则与行程时间描述 方案的可行性主要体现在乘客对其满意

度，主要有两种表现形式：一种是总

出行时间，另一种是乘客的出行总成本。目前乘客满意度中的两种形式，可以利 用乘客的时间价值研究成果进行统一处理。在此为研究的方便，将主要考虑用公 交路径行程时间（包括步行时间、等车时间及车间时间）作为乘客满意度的度量。 通过对公交乘客出行心理的调查研究，说明了出行者选用换乘次数最少作为首要

11

优化目标，以出行耗时最少为第二重要因素，而出行距离最短为第三重要因素。

以上结论是对普通市民的出行进行调查得到的结果，是一般出行者对公交网 络性能信息掌握不全面情况下而做出的择路要素排序。但是如果从公交查询服务 的角度来看，以出行耗时最少（耗时中包括出行费用的转化时间）为第一优化目 标，以换乘次数最少为第二重要因素为宜。 某条公交路径的行程时间，是历经

该公交路径所花费的时间。典型的公交路

径行程时间包括从站点的等车时间、上车时间、行车时间（一般指车辆的行驶时 间）、转乘时间、最后离开公交车线网的下车时间。这其中，转乘时间可进一步 细划分为下车时间、改变乘车点的步行时间、等车时间及上车时间。

公交网络初始时间矩阵Tn×n 定义为： ?0, i = j

?'

t = min{t d/ d , t },当i ≠j, 且i到j有m条车线经过（3）? ij k ij k ij

?? ∞，其他

式中： m —— 车线条数，m≥1；

tk —— 车线 k 的车辆全线行驶时间； dk —— 线路k的全线距离；

dij —— i到j的实际距离,i与 j ∈ V (G )

当车线为环线时,上面的公式要相应作出调整。同时，定义Qn×n 为对应与Tn×n 选择

车线矩阵为：

? 0, i = j

? '

q 是满足 min{t dij / d t 的k 值k k , ij }ij ?k ', k '

?

? ∞ , 其他

针对每一个 Ri 设立一个票价函数：

' v'为单一票价） ?1， 0 < u ' ≤ 20或v（

? ， 20 < u ' ≤ 40 C = f (R ) =（4） Ri i ?2

?3， u ' ≥ 4（0 u ' 表示途经站点数）?

同时建立公交网络的换乘步行时间矩阵 H n×n 为：

?0, i = j ?

hij = ?tij ,当i ≠ （5） ?∞, 其他 ?

i 到 j 的步行时间； 式中： tij —— 从

由于实际问题的复杂性，可以先选择一个长度 Ln 做半径，以i点为圆心作圆， 将该圆覆盖区域内的公交站点设为i点的待定转乘站点，其构成集合O R。然后求

d < R 判断j是否为选定转乘站点。所有选定的转乘站点构 d ( j ∈ OL R ) ，并用式

成集合Oi 。显然Oi至少包含元素i。

利用票价函数以及Qn×n 即可确定一个与Tn×n 对应的 n 阶方阵Cn×n ，其元素 cij表示从 i 到 j 沿 qij 线乘车的票价时间值。

' ij

' ij

L

j

设公交网络中有NR 条不同的车线, 各个车线的发车间隔时间可以分别用

12

t f1 ,t f2 ,L , t fNR 。考虑到发车间隔的确定性和乘客出行到达某站点的随机性，本

文采用t f i /2 为在某站点选乘第i条车线的等车时间。

5.3.2、 公交网络最优路径求解思路和步骤 新算法的求解过程可分为两个阶段。第一阶段分别求解与起始区域 r 以及终 止区域 s 以步行边相接的公交站点集合 Or 与 Os 。判断 Or Os 是否非空。如果 I

Or I Os 非空，即有公共点存在，说明 r 与 s 间有步行边相接，可求解 r 与 s 间的 行程时间。如果Or I Os 为空集，则进入第二阶段求解。依次取Or 中的点，求其 与Os 中各点的最短行程时间和最优公交路径。结合与Or 及Os 中各点所对应的已 记录的步行边行程时间，即可求出 r 与 s 间的最优公交路径、最短行程时间和换 乘次数。

求解的具体步骤如下： a．给定 R 值，建立初始化的步行时间矩阵 H n×n 。建立包含等车时间的初始 时间矩阵T 0 为：

? 0，i = j t o =? / 2 + t d/ d )，当i ≠j且i到j有m条车线经过

min (t ? ij f k ij k

?l ≤ k ≤ m

k

n×n

（6）

∞ ，其他

n×n

同时建立与T 0n ×n对应的矩阵Qn ×n 。按照给定的票价函数及Q 建立换乘票价时间 的 n 阶方阵Cn×n 。

b．求解与起始区域 r 相接的公交站点集Or ，记 Or = n r ；求解与终止区域 s 以步行边相接的公交站点集Os ，记 Os = ns 。如果Or I Os ≠ ?(?表示空集），记

k

Or I Os = nrs ，Ors ∈ (Or I Os )，k = 1, 2,L , nrs )，求 r 到 s 经Ors 的两条步行边行程

k

时间之和 R

? krs

t ，可得

? 1 rs

, t , L, t

? 2

rs

? n rs

r s

，取其中最小者为trs （r 与 s 间

最短行程时间），并可得相应的路径 (r ≠ s)。如果 Or I Os = ? ，则转下一步。

i

c.依次取出Or 中的公交站点Or 表示Or 中的第 i 个元素。按以下步骤求该点与Os 中各站点间的最短行程时间、最优公交路径以及对应的换乘次数。

(a) 建立 ns 维的数组 F 与Gt （置数组 F 元素初始值为∞，置数组Gt 元素初 始值为 0）。F 记录最短行程时间，Gt 记录路径的换乘次数。建立 V (G) 个 20 维

j

的数组 R ≤ j ≤ n, 置数组元素初始值为0) 。这里的 20 维表示最多可以换乘 5 次， p (1

可作相应调整。建立 n 维数组 D（置数组元素初始值为 0）。D 中元素值表示所 选公交站点到对应的各站点的最优路径行程时间的判断结果，0 表示未达到有限 值，1 表示已达到非∞的值，2 表示已得到最优路径。

j

(b) 依次取O s 中的元素O s 表示O j 个元素，1 ≤ j ≤ n s。 s 中的第 按以下步骤求 解Oi 与 V(G)中各点 v 的最优公交路径、换乘次数及总的行程时间。

r k

t ①首先在T 0 中找出

n×n

0

i

O r v k

的值t 0 。如果t 0 < ∞ ，则说明Oi 与 之间有公交

13 vr k

线直达，行程时间记为t0 。数组 D 中与 vk 对应的元素 Dk 记为 1。令

14

i j qor os

中的车线。同时如果 ∈ O 。则作如下改 t 0 对应的 Qvn×n k s 其中 为与中 = t 0 , G = 0 ， 点对应的数组 变： Fk F vkF 与 Gt 中的元素。 k k 与Gk 分别表示与

Tn0×n

RpOk = (r,O, qoo , O , s, 0, 0,L, 0)

r

vk

i

r i j r s j s

i j

②如果t 0 = ∞ ，则说明Or 如果 j = V (G) ，则令 N=0， 与Os 之间无直达公交线。转步骤③；否则取 j=j+1，转步骤①。 ③依次取 D 中的元素 D j 先判断，后依不同情况分别进行计算。当 D j = 0 时

i N i + t0 (m, j) + c ] t N +1 (or , j) = min [t (o, k) + hmj r km Ni

k∈W i .m∈ok

Or

(8)

当式(8)的值小于∞时,令 D j = 1 ；建立新的

j

, j, 0, 0,L , 0) i R R pOi 为 i 以前值的末尾添加(r, O,L, k , m, q，划线处为对原 r mj pO

r

k

的元素。

N +1 i N +1

当 j ∈ Os 时， Fj = t(Or , j)，G j = N + 1。当 D j = 1 时，仍按式(8)计算t 。

i R pO i 为 k , m, qmj , j, 0, 0,L , 0) 划线 如果t N +1 < Fj ，则令 D j = 2 。建立新的 (r, Or ,L , r

r

j

k

R 处为对原 p O

ir

以前值的末尾添加的元素。

N +1 i = N + 1。如果t N +1 ≥ F ，则令 当 j ∈Os 时： F (Or , j)，Gj D = 2 。 j = t j j

当 D j = 2 时，取下一个 D j +1 进行如上的新的判断与计算，直到 j = V (G) 。

④检查 D 中与Os 中的点对应的值是否均为 2。如果有 0，1 存在，则令 N=N+1，

转步骤如果对应值均为 2,则转步骤③。这里的判定原则是建立在公交网络 G 连 通的假设之上。

B min

。得到OO ⑤求 F1 中的最小值 Fmin ，记录对应 Fmin 的站点 s

i

R 径为

s

i 最短行程时间为 F mi n 转步骤 c，直到取遍Or 中的所有元素。 pO r

r

到 s 的最优路

d．利用步骤 c 中求出的Or 中各点至 s 的最优路径、最短行程时间、换乘次

数，可以最终求出 r 到 s 的最优路径、最短行程时间及换乘次数。

在上述计算过程中，当出现满足式(7)或式(8)的 k 有几个不同值时，可能会 出现多条最优路径。处理的办法是相应增加对应的路径记录数组 Rp 的个数，以 记录多条路径。同时，上述计算步骤也可以稍加修改，求解单起点多终点的公交 网络最优路径。

5.3.3 基于阻抗时间最短的最优选择模型

1、公交网络换乘类型分析 两条公交线路间的换乘按照换乘站点重合程度的不

同，可以分为同站换乘与

步行换乘两种。结合两线路位置关系的特点，又可进一步划分为下列四种类型：

a)同站换乘类型 1(见图 3（a）)： 两条公交线路相交于一点,并在该点同时存在公交站点,乘客可在此站点进行 直接换乘；

15

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