Integrated Optimization of Road Repair Routing and Drone-Based Relief Scheduling in Isolated Areas Post-Disaster

 

 

 Natural disasters, including earthquakes, floods, and landslides, often result in significant infrastructural damage, particularly in rural and remote regions.

One of the most critical consequences of such disasters is the destruction of road networks, which can isolate affected communities and hinder the timely delivery of humanitarian aid. These disruptions can exacerbate the impacts of disasters by delaying access to vital medical supplies and relief goods. Given the urgency and complexity of post-disaster logistics, developing efficient and responsive operational strategies is essential to mitigate further loss and suffering.

This study addresses the challenge of restoring accessibility to isolated areas by integrating the scheduling of road repair activities and the delivery of emergency supplies via drones. Specifically, the problem is modeled under the assumption that a single repair crew is available to restore connectivity by sequentially repairing damaged road segments. The objective is to determine an optimal repair route that prioritizes isolated areas based on the severity of their needs and the availability of temporary relief.

Recognizing that many isolated regions may possess limited stockpiles of essential medical equipment, we introduce the concept of deadlines for re-establishing access. These deadlines represent the maximum allowable time before the situation in each area becomes critical due to resource depletion. However, these deadlines are not fixed. They can be dynamically extended if drones are deployed to deliver small quantities of medical and relief supplies, thereby postponing the critical need for ground-based access.

To capture the intricacies of this problem, an integrated integer linear programming (ILP) model is formulated. This model simultaneously determines the optimal repair sequence for the road crew and the drone delivery schedule. The dual consideration of ground and aerial logistics introduces significant computational complexity, particularly under tight time constraints and a larger number of affected areas and damaged roads.

Initial computational experiments reveal that the ILP model struggles to yield optimal solutions within acceptable time limits for medium-sized problem instances. For example, the model fails to find the optimal solution for instances involving more than six isolated nodes and six road segments within one hour when tight deadlines are imposed. This finding underscores the necessity for a more scalable and efficient solution methodology.

To address the limitations of the ILP model, a logic-based Benders decomposition (LBBD) algorithm is developed. LBBD is a well-established technique for solving large-scale optimization problems by decomposing them into a master problem and one or more subproblems, which are solved iteratively. In this study, the master problem determines the repair sequence of the road crew, while the subproblem handles the scheduling of drone deliveries. The LBBD approach demonstrates superior computational performance, solving instances with up to sixteen demand nodes in under 45 minutes.

A comprehensive computational study using randomly generated instances is conducted to evaluate the performance of both the ILP and LBBD approaches. The results show that LBBD consistently outperforms the ILP model in terms of both solution quality and computational efficiency. Moreover, a series of sensitivity analyses is performed to examine the impact of key parameters, such as drone capacity, road repair times, and deadline flexibility, on the overall system performance.

In conclusion, the integration of road repair routing with drone-based relief delivery presents a promising approach to enhancing post-disaster response in isolated areas. The proposed modeling framework and solution algorithm provide valuable insights for disaster management planners and policymakers seeking to improve resilience and reduce the adverse effects of natural disasters on vulnerable communities.

 References

Safdari Shadlou, M., Ranjbar, M., & Salari, M. (2022). Integrated Optimal Repair Crew Routing and Drone Scheduling after a Natural Disaster

Lakzaei, S., Rahmani, D., Tosarkani, B. M., & Nasiri, S. (2023). Integrated optimal scheduling and routing of repair crew and relief vehicles after disaster: a novel hybrid solution approach. Annals of Operations Research, 328(2), 1495–1522

Akbari, V., Shiri, D., & Salman, F. S. (2021). An online optimization approach to post-disaster road restoration. Transportation Research Part B: Methodological, 145, 1–23