Ant Colony Algorithm Optimization for Vehicle Routing Problem with Time Windows and Capacity Constraint

Authors

1 Associate Professor, Civil Engineering Department, Faculty of Engineering, University of Zanjan, Zanjan, Iran

2 M.Sc., Grad., Civil Engineering Department, Islamic Azad University, Ahar Branch Iran

Abstract

Vehicle routing problem has an important place in applied research. Finding the right path to solve Vehicles Routing Problem is one of the most significant measures taken in recent decades. In this routing method, each delivery must be made within time windows, and not to mention the fact that each customer must be visited only once. At the present paper, Ant Colony Algorithm Optimization for Vehicle Routing Problem with Time Windows and Capacity Constraint (ACOVRPTWCC) has been utilized. First, Ant Algorithm for Vehicle routing Problem with Time Windows and vehicle Capacity Constraint classic has been implemented. In this way, of 9 problem implemented through 100 customers in 6 problems, solutions are optimized. Then, algorithm is carried out on a new type of vehicle routing problem with time window. The most decrease of cost related to R206 problem by 32.72 percent minimization of cost. For any problem, on the average, 20 second time is needed.
 
 

Keywords

References

 
-Esmat Zare-Reisabadi, S. Hamid Mirmohammadi, (2015), Site dependent vehicle routing problem with soft time window: Modeling and solution approach, Accepted 2 September, Computers & Industrial Engineering 90 pp.177–185.
-­Er. GurpreetSingh, Dr. Vijay Dhir, (2014), “Open Vehicle Routing Problem by Ant Colony Optimization”, International Journal of Advanced Computer Science and Applications, Vol. 5, No. 3.
-http://neo.lcc.uma.es/radi-aeb/WebVRP.
-Geraldine Heilporn, JeanFrancois Cordeau, Gilbert Laporte, (2010), “The Delivery Man Problem with Time Windows, Discrete Optimization,Volume 7, Issue 4, November,  PP. 269–282.
-­John E. Bell, Patrick R. McMullen, (2004), “Ant colony optimization techniques for the vehicle routing problem”, Advanced Engineering Informatics 18, pp. 41–48.
-­Koushik Venkata Narasimha, Elad Kivelevitch, Balaji Sharma, Manish Kumar, (2013), “An ant colony optimization technique for solving min–max Multi- Depot Vehicle Routing Problem”, Accepted 6 May, Swarm and Evolutionary Computation 13, pp. 63–73.
-Marco Dorigo and Krzysztof Socha, (2007), “An Introduction to Ant Colony Optimization, IRIDIA -Technical Report Series ISSN 1781-3794”, April 30.
-Marcus E. McNabb, Jeffery D. Weir, Raymond R. Hill, Shane N. Hall, (2015), Testing local search move operators on the vehicle routing problem with split deliveries and time windows, Available online 26 November, Computers & Operations Research 56, pp.93–109.
-Martin Reed, Aliki Yiannakou, Roxanne Evering, (2014), “An ant colony algorithm for the multi-compartment vehicle routing problem”, Accepted 23 October, Applied Soft Computing 15, pp.­169–176.
-M.Schyns, (2015), “An ant colony system for responsive dynamic vehicle routing,  Accepted 6 April”, European Journal of Operational Research 245, pp.704–718.
 -Mohamed M.S. Abdulkader, Yuvraj Gajpal, Tarek Y. ElMekkawy, 2015, Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem, Accepted 11 August 2015, Applied Soft Computing 37 pp.196–203.
-R.­Tavakkoli-Mogaddam, M. Alinaghian, A. Salamatbakhsh, N. Norouzi, (2011), “A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing”, Journal of Manufacturing Systems Volume 30, Issue 2, April 2011, pp. 83–92.
-Yingtao Ren, Maged Dessouky, and Fernando Ordóñez, (2010),
“The Multi-shift Vehicle Routing Problem with Overtime, Daniel J. Epstein Department of Industrial and Systems Engineering University of Southern California”, Vol. 37 Issue 11, November, pp.1987-1998.
-Zhang Xiao, Wang Jiang-qing, (2012), “Hybrid Ant Algorithm and Applications for Vehicle Routing Problem”, International Conference on Solid State Devices and Materials Science, Physics Procedia 25, pp.­1892­–­1899. 
-Yi Yunfei, Lin Xiaodong, Sheng Kang, and Cai Yongle, 2015, An Improved Ant Colony Algorithm to Solve Vehicle Routing Problem with Time Windows, Springer International Publishing Switzerland 2015, D.-S. Huang et al. (Eds.): ICIC 2015, Part I, LNCS 9225, pp. 11–22, 2015.

Files

Share

How to cite

Statistics