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

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.