Disaster relief routing under uncertainty: A robust optimization approach

ABSTRACTThis 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...