Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows
DOI:
https://doi.org/10.7494/dmms.2009.3.2.87Keywords:
simulated annealing, vehicle routing problem with time windows, bi-criterion optimizationAbstract
This article presents a new simulated annealing algorithm that provides very high quality solutions to the vehicle routing problem. The aim of described algorithm is to solve the vehicle routing problem with time windows. The tests were carried out with use of some well known instances of the problem defined by M. Solomon. The empirical evidence indicates that simulated annealing can be successfully applied to bi-criterion optimization problems.
References
Aarts E.H.L. & Korst J.H.M. (1989). Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. Chichester: Wiley.
van Laarhoven P.J.M. & Aarts E.H.L. (1987). Simulated Annealing: Theory and Applications. Mathematics and Its Applications, 37. Dordrecht: Springer. DOI: https://doi.org/10.1007/978-94-015-7744-1.
Berger J. & Barkaoui M. (2000). An improved hybrid genetic algorithm for the vehicle routing problem with time windows. In: Proceedings of the International ICSC Symposium on Computational Intelligence, part of the International ICSC Congress on Intelligent Systems and Applications (ISA’2000), University of Wollongong, Wollongong, Australia.
Bräysy O. & Gendreau M. (2005). Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Science, 39(1), pp. 104–118. DOI: https://doi.org/10.1287/trsc.1030.0056.
Bräysy O. & Gendreau M. (2005). Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Science, 39(1), pp. 119–139. DOI: https://doi.org/10.1287/trsc.1030.0057.
Černý V. (1985). A thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45(1), pp. 41–51. DOI: https://doi.org/10.1007/BF00940812.
Chiang W.-C. & Russell R.A. (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, 63, pp. 3–27. DOI: https://doi.org/10.1007/BF02601637.
Cordeau J.-F., Laporte G. & Mercier A. (2000). A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Working Paper CRT-00-03. Montreal: Centre for Research on Transportation, University of Montreal.
Cordeau J.-F., Desaulniers G., Desrosiers J., Solomon M.M. & Soumis F. (2002). The VRP with time windows. In: Toth P. & Vigo D. (Eds.), The Vehicle Routing Problem, pp. 157–193. Philadelphia: SIAM. DOI: https://doi.org/10.1137/1.9780898718515.ch7.
Cordeau J.-F., Laporte G. & Mercier A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8), pp. 928–936. DOI: https://doi.org/10.1057/palgrave.jors.2601163.
Cortés J. & Bullo F. (2009). Nonsmooth coordination and geometric optimization via distributed dynamical systems. SIAM Review, 51(1), pp. 163–189. DOI: https://doi.org/10.1137/080737551.
Czech Z.J. (2001). Parallel simulated annealing for the delivery problem. In: Proceedings of the Ninth Euromicro Workshop on Parallel and Distributed Processing, Mantova, Italy, pp. 219–226. IEEE Computer Society. DOI: https://doi.org/10.1109/EMPDP.2001.905046.
Desrochers M., Desrosiers J. & Solomon M.M. (1992). A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2), pp. 342–354. DOI: https://doi.org/10.1287/opre.40.2.342.
Fisher M.L., Jörnsten K.O. & Madsen O.B.G. (1997). Vehicle routing with time windows: Two optimization algorithms. Operations Research, 45(3), pp. 488–492. DOI: https://doi.org/10.1287/opre.45.3.488.
Gambardella L.M., Taillard É. & Agazzi G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne D., Dorigo M. & Glover F. (Eds.), New Ideas in Optimization, pp. 63–76. London: McGraw-Hill.
Gehring H. & Homberger J. (1999). A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen K., Mäkelä M.M. & Toivanen J. (Eds.), Proceedings of EUROGEN99 – Short Course on Evolutionary Algorithms in Engineering and Computer Science, pp. 57–64. Reports of the Department of Mathematical Information Technology, Series A, No. A 2/1999. Jyväskylä: University of Jyväskylä.
Hajek B. (1988). Cooling schedules for optimal annealing. Mathematics of Operations Research, 13(2), pp. 311–329. DOI: https://doi.org/10.1287/moor.13.2.311.
Halse K. (1992). Modeling and Solving Complex Vehicle Routing Problems [PhD dissertation]. Lyngby: Institute of Mathematical Statistics and Operations Research, Technical University of Denmark.
Homberger J. & Gehring H. (1999). Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR: Information Systems and Operational Research, 37(3), pp. 297–318. DOI: https://doi.org/10.1080/03155986.1999.11732386.
Ibaraki T., Imahori S., Kubo M., Masuda T., Uno T. & Yagiura M. (2005). Effective local search algorithms for routing and scheduling problems with general time-window constraints. Transportation Science, 39(2), pp. 206–232. DOI: https://doi.org/10.1287/trsc.1030.0085.
Kirkpatrick S., Gelatt C.D. Jr. & Vecchi M.P. (1983). Optimization by simulated annealing. Science, 220(4598), pp. 671–680. DOI: https://doi.org/10.1126/science.220.4598.671.
Kohl N. & Madsen O.B.G. (1997). An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation. Operations Research, 45(3), pp. 395–406. DOI: https://doi.org/10.1287/opre.45.3.395.
Lenstra J.K. & Rinnooy Kan A.H.G. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), pp. 221–227. DOI: https://doi.org/10.1002/net.3230110211.
Li H. & Lim A. (2003). Local search with annealing-like restarts to solve the VRPTW. European Journal of Operational Research, 150(1), pp. 115–127. DOI: https://doi.org/10.1016/S0377-2217(02)00486-1.
Osman I.H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41, pp. 421–451. DOI: https://doi.org/10.1007/BF02023004.
Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H. & Teller E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21(6), pp. 1087–1092. DOI: https://doi.org/10.1063/1.1699114.
Reeves C.R. (Ed.) (1993). Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications.
Sariklis D. & Powell S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51(5), pp. 564–573. DOI: https://doi.org/10.1057/palgrave.jors.2600924.
Shaw P. (1997). A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. Technical Report. Glasgow: APES Group, Department of Computer Science, University of Strathclyde.
Shaw P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M. & Puget J.-F. (Eds.), Principles and Practice of Constraint Programming – CP98. Lecture Notes in Computer Science, 1520, pp. 417–431. Berlin–Heidelberg: Springer. DOI: https://doi.org/10.1007/3-540-49481-2_30.
Solomon M.M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), pp. 254–265. DOI: https://doi.org/10.1287/opre.35.2.254.
Taillard É., Badeau P., Gendreau M., Guertin F. & Potvin J.-Y. (1997). A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31(2), pp. 170–186. DOI: https://doi.org/10.1287/trsc.31.2.170.
Tan K.C., Lee L.H. & Ou K. (2001). Hybrid genetic algorithms in solving vehicle routing problems with time window constraints. Asia-Pacific Journal of Operational Research, 18(1), pp. 121–130.
Tang J., Pan Z., Fung R.Y.K. & Lau H. (2009). Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems, 160(5), pp. 683–695. DOI: https://doi.org/10.1016/j.fss.2008.09.016.
Woch M. (2004). Rozwiązanie problemu dostaw z oknami czasowymi za pomocą symulowanego wyżarzania. Studia Informatica, 25(2/58), pp. 67–80. URL: https://delibra.bg.polsl.pl/dlibra/publication/82318/edition/73224.
Woch M. (2008). Zarządzanie kosztami zapasów w systemie zintegrowanym klasy ERP Microsoft Dynamics NAV 4.0. In: Knosala R. (Ed.), Komputerowo Zintegrowane Zarządzanie, Vol. 2, pp. 552–557. Opole: Oficyna Wydawnicza Polskiego Towarzystwa Zarządzania Produkcją.
Woch M. & Łebkowski P. (2008). Manufacturing cost management in Microsoft Dynamics NAV 5.0 – A case study. Total Logistic Management, 1, pp. 185–194. URL: https://repo.agh.edu.pl/handle/AGH/110729.
Woch M. & Łebkowski P. (2008). Rozwiązanie problemu dostaw z oknami czasowymi w systemie Microsoft Dynamics NAV 5.0. In: Zarządzanie przedsiębiorstwem – teoria i praktyka: XI Międzynarodowa Konferencja Naukowa, Kraków, 27–29 listopada 2008: materiały konferencyjne, pp. 1–8. Kraków: Wydział Zarządzania AGH.
Woch M. & Łebkowski P. (2009). Rozwiązanie problemu dostaw z oknami czasowymi w systemie Microsoft Dynamics NAV 5.0. In: Łebkowski P. (Ed.), Innowacyjno-efektywnościowe problemy teorii i praktyki zarządzania, pp. 73–80. Kraków: AGH Uczelniane Wydawnictwa Naukowo-Dydaktyczne. ISBN 978-83-7464-248-4.
