PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 3 | nr 1/2 | 87--100
Tytuł artykułu

Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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. (original abstract)
Rocznik
Tom
3
Numer
Strony
87--100
Opis fizyczny
Twórcy
autor
  • AGH University of Science and Technology Kraków, Poland
  • AGH University of Science and Technology Kraków, Poland
Bibliografia
  • Aarts, E.H.L., Korst, J.H.M.(1989). Simulated annealing and Boltzmann machines. Wiley, Chichester.
  • Aarts E.H.L., van Laarhoven P.J.M. (1987). Simulated annealing: Theory and applications. Wiley, New York.
  • Berger, J., Barkaoui, M. (2000). An Improved Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. 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. (2001). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Working Paper, SINTEF Applied Mathematics, Department of Optimisation, Norway.
  • Bräysy, O., Gendreau, M. (2001). Vehicle Routing Problem with Time Windows, Part II: Metaheuristics., Working Paper, SINTEF Applied Mathematics, Department of Optimisation, Norway.
  • Cerny, V.(1985). A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm, J. of Optimization Theory and Applic. 45, pp. 41-55.
  • Chiang, W.-C., Russell, R.A. (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research 63, 3-27.
  • Cordeau, J.F., Laporte, G., Mericier, A.,(2000) A unified tabu search heuristic for vehicle routing problems with time windows. Technical report CRT-00-03, Centre for Research on Transportation, Montreal, Canada.
  • Cordeau, J.F., Desaulniers, G., Desrosiers, J., Solomon, M.M., Soumis, F. (2001). The VRP with Time Windows. To appear in The Vehicle Routing Problem, Chapter 7, P. Toth and D. Vigo (eds), SIAM Monographs on Discrete Mathematics and Applications.
  • 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, pp. 928-936.
  • Cortes, J., Bullo, F. (2009). Nonsmooth Coordination and Geometric Optimization via Distributed Dynamical Systems. SIAM Review, 51(1).
  • Czech, Z.J. (2001). Parallel simulated annealing for the delivery problem. Proc. of the 9th EuromicroWorkshop on Parallel and Distributed Processing, Mantova, Italy, 219-2261.
  • Desrochers, M., Desrosiers, J., Solomon, M. (1992). A New optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40, 342-354, 1992.
  • Fisher, M.L., Jornsten, K.O., Madsen, O.B.G. (1997). Vehicle routing with time windows - two optimization algorithms. Opns. Res. 45, pp. 488-498.
  • Gambardella, L.M., Taillard, E., Agazzi, G. (1999). MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. In: New Ideas in Optimization, D. Corne, M. Dorigo and F. Glover (eds.), pp. 63-76, McGraw-Hill, London.
  • Gehring, H., Homberger, J. (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. No. A 2/1999, University of Jyväskylä, Finland, pp. 57-64.
  • Hajek, B. (1988). Cooling schedules for optimal annealing. MOR 13, pp. 311-329.
  • Halse, K. (1992). Modeling and solving complex vehicle routing problems. PhD dissertation no. 60, Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, DK-2800 Lyngby, Denmark.
  • Homberger, J., Gehring, H. (1999). Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows. INFOR 37, pp. 297-318.
  • Ibaraki, T., Kubo, M., Masuda, T., Uno, T., Yagiura, M. (2001). Effective local search algorithms for the vehicle routing problem with general time windows. Working paper, Department of Applied Mathematics and Physics, Kyoto University, Japan.
  • Kirkpatrick, S., Gellat, C.D., Vecchi, M.P. (1983). Optimization by simulated annealing, Science 220, pp. 671-680.
  • Kohl, N., Madsen O.B.G., (1997). An optimization algorithm for the vehicle routing problem with time windows based on lagrangean relaxation, Opns. Res. 45, pp. 395-406.
  • Lenstra J., Rinnooy, K.A. (1981). Complexity of vehicle routing and scheduling problems, Networks 11, pp. 221-227.
  • Li, H., Lim, A., Huang, J. (2001). Local search with annealing-like restarts to solve the VRPTW. Working paper, Department of Computer Science, National University of Singapore.
  • Osman, I.H. (1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem. Annals of Operations Research 41, pp. 421-451.
  • Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E. (1953). Equation of state calculation by fast computing machines. Journ. of Chem. Phys. 21, pp. 1087-1091.
  • Reeves C.R. (1993). Modern Heuristics Techniques for Combinatorial Problems. Halsted Press, New York.
  • Sariklis, D., Powell, S. (2000). A Heuristic Method for the Open Vehicle Routing Problem. Journal of the Operational Research Society, 51, pp. 564-573. ,
  • Shaw, P. (1997). A new local search algorithm providing high quality solutions to vehicle routing problems. Working paper, University of Strathclyde, Glasgow, Scotland.
  • Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. [in:] Principles and Practice of Constraint Programming - CP98, Lecture Notes in Computer Science, M. Maher and J.-F. Puget (Eds), Springer-Verlag, New York, pp. 417-431.
  • Solomon, M.M. (1987). Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operations Research 35, pp. 254-265.
  • 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, pp. 170-186.
  • 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, pp. 121-130.
  • Tang, J., Pan, Z., Fung, R., Lau, H. (2009). Vehicle Routing Problem with Fuzzy Time Windows. In: Fuzzy Sets and Systems Vol. 160(5), pp. 683-695, Amsterdam.
  • Woch, M. (2004). Rozwiązanie problemu dostaw z oknami czasowymi za pomocą symulowanego wyżarzania. STUDIA INFORMATICA Vol. 25, No. 2 (58), s. 67-81, Gliwice.
  • Woch, M. (2008). Zarządzanie kosztami zapasów w systemie zintegrowanym klasy ERP Microsoft Dynamics NAV 4.0. [w:] R. Knosala [red.], Komputerowo Zintegrowane Zarządzanie, Oficyna Wydawnicza Polskiego Towarzystwa Zarządzania Produkcją, T. 2, s. 552-557, Opole.
  • Woch, M., Łebkowski, P. (2008). Manufacturing Cost Management in Microsoft Dynamics NAV 5.0 - Case Study.
  • Woch, M., Łebkowski, P. (2008). Rozwiązanie problemu dostaw z oknami czasowymi w systemie Microsoft Dynamics NAV 5.0. XI Międzynarodowa Konferencja Naukowa Zarządzanie Przedsiębiorstwem - Teoria i Praktyka, Kraków 27-28.11.2008.
  • Woch, M., Łebkowski, P. (2009). Rozwiązanie problemu dostaw z oknami czasowymi w systemie Microsoft Dynamics NAV 5.0. [w:] Łebkowski P. (red.), Innowacyjno-efektywnościowe problemy teorii i praktyki zarządzania, AGH Uczelniane Wydawnictwa Naukowo-Dydaktyczne, s. 73-80, Kraków.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171387731

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.