BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Jadczak Radosław
Tytuł
Rozwiązywanie zagadnień układania tras pojazdów z wykorzystaniem algorytmów ewolucyjnych
Solving Vehicle Routing Problems with evolutionary algorithms
Źródło
Badania Operacyjne i Decyzje, 2005, nr 3-4, s. 7-22, bibliogr. 15 poz.
Operations Research and Decisions
Słowa kluczowe
Algorytmy, Badania operacyjne, Kombinatoryka, Metody numeryczne
Algorithms, Operations research, Combinatorial analysis, Numerical methods
Uwagi
streszcz., summ.
Abstrakt
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

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.
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Szkoły Głównej Handlowej
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu
Pełny tekst
Pokaż
Bibliografia
Pokaż
  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.
Cytowane przez
Pokaż
ISSN
1230-1868
Język
pol
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu