Incremental network design with shortest paths

DOI10.1016/j.ejor.2014.04.018zbMath1338.90074OpenAlexW1991615243WikidataQ57955347 ScholiaQ57955347MaRDI QIDQ296857

Matthew Baxter, Thomas Kalinowski, Andreas T. Ernst, Tarek Elgindy, Savelsbergh, Martin W. P.

Publication date: 23 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.04.018

zbMATH Keywords

integer programmingapproximation algorithmheuristicnetwork designmulti-period

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Deterministic network models in operations research (90B10)

Related Items (23)

Polynomial-time algorithms for single resource stochastic capacity expansion models with lost sales ⋮ Interdependent network restoration: on the value of information-sharing ⋮ Network construction problems with due dates ⋮ Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period ⋮ Online scheduling problems with flexible release dates: applications to infrastructure restoration ⋮ Designing and constructing networks under uncertainty in the construction stage: definition and exact algorithmic approach ⋮ The Post-Disaster Debris Clearance Problem Under Incomplete Information ⋮ Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems ⋮ Network construction/restoration problems: cycles and complexity ⋮ Polynomial-time approximation schemes for a class of integrated network design and scheduling problems with parallel identical machines ⋮ Integrated reinforcement and repair of interdependent infrastructure networks under disaster-related uncertainties ⋮ Incremental Network Design with Minimum Spanning Trees ⋮ Lateness Minimization in Pairwise Connectivity Restoration Problems ⋮ Quantitative Models for Infrastructure Restoration After Extreme Events: Network Optimization Meets Scheduling ⋮ Approximating Incremental Combinatorial Optimization Problems ⋮ A quantitative approach for the long-term assessment of railway rapid transit network construction or expansion projects ⋮ Dynamic resource allocation to support oil spill response planning for energy exploration in the Arctic ⋮ Tree optimization based heuristics and metaheuristics in network construction problems ⋮ Interdependent integrated network design and scheduling problems with movement of machines ⋮ Exact solution approaches for the multi-period degree constrained minimum spanning tree problem ⋮ Incremental network design with maximum flows ⋮ Wasserstein distributionally robust shortest path problem ⋮ The incremental connected facility location problem

Cites Work

• Emergency path restoration problems
• Orbital branching
• Strategic network restoration
• A new algorithm for reoptimizing shortest paths when the arc costs change
• Restoring infrastructure systems: an integrated network design and scheduling (INDS) problem
• Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems
• Efficient recovery from power outage (extended abstract)
• Incremental Network Design with Minimum Spanning Trees
• Simpler and better approximation algorithms for network design
• Reoptimization procedures in shortest path problem
• Integrated network design and scheduling problems with parallel identical machines: Complexity results and dispatching rules
• The Online Median Problem
• Design of Survivable Networks: A survey
• A General Approach for Incremental Approximation and Hierarchical Clustering
• Unnamed Item

This page was built for publication: Incremental network design with shortest paths