PL EN


2015 | 235 | 132-143
Article title

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

Authors
Content
Title variants
EN
Analysis of robust optimization for shortest path problem in urban areas
Languages of publication
PL
Abstracts
PL
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.
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.
Year
Volume
235
Pages
132-143
Physical description
Contributors
author
References
  • 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.
Document Type
Publication order reference
Identifiers
ISSN
2083-8611
YADDA identifier
bwmeta1.element.cejsh-6d18a8ba-0db9-4c49-8a25-7e87f5061d5a
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.