The robust shortest path problem in series -- parallel multidigraphs with interval data

DOI10.1016/J.ORL.2005.01.008MaRDI QIDQ2583712zbMATH OpenOpenAlexFDO

Authors Adam Kasperski, Paweł Zieliński

Publication date 18 January 2006

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2005.01.008

zbMATH Keywords

combinatorial optimizationNP-hardnesspseudopolynomial algorithmrobust optimizationshortest path problem

Mathematics Subject Classification ID

Convex programming (90C25)

Recommendations

• A branch and bound algorithm for the robust shortest path problem with interval data.
• The computational complexity of the relative robust shortest path problem with interval data
• On the robust shortest path problem.
• The minmax regret robust shortest path problem in a finite multi-scenario model
• An exact algorithm for the robust shortest path problem with interval data

Cites work

• A branch and bound algorithm for the robust shortest path problem with interval data.
• An exact algorithm for the robust shortest path problem with interval data
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Interval data minmax regret network optimization problems
• On latest starting times and floats in activity networks with ill-known durations
• On the hardness of evaluating criticality of activities in a planar network with duration intervals
• On the robust shortest path problem.
• Robust discrete optimization and its applications
• The computational complexity of the relative robust shortest path problem with interval data
• The Recognition of Series Parallel Digraphs

Cited in

(26)

• Some tractable instances of interval data minmax regret problems
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• On the robust shortest path problem.
• A branch and bound algorithm for the robust shortest path problem with interval data.
• Complexity of strict robust integer minimum cost flow problems: an overview and further results
• Dynamic preprocessing for the minmax regret robust shortest path problem with finite multi-scenarios
• An exact algorithm for the robust shortest path problem with interval data
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks
• Combinatorial two-stage minmax regret problems under interval uncertainty
• On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data
• The robust shortest path problem with interval data via Benders decomposition
• Recoverable robust shortest path problems
• The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows
• The most likely path on series-parallel networks
• New models for the robust shortest path problem: complexity, resolution and generalization
• Risk models for the prize collecting Steiner tree problems with interval data
• Minmax regret bottleneck problems with solution-induced interval uncertainty structure
• Robust shortest path problems with two uncertain multiplicative cost coefficients
• An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem
• The shortest path with at most / nodes in each of the series/parallel clusters
• Some Tractable Instances of Interval Data Minmax Regret Problems: Bounded Distance from Triviality
• The computational complexity of the relative robust shortest path problem with interval data
• Criticality analysis of activity networks under interval uncertainty
• Robust and distributionally robust shortest path problems: a survey
• Reduction approaches for robust shortest path problems

This page was built for publication: The robust shortest path problem in series -- parallel multidigraphs with interval data

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