基于Floyd算法的城市交通最优路线问题的研究.docx

摘要:现如今城市交通问题与居民生活和城市经济具有紧密的联系，建立以交通网络为基础的交通优化模型十分重要。到目前为止，最优路线的方法有很多，其主要代表是Dijkstra算法，Floyd算法，Bellman算法。但这些算法只能够解决单权最短路径问题，实际上大部分交通最优化问题是多权交通优化问题。为此，本文基于现有的Floyd算法，经过改进后得到一种多维Floyd算法。

首先，本文对最佳路线以及最佳路线评价指标进行了定义和量化。最佳路线就是指从出发点选择最优的路线或者方案来到达终点。然后，本文提出了Floyd算法。该算法就是求任意两点之间的最短路径，从图的带权领接矩阵出发，对其进行最短路径的搜索。然而Floyd算法过程中也存在着运算量大、繁琐等问题，因此本文对Floyd算法进行了改进。并且运用改进的Floyd算法，分析解决了北京市6对站点之间的最优路线（仅考虑公交路线），得到了这6对站点的最优路线。

其次，由于Floyd算法只是针对单一的交通工具，而现实中的换乘问题也含有多种交通工具，因此本文又提出了一种多维Floyd算法来解决此类问题。并且运用多维Floyd算法建立了数学模型，对同时考虑公交和地铁的换乘问题以及任意两站点之间的最优路线进行了分析求解，得出了问题的最优路线。

关键词 最优路线；Dijkstra算法；Floyd算法；多维Floyd算法

目录

摘要

Abstract

1 绪论-1

1.1 论文研究背景及意义-1

1.2 研究现状-1

1.3 研究内容-1

1.4 本文的主要进程-2

2 最佳路线和最佳路线的评价标准-3

2.1 最佳路线的定义及评价指标-3

2.2 最佳路线评价指标的量化-3

2.2.1 最短出行线路的量化-3

2.2.2 最少转乘的量化-3

2.2.3 最低票价的量化-4

3 Floyd算法-5

3.1 Floyd算法的基本思想-5

3.2 Floyd算法构造距离矩阵的原理-5

3.2.1 Floyd算法步骤-6

3.2.2 查找最短路路径的方法-6

3.2.3 Floyd算法存在的问题-6

3.3 Floyd算法的改进-7

3.3.1 改进Floyd算法原理-7

3.3.2 改进Floyd算法的计算步骤-7

4 多维Floyd算法-8

4.1 算法的基本思想-8

4.1.1 构造赋权有向图D-8

4.1.2 构造路由矩阵T-9

4.1.3 构造统计矩阵S-9

4.1.4 迭代过程-10

4.2 算法的基本步骤-11

5 Dijkstra算法-13

5.1 Dijkstra算法原理-13

5.2 Dijkstra算法的基本步骤-13

5.3 Dijkstra算法与Floyd算法的比较-14

6 基于多维Floyd算法的城市交通路线优化问题-15

6.1 问题的提出-15

6.2 问题一的分析、求解以及结果-16

6.2.1 问题一的分析-16

6.2.2 问题一的求解-17

6.2.3 问题一的公交换乘最优路线-18

6.3 问题二的分析、求解和结果-20

6.3.1 问题二的分析-20

6.3.2 问题二的求解-21

6.3.3 问题二的最优路线-22

6.4 问题三的分析、求解和结果-22

6.4.1 问题三的分析-22

6.4.2 问题三的求解-23

6.4.3 问题三的最优线路-24

结论-25

致谢-26

参考文献-27

附录-28