Reduction approaches for robust shortest path problems

DOI10.1016/j.cor.2011.01.022zbMath1210.90137OpenAlexW2064901027MaRDI QIDQ716356

Daniele Catanzaro, Martine Labbé, Martha Salazar-Neumann

Publication date: 28 April 2011

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2011.01.022

zbMATH Keywords

robust optimizationshortest path probleminterval datapreprocessingpegging testminimax regret optimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

The minmax regret robust shortest path problem in a finite multi-scenario model, A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, How much the grid network and rescuers' communication can improve the rescue efficiency in worst-case analysis, A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty, Optimizing the ecological connectivity of landscapes, An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem, Shortest path network problems with stochastic arc weights, Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenarios, Generating hard instances for robust combinatorial optimization, A minmax regret version of the time-dependent shortest path problem, Bulk-robust combinatorial optimization, Routing Optimization Under Uncertainty

Cites Work

• Unnamed Item
• A reduction approach to the repeated assignment problem
• The computational complexity of the relative robust shortest path problem with interval data
• Robust discrete optimization and its applications
• A branch and bound algorithm for the robust shortest path problem with interval data.
• Interval data minmax regret network optimization problems
• An exact algorithm for the robust shortest path problem with interval data
• The robust shortest path problem with interval data via Benders decomposition
• The robust shortest path problem in series -- parallel multidigraphs with interval data