Reduction approaches for robust shortest path problems

DOI10.1016/J.COR.2011.01.022MaRDI QIDQ716356zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the robust shortest path problem.
• Interval data minmax regret network optimization problems
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• Algorithms for the minmax regret path problem with interval data
• The minmax regret robust shortest path problem in a finite multi-scenario model

Cites work

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

Cited in

(15)

• Recoverable robust shortest path problems
• The minmax regret robust shortest path problem in a finite multi-scenario model
• Robust shortest path planning and semicontractive dynamic programming
• The Exact Subgraph Recoverable Robust Shortest Path Problem
• A minmax regret version of the time-dependent shortest path problem
• Bulk-robust combinatorial optimization
• Routing optimization under uncertainty
• Shortest path network problems with stochastic arc weights
• 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
• Generating hard instances for robust combinatorial optimization
• Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenarios
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• Optimizing the ecological connectivity of landscapes

This page was built for publication: Reduction approaches for robust shortest path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716356)