Multiple-Drones-Multiple-Trucks Routing Problem for Disruption Assessment

Abstract

This study proposes a multiple-drones-multiple-trucks (MDMT) routing problem to assess infrastructure in the areas of disruption epicenters using multiple drones that operate in synchronicity with multiple trucks. Incorporating the trucks as moving depots enables drones to move across disrupted areas further from their flight range. The MDMT routing problem is formulated as mixed integer linear programming (MILP). This is an NP-Hard (Non-deterministic Polynomial-time Hardness) problem, which is solved by introducing a greedy heuristic algorithm to cluster the disrupted locations and plan each drone’s schedule within each disrupted cluster and between clusters. Both MILP and the greedy heuristic algorithm are tested for small to large test problems extracted from the Minneapolis–St. Paul freeway system with a grid-like network topology. Results show that disrupted locations’ spatial distribution affects the efficient number of active drones and trucks in the system. When direct travel between two nodes takes longer than other alternative paths, increasing the number of trucks accelerates the assessment procedure. Findings also indicate that the spatial distribution of disruptions clustered by the greedy heuristic algorithm is correlated with the routing time and affects drone scheduling. If clusters are scattered, each drone is typically assigned to one cluster for damage assessments. With a dense pocket of clusters in the network, however, a drone moves back and forth between multiple clusters. The proposed framework for disruption assessment provides insights on the optimal deployment of resources to collect information following a network disruption. Practitioners will also benefit from the findings to augment resource management.