PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Adaptive threads co-operation schemes in a parallel heuristic algorithm for the vehicle routing problem with time windows

Treść / Zawartość
Identyfikatory
Warianty tytułu
PL
Adaptacyjne schematy kooperacji wątków w równoległym heurystycznym algorytmie dla problemu trasowania pojazdów z oknami czasowymi
Języki publikacji
EN
Abstrakty
EN
The influence of the co-operation frequency of threads in a parallel heuristic algorithm to solve the vehicle routing problem with time windows on the accuracy of solutions is investigated. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger's benchmarking tests. Two adaptive co-operation schemes are proposed and experimentally evaluated.
PL
Wyznaczanie tras dla pojazdów z oknami czasowymi (ang. vehicle routing problem with time windows) jest problemem optymalizacji dyskretnej należącym do klasy problemów NP-trudnych. Istnieją metody heurystyczne rozwiązywania problemu, pozwalające wyznaczyć w rozsądnym czasie rozwiązania nieoptymalne o koszcie bliskim kosztowi rozwiązania optymalnego, takie jak symulowane wyżarzanie, przeszukiwanie tabu, algorytmy genetyczne czy algorytmy memetyczne. Wprzypadku algorytmów dwustopniowych, w pierwszej fazie minimalizowana jest liczba tras, a w fazie drugiej całkowita przebyta odległość. Flota składa się z pojazdów o jednakowej, zdefiniowanej pojemności, która nie może zostać przekroczona, a obsługa klientów musi rozpocząć się w czasie trwania ich okien czasowych.
Rocznik
Strony
191--203
Opis fizyczny
Bibliogr. 34 poz., rys.
Twórcy
autor
autor
  • Institute of Informatics, Silesian University of Technology ul. Akademicka 16, 44-100 Gliwice, Poland, Jakub.Nalepa@polsl.pl
Bibliografia
  • 1. J.F. Bard, G. Kontoravdis, G. Yu: A branch-and-cut procedure for the vehicle routing problem with time windows. Transportation Science, 36(2), 250–269, 2002.
  • 2. J. Berger, M. Barkaoui: A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Computers and Operations Research, pages 2037–2053, 2004.
  • 3. M. Blocho, Z.J. Czech: An improved route minimization algorithm for the vehicle routing problem with time windows. Studia Informatica, 32(99), 5–19, 2010.
  • 4. M. Blocho, Z.J. Czech: A parallel EAX-based algorithm for minimizing the number of routes in the vehicle routing problem with time windows. In Proceedings of the Fifth Symposium on Advances of High Performance Computing and Networking, AHPCN’12,2012.
  • 5. A. Chabrier: Vehicle routing problem with elementary shortest path based column generation.Comput. Oper. Res., 33(10), 2972–2990, 2006.
  • 6. Ch.-B. Cheng, K.-P. Wang: Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm. Expert Syst. Appl., 36(4), 7758–7763, 2009.
  • 7. J. Cordeau, G. Laporte, É. Hautes, É. Commerciales, L.C.D. Gerad: A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52, 928–936, 2001.
  • 8. A. Debudaj-Grabysz, Z.J. Czech: A concurrent implementation of simulated annealing and its application to the VRPTW optimization problem. In Distributed and Parallel Systems, volume 777 of The Kluwer International Series in Engineering and Computer Science, pages 201–209. Springer US, 2005.
  • 9. CI TASK. Website, 2011. http://www.task.gda.pl/kdm/sprzet/ Galera.
  • 10. H. Gehring, J. Homberger: Parallelization of a two-phase metaheuristic for routing problems with time windows. Journal of Heuristics, 8(3), 251–276, 2002.
  • 11. S.C. Ho, D. Haugland: A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers and Operations Research, 31, 1947–1964, 2002.
  • 12. J. Homberger, H. Gehring: Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR, 37, 297–318, 1999.
  • 13. Problems and benchmarks, VRPTW. Website, 2011. http://www.sintef.no/Projectweb/TOP/VRPTW/Homberger-benchmark/.
  • 14. S. Irnich, D. Villeneuve: The shortest-path problem with resource constraints and k-cycle elimination. INFORMS J. on Computing, 18(3), 391–406, 2006.
  • 15. M. Jepsen, B. Petersen, S. Spoorendonk, D. Pisinger: A non-robust branchand- cut-andprice algorithm for the vehicle routing problem with time windows. Technical Report 06-03, DIKU, University of Copenhagen, Denmark, 2006.
  • 16. B. Kallehauge, J. Larsen, O.B.G. Madsen: Lagrangian duality applied to the vehicle routing problem with time windows. Comput. Oper. Res., 33(5), 1464–1487, 2006.
  • 17. I. Kamkar, M. Poostchi, M.R.A. Totonchi: A cellular genetic algorithm for solving the vehicle routing problem with time windows. In Soft Computing in Industrial Applications, volume 75 of Advances in Intelligent and Soft Computing, pages 263–270. Springer, Berlin, Heidelberg, 2010.
  • 18. H. Kanoh, S. Tsukahara: Solving real-world vehicle routing problems with time windows using virus evolution strategy. Int. J. Know.-Based Intell. Eng. Syst., 14(3), 115–126, 2010.
  • 19. N. Labadi, Ch. Prins, M. Reghioui: A memetic algorithm for the vehicle routing problem with time windows. RAIRO – Operations Research, 42(3), 415–431, 2008.
  • 20. D. Mester, O. Bräysy: Active guided evolution strategies for large-scale vehicle routing problems with time windows. Comput. Oper. Res., 32(6), 1593– 1614, 2005.
  • 21. Y. Nagata, O. Bräysy: A powerful route minimization heuristic for the vehicle routing problem with time windows. Operation Research Letters, 37(5), 333–338, 2009.
  • 22. Y. Nagata, O. Bräysy, W. Dullaert: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Comput. Oper. Res., 37(4), 724–737, 2010.
  • 23. J. Nalepa, Z.J. Czech: A parallel heuristic algorithm to solve the vehicle routing problem with time windows. Studia Informatica, 33(1), 91–106, 2012.
  • 24. K.-W. Pang: An adaptive parallel route construction heuristic for the vehicle routing problem with time windows constraints. Expert Syst. Appl., 38(9), 11939– 11946, 2011.
  • 25. J.-Y. Potvin, J.-M. Rousseau: A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 66(3), 331–340, 1993.
  • 26. J.-Y. Potvin, J.-M. Rousseau: An exchange heuristic for routing problems with time windows. Journal of the Operational Research Society, 46, 1433–1446, 1995.
  • 27. Ch. Qi, Y. Sun: An improved ant colony algorithm for VRPTW. In Proceedings of the 2008 International Conference on Computer Science and Software Engineering – Volume 01, pages 455–458, Washington, DC, USA, 2008. IEEE Computer Society.
  • 28. R.A. Russell: Hybrid heuristics for the vehicle routing problem with time windows. Transportation Science, 29(2), 156, 1995.
  • 29. R. Skinderowicz: Co-operative, parallel simulated annealing for the VRPTW. In Proceedings of the Third international conference on Computational collective intelligence:technologies and applications – Volume Part II, ICCCI’11, pages 495– 504, Berlin, Heidelberg, 2011. Springer-Verlag.
  • 30. M.M. Solomon: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35, 254–265, 1987.
  • 31. X. Tan, X. Zhuo, J. Zhang: Ant colony system for optimizing vehicle routing problem with time windows (VRPTW). In Proceedings of the 2006 international conference on Computational Intelligence and Bioinformatics – Volume Part III, ICIC’06, pages 33–38, Berlin, Heidelberg, 2006. Springer-Verlag.
  • 32. P.M. Thompson, H.N. Psaraftis: Cyclic transfer algorithms for multivehicle routing and scheduling problems. Oper. Res., 41(5), 935–946, 1993.
  • 33. Z. Ursani, D. Essam, D. Cornforth, R. Stocker: Localized genetic algorithm for vehicle routing problem with time windows. Appl. Soft Comput., 11(8), 5375–5390, 2011.
  • 34. Y. Zhong, X. Pan: A hybrid optimization solution to VRPTW based on simulated annealing. In Automation and Logistics, 2007 IEEE International Conference on, pages 3113–3117, 2007.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUJ8-0026-0002
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ć.