摘 要

本文主要研究了在自然灾害发生导致交通阻塞的情况下，关键地点之间的交通受阻，此次研究的目的在于找到一种快速有效的方法来指定一个清理团队的路线。这条路线从仓库节点出发，经过所有的关键节点。目标是最小化关键节点的总延迟，即从仓库节点到达关键节点的总耗时。关于这个模型的求解已经在前辈的文献中完成，但对于七个关键节点之上的实例，这个求解公式已经不能满足在三个小时内求解的要求。为了在短时间内找到近似最优解，我们使用了一种能够在变换后的路网上求解混合整数规划的启发法，并使用了一种求最优延迟的下界法。我们还将我们的成果与文献中已有的成果进行了比较。

本文的特色在于使用有了一种基于贪婪随机自适应搜索法（GRASP）和变领域搜索（VNS）相结合的元启发式算法。我们对伊斯坦布尔地区路网数据使用界限法，启发式法和元启发式进行了测试，证明了较优近似解能够在三十分钟左右求解。

关键词：清理路线；最小延迟；界限法；启发式

Abstract

This paper mainly studies the traffic congestion between key locations in the case of traffic congestion caused by natural disasters. the purpose of this study is to find a fast and effective way to designate the route of a cleaning team. This route starts from the warehouse node and passes through all the key nodes. The goal is to minimize the total delay of the critical nodes, the total time it takes to get from the warehouse node to the critical node.The solution of this model has been completed in the previous literature, but for the examples above seven key nodes, this formula can no longer meet the requirements of solving within three hours. In order to find the approximate optimal solution in a short time, we propose a heuristic method which can solve mixed integer programming on the transformed road network, and propose a lower bound method to find the optimal delay. We also compare our results with those in the literature. 

The characteristic of this paper is to develop a meta-heuristic algorithm based on Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Search (VNS). We test the simplified road network data of Istanbul Ring Road by using mathematical method and meta-heuristics, and prove that the better approximate solution can be solved in about 30 minutes.

Key Words：Clean-up route; minimum delay; bound method; heuristic

目 录

第1章 绪论 1

1.1 研究意义及背景 1

第2章 文献综述 3

2.1 道路清理 3

2.2 最低化总延迟 4

第3章 问题描述 6

第4章 ML-RCP的下界算法 8

第5章 启发式法及元启发式法 13

5.1 启发式法 13

5.2 元启发式算法 14

5.2.1 GRASP 15

5.2.2 VNS 16

第6章 数据集及结果分析 19

6.1 数据集 19

6.2 测试方案 19

6.3 伊斯坦布尔路网结果 20

6.4 与文献中相关研究的比较 22

第7章 结论 24

7.1 本文的贡献 24

7.2 展望 24

参考文献 26

致谢 28

绪论

1.1 研究意义及背景

每当火山爆发或者地震等较严重的自然灾害破坏受影响地区的基础设施，会造成大量的残骸废物堆积，包括建筑材料（如混凝土、砖块、木材）、车辆、植被（如倒下的树木）和道路基础设施的瓦砾。为了应急救援行动的及时进行，必须在尽可能短的时间内清除道路上的障碍。从长远看，废物清理和修复受损道路能够使该区域恢复重要活动（如医疗以及物资运输等）。在这项研究中，我们侧重于及时反映的效用，例如在灾后的24小时内着力于优先清除残骸的决定。

灾后恶劣的道路状况妨碍了医院、救援总部、庇护所和受灾区等重要地区之间的交通。例如在2011年日本地震和海啸使十万人滞留在受灾区域^[1]。所以，为了尽快的清理受损道路，使受损的路段恢复使用，在受灾最初阶段的损坏评估后即需要对多个救援队伍的进行合理分配。在大多数情况下，修复道路的任务是受时间限制的，清除所有受影响的道路是不可能的，因此，有必要选择最有利的清除任务，以便在最短时间内到达关键位置。对于关键地点的疏通任务完成的越早，就有可能避免生命的损失或者其他的痛苦。

此项研究的目的是指定一种有效且适用的方法，通过建立一个清理小组的路线来决定哪些道路应该按照什么顺序被清除或修复。我们可以注意到在这片论文中，我们交替使用道路清除和解除阻塞的行动，即进入阻塞边，也可能包括清理。在我们对这个问题的定义中，道路用网络表示，关键位置即为节点的子集。每一条边都存在一个遍历耗时，另外，每条阻塞边的清除时间也都是被预计给定的。如果阻塞边被清除，则它可能在稍后其他单位的工作中再次被遍历。总遍历耗时包括路径中所有边的遍历时间和阻塞边的清理耗时。路径应该访问所有关键节点，以确保他们是可被遍历的。该路由问题的目的是最小化所有关键节点的总延迟，关键节点的耗时定义为访问之前的时间。也就是说，“延迟”是从该遍历行为开始到到达关键节点位置的路程时间，遍历行为是从起始节点（仓库节点）开始的。

图1.1 对于相同的最大等待时间值具有不同总等待时间的示例