Rozwiązywanie zagadnień układania tras pojazdów z zastosowaniem

• Autorzy: Jadczak R.

Warianty tytułu

EN

Solving vehicle routing problems with evolutionary algorithms

• Języki publikacji: PL

Abstrakty

PL

Jednym z najbardziej znanych problemów kombinatorycznych jest problem komiwojażera. W artykule omówiono jego rozszerzoną wersję – problem wielu komiwojażerów, znany także w literaturze jako zagadnienie układania tras pojazdów. Zagadnienie to, należące do problemów NP-zupełnych, łatwo można sformułować, jednak znalezienie jego optymalnego rozwiązania jest bardzo trudne. Zaprezentowano możliwość wykorzystania algorytmów ewolucyjnych. Są to metody przeznaczone przede wszystkim do rozwiązywania zadań optymalizacji, a wydają się szczególnie użyteczne w przypadku zagadnień o charakterze kombinatorycznym. Przedstawiono sformułowanie problemu układania tras pojazdów oraz znane dotychczas metody jego rozwiązywania. Następnie zaprezentowano algorytm ewolucyjny dla zadania układania tras pojazdów. W części empirycznej pracy zaprezentowano wyniki uzyskane za pomocą algorytmu ewolucyjnego do rozwiązania kilku zadań testowych.

EN

One of the best known combinatorial problems is a Travelling Salesman Problem. In the paper, an extended version is considered, i.e., a multisalesman problem, which is known in the literature as a vehicle routing problem. This NP-hard problem is very easy to define but finding an optimal solution is very hard. In this work, the applicability of evolutionary algorithms is presented. These methods are developed for optimization problems, and particularly, they seem to be very useful when applied to combinatorial problems. In the paper, a vehicle routing problem is defined and the best known heuristic methods are presented. Naxt evolutionary program for solving vehicle routing problem is formulated. Finally, experimental results for some test problems are shown and analyzed.

Słowa kluczowe

PL

problem układania tras pojazdów; algorytmy ewolucyjne

EN

vehicle routing problem; evolutionary algorithms

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2005
• Tom: nr 3-4
• Strony: 7--22
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Jadczak R.

• Katedra Badań Operacyjnych, Uniwersytet Łódzki, ul. Rewolucji 1905 r. 41, 90-214 Łódź,

Bibliografia

• [1] CAŁCZYŃSKI A., Modele i metody ustalania tras przewozów towarowych, Instytut Handlu Wewnętrznego i Rynku, Warszawa 1979.
• [2] CLARKE G., WRIGHT J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 1964, Vol. 12, s. 568–581.
• [3] FISHER M., JAIKUMAR R., A generalized assignment heuristic for the vehicle routing, Networks, 1981, Vol. 11, s. 109–124.
• [4] GILLET B.E., MILLER L.R., A heuristic algorithm for the vehicle dispatch problem, Operations Research, 1974, Vol. 22, s. 340–349.
• [5] GOLDERBERG D.E., Algorytmy genetyczne i ich zastosowania, WNT, 2003.
• [6] JADCZAK R., Wykorzystanie metod programowania ewolucyjnego do rozwiązania problemu wielu komiwojażerów, praca doktorska napisana w Katedrze Badań Operacyjnych, w Instytucie Ekonometrii i Statystyki Uniwersytetu Łódzkiego, Łódź 2005.
• [7] JASIŃSKI L.J., Optymalizacja dostawy towarów na zaopatrzenie rynku w warunkach niepewności, Instytut Rynku Wewnętrznego i Konsumpcji, Warszawa 1987.
• [8] LAPORTE G., The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 1992, Vol. 59, Issue 3, s. 345–358.
• [9] LAPORTE G., SEMET F., Classical heuristic for the vehicle routing problem, [w:] Toth P., Vigo D. The Vehicle Routing Problem, Monograph on Discrete Mathematics and Applications, SIAM 2000.
• [10] LENSTRA J.K., RINOOY KAN A.H.G., Complexity of vehicle routing and scheduling problems, Networks,1981, Vol. 11, s. 221–227.
• [11] LIN S., KERNIGHAN B.W., An effective heuristic for the traveling salesman problem, Operations Research, 1973, Vol. 21, s. 498–516.
• [12] LITTLE J.D.C., MURTY K.G., SWEENEY D.W., KAREL C., An algorithm for the traveling salesman problem, Operations Research, 1963, Vol. 11.
• [13]MICHALEWICZ Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, 1999.
• [14]MOLE R.H., JAMESON S.R., A sequential route-building algorithm employing a generalized savingscriterion, Operations Research Quarterly, 1976, Vol. 27, s. 503–511.
• [15] PAESSENS H., The savings for the vehicle routing problem, European Journal of Operational Research, 1988, Vol. 34, s. 336–344.