Research On Hybrid Intelligent Optimization Algorithm Based On Solving Vehicle Routing Problem

Vehicle routing problem is often complicated by factors such as large-scale, uncertainty, multi-objective. The relevant scheduling algorithm research of vehicle routing problem is always a hot topic in academic and engineering fields. According to the difference of constraint conditions of the VRP, it can be classified into different models. Traveling aalesman problem (TSP) is a simple model of vehicle routing problem and vehicle routing problem with capacitated (CVRP) is a widely used model of VRP and vehicle routing problem with time windows (VRPTW) is one of the most studied model of VRP. It is proved that all VRP problems belongs to NP problem. The intelligent algorithm is an effective method to solve the NP problems. Genetic algorithm (GA) is a kind of stochastic optimization algorithm, which emphasizes on the genetic level evolution. It guides algorithm to search best solutions through individual evaluation and genetic operators operation. Ant colony algorithm (ACA) also is a kind of stochastic optimization algorithm which draws lessons from foraging behavior of ants. The probability search scheme of ACA is constructed by imitating ants’ internal feedback and coordination mechanism in order to optimize objective. Quantum evolutionary algorithm (QEA) is a new type of swarm intelligence algorithms, which utilize the rotate quantum gate to guidance algorithm implementation the individual evolution. In this thesis, GA, QEA and ACA are used to solve TSP, CVRP and VRPTW, respectively.(1) In chapter two, a hybrid genetic algorithm (HGA) is presented for solving the TSP. Firstly, a diversified selection strategy is proposed to avoid the solution prematurity; Secondly, a new type of genetic operators operating mode is presented to guide the algorithm’s volution, which can overcome the randomness in the common genetic operators operating, reduce the time of individual evaluation, and improve the efficiency of the algorithm.(2) In chapter three, an effective hybrid quantum evolutionary qlgorithm (EHQEA) is presented for dealing with the CVRP. Firstly, a solution generation method based on the two-dimensional qubit measurement model (QMM) and visibility is proposed, which is used to find the promising regions over the solution space. Secondly, an Interchange operation based on the distance similar degree between customers is constructed to improve the quality of the solution. Thirdly, the Interchange and Inverse operations based on the problem’s property are proposed to construct a two-phase hybrid variable neighborhood local search, which help the algorithm to achieve a balance between the global and local search.(3) In chapter four, an effective hybrid Quantum ant colony algorithm (EHQACA) is presented for solving the VRPTW. Firstly, the observation method based on the two-dimensional qubit measurement model (QMM)、two-dimensional ant probability model and the property of time windows is designed to guide the global search. Secondly, the updateing mechanism is improved. The QMM’s difference can be updated based on the difference between the best and the current individuals’ evaluation value. So the accuracy of qubits observation model will be improved. Thirdly, the minimum cost of Insert and Exchange operations based on the time windows problem’s property are proposed to construct a two-phase hybrid variable neighborhood local search, which help the algorithm to optimize the distribution vehicle number. At the same time, a HOA optimization of vehicle distribution total distances is designed to enhance the local search ability under multiple constraints for the algorithm.In this thesis, all the proposed algorithms are tested by using the international standard test problems. A large number of simulation experiments and comparisons demonstrate the effectiveness and the robustness of the proposed hybrid intelligent optimization algorithm.