2007优秀论文 - 图文(2)

另一种方案是为了我们问题计算的方便性，同时是我们建立的目标函数的可 操作性，我们引入路段阻抗的思想，将我们的最小换乘次数最优通过相应惩罚因 子的处理转换为时间最优，来构造我们的目标函数。

6

5.1 问题一

五、 模型的建立与算法的实现

1、数据的预处理：

首先将文本附件（1.1 公汽线路信息）导入到 Excel 中，并筛去线路中上行 或下行为空的信息。

其次对于只有上行或下行的，将已有行反向复制成对应的下行或上行；对于 环线的，其上行与下行的数据信息相同。

第三步，将 Excel 已经处理好的数据导入 matlab，并将其组织为结构体数组 的形式，其数据结构如下：

bus{i} name style plat1 plat2 其中，bus{i}表示第 i 条公汽线路；

bus{i}.name 表示第 i 条公汽线路的名称； bus{i}.style 表示第 i 条公汽线路的计费方式； bus{i}.plat1 表示第 i 条公汽线路的上行站台列表； bus{i}.plat2 表示第 i 条公汽线路的下行站台列表。 data1 为 Excel 的导入数据，将其化为结构体细胞数组的程序为：

p={1,2080}; for i=1:2080

p{i} = cell2mat(data1(i,:)); end

bus={1,520}; for i=1:520

bus{i} = struct('name', p{4*(i-1)+1}, 'style',

p{4*(i-1)+2}, 'plat1', p{4*(i-1)+3},'plat2',p{4*(i-1)+4}); end

2、基于广度优先的公交换乘搜索算法 第一步：输人

乘车的起始站点 A 和目的站点 B。 第二步：经过起始站点 A 的公交线路存为 X(i) (i=1,2,3?m,m 为正整数)。经 过目的站点 B 的公交线路 Y(j) (j=1,2,3?n,n 为正整数)。

第三步：判断是否有 X(i)=Y(j)，将满足条件的存入 Z。若只有一条线路满足 要求，则该路线即为最优路线，输出结果；若有几条路线满足要求，则从这几条 线路里找出最优路线，并将几条路线由优等到次等排序输出。

第四步：将公交线路 X(i)所包含的公交站点存为公交换乘矩阵 O(i,u)(u=1,2,3,?,p,p 为正整数)，公交线路 Y(j)中所包含的站点存为公交换乘矩阵 P(j,v)(v=1,2,3,?,h,h 为正整数)。

第五步:判断是否有 O(i,u)= P(j,v)，将满足条件的存人 W，若有一个站点满 足要求，该站点即为一次换乘的转站点。从 A 站点出发，在该站点换乘即可以 到达 B 点。如有几个站点满足要求，则先分别求出每一个站点的距离最短的换 乘方案，然后比较各换乘方案的距离，选择所有方案中距离最短的换乘方案即为

7

最优线路，输出结果。

第六步：将经过站点 O(i,u)的公交线路存为 R(k) (k=1,2,3,?,p,p 为正整数)。 公交线路 R(k)所包含的站点 G(k,t) (t=1,2,3,?,g,g 为正整数)扩充到公交换乘矩阵 O(i,u)中。

第七步：判断是否有 G(k,t) = P(j,v)，将满足条件的存人 W，若 W 非空，则 站点 G(k,t)即 P(j,v)为从站点 A 到站点 B 的二次换乘站点，公交线路 X(i)，R(k)， Y(j)为换乘二次的最优路线，输出结果并结束运算。

第八步：设定换乘次数的上界 N，然后可在不大于 N 次换乘的某次循环中 找到可行路径，若可行路径有多条，考虑综合因素最高的为最优路径并输出。

以上步骤如果没有找到合适的公交线路，则输出“没有找到换乘次数不超过 N 次的最优换乘方案”，结束运算。 3、算法的改进：

上述方法的局限性是：在 a 到 b 与 b 到 a 的站点相同的时候是正确的，没有 考虑上行线与下行线不同的情况，如果在 a 到 b 与 b 到 a 的站点不完全相同时， 上述算法就不适用了，所以我们的方法时，考虑上行线和下行线可能不同的情况， 这样得到从 a 到 b 的一次换乘线路有 4 种类型（c 为中间站点）：

1) a 到 c 走上行线，c 到 b 走上行线；查找函数为（见附录）：

[n1,m1,m,n2,m2]=ff2(bus,a,b)

查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换乘站点， n2 为换乘车次(上行)。

2) a 到 c 走上行线，c 到 b 走下行线；查找函数为：

[n1,m1,m,n2,m2]=ff3(bus,a,b)

查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换乘站点， n2 为换乘车次(下行)。

3) a 到 c 走下行线，c 到 b 走上行线；查找函数为：

n1,m1,m,n2,m2]=ff4(bus,a,b)

查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换乘站点， n2 为换乘车次(上行)。

4) a 到 c 走下行线，c 到 b 走下行线；查找函数为：

[n1,m1,m,n2,m2]=ff5(bus,a,b)

查找 a,b 的所有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换乘站点， n2 为换乘车次(下行)。 这样能得到所有 a 到 b 的一次换乘线路。 4、6 对起始站与终点站最佳路线的结果

通过以上的改进算法，利用 matlab 运行所编写的程序，主要的实现函数及 其的功能如下： m=isup(bus,s1,s2) %判断 s1，s2 站点是否在同一个上行公交线路,如果有则返回线路的序号,其中 s1 为起点。

m=isdown(bus,s1,s2) %判断 s1，s2 站点是否在同一个下行公交线路,如果有则返回线路的序号,其中 s1 为起点。

[n1,m1,m,n2,m2]=ff2(bus,a,b) %查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换

8

乘站点，n2 为换乘车次(上行)。 [n1,m1,m,n2,m2]=ff3(bus,a,b) %查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(上行)，m 为换 乘站点，n2 为换乘车次(下行)。 [n1,m1,m,n2,m2]=ff4(bus,a,b) %查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换 乘站点，n2 为换乘车次(上行)。 [n1,m1,m,n2,m2]=ff5(bus,a,b) %查看站点 a,b 是否有一次换乘的线路，返回值中 n1 为乘坐车次(下行)，m 为换 乘站点，n2 为换乘车次(下行)。 d=dis(bus,line,s1,s2)

%计算同一线路中两站点的距离,其中 s1,s2 分别为起终站点，line 为线路编号。

根据我们的算法得到我们的结果：6 对站点中没有直达的线路，那么我们再 考虑换乘一次能到达目的站点，如果不行再考虑换乘二次，对于二次换乘以上的， 考虑乘客的满意度，我们不做考虑。除了第 2 对和第 5 对需要换乘两次之外，其 余 4 对均可通过换乘一次到达目的站点。

最佳路线如下： 转乘次数 最短时间 费用 (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

关于最佳路线更详细的信息见表 1 到表 6：

表 1 起始站 S3359→目标站 S1828

序号 1 2 3 4 5

路线一 L436 L436 L436 L436 L436 转站点 S1784 S1784 S1241 S1241 S3695 路线二 L167 L217 L167 L217 L217 耗时 106 106 112 112 118 费用 3 3 3 3 3 表 3 起始站 S0971→目标站 S0485

序号 1 2 3 4 5 路线一 L13 L13 L13 L13 L13 转站点 S2184 S992 S2322 S1770 S1789 路线二 L417 L417 L417 L417 L417 耗时 128 131 134 134 134 费用 3 3 3 3 3 9

表 4 起始站 S0008→目标站 S0073

序号 1 2 3 5 5

路线一 L159 L159 L159 L159 L159 转站点 S400 S2633 S3053 S2683 S291 路线二 L474 L474 L474 L58 L58 耗时 83 83 83 83 83 费用 2 2 2 2 2 表 6 起始站 S0087→目标站 S3676

序号 1 2

线路一 L454 L454 转站点 S3496 S1893 线路二 L209 L209 耗时 65 71 费用 2 2

表 2 起始站 S1557→目标站 S0481（需要转乘两次）：

序号 1 2 3 4 5

线路一 L84 L84 L84 L84 L363 转站点一 S1919 S1919 S1919 S1919 S1919 线路二 L417 L417 L417 L417 L417 转站点二 S2424 S2424 S2424 S2424 S2424 线路三 L254 L312 L447 L516 L254 耗时 112 112 112 112 112 费用 3 3 3 3 3 序号 1 2 3 4 5 路线一 L308 L308 L24 L24 L24 表 5 起始站 S0148→目标站 S0485 转站点一 路线二 转站点二 路线三 S36 S36 S345 S1487 S345 L156 L157 L140 L378 L140 S2210 S2480 S2654 S2023 S2654 L417 L417 L469 L469 L104 耗时 117 120 132 135 141 费用 17 3 8 6 8 5.2 问题二

5.2.1 模型的建立： 由附件中的地铁线路信息，可以画出其对应的线路示意图

B C

A(D01) D12 D18 D（D23）

E

图 2 地铁线路示意图

F

模型假设：

10

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