Charakterystyka optymalizacji odpornej problemu najkrótszej ścieżki w obszarach zurbanizowanych

• Autorzy: Daniel Kubek

Warianty tytułu

Analysis of Robust Optimization for Shortest Path Problem in Urban Areas

• Języki publikacji: PL

Abstrakty

Niniejszy artykuł przedstawia problematykę wyznaczania ścieżek dla pojazdów poruszających się w sieci drogowej miasta. Ścieżki te zostały wyznaczone w oparciu o optymalizację odporną, która uwzględnia możliwość wystąpienia wahań od wartości oczekiwanej czasów przejazdu na odcinkach sieci drogowej. Poruszone zagadnienie popularnie znane jest jako problem najkrótszej ścieżki z niepewnymi czasami przejazdów (robust shortest path problem). Odporny model matematyczny problemu najkrótszej ścieżki został rozwiązany za pomocą metody, która zamienia oryginalny problem na deterministyczny odpowiednik programowania liniowego. Odpowiednik ten jest uzyskiwany przez przyjęcie założenia, że zmienna decyzyjna jest funkcją afiniczną, która zależy od realizacji niepewności danych. Niepewność jest zdefiniowana na podstawie odchylenia standardowego czasu przejazdu na poszczególnym odcinku. Parametry te są wykorzystane do opisu rodziny rozkładów prawdopodobieństwa, zgodnie z którymi wartość niepewności danych będzie realizowana. Zalety stosowania optymalizacji odpornej oraz charakterystyka problemu zostały zaprezentowane na rzeczywistej sieci drogowej miasta Krakowa.(abstrakt oryginalny)

EN

The paper addresses the shortest path problem for vehicles traversing the road network of the city. The paths have been determinate based on the robust optimization theory, which take into account the data uncertainty. The problem is known as robust shortest path problem. Formulation of robust mathematical model is solved by transforming the robust model into a deterministic counterpart. Deterministic counterpart is obtained by assumption that variables are affinely dependent on primitives uncertainty. Uncertainty set is defined as affine function of standard deviation of sections travel time. These parameters are used to describe a family of probability distributions under which the value of the uncertainty of the data will be implemented. The advantages, analysis and the characteristics of robust approach are presented on a real example - the road network of Cracow.(original abstract)

Słowa kluczowe

PL

Transport drogowy; Optymalizacja; Transport miejski

EN

Road transport; Optimalization; City transport

• Czasopismo: Studia Ekonomiczne / Uniwersytet Ekonomiczny w Katowicach
• Rocznik: 2015
• Numer: nr 235
• Strony: 132--143

Twórcy

autor

Daniel Kubek

• Politechnika Krakowska

Bibliografia

• Adamski A., Kubek D. (2014), HITS: Advanced City Logistics Systems [w:] T. Marek (red.), "Human Factors of a Global Society: A System of Systems Perspective", CRC Press.
• Ben-Tal A., Goryashko A., Guslitzer E., Nemirovski A. (2004), Adjustable robust solutions of uncertain linear programs, "Mathematical Programming", Vol. 99.
• Bertsimas D., Sim M., (2003), Robust discrete optimization and network flows, "Mathematical Programming", Vol. 98.
• Bertsimas D., Sim M. (2004), Price of Robustness. "Operations Research", Vol. 52, Iss. 1.
• Calvete H.I., Galé C., Oliveros M.J., Sánchez-Valverde B. (2007), A goal programming approach to vehicle routing problems with soft time windows, "European Journal of Operational Research", Vol. 177, Iss. 3.
• Cheng J., (2013), Distributionally robust stochastic shortest path problem, "Electronic Notes in Discrete Mathematics", Vol. 41.
• Dellaert N., Woensel T., Kok T. (2013), Dynamic shortest path problems: Hybrid routing policies considering network disruptions, "Computers & Operations Research", Vol. 40, Iss. 12.
• Desaulniers G., Villeneuve D. (2000), The Shortest Path Problem with Time Windows and Linear Waiting Costs, "Transportation Science", Vol. 34, Iss. 3.
• Gabrela V., Murata C., Thiele A. (2014), Recent advances in robust optimization: An overview, "European Journal of Operational Research", Vol. 235, Iss. 3.
• Goh J., Sim M. (2010), Distributionally Robust Optimization and its Tractable Approximations, "Operations Research", Vol. 58.
• Kara ̧san O.E., Pinar M.Ç., Yaman H. (2001), The robust shortest path problem with interval data. Technical report, Bilkent University.
• Kubek, D. (2014), Integration of robust shortest path with pickup and delivery vehicle routing problem, ICTTE: International conference on traffic and transport engineering, November 27-28, 2014 Belgrade, Serbia.
• Soyster A. (1973), Convex programming with set-inclusive constraints and application to inexact linear programming, "Operation Research", Vol. 21.