Rozwiązywanie zagadnień układania tras pojazdów z wykorzystaniem algorytmów ewolucyjnych

• Autorzy: Radosław Jadczak

Warianty tytułu

Solving Vehicle Routing Problems with evolutionary algorithms

• Języki publikacji: PL

Abstrakty

W artykule poruszono zagadnienie układania tras pojazdów, znane także w literaturze jako problem wielu komiwojażerów. Zagadnienie to, należące do problemów NP-zupełnych, można łatwo sformułować, jednak znalezienie jego rozwiązania optymalnego jest bardzo trudne. Zaprezentowano możliwość wykorzystania algorytmów ewolucyjnych, które - w przeciwieństwie do klasycznych metod z dużą efektywnością- przeszukują przestrzeń rozwiązań rozpatrywanego zagadnienia

EN

One of the most known combinatorial problem is a Traveling Salesman Problem. In this paper a extended version is considered - multisalesman problem, which is known in the literature as a vehicle routing problem. It is very easy to define this W-hard problem, but to find a optimal solution is very hard. In this work application of evolutionary algorithm is presented. These methods arę constructed for optimization problems, but in particular they arę very useful for combinatorial problems. In this paper vehicle routing problem is defined and the most known heuristic methods arę presented. In the next section, evolutionary program for solving vehicle routing problem is formulated. At the end, the experimental results for some test problems arę shown and analyzed.

Słowa kluczowe

PL

Algorytmy; Badania operacyjne; Kombinatoryka; Metody numeryczne

EN

Algorithms; Operations research; Combinatorial analysis; Numerical methods

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2005
• Numer: nr 3-4
• Strony: 7--22

Twórcy

autor

Radosław Jadczak

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 deliverypoints, 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] GlLLET 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, SI AM 2000.
• [10] LENSTRA J.K., RINOOY KAŃ A.H.G., Complexity of vehicle routing and scheduling problems, Networks, 1981, Vol. ll,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., KAREŁ 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 savings criterion, 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.