A two-stage algorithm for vehicle routing problem with charging relief in post-disaster

This paper first investigates emergency transportation for power recovery in post-disaster. The problem is formulated as a mixed-integer linear programming model called vehicle routing problem with charging relief (VRPCR). The battery state of charge (SoC$SoC$) implies the working hours that the battery can provide. The goal is to make a set of shelters charge before the battery SoC$SoC$ of shelters reaches the minimum bound over time. To this end, a two-stage algorithm is developed to deal with the problem. In stage I, a reduced road network is obtained from a leading road network by the A-star search algorithm. Subsequently, to determine the order of power delivery with charging operations at shelters by enhanced genetic algorithm (EGA) in stage II. To evaluate this strategy, the detailed complexity analysis of the three algorithms and results tested on a realistic disaster scenario shows the performance of the A-star search algorithm for VRPCR that outperforms the Dijkstra and Floyd algorithms. In addition, the EGA is applied to Solomon's benchmarks compared with the state-of-the-art heuristic algorithms, which indicates a better performance of EGA. A real case obtained from a disaster scenario in Ichihara City, Japan is also conducted. Simulation results demonstrate that the method can achieve satisfactory solutions.