Title: A two stage method for VRP based on the improved ant colony algorithm

Authors: Yong Liu; Sheng Wang; Fangmin Dong; Dong Ren

Addresses: Institute of Intelligent Vision and Image Information, China Three Gorges University, Yichang 443002, China ' Institute of Intelligent Vision and Image Information, China Three Gorges University, Yichang 443002, China ' Institute of Intelligent Vision and Image Information, China Three Gorges University, Yichang 443002, China ' Institute of Intelligent Vision and Image Information, China Three Gorges University, Yichang 443002, China

Abstract: A two stage method for the VRP based on the improved ant colony algorithm is proposed in this paper. On the first stage of the method, a simplified ant colony algorithm is used to divide all the material demand locations into several groups for each vehicle, and different division ways of the material demand locations can be obtained effectively, then saving algorithm is used to assess all division ways, some better division ways are chosen. On the second stage, the improved ant colony algorithm is applied in solving the travelling salesman problems in those better division ways, then the solutions of the TSP are combined together to be the best solution of the VRP corresponding with the division way. Every solution is compared with each other, the best one is the last solution of the VRP got from the two stage method. Finally, the effectiveness and superiority are verified through two cases.

Keywords: vehicle routing problem; VRP; travelling salesman problem; TSP; ant colony optimisation; ACO; saving algorithm.

DOI: 10.1504/IJMIC.2013.052299

International Journal of Modelling, Identification and Control, 2013 Vol.18 No.2, pp.174 - 181

Published online: 31 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article