Quantum Evolutionary Algorithm For Vehicle Routing Problem

The logistics industry, an important service industry for promoting economic globalization, has become an important part of international economic system. Transportation is the key part in the logistics industry. The transportation costs account for more than half of the total cost of logistics, so that it has a great influence on the total cost of logistics. Vehicle routing problem, which is research on how to plan the vehicle routes in order to save the transportation costs, is a well known NP problem in the field of operation research and combination optimization. For large or medium scale problems, there is a problem that combinatorial explosion will happen. For NP complexity, most researchers concentrate on the research of meta-heuristic algorithm.The dissertation mainly studied quantum Evolutionary Algorithm in solving four VRP models: Capacity Vehicle Routing Problem, Open Vehicle Routing Problem, Dynamic Networks Vehicle Routing Problem, Dynamic Demands Vehicle Routing Problem. The main contributions of the paper as follows:1. Quantum evolutionary algorithm for capacity vehicle routing problem is deeply studied. 0-1 matrix encoding is used to construct chromosomes, quantum rotation gate is used to realize evolution, cataclysm is introduced to ensure the diversities of the solution spaces, Nearest Insert and 2-Opt are adopted to optimize sub-routes. Compared to the results of other algorithms are reported, the experiments show that the proposed algorithm is an efficient method for solving Capacitated Vehicle Routing Problem.2. The mathematical model of Open Vehicle Routing Problem is founded, and Quantum evolutionary algorithm combined local search algorithms are presented. Rotation gate with adaptively adjusting rotation angle is used to realize evolution, Nearest Neighbors and 2-Opt are incorporated to further improve solutions. The algorithm's parameters are discussed. Benchmark problems are chosen for experiment.3. Quantum evolutionary algorithm for Dynamic Networks Vehicle Routing Problem is studied. The basic concepts of Dynamic Networks Vehicle Routing Problem are introduced. The mathematical model of Dynamic Networks Vehicle Routing Problem is founded. Benchmark problems are modified and test. 4. The two-step mathematical model of Dynamic Demands Vehicle Routing Problem is founded. The first stage is pre-optimization stage, Quantum evolutionary algorithm is adopted for known information. The second stage is real-time optimization stage, Genetic algorithm is adopted for real-time information. At last, instances are designed and tested...