Let's Connect
Follow Us
Watch Us
(+385) 1 2380 262
journal.prometfpz.unizg.hr
Promet - Traffic&Transportation journal

Accelerating Discoveries in Traffic Science

Accelerating Discoveries in Traffic Science

Login Submit

PDF
PUBLISHED
05.02.2021
DOI
https://doi.org/10.7307/ptt.v33i1.3538
ISSUE
2021 (Vol 33), Issue 1
LICENSE
Copyright (c) 2024 Marko Špoljarec, Robert Manger
Creative Commons 4.0 logo
This work is licensed under a
Creative Commons Attribution-NonCommercial-
NoDerivatives 4.0 International License.

Solving Robust Variants of Integer Flow Problems with Uncertain Arc Capacities

Authors:

Marko Špoljarec
Intesa Sanpaolo International Value Services, Zagreb, Croatia

Robert Manger
University of Zagreb, Faculty of Science, Zagreb, Croatia

Keywords:network flow, integer flow, robust optimization, algorithm

Abstract

This paper deals with robust optimization and network flows. Several robust variants of integer flow problems are considered. They assume uncertainty of network arc capacities as well as of arc unit costs (where applicable). Uncertainty is expressed by discrete scenarios. Since the considered variants of the maximum flow problem are easy to solve, the paper is mostly concerned with NP-hard variants of the minimum-cost flow problem, thus proposing an approximate algorithm for their solution. The accuracy of the proposed algorithm is verified by experiments.

References

  1. Bazaraa MS, Jarvis JJ, Sherali HD. Linear Programming and Network Flows. Fourth Edition. Hoboken NJ: Wiley; 2010.

    Jungnickel D. Graphs, Networks and Algorithms. Fourth Edition. Springer, Berlin; 2013.

    Papadimitriou CH, Steiglitz K. Combinatorial Optimization – Algorithms and Complexity. Mineola NY: Dover Publications; 1998.

    Ben-Tal A, El Ghaoui L, Nemirovski A. Robust Optimization. Princeton NJ: Princeton University Press; 2009.

    Bertsimas D, Sim M. Robust discrete optimization and network flows. Mathematical Programming. 2003;98: 49-71.

    Bertsimas D, Sim M. The price of robustness. Operations Research. 2004;52: 35-53.

    Kouvelis P, Yu G. Robust Discrete Optimization and Its Applications. Berlin: Springer; 1997.

    Aissi H, Bazgan C, Vanderpooten D. Min-max and min-max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research. 2009;197: 427-438.

    Aissi H, Bazgan C, Vanderpooten D. General approximation schemes for mi

Show more
How to Cite
Špoljarec, M. (et al.) 2021. Solving Robust Variants of Integer Flow Problems with Uncertain Arc Capacities. Traffic&Transportation Journal. 33, 1 (Feb. 2021), 77-89. DOI: https://doi.org/10.7307/ptt.v33i1.3538.

SPECIAL ISSUE IS OUT

Innovation and New Technologies in Transport and Logistics

Guest Editor: Eleonora Papadimitriou, PhD

Editors: Marko Matulin, PhD, Dario Babić, PhD, Marko Ševrović, PhD

RECENT PAPERS

Browse through the selection of our recent research
Driving Characteristics and Speed Behaviour Parameters of Direct Traffic at Intersections Based on Field Driving TestsExploring and Comparing Spatial Clusters of Pedestrian Night-Time Crashes Based on Different Street Lighting Conditions at County Spatial UnitUnderstanding the Impact of Integration Strategy of Ride-Hailing Platforms on Traveller’s Choice BehaviourOnline Model Predictive Control for Energy-saving Train Operation in Passenger-Freight Mixed Lines

Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal