Abstract:

Traditional optimization algorithms from operations research are not well-suited for addressing the vehicle routing problem (VRP) with a large number of instances and high real-time requirements. Deep reinforcement learning (DRL) introduces a new approach to solving VRP, characterized by its rapid problem-solving capabilities and robust generalization abilities. In the domain of VRP variants, numerous benchmarks are utilized to evaluate the performance of the solving algorithms. However, the limited number of instances in these public benchmarks is insufficient for training DRL algorithms. To address this issue, an effective benchmark augmentation method using distribution derivation is proposed. By modeling the distributions of key VRP variables and estimating their parameters, the method derives distributions closely resembling the original benchmark and subsequently generates a large number of synthetic instances accordingly. The proposed method holds promise for widespread applications across various benchmarks. Experiments on VRP with time windows (VRPTW) and heterogeneous fleet VRP (HFVRP) verify the generalization abilities. The results show that DRL trained using the augmented benchmarks performs much better on public benchmarks than trained using the data customized by the algorithm authors. In addition, the DRL algorithms trained using the augmented benchmarks achieve performance comparable to state-of-the-art algorithms in public benchmarks for various VRP variants while significantly reducing the computation time.

Key words: benchmark, vehicle routing problem (VRP), deep reinforcement learning (DRL), comparison between DRL and traditional algorithms