Disaster relief routing under uncertainty: A robust optimization approach

ABSTRACT

This article addresses the Capacitated Vehicle Routing Problem (CVRP) and the Split Delivery Vehicle Routing Problem (SDVRP) with uncertain travel times and demands when planning vehicle routes for delivering critical supplies to a population in need after a disaster. A robust optimization approach is used for CVRP and SDVRP considering the five objective functions: minimization of the total number of vehicles deployed (minV), the total travel time/travel cost (minT), the summation of arrival times (minS), the summation of demand-weighted arrival times (minD), and the latest arrival time (minL), out of which we claim that minS, minD, and minL are critical for deliveries to be fast and fair for relief efforts whereas minV and minT are common cost-based objective functions in the traditional VRP. A new two-stage heuristic method that combines the extended insertion algorithm and tabu search is proposed to solve the VRP models for large-scale problems. The solutions of CVRP and SDVRP are compared for different examples using five different metrics in which we show that the latter is not only capable of accommodating the demand greater than the vehicle capacity but also is quite effective to mitigate demand and travel time uncertainty, and thereby outperforms CVRP in the disaster relief routing perspective.

KEYWORDS:

• Robust optimization
• split delivery vehicle routing problem
• tabu search
• insertion algorithm

Additional information

Funding

This research is partially funded by the Region II University Transportation Research Center (UTRC). Authors are grateful for the support.

Notes on contributors

Yinglei Li

Yinglei Li received her Ph.D. in industrial and systems engineering from State University of New York (SUNY) at Binghamton in 2017, a master's degree in biomedical engineering from SUNY at Binghamton in 2014, and a bachelor's degree in bioengineering from South China Agricultural University, Guangzhou, China in 2012. She has worked on several research projects involving data analysis, machine learning, operations research, and mathematical optimization for transportation planning, supply chain management, and healthcare.

Sung Hoon Chung

Sung Hoon Chung is an assistant professor of systems science and industrial engineering at the State University of New York at Binghamton. He earned his Ph.D. from Pennsylvania State University, and M.S. and B.S. from Yonsei University. Dr. Chung's research interests include supply chain management, hazards and disaster management, transportation/logistics, and healthcare operations management.