最短路径算法在物流运输中的应用.doc

本科生毕业设计（论文）

题 目： 线性表的设计和实现
学生姓名： 张三
学 号： 201107011153
院 系： 基础科学学院信息技术系
专业年级： 2012级信息与计算科学专业
指导教师： 李四 　

注：1.论文封面单独打印一张纸；中英文摘要正反打印一张纸；目录、正文、参考文献、致谢、附录均独立正反打印！
2.部分专业对格式有特殊要求的，教学院（系）可自行商定。
年 月 日

摘 要

随着现代物流业的发展，如何优化和配置物流的运输路径成为了一个热点的问题。其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径，使其距离最短。为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法，分析了它们的适用范围以及时间复杂度。最后，对一个具体的航空公司物流配送问题进行了求解，得到了理论最优路径。

关键词：最短路径问题；DIJKSTRA算法；物流运输
ABSTRACT

With the development of modern logistics industry, how to optimize and configure the transport path of logistics has become a hot issue. Among them, the most representative problem is how to select the appropriate path between two points in a road network to minimize the distance. In order to solve this problem, this paper introduces two most common shortest path solutions — — Dijkstra algorithm and Floyd algorithm, and analyzes their application range and time complexity. Finally, a specific airline logistics distribution problem is solved, and the theoretical optimal path is obtained.

Keywords：Minimum path problem；Dijkstra algorithm；Logistics transportation
目 录

第一章 引言 1
1.1 研究背景 1
1.2 研究现状 1
1.2.1 最短路径算法研究现状 1
1.2.2 最短路径算法分类 2
第二章 最短路径问题的基本理论知识 3
2.1 最短路问题的定义 3
2.2 最短路问题的Dijkstra算法 3
2.2.1 Dijkstra算法的局限性 3
2.2.2 Dijkstra算法求解步骤 3
2.2.3 Dijkstra算法的时间复杂度 4
2.2.4 简单案例分析 4
2.3 最短路问题的Floyd算法 5
2.3.1算法定义 5
2.3.2 算法思想原理 5
2.3.3 算法过程描述 6
2.3.4 算法适用范围 6
2.3.5 算法简单实例 6
第三章 实际案例分析 7
3.1 问题描述 7
3.1.1 问题的背景及假设 7
3.1.2 符号说明 7
3.2 模型的建立与求解 8
3.2.1 模型一 8
3.2.2 模型二 10
第四章 总结 15
4.1 优点 15
4.2 缺点 15
参考文献 16
致 谢 17
附 录 18
附录A 实际案例背景数据 18

第一章 引言

1.1 研究背景
在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。

1.2 研究现状

本节主要讨论两个方面的问题，首先简要回顾最短路径算法研究现状，然后概要总结最短路径算法分类。
1.2.1 最短路径算法研究现状
最短路径问题一直是计算机科学、运筹学、地理信息科学等学科领域的研究热点。国内外大量专家学者对此问题进行了深入研究。
经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。常用的路径规划方法有:平行最短路径搜索算法，蚁群算法，基于矩阵负载平衡的启发算法, EBSP*算法和Dijkstra算法等。创门在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色但是因为Dijkstra算法可以给出最可靠的最短路径，并且容易实现，所以备受青睐和并被广泛应用。
经典的Dijkstra算法的时间复杂度为，直接应用到大规模城市路网时，最短路径查询时间难以令人接受，专家学者纷纷开展Dij kstra优化算法研究，概括起来，以往研究者主要是从5个方面对最短路径算法进行性能优化：(1)基于数据存储结构的优化，以空间换取时间；( 2 )基于路网规模控制的优化；(3)基于搜索策略的优化；( 4 )优先级队列结构的优化；( 5 )基于双向搜索的并行计算优化。
1.2.2 最短路径算法分类
由于问题类型、网络特性的不同，最短路径算法也表现出多样性。
(1) 按照最短路径问题分类，最短路径问题通常可分为2个基本类型：一是单源最短路径问题，即查找某一源点到其余各点的最短路径；另一类是查找某个节点对之间的最短路径。
最短路径问题具体可细分为以下几种，单源最短路径问题，单对节点间最短路径、所有节点间最短路径、k则最短路径、实时最短路径、指定必经节点的最短路径以及前N条最短路径问题等，本文的研究范畴属于单对节点间最短路径问题。
(2) 按照网络类型和表示方法分类，网络可以分为稀疏网络和非稀疏网络，常用的表示方法有邻接矩阵和邻接表。
邻接矩阵方法能够在时间内查询到任意两个节点之间是否有一条边，它的空间复杂度为。现实生活中网络节点往往很多，动辄上万，而且是稀疏网络居多，比如城市路网，所以用邻接矩阵表示既不现实，又浪费空间。
邻接表是另一种存储网络拓扑的数据结构，它是一种链式存储结构，对于交通网络等稀疏图，采用邻接表数据结构存储网络拓扑数据空间复杂度仅为，不存在存储空间的浪费。邻接表数据结构已被证明是网络表达中最有效率的数据结构，在最短路径算法中得到了广泛应用。

第二章 最短路径问题的基本理论知识

2.1 最短路问题的定义
最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题。
2.2 最短路问题的Dijkstra算法
2.2.1 Dijkstra算法的局限性
在了解和使用某种算法之前，我们先要明白这种算法有怎样的局限性。只有深入理解来每一种算法的局限性，才能根据具体的问题选择合适的算法来求解。
Dijkstra算法最大的局限性在于不能够处理带有负边的图，即图中任意两点之间的权值必须非负。如果某张图中存在长度为负数的边，那么Dijkstra算法将不再适用，需要寻找其他算法求解。
2.2.2 Dijkstra算法求解步骤
(1) 先给图中的点进行编号，确定起点的编号。
(2) 得到图的构成，写出图的矩阵

(3) 根据要求求出发点S到终点E的最短距离，那么需要从当前没被访问过的结点集合中找到一个距离已经标记的点的集合中的最短距离，得到这个顶点；
(4) 利用这个顶点来松弛其它和它相连的顶点距离S的值
(5) 重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S到其它任意点的最短距离。
2.2.3 Dijkstra算法的时间复杂度
我们可以用大符号将Dijkstra算法的时间复杂度表示成边数m与顶点数n的函数。 
Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q，因此搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素，据此我们可以知道算法的时间复杂度是。 
对于边数少于n2稀疏图而言，我们可以用邻接表来更有效的实现Dijkstra算法。为了达到这一目的，需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点(Extract-Min)。当用到二叉堆的时候，算法所需的时间为，斐波纳契堆能稍微提高一些性能，使得算法运行时间达到。
2.2.4 简单案例分析
给出对应的结点之间的关系（表2-1为对应的结点之间的关系）

长度
A
B
C
D
E
A
0
2
15
10
10
B
2
0
11
1
5
C
15
11
1
20
7
D
10
10
20
0
3
E
10
5
7
3
0
表2-1
需要注意的是，其中（A,B）= 2 表示结点A到B 的长度为2
第一步：进行编号，假定A点即为起点。
第二步：得到图

第三步：首先从起点A开始找到距离A最近的点，那就是A点了；
第四步：把A点标记到已经用过的的集合用A来更新其它点到起点的距离得到的集合

表示起点到B,C,D,E的距离分别为2,15,10,10
第五步：重复上述步骤：得到
,,
继续重复上述步骤，最后的到,,得到的 ，
即最短路求解完毕。
2.3 最短路问题的Floyd算法
2.3.1算法定义
除了Dijkstra算法，另外一种简单的最短路算法是floyd算法，它也经常被用于解决含有有向图或者是负权的最短路径问题，并且能够用于计算有向图的传递闭包。该算法的时间复杂度为，空间复杂度为。
2.3.2 算法思想原理
Floyd算法是非常常见的使用动态规划来寻找最优路径的算法。如果我们用简单的语言解释，总体要实现的目标是找到从点i到点j的最短路径。如果我们换一个角度，从动态规划的角度观察，那就必须得要对这个目标进行一个重新的诠释。
从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。
2.3.3 算法过程描述
（1）从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　
（2）对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短，如果是的话需要更新它。
2.3.4 算法适用范围
⑴ 无向图最短路问题； 
⑵ 稠密图效果最佳； 
⑶ 边权可正可负。
2.3.5 算法简单实例

图3-2 无向图

根据图3-2，用Floyd算法找出任意两点的最短路径步骤如下表3-2：

distk[1]
distk[2]
distk[3]
MIN
A->B
1
3
7
1
A->C
1
3
5
*
1
A->D
3
3
5
3
B->C
2
2
6
2
B->D
*
4
4
*
4
C->D
2
4
6
2
表3-2 Floyd算法步骤流程
第三章 实际案例分析

3.1 问题描述
3.1.1 问题的背景及假设
网上购物一直是常见的消费方式，其依托于物流业逐渐蓬勃发展，每个送货人员都需要以最快的速度送货，而且往往会发送多个地方，所以有必要设计耗时最小的路线。
现在考虑一个快递公司，总部在地图上的O点，派送人员需要将货物发往城市很多，如何设计交货方案，以便花费最少的时间。物流地图如图1所示，下表中显示了每个点的信息，假设托运人只能沿着这些连接的线行进，而不采取任何其他路线。
（1）最大承载能力为50公斤，货量最大为1立方米。
（2）调度员的平均速度为24公里/小时。假设每件货物要交出需要3分钟，为了简单起见，在同一地点有几件商品，这些货物只需每3分钟一次交割即可。
现在派送者将向50个地点发送100件货物。问题要求如下：
1. 假设货物从1到30到指定地点并返回。设计最快的路线和方式来求出结果。要求标记送货线路。
2. 假设送货人员从上午8点开始交货，1到30天货物交货时间不能超过规定的时间，请设计最快的路线和方式。要求标记送货线。
具体数据请参见附录。
3.1.2 符号说明
所载货物的质量总和；
所载货物的体积总和；
第i件货物的质量；
第i件货物的体积；
从i点到j点的距离权值；
任意两节点之间最短路径距离矩阵；

3.2 模型的建立与求解
3.2.1 模型一
我们首先对题中所给的数据进行汇总分析，得出=48.5公斤，V30==0.88立方米，所以均未超出送货员的载重，所以送货员可以一次性将货物送完。而题中数据显示送货员需到达的节点数位22个（包括出发点O）如下表

0
13
14
16
17
18
21
23
24
26
27
31
32
34
36
38
39
40
42
43
45
49
表3-1 节点数
利用程序用Floyd算法我们可以得出任意两点之间最短路径的距离矩阵其中（i,j=1…22），
（1）先根据题目数据给初始矩阵赋值，其中没有给出距离的赋inf，以便于更新。
（2）进行迭代计算。对任意两点，若存在，使，则更新。
（3）直到所有点的距离不再更新停止计算。则得到最短路距离矩阵 。由旅行售货员问题(TSP)建立矩阵,；其中表示点i到点j的距离权值。d为对称矩阵，令=0。现求节点0到各节点再到节点0的最短距离，要求各线路上的权值最小。设立变量, 其关系如下:
当节点和节点连通，=1；当节点和节点不连通，=0；目标函数为寻找一条从起点0到各节点再到节点0的最短距离，要求各线路上的权值和最小，故目标函数为：最短路径
（3-1）
（1） 对起始点0至少有一条路径出去，故有
（3-2）
（2） 对其余各节点，恰有一条路径进去，故有
（3-3）
（3） 所有节点不出现闭合回路，约束为；
总的线性规划模型为：
（3-4）
(1)
(2)
约束条件s.t. (3)
(4)
利用lingo软件编程算出在各约束条件下的最短路径距离、最短路径所经过的各节点的顺序得：
最短距离 .
最短时间
各节点行进路线为：
0→26→27→39→36→38→43→42→49→45→40→34→24→13→18→14→16→32→23→17→21→0

图3-1 节点路线表

3.2.2 模型二
问题2题目增加了时间约束，所以我们需要在模型一的基础上进行改进。送货员从早上8:00出发，需要分别在9:00、9：30、10：15、12:00之前件货物送到各指定点。根据“时间要求越早，先送的原则”，将22个节点按时间限制划分为四个区域，然后分阶段依次解决各区域的最短路径，得出各出发点和各终点。从而得出总距离最短路径。
首先我们在图中描出各节点坐标，找到各节点位置。如下图：

图3-2 节点位置表

阶段1：要求9:00送到：
限制在此时间段的节点为三个：13、18、24，送货员8:00从O点出发，需选择最短路径在9:00之前将货物送达。根据各节点之间的距离和上图，我们很容易得出此段最短路径出发点为18，终点为24，从而路线为18→13→24，再根据示以及问题1所得数据，确定最优线路为18→13→19→24。
最后验证结果：根据路径我们算得此路径距离:
2182.0289+3113.4627+5704.3372=10999.83 m.
从而得出此段用去的时间=10999.83*3/20=27.50min<60min，从而可以知道按此路径送货员能按时将货物送到。

阶段2：要求9:30送到：
根据题中信息知，限制在此时间的点为：31,34,40,45。
同上阶段相同，结合数据和上图分析的出发点为31，终点为45，从而我们可以得到两种行程路线：31→34→40→45或31→40→34→45。需要对两条路线进行对比优化。
两种路线的行程总路程如下：

路线1
24—31
31—34
34—40
40—45
路程（m）
1780.1475
2324.7473
1630.782
3217.0056
路线2
24—31
31—40
40—34
34—45
路程（m）
1780.1475
3954.9293
1630.782
4847.7876
表3-2 行程路线表
对比两组数据，可以选定线路1为最佳方案。
按此路径行进距离=1780.1475+3954.9293+1630.782+4847.7876=12213.6464米。
得出耗时=12213.6464*3/20=30.53min<30min+60min-27.50min。即得出满足时间要求。

阶段3：要求10:15送到：
此时间要求共有四个指定地点：49，42，43，38。
分析可得起点为42，终点为38，从而得到两种送货路线：42→49→43→38或
42→43→49→38。两种路线的总路程如下：

路线1
45—42
42—49
49—43
43—38
各段路程（m）
2351.7228
1971.3764
2889.0501
2618.4442
路线2
45—42
42—43
43—49
49—38
各段路程（m）
2351.7228
917.6737
2889.0501
5507.4943
表3-3 总路程表
分析比较两组数据，可以选定线路1为最佳方案。
同上对数据进行验证：
按此路径行进距离=2351.7228+1971.3764+2889.0501+2618.4442=9830.5935米
得出耗时=9830.5935*3/20=24.58min<45min.
即能够按时件货物送到。

阶段4：要求12：00到达：
此时间段共有十个指定地点：26，21，14，17，23，32，39，36，27，16。分析可确定36为起点。起点确定终点不确定。
对此我们进行迭代算法：即从出发点开始，找出到出发点的最近距离的一个点，然后依次迭代计算，再以找出的点为出发点，找出到该点的最短距离的点，如此进行下去，则可以找出一条较短的行进路线。
首先以36为起点，具体计算过程如下：

点36 到其他点的距离（单位：m）如下：

36
27
21
39
32
17
26
23
14
16
距离
2203.917
2880.178
3983.84
4061.144
4704.089
4808.696
5373.013
6176.911
7470.654
表3-4 点36距离表

所以确定27为第二次所到地点。

点27到其他点的距离（单位：m）如下：

27
39
26
21
32
17
23
14
16
距离
1779．923
2604.781
4796.521
6265.06
6620.432
7576.93
8093.254
9674.571
表3-5 点27距离表

所以确定39为第三次所到地点。
由线路图可知，离开39后需要回到27，才能送货到其它地点，则再根据上述表格选取除39外距离27最近的地点的，即是第四次所到地点，易知26为第四次所到地点（途经31）。

点26到其他点的距离（单位：m）如下：

26
21
17
14
23
32
16
距离
2191.74
4015.651
5488.473
5790.165
7102.034
7887.806
表3-6 点26距离表

可得21为第五次所到地点。

点21到其他点的Euclid距离（单位：m）如下：

21
17
14
23
32
16
距离
1823.911
3296.733
3598.425
4910.294
5696.066
表3-7 点21距离表

可得17为第五次所到地点。

点17到其他点的Euclid距离（单位：m）如下：

17
23
14
32
16
距离
1774.514
9215.723
3086.383
3872.156
表3-8 点17距离表

理论上讲应该选取点23，但根据线路图以及剩余送货的地点，综合考虑后选取次优解即14为第六次送货地点。

点14到其他点的Euclid距离（单位：m）如下：

14
16
23
32
距离
2607.681
3970.237
5282.106
表3-9 点14距离表

可得16为第七次所到地点。

点16到其他点的距离（单位：m）如下：

16
23
32
距离
2097.6
3409.5
表3-10 点17距离表

可得23为第八次所到地点，32为终点。
由以上结果可得最佳送货路线如下：
36→27→39→（27）→（31）→26→21→17→14→16→23→32
在图中标出路线：

图3-3 路线表

所以综上考虑将各阶段的路径连接起来形成的最终最短路径为：
0→18→13→19→24→31→34→40→45→42→49→43→38→36→27→39→27→31→26→21→17→14→18→23→32。
得出最短路径距离minZ=54629.65m
时间minT=2.276h

第四章 总结

4.1 优点
对于题中各数据的处理，采用的工具、方法比较先进，各种计算方法精确，误差较小。在解决问题时，我们把原图变为完全图，利用全局线性规划法充分发挥lingo软件包求最优解功能。并且成功地对0—1变量进行了使用和约束，简化了模型建立难度，同时给出了在各种约束条件下的最短路径的计算方法，具有较强的实用性和通用性，在日上生活中经常可以用到。
4.2 缺点
由于数据较多，难以对模型结果进行验证，只能一步一步的对模型进行优化。

参考文献

[1] 朱道立. 运筹学[M]. 高等教育出版社, 2006.
[2] 周建兴. MATLAB从入门到精通.第2版[M]. 人民邮电出版社, 2012.
[3] 徐立华. 求解最短路问题的一个计算机算法[J]. 系统工程, 1989(5):46-51.
[4] 林澜, 闫春钢, 蒋昌俊,等. 动态网络最短路问题的复杂性与近似算法[J]. 计算机学报, 2007, 30(4):608-614.
[5] 牛学勤, 王炜. 基于最短路搜索的多路径公交客流分配模型研究靠[J]. 东南大学学报(自然科学版), 2002, 32(6):917-919.
[6] 马良河, 刘信斌, 廖大庆. 城市公交线路网络图的最短路与乘车路线问题[J]. 数学的实践与认识, 2004, 34(6):38-44.
[7] 魏航, 李军, 刘凝子. 一种求解时变网络下多式联运最短路的算法[J]. 中国管理科学, 2006, 14(4):56-63.
[8] 张运河, 林柏梁, 梁栋,等. 优化多式联运问题的一种广义最短路方法研究[J]. 铁道学报, 2006, 28(4):22-26.
[9] 李帮义, 姚恩瑜. 最短路网络及应用[J]. 系统工程理论与实践, 2000, 20(6):104-107.
[10] 龙光正, 杨建军. 改进的最短路算法[J]. 系统工程与电子技术, 2002, 24(6):106-108.
[11] 周经伦, 吴唤群. 受顶点数限制的最短路问题及其算法[J]. 系统工程, 1996(5):37-44.
[12] 贺国先. 集装箱公铁联运的费用加权最短路计算机算法[J]. 铁道学报, 2006, 28(1):1-5.
一级标题，中间空4格。
致 谢
空1行

大学四年的学习生活即将结束，在此，我要感谢所有曾经教导过我的老师和关心过我的同学，他们在我成长过程中给予了我很大的帮助。本文能够成功的完成，要特别感谢我的导师XXX教授的关怀和教导。
附 录

附录A 实际案例背景数据

图1 快递公司送货地点示意图
O点为快递公司地点，O点坐标(11000,8250),单位：米

表1 各货物号信息表
货物号
送达地点
重量(公斤)
体积(立方米)
不超过时间
1
13
2.50
0.0316
9：00
2
18
0.50
0.0354
9：00
3
31
1.18
0.0240
9：30
4
26
1.56
0.0350
12：00
5
21
2.15
0.0305
12：00
6
14
1.72
0.0100
12：00
7
17
1.38
0.0109
12：00
8
23
1.40
0.0426
12：00
9
32
0.70
0.0481
12：00
10
38
1.33
0.0219
10：15
11
45
1.10
0.0287
9：30
12
43
0.95
0.0228
10：15
13
39
2.56
0.0595
12：00
14
45
2.28
0.0301
9：30
15
42
2.85
0.0190
10：15
16
43
1.70
0.0782
10：15
17
32
0.25
0.0412
12：00
18
36
1.79
0.0184
12：00
19
27
2.45
0.0445
12：00
20
24
2.93
0.0420
9：00
21
31
0.80
0.0108
9：30
22
27
2.25
0.0018
12：00
23
26
1.57
0.0210
12：00
24
34
2.80
0.0103
9：30
25
40
1.14
0.0155
9：30
26
45
0.68
0.0382
9：30
27
49
1.35
0.0144
10：15
28
32
0.52
0.0020
12：00
29
23
2.91
0.0487
12：00
30
16
1.20
0.0429
12：00
31
1
1.26
0.0250

32
2
1.15
0.0501

33
3
1.63
0.0483

34
4
1.23
0.0006

35
5
1.41
0.0387

36
6
0.54
0.0067

37
7
0.70
0.0129

38
8
0.76
0.0346

39
9
2.14
0.0087

40
10
1.07
0.0124

41
11
1.37
0.0510

42
12
2.39
0.0428

43
13
0.99
0.0048

44
14
1.66
0.0491

45
15
0.45
0.0209

46
16
2.04
0.0098

47
17
1.95
0.0324

48
18
2.12
0.0554

49
19
3.87
0.0262

50
20
2.01
0.0324

51
21
1.38
0.0419

52
22
0.39
0.0001

53
23
1.66
0.0502

54
24
1.24
0.0534

55
25
2.41
0.0012

56
26
1.26
0.0059

57
27
0.42
0.0224

58
28
1.72
0.0580

59
29
1.34
0.0372

60
30
0.06
0.0402

61
31
0.60
0.0274

62
32
2.19
0.0503

63
33
1.89
0.0494

64
34
1.81
0.0325

65
35
1.00
0.0055

66
36
1.24
0.0177

67
37
2.51
0.0361

68
38
2.04
0.0110

69
39
1.07
0.0440

70
40
0.49
0.0329

71
41
0.51
0.0094

72
42
1.38
0.0455

73
43
1.31
0.0121

74
44
1.26
0.0005

75
45
0.98
0.0413

76
46
1.35
0.0241

77
47
2.12
0.0230

78
48
0.54
0.0542

79
49
1.01
0.0566

80
50
1.12
0.0284

81
25
0.79
0.0011

82
46
2.12
0.0492

83
32
2.77
0.0034

84
23
2.29
0.0054

85
20
0.21
0.0490

86
25
1.29
0.0088

87
19
1.12
0.0249

88
41
0.90
0.0038

89
46
2.38
0.0434

90
37
1.42
0.0020

91
32
1.01
0.0300

92
33
2.51
0.0133

93
36
1.17
0.0020

94
38
1.82
0.0308

95
17
0.33
0.0345

96
11
0.30
0.0172

97
15
4.43
0.0536

98
12
0.24
0.0056

99
10
1.38
0.0175

100
7
1.98
0.0493

表2 50个位置点的坐标
位置点
X坐标(米)
Y坐标(米)
1
9185
500
2
1445
560
3
7270
570
4
3735
670
5
2620
995
6
10080
1435
7
10025
2280
8
7160
2525
9
13845
2680
10
11935
3050
11
7850
3545
12
6585
4185
13
7630
5200
14
13405
5325
15
2125
5975
16
15365
7045
17
14165
7385
18
8825
8075
19
5855
8165
20
780
8355
21
12770
8560
22
2200
8835
23
14765
9055
24
7790
9330
25
4435
9525
26
10860
9635
27
10385
10500
28
565
9765
29
2580
9865
30
1565
9955
31
9395
10100
32
14835
10365
33
1250
10900
34
7280
11065
35
15305
11375
36
12390
11415
37
6410
11510
38
13915
11610
39
9510
12050
40
8345
12300
41
4930
13650
42
13265
14145
43
14180
14215
44
3030
15060
45
10915
14235
46
2330
14500
47
7735
14550
48
885
14880
49
11575
15160
50
8010
15325

表3 相互到达信息
序号
位置点1
位置点2
1
1
3
2
1
8
3
2
20
4
2
4
5
3
8
6
3
4
7
4
2
8
5
15
9
5
2
10
6
1
11
7
18
12
7
1
13
8
12
14
9
14
15
9
10
16
10
18
17
10
7
18
11
12
19
12
13
20
12
25
21
12
15
22
13
18
23
13
19
24
13
11
25
14
18
26
14
16
27
14
17
28
14
21
29
15
22
30
15
25
31
16
23
32
17
23
33
18
31
34
19
24
35
20
22
36
21
26
37
21
36
38
21
17
39
22
30
40
23
17
41
24
31
42
25
41
43
25
19
44
25
29
45
27
31
46
28
33
47
29
22
48
30
28
49
30
41
50
31
26
51