Applied Deep Reinforcement Learning for Solving the Vehicle Routing Problem with Time Windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a challenging combinatorial optimization problem with many real-world applications. In this paper, we propose a Deep Reinforcement Learning (DRL) approach for solving the VRPTW using the Deep Q-Network (DQN) algorithm. Specifically, we use a variant of the DQN algorithm that incorporates the target network and experience replay techniques to improve the learning process. We also introduce a hybrid approach that combines a Greedy algorithm with the DQN algorithm (GDQN) to further enhance the exploration-exploitation trade-off in the search process. We evaluate the performance of the proposed approach on the Solomon benchmarks, which are widely used in the literature to benchmark the performance of various algorithms for the VRPTW. Our experimental results show that the proposed GDQN outperforms the DQN approach in terms of the quality of solutions generated, for type 25, achieving an average total used vehicle of 41.37% compared to 58.63% and average total distances of 52.34% compared to 47.66% for the DQN approach. For type 50, achieving an average total used vehicle of 42.22% compared to 57.78% and average total distances of 47.56% compared to 52.44% for the DQN approach. The proposed GDQN method provides an effective solution for the VRPTW problem in total used vehicle and total distances and use the same average total waiting time.