Study On Vehicle Routing Problem Based On The Hysteretic Optimization

The Vehicle Routing Problem (VRP) is a typical problem related to dispatching subject in logistics and also one of the most important and intensively studied combinatorial optimization problems. This thesis studies on the Capacitated Vehicle Routing Problem (CVRP). Based on the mathematical programming model, hysteretic optimization (HO) algorithm and an improved HO optimization algorithm are used respectively to study the CVRP. The experimental results with benchmark problems are given including compared data and analysis with other optimization algorithms, such as particle swarm optimization, genetic algorithms, etc.Firstly, the basic theory of CVRP is introduced. In this problem, all customers have a pre-determined demand, and each vehicle has the same capacity constraints. We have to decide a fleet of vehicles which start from the depot to serve these customers with a minimum cost, including which vehicle serve specified customers and the visiting sequence. We first give its graph model and mathematical model. Based a detailed description of basic principles of several common intelligent optimization methods, the process and steps of these algorithm on how to be applied to CVRP is given for each algorithm. respectively, which including simulated annealing algorithm, tabu search algorithm, genetic algorithms and ant colony algorithm.Then, hysteretic optimization algorithm (HO) is applied for the first time in this thesis to the study of CVRP. The hysteretic optimization (HO) is a physical optimization algorithm initially based on spin glass model and was originally proposed by G. Zarand et al in 2002. The initiative of the algorithm is that it uses the AC-demagnetization process to achieve the purpose for optimization process. Specifically, the objective function is optimized step by step by introducing an alternating external field with gradually attenuated amplitude into the original model and alternately switching its direction and at last, it approaches to the optimal solution. Zarand, once applied it to a travelling salesman problem (TSP) with 100 cities and verified its efficiency. In this study, we successfully apply HO to CVRP and the simulation results show that HO is easy to get the approximate optimal solution and can compete well with other popular intelligent optimization algorithms.Then, an improved HO algorithm is extended and successfully exploited in this thesis to study the CVRP. As the design of HO algorithm is generally more complicated than other intelligent optimization algorithms such as Simulated Annnealing (SA), in addition, the distance defination over the configuration space is much troublesome for general optimization problem, an impvoed HO algorithm was proposed for CVRP. By generalizing the external magnetic field, and set the abrupt avalanche point, we further impoved the CVRP optimization solution and make the algorithm simpler, faster and more general.The conclusion and the future work are discussed in the end of this thesis.