Wenxue Ran
Department of Logistics, Yunnan University of Finance and Economics, Kunming, China
Li Liu
Department of Logistics, Yunnan University of Finance and Economics, Kunming, China
Guomin Yang
Department of Logistics, Yunnan University of Finance and Economics, Kunming, China
ABSTRACT
Vehicle routing problem is proved as a NP-Hard problem. VRPTW involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and pre-defined time windows. In this study, a new hybrid algorithm based on Ant Colony Optimization (ACO) and Genetic Algorithm (GA) is provided to solve the vehicle routing problem with time windows. The proposed algorithm combines the advantages of ACO and GA. Then a mathematical programming formulation for the problem is given. The performance of the model and the heuristic approaches are evaluated using instances generated from a set of classic examples. Results of numerical experiments show that the proposed algorithm is an effective tool in solving VRPTW problem.
PDF References Citation
How to cite this article
Wenxue Ran, Li Liu and Guomin Yang, 2013. A Hybrid Ant Colony Algorithm for Vehicle Routing Problem with Time Windows. Information Technology Journal, 12: 5701-5706.
DOI: 10.3923/itj.2013.5701.5706
URL: https://scialert.net/abstract/?doi=itj.2013.5701.5706
DOI: 10.3923/itj.2013.5701.5706
URL: https://scialert.net/abstract/?doi=itj.2013.5701.5706
REFERENCES
- Baldacci, R., A. Mingozzi and R. Roberti, 2011. New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res., 59: 1269-1283.
CrossRef - Braysy, O. and M. Gendreau, 2005. Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transport. Sci., 39: 104-118.
CrossRefDirect Link - Tas, D., N. Dellaert, T. van Woensel and T. de Kok, 2013. Vehicle routing problem with stochastic travel times including soft time windows and service costs. Comput. Oper. Res., 40: 214-224.
CrossRef - Lang, M.L. and S.J. Hu, 2010. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm. Chin. J. Manage. Sci., 10: 51-56.
Direct Link - Rochat, Y. and E.D. Taillard, 1995. Probabilistic diversification and intensification in local search for vehicle routing. J. Heurist., 1: 147-167.
CrossRefDirect Link - Vidal, T., T.G. Crainic, M. Gendreau and C. Prins, 2013. A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Comput. Oper. Res., 40: 475-489.
CrossRef - Gehring, H. and J. Homberger, 1999. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. Proceedings of EUROGEN99-Short Course on Evolutionary Algorithms in Engineering and Computer Science, Reports of the Department of Mathematical Information Technology, Series A. Collections, No. A 2/1999, (EUROGEN'99), University of Jyvaskyla, Finland, pp: 57-64.
Direct Link - Dantzig, G.B. and J.H. Ramser, 1959. The truck dispatching problem. Manage. Sci., 6: 80-91.
CrossRefDirect Link