Robust drone selective routing in humanitarian transportation network assessment

Guowei Zhang, Ning Jia, Ning Zhu, Yossiri Adulyasak and Shoufeng Ma

European Journal of Operational Research, 2023, vol. 305, issue 1, 400-428

Abstract: 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.

Keywords: Humanitarian logistics; Post-disaster assessment; Arc routing problem; Robust optimization; Branch-and-price algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722004489
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:305:y:2023:i:1:p:400-428

DOI: 10.1016/j.ejor.2022.05.046

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().