Algorithms for the weight constrained shortest path problem

DOI10.1111/1475-3995.00003MaRDI QIDQ2767722zbMATH OpenOpenAlexFDO

Authors Irina Dumitrescu, Natashia Boland

Publication date 23 July 2002

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/1475-3995.00003

zbMATH Keywords

combinatorial optimizationnetworksrouting

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Traffic problems in operations research (90B20) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Solving shortest path problems with a weight constraint and replenishment arcs
• Algorithms for finding paths with multiple constraints
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• The exact path length problem.
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem

Cited in

(22)

• A column generation heuristic for a dynamic generalized assignment problem
• Branch-and-price-and-cut algorithms for solving the reliable \(h\)-paths problem
• Algorithms for the constrained quickest path problem and the enumeration of quickest paths
• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• Solving shortest path problems with a weight constraint and replenishment arcs
• A dynamic programming algorithm for solving the k-color shortest path problem
• T*: a weighted double-heuristic search algorithm to find the shortest path
• Solving the shortest path tour problem
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
• An optimal algorithm for the obstacle neutralization problem
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
• Algorithms for finding paths with multiple constraints
• A penalty search algorithm for the obstacle neutralization problem
• Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Acceleration strategies for the weight constrained shortest path problem with replenishment
• An exact bidirectional pulse algorithm for the constrained shortest path
• Branch-and-cut-and-price algorithm for the constrained-routing and spectrum assignment problem
• Enhanced methods for the weight constrained shortest path problem
• On approximating optimal weight ``no-certificates in weighted difference constraint systems
• The aircraft routing problem with refueling
• Some observations about the extreme points of the generalized cardinality-constrained shortest path problem polytope

This page was built for publication: Algorithms for the weight constrained shortest path problem

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