BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Jadczak Radosław
Title
Rozwiązywanie zagadnień układania tras pojazdów z wykorzystaniem algorytmów ewolucyjnych
Solving Vehicle Routing Problems with evolutionary algorithms
Source
Badania Operacyjne i Decyzje, 2005, nr 3-4, s. 7-22, bibliogr. 15 poz.
Operations Research and Decisions
Keyword
Kombinatoryka, Metody numeryczne, Algorytmy, Badania operacyjne
Combinatorial analysis, Numerical methods, Algorithms, Operations research
Note
streszcz., summ.
Abstract
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.
Accessibility
The Main Library of the Cracow University of Economics
The Library of Warsaw School of Economics
The Library of University of Economics in Katowice
The Main Library of Poznań University of Economics and Business
The Main Library of the Wroclaw University of Economics
Full text
Show
Bibliography
Show
  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.
Cited by
Show
ISSN
1230-1868
Language
pol
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu