Heurystyki i metaheurystyki w problemach VRP

• Autorzy: Radosław Jadczak

Warianty tytułu

Heuristics and Metaheuristics for the Vehicle Routing Problem (VRP)

• Języki publikacji: PL

Abstrakty

Zagadnienia układania tras dla pojazdów (vehicle routing problem - VRP) interesują wielu badaczy ze względu na łatwość sformułowania konkretnego problemu - w przeciwieństwie do jego rozwiązania. Wśród znacznej liczba propozycji uzyskiwania najlepszych rozwiązań można wyróżnić metody dokładne, dające rozwiązania optymalne oraz metody przybliżone, które pozwalają na uzyskanie rozwiązań bliskich optymalnym. Metody heurystyczne stosowane są w tych problemach, w których czas potrzebny na uzyskanie rozwiązania optymalnego metodą dokładną jest zbyt długi i nie jest do zaakceptowania. W niniejszym artykule dokonano przeglądu wybranych algorytmów heurystycznych zaproponowanych dla problemów VRP, opartych na algorytmach ewolucyjnych, przeszukiwania tabu, algorytmach symulowanego wyżarzania oraz algorytmach mrówkowych. (abstrakt oryginalny)

EN

The paper presents the vehicle routing problem (VRP), its modifications and main strategies used to solving this combinatorial problem. The review of proposed heuristics and the comparison of results are presented. (original abstract)

Słowa kluczowe

PL

Metody heurystyczne; Planowanie w transporcie

EN

Heuristics methods; Planning in transport

• Czasopismo: Prace Naukowe Uniwersytetu Ekonomicznego we Wrocławiu
• Rocznik: 2010
• Numer: nr 108 Współczesne tendencje rozwojowe badań operacyjnych
• Strony: 101--112

Twórcy

autor

Radosław Jadczak

• Uniwersytet Łódzki

Bibliografia

• Bullnheimer B., Hartl R.F., Strauss Ch., Applying the ant system for the vehicle routing problem, "Annals of Operation Research" 1999 vol. 89, s. 319-328.
• Całczyński A., Metody optymalizacji w obsłudze transportowej rynku, PWE, Warszawa 1992.
• Christofides N., Mignozzi A., Toth P., The vehicle routing problem, [w:] Combinatorial Optimization, eds. N. Christofides, A. Mignozzi, P. Toth, C. Sand, Wiley, New York 1979, s. 315-338.
• Clarke G., Wright J.W., Scheduling of vehicles from a central depot to a number of delivery points, "Operations Reseach" 1964 vol. 12, s. 568-581.
• Fisher M., Jaikumar R., A generalized assignment heuristic for the vehicle routing, "Networks" 1981 vol. 11, s. 109-124.
• Gendreau M., Hertz M., Laporte G., A tabu search heuristic for the vehicle routing problem, "Management Science" 1994 vol. 40, s. 1276-1290.
• Gillett B.E., Miller L.R., A heuristic algorithm for the vehicle dispatch problem, "Operations Research" 1974 vol. 22, s. 340-349.
• Jadczak R., Rozwiązywanie zagadnień układania tras pojazdów z wykorzystaniem algorytmów ewolucyjnych, "Badania Operacyjne i Decyzje" 2005 nr 3-4, s. 7-22.
• Jasiński L.J., Optymalizacja dostawy towarów na zaopatrzenie rynku w warunkach niepewności, Instytut Rynku Wewnętrznego i Konsumpcji, Warszawa 1987.
• Kirkpatrick S., Gelatt J.C.D., Vecchi M.P., Optimization by simulated annealing, "Science" 1983 vol. 220, s. 671-680.
• Laporte G., Semet F., Classical heuristic for the vehicle routing problem, [w:] The Vehicle Routing Problem, monograph on discrete mathematics and Applications, eds. P. Toth, D. Vigo, SIAM, Austin 2000.
• Little J.D.C., Murty K.G., Sweeney D.W., Karel C., An algorithm for the traveling salesman problem, "Operations Research" 1963 vol. 11.
• Osman I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, "Annals of Operations Research" 1993 vol. 41, s. 421-451.
• 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.
• Prins Ch., A simple effective evolutionary algorithm for the vehicle routing problem, "Computers and Operations Research" 2004 vol. 31, s. 1985-2002.
• Taillard E.D., Parallel iterative search methods for the vehicle routing problem, "Networks" 1993 vol. 23, s. 661-673.
• Toth P., Vigo D., Granular tabu search heuristic for vehicle routing problems with time windows, "Journal of the Operational Research Society" 2001 vol. 52, s. 928-936.