A heuristic approach to an interdependent restoration planning and crew routing problem
A heuristic approach to an interdependent restoration planning and crew routing problem
复制标题
DOI：
10.1016/j.cie.2021.107626
复制
发表时间：
2021-09-08
影响因子：
7.9
通讯作者：
Ermagun, Alireza
中科院分区：
文献类型：
--
作者：
Tajik, Nazanin;Barker, Kash;Ermagun, Alireza
本研究提出有效的解决方法，以解决相互依赖的恢复规划和船员路由问题。无论中断的基础设施网络的规模和结构如何，这些解决方案都能提供可靠的恢复计划。我们提出了一个宽松的混合整数线性规划（MILP）模型和两个启发式算法来寻找有效的可行的初始解的恢复路由问题。我们还提出了一个局部搜索启发式算法，找到一个接近最优的解决方案，使用所提出的模型得到的结果。使用电力，水，天然气基础设施网络的例子，从谢尔比县，田纳西州，计算结果证实了有效性的数学公式，并表明，启发式算法获得最佳或接近最佳的解决方案。特别是，我们应用序列的放松模型，初始解算法，和本地搜索算法的62个场景与不同程度的中断和不同数量的恢复工作人员。通过对局部搜索算法性能的分析，我们证实了初始解算法在产生可靠的、总恢复时间相对较低的恢复时间表方面的优势，特别是对于大规模的问题。观察结果还揭示了如何分散强度分布的中断位置影响放松模型的性能，因此，集成的启发式。
This study proposes efficient solution methods to solve interdependent restoration planning and crew routing problems. The solutions provide reliable restoration plans regardless of the size and structure of disrupted infrastructure networks. We propose a relaxed mixed integer linear programming (MILP) model and two heuristic algorithms to find efficient feasible initial solutions for the restoration routing problem. We also propose a local search heuristic algorithm to find a near-optimal solution using the results obtained from the proposed model. Using electric power, water, and gas infrastructure network instances from Shelby County, TN, the computational results corroborate the efficacy of the mathematical formulation and shows that the heuristic algorithm obtains optimal or near-optimal solutions. In particular, we apply the sequence of the relaxed model, initial solution algorithm, and the local search algorithm for 62 scenarios with different magnitudes of disruption and different numbers of restoration crews. Analyzing the performance of the local search algorithm, we confirm the advantages of using the initial solution algorithm in producing the restoration schedules with reliable and relatively low total restoration time, particularly for large size problems. The observations also reveal how the scattering intensity in the distribution of disrupted locations affects the performance of relaxed models, and consequently, the integrated heuristic.