A History Information-Guided Evolutionary Algorithm for the Multiobjective Vehicle Routing Problem With Time Windows

The vehicle routing problem with time windows (VRPTWs) is a complex NP-hard optimization challenge that requires optimizing two objective functions: total driving distance and the number of vehicles to be utilized. This must be accomplished while adhering to vehicle capacity constraints and customer-specific time windows. Despite the proposal of numerous evolutionary algorithms to address this challenge, their effectiveness and search efficiency are frequently limited due to a reliance on random search methods. To address this limitation, this article introduces a history information-guided multi-objective evolutionary algorithm (MOEA). This algorithm leverages the structural information of feasible solutions accumulated from previous evolutionary processes. It specifically utilizes an information matrix to efficiently record valid crossover positions, thereby guiding the crossover operator between two parent solutions to produce higher quality offspring. To evaluate the effectiveness of the proposed algorithm, a comprehensive comparison is conducted with the state-of-the-art MOEAs using a public test suite. The experimental results demonstrate that the proposed algorithm significantly enhances convergence speed while also achieving competitive solutions.