Robust drone selective routing in humanitarian transportation network assessment

Assessing a humanitarian transportation network at an early stage after disaster occurrence plays a crucial role in the mitigation of casualties. As a class of uncrewed aerial vehicles, drones have the potential to perform such assessment operations. We consider a drone arc routing problem in which road segments are evaluated selectively with the goal of maximizing the collected arc informative profits within a predefined time limit. The problem allows drones to travel between nodes without following the physical road network; i.e., drones can travel along the road network for assessment purposes, but they can also travel off the network to save travel time. This feature raises a novel challenge compared to the conventional arc routing problem, as multiple edges exist between two nodes, with different corresponding benefits. To address this challenge, a graph transformation technique is presented in which the multigraph-based arc routing problem is reduced to a node-based routing problem on a simple graph. Due to the significant uncertainties and limited information regarding the post-disaster transportation network, the problem is modeled as a new variant of a robust team orienteering problem with uncertain assessment time. Since the original robust formulation is intractable, we leverage path-based reformulation and apply Lagrangian decomposition to the robust counterpart, which allows us to solve the robust subproblem efficiently through a series of deterministic auxiliary problems. We propose an efficient exact branch-and-price (B&P) framework to solve this problem exactly. In computational experiments, we examine the efficiency of our solution approach using various instances, including instances generated from real-world data as well as simulation, to demonstrate its practical applicability. The results show that compared with the traditional arc orienteering problem, our model achieves an approximately 30% improvement in the objective value.