Zastosowanie optymalizacji odpornej w problematyce wyznaczania tras pojazdom : charakterystyka oraz kierunki badań

• Autorzy: Kubek D.

Warianty tytułu

EN

Application of robust optimization in vehicle routing problems : characteristics and research directions

• Języki publikacji: PL

Abstrakty

PL

Niepewność zjawisk oraz procesów występujących w rzeczywistym systemie transportowym miasta jest powszechna i naturalna. Niepewność występowania tych elementów istotnie wpływa na sposób i jakość planowania transportu towarowego w mieście. Czynniki behawioralne użytkowników, warunki pogodowe, występowanie incydentów drogowych, błąd metody pomiaru, czy też metody prognozy, to jedne z wielu czynników powodujących, że estymowane czasy przejazdu mogą odbiegać od rzeczywistych wartości. Planowanie tras pojazdom o wartości danych odbiegających od rzeczywistych mogą generować zbędne koszty dla firm transportowych oraz negatywnie wpływać na środowisko naturalne. W ostatniej dekadzie można zauważyć, w światowych badaniach, powstanie nowego trendu w badaniach nad problematyką wyznaczania tras pojazdom, który zakłada, że dane mogą być niepewne. Rozwiązywanie takich problemów wykonywane jest przy pomocy optymalizacji odpornej. W artykule przedstawiono ogólną charakterystykę optymalizacji odpornej, jej porównanie z programowaniem stochastycznym, dotychczasowy stan badań aplikacyjnego zastosowania tej metodologii w problematyce marszrutyzacji oraz dalsze kierunki badań.

EN

An uncertainty of phenomena and processes occurring in the real urban transportation system is common and natural. The uncertainty of these elements has a significant impact on the manner and quality of freight transportation planning in the cities. The user behavioral factors, weather conditions, traffic incidents, error of measurement methods or methods of predictions are small number of factors which make the estimated travel times may differ from the actual values. Route planning based improper data may lead to generate unnecessary costs for transportation companies and negatively affect the environment. In the last decade it can be found in the world's researches, the emergence of a new trend in the study of robust vehicle routing problems. Solving such problems is performed using robust optimization. The paper presents the general characteristics of the robust optimization, its comparison with the stochastic programming, the current state of research on the application into vehicle routing problems and it is shows further directions of research.

Słowa kluczowe

PL

optymalizacja odporna; problem; pojazd; wyznaczanie trasy

EN

robust optimization; vehicle routing; problem

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2015
• Tom: nr 3
• Strony: 2654--2663, CD 1
• Opis fizyczny: Bibliogr. 34 poz., rys.

Twórcy

autor

Kubek D.

• Politechnika Krakowska, Wydział Inżynierii Lądowej, Instytut Zarządzania w Budownictwie i Transporcie, Zakład Transportu

Bibliografia

• 1. Adamski A., Inteligentne systemy transportowe: sterowanie, nadzór i zarządzanie. Kraków: Wydawnictwo AGH, 2003.
• 2. Adamski A., Kubek D., HITS: Advanced City Logistics Systems. [aut. książki] T. Marek, i inni. Human Factor of s Global Society: a System of Systems Perspective. brak miejsca : CRC Press, 2014,
• 3. Adamski A., Kubek D., VRP-R: Robust routing problems solutions based on the HILS platform. Logistyka. 2014, nr 6.
• 4. Agra A., i inni., The robust vehicle routing problem with time windows. Computers & Operations Research. 2013, Tom 40(3),
• 5. Bent R., Van Hentenryck P., A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science. 2004, Tom 38(4),
• 6. Ben-Tal A., El Ghaoui L., Nemirovski A., Robust optimization. New Jersey: Princeton University Press, 2009.
• 7. Ben-Tal A., Nemirovski A., Robust solutions of Linear Programming problems contaminated with uncertain data. Mathematical Programming. 2008, Tom 88(3),
• 8. Bertsimas D., Brown D.B., Caramanis C., Theory and Applications of Robust Optimization. SIAM Review. 2008, Tom 53(3),
• 9. Bertsimas D., Sim M., Price of Robustness. Operations Research. 2004, Tom 54(1)
• 10. Bertsimas D., Sim M., Robust discrete optimization and network flows. Mathematical Programming. 2003, Tom 98,
• 11. Bianchi L., i inni,. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing. 2009, Tom 8(2),
• 12. Chen X., Sim M., Sun P., A Robust Optimization Perspective on Stochastic Programming. Operations Research. 2007, Tom 55(6),
• 13. Donati A.V., i inni., Time dependent vehicle routing problem with a multi ant colony system. European Journal of Operational Research. 2008, 185,
• 14. El Ghaoui L., Uniwersytet w Berkeley. Robust Optimization and Applications. [Online] [Zacytowano: 17 styczeń 2015.] http://www.eecs.berkeley.edu/~elghaoui/Talks/talkIMA2003b.pdf.
• 15. Fleury G., Lacomme P., Prins C., Evolutionary Algorithms for Stochastic Arc Routing Problems. Applications of Evolutionary Computing. 2004, Tom 3005,
• 16. Goh J., Sim M., Distributionally Robust Optimization and Its Tractable Approximations. Operations Research. 2010, Tom 58(4),
• 17. Goh J., Sim M., Robust Optimization Made Easy with ROME. Operations Research. 2011, Tom 59(4),
• 18. Kubek D., Integration of robust shortest path with pickup and delivery vehicle routing problem. Proceedings of the Second International Conference on Traffic and Transport Engineering ICTTE. 2014.
• 19. Montemanni R., Gambardella L.M., Donati A.V., A branch and bound algorithm for the robust shortest path problem with interval data. Operations Research Letters. 2004, Tom 32,
• 20. Osman I.H., Wassan N.A., A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. JOURNAL OF SCHEDULING. 2002, Tom 5(4),
• 21. Pisinger D., Ropke S., A general heuristic for vehicle routing problems. Computers & Operations Research. 2007, Tom 34(8),
• 22. Ropke S., Pisinger D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science. 2006, Tom 40(4),
• 23. Russell R.A., Chiang W.C., Scatter search for the vehicle routing problem with time windows. European Journal Of Operational Research. 2005, Tom 169(2),
• 24. Science. Web of Science.[Online] [Zacytowano: 30 grudzień 2014.] https://webofknowledge.com/
• 25. Shapiro A., Dentcheva S., Ruszczyński A., Lectures on stochastic programming: modeling and theory: SIAM-Society for Industrial and Applied Mathematics, 2009,
• 26. Solomon M.M., Algorithms for the vehicle routing and scheduling problems with time window constraints. Operatoin Research. 1987, Tom 35(2),
• 27. Solyalı O., Cordeau J.F., Laporte G., Robust Inventory Routing Under Demand Uncertainty. Transportation Science. 2011, Tom 46(3),
• 28. Sungur I., Ordonez F., Dessouky M., A robust optimization approach for the capacitated vehicle routing. IIE Transactions. 2008, Tom 40,
• 29. Taillard ED., A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Recherche Operationnelle-Operations Research. 1999, Tom 33(1),
• 30. Tajik N., i inni., A robust optimization approach for pollution routing problem with pickup and delivery under uncertainty. Journal of Manufacturing Systems. 2014, Tom 33(2),
• 31. Tan K. C., Cheong C.Y., Goh C.K., Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. European Journal Of Operational Research. 2007, Tom 177, 2,
• 32. Tarantilis C.D., Kiranoudis C.T., Vassiliadis, V.S., A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. European Journal Of Operational Research. 2004, Tom 152(1),
• 33. Thiele A., Robust stochastic programming with uncertain probabilities. IMA J Management Math. 2008, Tom 19, 3,
• 34. Verderame P.M., i inni, Planning and Scheduling under Uncertainty: A Review Across Multiple Sectors. Ind. Eng. Chem. Res. 2010, Tom 49(9),