Application Of Ant Colony Algorithm In Vehicle Routing Problem

The Vehicle Routing Problem(VRP), a kind of combinational optimization problem, has been proved to be NP-complete problems. Solving NP-complete problem is one of the bottleneck tasks of today’s computer science and other fields. The traditional method can’t solve such problems within a reasonable time, people usually use heuristic algorithm such problems in order to find acceptable approximate solution within a reasonable time. Researching vehicle routing problem has important theoretical significance. A lot of problems in real life can be regarded as VRPs, among which vehicle scheduling in the logistics is a typical application of VRP. Establishing reasonable delivery lines can effectively reduce the product costs and improve the competitiveness of enterprises, and also can help to reduce traffic problems caused by logistics delivery such as:traffic congestion, traffic accidents, vehicle exhaust pollution. Therefore, the researching on solving vehicle routing problem can optimize delivery routes, thereby reduce transportation costs end exhaust pollution and other problems. So this research also has important practical significance.This thesis studies the application of ant colony algorithm in vehicle routing problem, Basing on the advantage of Savings based Ant System, three algorithms are poposed and used to solve the small-scale vehicle routing problem, large-scale vehicle routing problem, and multi-depot vehicle routing problem respectively. This work is the main research content of Fund of Engineering Reseach Center for Transportation Safety, Ministry of Education(Grant No.:WHUTERCTS2010A01), and also be supported by the National Natural Science Foundation of China (Grant No.:61170016).The main research work and research fruits are as follows:1、Basing on Savings-based Ant System(SbAS) proposed Improved Savings-based Ant System(ISbAS). To overcome SbAS’s defect that it is easy to fall into local optima, proposed two improving strategies:perturbation strategy and attractivness local search. perturbation strategy is that before the ants construct solutions randomly taboo several edges with high attractiveness to help the algorithm escape from local optima. Attractiveness local search is a new attractiveness-guiding local search, search direction is decided by attractiveness. we do our experiment on CMT standard test problems, discussed the parameter settings, and ISbAS were compared with SbAS and other existing algorithms. The experimental results show that ISbAS outperforms SbAS, verifying the effectiveness of the two improving strategies. Comparison with ant colony algorithms and other meta-heuristic algorithms show that the solution’s quality ISbAS find is at a high level. there is a defect of ISbAS, the computation time grows too fast as the problem scale, which restricts the ISbAS to solve the larger scale problems. 2, Taking advantage of ISbAS’s advantage that can find high quality solutions within little time when solving small-scale problems (50-75nodes), we propose Decompose Improved Savings-based Ant System(DISbAS). Firstly ISbAS use a small number of iterations solve the whole problem as the current solution. According to the current solution, the problem is decomposed into a number of small problems. Use ISbAS solve each subproblem and update the current solution, according to the solution of each sub-problem, iterate until meet the algorithm ending conditions.The experimental results of solving CMT problem show that, DISbAS has good performance, DISbAS performs comparable or better when comparing with current best algorithms. Contrast to ISbAS, when solving problems of scale more than150DISbAS use less computing time to obtain better solutions. DISbAS is more adapted to solving larger scale problems. Furthermore use large-scale standard test problems to verify DISbAS’s performance. Comparison experiment shows that DISbAS can solve large-scale problems effectively.3, Some logistics companies have multiple-depot, which prompts the research on Multiple-Depot Vehicle Routing Problem(MDVRP). To solve MDVRP, HACS is proposed. The HACS take the advantage of ant colony algorithm’s advantage that it is good at finding the region where the optimal solution may be and the tabu search’s advantage that it is good at finding the region where better solutions may be, and hybrid them to improve the search performance of the algorithms. Do experiment on p01, p02and p03of CGW standard test questions. HACS found all three problems’best-known solution, and the algorithm has a high stability, HACS can effectively solve MDVRP.