Równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi

• Autorzy: Nalepa J. , Czech Z.

Warianty tytułu

EN

A parallel heuristic algorithm to solve the vehicle routing problem with time windows

• Języki publikacji: EN

Abstrakty

EN

The following article presents a parallel heuristic algorithm to solve the vehicle routing problem with time windows (VRPTW). The fleet size is minimized in the first phase and the traveled distance in the second one. The objective is to compare the accuracy of solutions obtained by the sequential and the parallel heuristics in the first phase. The influence of the population diversification and child generation on the accuracy is analyzed together with the speedups for the memetic algorithm in the second phase. The accuracy of solutions is defined as their proximity to the best known solutions of Gehring and Homberger’s benchmarking tests.

PL

W niniejszej pracy został przedstawiony równoległy heurystyczny algorytm dla rozwiązywania problemu trasowania pojazdów z oknami czasowymi. W pierwszej fazie jest minimalizowany rozmiar floty, a w drugiej fazie całkowita przebyta odległość. Celem pracy jest porównanie jakości rozwiązań otrzymanych za pomocą algorytmu sekwencyjnego oraz równoległego w pierwszej fazie. Przeanalizowany został wpływ zróżnicowania populacji i generowania rozwiązań potomnych na jakość rozwiązań wraz z przyspieszeniami dla algorytmu memetycznego drugiej fazy. Jakość rozwiązań jest oceniana na podstawie najlepszych obecnie znanych wyników dla problemów testowych Gehringa i Hombergera.

Słowa kluczowe

EN

heuristics; memetic algorithm; approximation algorithm

PL

heurystyka; algorytm memetyczny; algorytm aproksymacyjny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2012
• Tom: Vol. 33, nr 1
• Strony: 91--106
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Nalepa J.

autor

Czech Z.

• Politechnika Śląska, Instytut Informatyki, Gliwice, Akademicka 16, pokój 520,

Bibliografia

• 1. Blocho M., Czech Z. J.: An improved route minimization algorithm for the vehicle routing problem with time windows. ZN Pol. SI. Studia Informatica Vol. 30, No. 1(39), Gliwice 2010, p. 5-19.
• 2. Czech Z. J., Mikanik W., Skinderowicz R.: Implementing a parallel simulated annealing algorithm. Proceedings of the 8th international conference on parallel processing and applied mathematics, 2010, Vol. 6067, p. 146-155.
• 3. Nagata Y., Braysy O.: A powerful route minimization heuristic for the vehicle routing problem with time windows. Operation Research Letters, 2009, Vol. 37, p. 333-338.
• 4. Nagata Y., Braysy O., Dullaert W.: A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers and Operations Research, 2010, Vol. 37, p. 724-737.
• 5. Moscato P., Cotta C: A Gentle Introduction to Memetic Algorithms in F. Glover (Ed.), Handbook of Metaheuristics, Kluwer 2003, p. 105-144.
• 6. Problems and benchmarks: The world's best solutions for Gehring and Homberger's benchmark: http://www.sintef.no/Projectweb/TOP/ProblemsA'RPTW/
• 7. CI TASK - Galera: http://www.task.gda.pl/kdm/sprzet/Galera