A Deep Reinforcement Learning-Based Adaptive Search for Solving Time-Dependent Green Vehicle Routing Problem

Abstract

The time-dependent green vehicle routing problem with time windows is a further deepening of the research on vehicle routing problems with time windows. Its simultaneous consideration of vehicle transportation time, carbon emissions, and customer satisfaction under time-dependent variables makes it more challenging to solve than traditional vehicle routing problems. This work proposes a multi-objective optimization algorithm that combines the learnable crossover strategy and the adaptive search strategy based on reinforcement learning to overcome the local optima, poor convergence, and reduced variety of solutions that plague the multi-objective optimization algorithms when solving this problem. The proposed approach solves the problem in two stages: In the first stage, a hybrid initialization strategy is used to generate initial solutions with high quality and diversity, and crossover strategies are used to further explore the solution space and improve convergence by learning the characteristics of pareto solutions. In the second stage, the adaptive search is designed and used for learning and searching in the later stage of the algorithm. The experimental results show better solution quality obtained by the proposed approach, and the effectiveness and superiority of the proposed approach over existing methods in terms of solution convergence and diversity are demonstrated through experimental comparisons.

Keywords

• Multi-objective optimization
• DQN
• GVRPTW
• time-dependent
• customer satisfaction