International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

Using an Ant Colony approach for Solving capacitated Vehicle Routing Problem with time Windows

    ,

Author Affiliations

  • 1Department of industrial management, Science and Research Branch, Islamic Azad University, Tehran, IRAN

Res. J. Recent Sci., Volume 4, Issue (2), Pages 30-35, February,2 (2015)

Abstract

In this paper, a capacitated vehicle routing problem with time windows (CVRPTW) is presented. In this work, a new idea for calculating the heuristic value to improve the performance of ant colony algorithms when solving capacitated vehicle routing problems with hard time windows is proposed. The performance of the model and the heuristic approach are evaluated by Solomon’s VRPTW benchmark problems. The results show that in 14 problem instances, our solutions are better than the best solutions reported for the VRPTW by other researchers in both total traveling distance and number of used vehicles. Our solutions superiority over the best solutions published in the literature are in instances R1, R2 and Particularly RC2 such a way that the average number of used vehicles are considerably less.

References

  1. Dantzig G., RamserB. and Hubert J., The Truck Dispatching Problem, Management Science, 6(1), 80–91 (1959)
  2. Solomon M.M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper Res, 35(2), 254–265 (1987)
  3. Laporte G., The vehicle routing problem : An overview of exact and approximate algorithms, Europe Journal of Operational Research, 59( 3), 345–358 (1992)
  4. Larsen J., Parallelization of the vehicle routing problem with time windows. Ph.D. thesis, Department of Mathematical Modelling, Technical University of Denmark, Lynghy, Denmark (1999)
  5. Lysgaard J., Letchford A.N. and Eglese, R.W., A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math Program, 100, 423–445 (2004)
  6. Taillard R.E., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661–73 (1993)
  7. Chiang W.C. and Russel R.A., Simulated annealing metaheuristic for the vehicle routing problem with time windows, Annals of Operations Research, 63, 3–27 (1996)
  8. Ombuki B., Ross B.J., Hanshar F., Multi-objective genetic algorithms for vehicle routing problem with time windows, App Intell, 24(1),17–30 (2006)
  9. Berger J., Barkaoui M., A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computers and Operations Research,31, 2037–2053 (2004)
  10. Cordeau J.F., Gendreau M., Laporte G., Potvin J.Y. and Semet, F., A guide to vehicle routing heuristics, Journal of the Operational Research Society, vol. 53(5), 512–522 (2002)
  11. Bräysy O., Gendreau M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transp Sci,39,104–118 (2005a)
  12. Bräysy O. and Gendreau M., Vehicle routing problem with time windows, part II: metaheuristics, Transp Sci, 39,119–139 (2005b)
  13. Pisinger D. and Ropke S., A general heuristic for vehicle routing problems, Comput Oper Res, 34,2403– 2435 (2007)
  14. Chand P., Mishra B.S.P. and Dehuri S., A multi objective genetic algorithm for solving vehicle routing problem, Int J Info Tech Knowl Mgmt, ,503–506 (2010)
  15. Wang C.H. and Li C.H., Optimization of an established multi-objective delivering problem by an improved hybrid algorithm, Expert Syst Appl, 38(4),4361–4367 (2011)
  16. Tavakkoli-Moghaddam R., Safaei N. and Shariat M.A., A multi-criteria vehicle routing problem with soft time windows by simulated annealing, J Indus Eng, 1(1),28–36 (2005)
  17. Tan K.C., Chew Y.H. and Lee L.H., A hybrid multi-objective evolutionary algorithm for solving vehicle routing problem with time windows, Comput Opt Appl, 34(1),115–15 (2006)
  18. Ghoseiri K. and Ghannadpour S.F., Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm, Appl Soft Comput, 10,1096–1107 (2010)
  19. Dorigo M. and Gambardella L.M., Ant Colony System: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, , 53–66 (1997)
  20. Solomon Benchmark Problems http://web.cba.neu.edu/msolomon/problems.html
  21. Best Known Solution http://www.sintef.no/TOP/ Problems/VRPTW/Solomon-benchmark/100- customers/
  22. Thompson P.M. and Psaraftis H.N., Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems, Operations Research, 41, 935946 (1993)
  23. Potvin J.Y. and Rousseau J.M., An Exchange Heuristic for Routing Problems with Time Windows, Journal of the Operational Research Society,46, 1433 1446 (1995)
  24. Homberger J. and H. Gehring, A two-phase hybrid metaheuristic for the vehicle routing problem with time windows, European Journal of Operational Research, 162 (1), 220-238 (2005)
  25. Mester D., Bräysy O. and Dullaert W., A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems, Expert Systems with Applications, 32(2), 508-517 (2007)
  26. Pisinger D, Ropke S, A General Heuristic for Vehicle Routing Problem, Department of Computer Science, University of Copenhagen (2005)
  27. Nagata Y., Bräysy O. and Dullaert W., A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows, Comput Oper Res, 37,724–737 (2010)
  28. Cordeau J.F. and Maischberger M., A parallel iterated tabu search heuristic for vehicle routing problems, Computers and Operations Research, 39(9), 2033–2205 (2012)