Research On Ant Colony Algorithms For Vehicle Routing Problems

Distribution plays an important role in logistics system, and takes account for considerable proportion in variable costs in logistics. Vehicle routing problem is the key question and one of the research hot spots in the logistics distribution system. Optimizing vehicle routing can increase economic benefit and realize the logistics scientifically. So it has great academic and practical value to research the vehicle routing problems.Based on summarizing the researching actualities of vehicle routing problems in logistics distribution in country and abroad, the author analyzed a few models of VRP and researches the ant colony algorithms for these problems.The main contents of this thesis are followed:(1) Vehicle routing problem with time windows is one of the basic VRP models, and has received lots of researches. A basic ant colony system is proposed to solve the problem, in addition, how the parameters and also the ant actions of ACO influence the performance of the algorithm are researched in detail by means of simulations.(2) Pickup and delivery problem with time windows is a much more general model compared with the VRPTW. To satisfy the subjection of the PDPTW, we design an ant colony algorithm whose solution construction is based on the insertion algorithm, and two kinds of pheromone are introduced to guide the solution construction procedures. The simulation results show the effectiveness of the algorithm.(3) An ant colony algorithm for vehicle routing problem with stochastic demands and soft time windows is researched. Firstly, the mathematical model of the problem is given with the introduction of the current relative research background. Based on the pre-optimization strategy, the violation of time windows is penalized by adding penalty information into the objective function of the ant colony algorithm, which transfers the mutli-objective problem to the single objective problem. Lastly, test instances are desiged and the algorithm is tested by the experiments on different instances.(4) Vehicle routing problem model with fuzzy travel time based on the credibility measure is given and a multiple ant colony system is proposed to solve the problem, which minimizes the number of vehicles used and the travel distance respectively.