A Study of Multi-Constraints Emergency Transportation Problem in Disaster Response

Wenhan Shao, Xiaolu Liu (), Jiaming Chen () and Zhipeng Lü ()
Additional contact information
Wenhan Shao: Huazhong University of Science and Technology, School of Computer Science and Technology, Wuhan 430074, P. R. China
Xiaolu Liu: College of System Engineering, National University of Defense Technology, Changsha 410073, P. R. China
Jiaming Chen: College of System Engineering, National University of Defense Technology, Changsha 410073, P. R. China
Zhipeng Lü: Huazhong University of Science and Technology, School of Computer Science and Technology, Wuhan 430074, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 02, 1-25

Abstract: The paper studies a real-world Multi-Constraints Emergency Transportation Problem in disaster response under travel time uncertainty(MCETP), whose objective is to determine the set of flights and routes and the airplane and vehicle assignment for delivering necessary living supplies to disaster areas as quickly as possible. The MCETP can be modeled as a variant of the Vehicle Routing Problem (VRP), which considers a heterogeneous fleet with multi-depots delivering supplies to customers in order to minimize the maximal travel time of all routes where travel time of vehicles is predicted by experts because ground transportation network is destroyed and affected degree is unknown. By adding copy points and imaginary depots, the MCETP can be transformed into a variant of the Travelling Salesman Problem (TSP), for which a Mixed Integer Linear Programming (MILP) formulation is presented. With the proposed initial solution construction algorithm, vehicle assignment strategy and penalty function, the transformed problem can be solved by the extension of Lin–Kernighan–Helsgaun solver (LKH-3). Computational experiments on two sets of totally 50 instances show that the idea of transforming a challenging complex problem to a widely studied problem and using its state-of-the-art algorithm to solve the original problem is highly effective and efficient for the MCETP. Specifically, it can obtain the same solution quality as GUROBI but with much less time for small-scale instances. Furthermore, the proposed algorithm can solve large-scale instances while GUROBI fails to obtain a feasible solution in most cases in a reasonable time.

Keywords: Disaster response; emergency transportation; VRP; TSP; mixed integer linear programming; LKH-3 (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595920500505
Access to full text is restricted to subscribers

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:wsi:apjorx:v:38:y:2021:i:02:n:s0217595920500505

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595920500505

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().