Równoległy algorytm tabu z elementami inspirowanymi naturą dla problemu planowania tras

• Autorzy: Pempera J.

Warianty tytułu

EN

Parallel tabu search for the vehicle routing problem with components inspired by nature

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono nową koncepcję konstruowania równoległego algorytmu tabu dla problemu planowania przydziału zadań transportowych i marszrutyzacji pojazdów. Główna idea tej koncepcji polega na wykorzystaniu mechanizmów inspirowanych naturą do zarządzania niezależnymi przebiegami algorytmu tabu. W pracy rozważany jest problem marszrutyzacji z ograniczeniami pracy kierowców. Przeprowadzono badania eksperymentalne mające na celu porównanie algorytmu z algorytmami opartymi na klasycznych metodach lokalnych przeszukiwań.

EN

The paper deals with the vehicle routing problem with constraints imposed on the working time of drivers. For this problem, there has been proposed a parallel tabu search algorithm. The algorithm uses a number of independent searching threads, managed by certain evolution mechanism. Results of computational experiments are also provided and discussed.

Słowa kluczowe

PL

marszrutyzacja pojazdów; algorytm tabu; obliczenia równoległe

EN

vehicle routing problem; parallel computing; tabu search

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2011
• Tom: T. 15, z. 2
• Strony: 399--408
• Opis fizyczny: Bibliogr. 14 poz., tabl.

Twórcy

autor

Pempera J.

• Politechnika Wrocławska, Instytut Informatyki Automatyki i Robotyki

Bibliografia

• [1] Alba E., Dorronsoro B., Solving the Yehicle Routing Problem by Using Cellular Genetic Algorithms. In Conference on Evolutionary Computation in Combinatorial Optimization, Portugal,2005, 11-20.
• [2] Braysy O., Gendreau M., Yehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, 39, 1, 2005, 104-118.
• [3] Cordeau J.-F., Laporte G., A tabu search algorithm for the site dependent yehicle routing problem with time windows. INFOR, 39(3), 2001, 292-298.
• [4] Czech Z.J., Czarnas R, Parallel simulated annealing for the yehicle routing problem with time windows, in Wth Euromicro Workshop on Parallel. Distributed and Networkbased Processing, Spain, 2002, 376-383.
• [5] Dorigo M., Maniezzo V., Coloni A., Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26, 1996, 29-41.
• [6] Gendreau M., Laporte G., Seguin R., A tabu search heuristic for the yehicle routing problem with stochastic demand and customers. Operations Research, 44, 3, 1996, 469-177.
• [7] Golden B.L., Magnanti T.L., Nguyan H.Q., Implementing yehicle routing algońthms. Networks, 7, 2, (1972), 113-148.
• [8] Osman I.H., Kelly J.P., Meta-heuristics: An overview. [w:] I.H. Osman & J. P. Kelly (Eds.), Metaheuristics: Theory and applications Boston: Kluwer Academic Publishers, 1996, 1-21.
• [9] Rego C, Roucairol C, Using tabu search for solying a dynamic multiterminal truck dispatching problem. European Journal of Operational Research, 83, 1995, 411-429.
• [10] Glover F., Laguna M., Tabu search. Boston: Kluwer Academic Publishers, 1997.
• [11] Bożejko W., Wodecki M., Sofoing Permutational Routing Problems by Population-Based Meta-heuristics. Computers & Industrial Engineering, 57, 2009, 269-276.
• [12] Nowicki E., Smutnicki C, Afast taboo search algorithm for the job shop problem. Management Science, 42, 6, 1996, 797-813.
• [13] Grabowski J., Pempera J., Some local search algorithms for no-wait flow-shop problem with makespan criterion. Computers & Operations Research, 32, 8, 2005, 2197-2212.
• [14] Pempera J., Planowanie tras pojazdów z ograniczeniami czasu pracy kierowców. Logistyka i zarządzanie produkcją - nowe wyzwania, odległe granice. Red. Marek Fertsch, Katarzyna Grzy-bowska, Agnieszka Stachowiak. Poznań, 2007, 156-163.