A multiobjective evolutionary algorithm with enhanced reproduction operators for the vehicle routing problem with time windows

This paper addresses the vehicle routing problem with time windows (VRPTW). The task is to assign customers to multiple vehicles and determine the visiting sequences of customers for the vehicles without violating the vehicle capacity constraint and customer service time window constraints. Two common objectives of VRPTW are to minimize the number of vehicles and the total traveling distance. Most of previous studies assumed that the number of vehicles is more important than the total distance. Hence, they solved the VRPTW by minimizing the number of vehicles first and then minimizing the total distance under the minimal number of vehicles. Recently, researchers started to solve the VRPTW without this assumption and tried to minimize both objectives simultaneously through searching for the Pareto optimal set of solutions. Following this perspective, we use a multiobjective evolutionary algorithm to solve the VRPTW. We propose enhanced crossover and mutation operators by incorporating the domain knowledge. Performance of the proposed algorithm is verified on a widely used benchmark problem set. Comparing with seven existing algorithms, our algorithm shows competitive performance and contributes many new best known Pareto optimal solutions.