Czasopismo
Tytuł artykułu
Autorzy
Warianty tytułu
Solving Vehicle Routing Problems with evolutionary algorithms
Języki publikacji
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
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.
Twórcy
autor
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000102526992