Improved Ant Colony System Algorithm To Solve The Vehicle Routing Problem


Abstract in English

We study in this paper the possibility of contribution in solving the vehicle routing problem (VRP) by using the improved ant colony system ( IACS) , which is one of the optimization problems that, because of its Real Life applications, has attracted a lot of attention at the present time. It is a problem of the NP-hard type. However, because of the complication of polynomial time there is still no algorithm providing us with the optimal solution of this problem. All the used algorithms give solutions that are close to the optimal one . We present the improved ant colony system algorithm that, based on ant colony system algorithm, possesses a new state transition rule, a new pheromone updating rule and diverse local search approaches . The experimental results of the proposed ( IACS) algorithm compared with the results of well-known standard tests show that our IACS yields better solutions than the other ant algorithms in the literature and is competitive with other meta-heuristic approaches in terms of quality(run time and number of good solutions ).

References used

DANTZIG, G.B.; RAMSER, J. H., “The Truck Dispatching Problem," Management Science, Vol. 6, No. 1, 1959, pp. 79-89
LAPORTE, G., “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, Vol. 59, No. 3, 1992, pp. 345-358
FISHER .M., "Vehicle Routing. , editors. Network routing, Vol. 8, Handbooks of Operations Research and Management Science, Amsterdam: Elsevier, " chap.1, 1995, pp:1-31
GILLETT, B.E.; L.R. MILLER, "A Heuristic Algorithm for the Vehicle Dispatch Problem," Oper Res 22, 1974, pp :341–347
GOLEN, B.L; ASSAD,A.A., "Vehicle Routing: Methods and Studies," eds. North Holland, Amsterdam,1988

Download