An improved route minimization algorithm for the vehicle routing problem with time Windows

• Autorzy: Błocho M. , Czech Z.

Warianty tytułu

PL

Ulepszony algorytm minimalizacji liczby tras dla problemu trasowania pojazdów z oknami czasowymi

• Języki publikacji: EN

Abstrakty

EN

A route minimization algorithm for the vehicle routing problem with time windows is presented. It was elaborated as an improvement of the algorithm proposed by Nagata and Bräysy (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). By making use of the improved algorithm the two new-best solutions for Gehring and Homberger's (GH) benchmarks were found. The experiments showed that the algorithm constructs the world-best solutions with the minimum route numbers for the GH tests in a short time.

PL

W pracy zaprezentowano algorytm minimalizacji liczby tras dla problemu trasowania pojazdów z oknami czasowymi. Został on opracowany przez ulepszenie algorytmu zaproponowanego przez Nagatę and Bräysy'ego (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). Przy użyciu ulepszonego algorytmu znaleziono dwa nowe najlepsze rozwiązania dla testów wzorcowych Gehringa i Hombergera (GH). W eksperymentach wykazano, że za pomocą ulepszonego algorytmu są konstruowane w krótkim czasie najlepsze światowe rozwiązania testów GH o minimalnej liczbie tras.

Słowa kluczowe

EN

vehicle routing problem; guided local search; heuristics; approximation algorithm

PL

trasowanie pojazdów; lokalne poszukiwanie z przewodnikiem; heurystyka; algorytm aproksymacyjny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2011
• Tom: Vol. 32, nr 3B
• Strony: 5--19
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Błocho M.

autor

Czech Z.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska,

Bibliografia

• 1. Czech Z. J.: A Parallel Simulated Annealing Algorithm as a Tool for Fitness landscapes Exploration. Parallel and Distributed Computing. InTech, 2010, chapter 13, p. 247-271.
• 2. Gehring H., Homberger J.: Parallelization of a two-phase metaheuristic for routing problems with time windows. Asia-Pacific Journal of Operational Research 18, 2001, p. 35-47.
• 3. Ibaraki T., Imahori S., Nonobe K., Sobue K., Uno T., Yagiura M.: An iterated local search algorithm for the vehicle routing problem with convex time penalty functions. Discrete Applied Mathematics 156, 2008, p. 2050-2069
• 4. Lenstra. J., and Rinnooy Kan, A.: Complexity- of vehicle routing and scheduling problems. Networks 11, 1981, p. 221-227.
• 5. Lim A., Zhang X.: A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. Informs Journal on Computing 19, 2007, p. 443-457.
• 6. Nagata Y.: Efficient evolutionary algorithm for the vehicle routing problem with time windows: Edge assembly crossover for the VRPTW. Proc. of the 2007 Congress on Evolutionary Computation, 2007, p. 1175-1182.
• 7. Nagata Y, Bräysy O.: A Powerful Route Minimization Heuristic for the Vehicle Routing Problem with Time Windows. Operations Research Letters 37, 2009, p. 333-338.
• 8. Nagata Y. Bräysy O., Dullaert W. (2010) A Penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research 37, 2010, p. 724-737.
• 9. Pisinger D., Ropke S.: A general heuristic for vehicle routing problems. Computers & Operations Research 34, 2007. p. 2403-2435.
• 10. Prescott-Gagnon E., Desaulniers G., Rousseau L.-M.: A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows. Working Paper, University of Montreal, Canada, 2007.
• 11. Toth P., and Vigo D., (Eds ): The vehicle routing problem. SLAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 2002.
• 12. Voudouris C., Tsang E.: Guided local search. Handbook of Metaheuristics. Kluwer, 2003, p. 185-218.