Vehicle Routing Strategy for Disaster Relief Operation: A Case Study

Advanced strategies for emergency logistics scheduling problem has been a challenging topic for centuries. This study proposed a cluster-first-route-second constructive heuristic method based on the continuous approximation (CA) for disaster relief operation which can turn the relatively complicated vehicle routing problem (VRP) into travel salesman problem (TSP) for pre-assigned customer sets. CA is adopted to determine optimal replenish amount and inventory level for the route serving a given location. Christofide’s method is then employed to solve the TSP for the selected cluster. We investigate two clustering methods, a local-based approach, where clustering and routing are determined, and K-mean clustering where points are clustered upfront by the CA solution. A case study is presented to demonstrate the proposed approach and compare two clustering methods. The numerical results illustrate the effectiveness of the algorithms and conclude that the local-based clustering approach may yield a lower total cost with a higher motion cost.