Two-Stage Multi-objective Evolutionary Algorithm Based on Classified Population for Tri-objective VRPTW
Hang Shu, Kang Zhou, Zhixin He and Xinyue Hu
This paper presents a two-stage multi-objective evolutionary algorithm based on classified population (TSCEA) to solve vehicle routing problem with time windows (VRPTW). It is a well-known NP-hard discrete optimization problem with three objectives: to minimize the total distance cost, to minimize the number of vehicles, and to optimize the balance of routes within a limited time. For TSCEA, there are two stages: In the first stage, a population is explored using the proposed algorithm and then classified according to the number of vehicles, we call this process population classification; In the second stage, Pareto solution set of tri-objective VRPTW is obtained by optimizing the classified population again. The advantages of classified population structure are that for the first stage, this population that the number of vehicles of each individual is in this range composed of the upper and lower bounds of vehicles can be classified as different small populations with the same number of vehicles. Due to the evolution of small population, Pareto solution set with better extensibility can be searched. For the second one, it can reduce the dimension of tri-objective function, that is, three objective functions can be reduced to two objective functions because one of them has been identified in the first stage. Moreover, to resolve the nonlinear discrete problems, the computational approach of crowding degree is modified. The paper chooses Solomon benchmark instances as testing sets and the simulated results show that TSCEA outperforms the compared algorithms in terms of quality or extension, which verified the feasibility of the algorithm in solving tri-objective VRPTW.
Keywords: Tri-objective VRPTW, two-stage multi-objective evolutionary algorithm, population classification