Multi-objective Evolutionary Algorithm With Decomposition And Similarity Measure In Decision Space For Vehicle Routing Problem

The Vehicle Routing Problem(VRP) is an important research content in logistics management and transportation services problems, which attracted many researchers to study it. Its main objective is to arrange the vehicle driving routes reasonably and reduce the transportation cost. Now, many researchers have proposed many exact methods, heuristic and meta-heuristic methods to solve this problem. However, most of existing works focus on VRP with single optimization object. In real world, there are many optimization objects related to transportation costs, such as the number of used vehicles, the total travel distance, total waiting time and travel time of the longest route. If we only optimize one objective, it could lead to the deterioration of the others. So, we need to consider the simultaneous optimization of multiple objectives. Therefore, we need to study multi-objective VRP, so that decision makers can choose the solution from the Pareto Front.Multi-objective evolutionary algorithm based on decomposition(MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problem by decomposing the target problem into a set of scalar subproblems and optimizing them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. This thesis proposes an improved MOEA/D to solve the vehicle routing problem with time windows(VRPTW), considering the minimisation of the number of vehicles and the travel distance in conflict simultaneously. As VRPTW has a discrete optimization goal and the number of used vehicle is limited in a small range, the non-dominated solutions of VRPTW are very few. The tchebycheff approach in MOEA/D can’t maintain the diversity of the evolution population. Therefore, we designed a novel selection operator instead of the original one in MOEA/D. Moreover, the role of local search is vital in multi-objective evolutionary optimization in order to encourage better convergence and to discover any missing trade-off region. So three local search heuristics are also introduced into the enhanced MOEA/D. The improved MOEA/D are noted as I-MOEA/D. Finally, the Solomon’s benchmark which consist of 56 data sets with 100 customers are adopted in the experimental studies to illustrate the superiority of the proposed I-MOEA/D and to validate of the effectiveness of the two newly designed components in I-MOEA/D.The neighborhood of a subproblem is build by calculating the Euclidean distances between its weight vector and each other weight vector of the subproblems in MOEA/D. However, for the VPRTW problem, because two solutions with similar target values in the object space might be far from each other in the decision space, so two optimal solutions to two neighboring subproblems might quite different from each other. Accordingly, we use the Jaccard similarity coefficient to measure the similarity between two individuals in the decision space for building the neighborhood of the subproblems. The I-MOEA/D which used the newly method to building neighborhood is noted as I-MOEA/DS. Finally, the I-MOEA/DS was tested in the Solomon’s benchmark to validate the effectiveness of the newly constructing neighborhood method.