Multiobjective Evolutionary Algorithm Research On Vehicle Routing Problem With Time Windows And Two Dimensional Loading Constraint

Vehicle routing problem exists widely in industry areas, and it has important application value in logistic and transportation business. With the rapid development of our country’s market economy, the scale of industry is becoming larger, and the transportation industry is also rapidly developing. Therefore vehicle routing problem has attracted more and more attention. As a key technology to improve resource utilization, algorithms to solve vehicle routing problem have very important significance in saving resource and promoting low-carbon economy.Time windows constraint and two dimensional loading constraint are two common constraints which are often encountered in practical applications of vehicle routing problem. So far there have been many scholars doing extensive research on these two constraints. However, these two constraints are considered individually by all the past research. Considering both constraints together, this research proposes a multiobjective vehicle routing problem with time windows and two dimensioal loading constraint, and then presents a multiobjective evolutionary algorithm to solve this problem, expecting to solve this new problem with new method.The proposed multiobjective evolutionary algorithm employs the framework of multiobjective evolutionary algorithm based on decomposition. To prevent this algorithm being trapped in local optimum, a split and reconnect operator based on the optimal matching of bipartite graph is proposed; To reduce the number of used vehicles, a worst route elimination operator is proposed; To enhance the ability of finding optimal solution, simulated annealing algorithm is used to search for improvement of single objective optimization subproblem. For the framework of multiobjective evolutionary algorithm based on decomposition, an improved selection strategy is proposed to employ larger diversity in crossover stage. The proposed algorithm outperforms other existing algorithms on Solomon’s vehicle routing problem benchmark and also updates some best-known non-dominated solutions. Finally, some test cases of vehicle routing problem with time windows and two dimensional loading constraint are constructed, then solved and analyzed by the proposed algorithm.