An algorithm for the resource constrained shortest path problem

DOI10.1002/net.3230190402zbMath0673.90085OpenAlexW2130679277MaRDI QIDQ3827808

Nicos Christofides, John E. Beasley

Publication date: 1989

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230190402

zbMATH Keywords

shortest pathLagrangean relaxationlower boundtree searchComputational results

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items (75)

The electric vehicle shortest-walk problem with battery exchanges ⋮ Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context ⋮ An exact method for the biobjective shortest path problem for large-scale road networks ⋮ Integer programming formulations for the elementary shortest path problem ⋮ The constrained shortest path problem with stochastic correlated link travel times ⋮ Using the primal-dual interior point algorithm within the branch-price-and-cut method ⋮ A penalty search algorithm for the obstacle neutralization problem ⋮ A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ Branch-and-cut methods for the network design problem with vulnerability constraints ⋮ On an exact method for the constrained shortest path problem ⋮ Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price ⋮ A new mixed-integer linear programming model for rescue path planning in uncertain adversarial environment ⋮ Solving resource constrained shortest path problems with LP-based methods ⋮ Vehicle routing problems with alternative paths: an application to on-demand transportation ⋮ Constraint-specific recovery network for solving airline recovery problems ⋮ Analyzing the reachability problem in choice networks ⋮ Feeder routing for air-to-air refueling operations ⋮ An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem ⋮ A learning based algorithm for drone routing ⋮ The rainbow Steiner tree problem ⋮ Unnamed Item ⋮ A fully polynomial time approximation scheme for the probability maximizing shortest path problem ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ Trajectory planning for unmanned aerial vehicles: a network optimization approach ⋮ Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline Puzzle ⋮ Reachability in choice networks ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ Optimal Network Design with End-to-End Service Requirements ⋮ Hybrid co-evolutionary particle swarm optimization and noising metaheuristics for the delay constrained least cost path problem ⋮ The resource constrained shortest path problem implemented in a lazy functional language ⋮ Cost-based filtering for shorter path constraints ⋮ Lagrangian relaxation and enumeration for solving constrained shortest-path problems ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ Maximum probability shortest path problem ⋮ The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach ⋮ Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints ⋮ A model to optimize placement operations on dual-head placement machines ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ Traffic equilibrium and charging facility locations for electric vehicles ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Optimal pricing and composition of multiple bundles: a two-step approach ⋮ A hybrid particle swarm optimization -- variable neighborhood search algorithm for constrained shortest path problems ⋮ The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach ⋮ Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming ⋮ Resource extension functions: properties, inversion, and generalization to segments ⋮ A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation ⋮ Robust scheduling on a single machine to minimize total flow time ⋮ Path optimization for the resource-constrained searcher ⋮ Dynamic programming approaches to solve the shortest path problem with forbidden paths ⋮ Budgeted matching and budgeted matroid intersection via the gasoline puzzle ⋮ Solving the constrained shortest path problem using random search strategy ⋮ Effective Algorithms for a Class of Discrete Valued Optimal Control Problems ⋮ Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem ⋮ Mathematical models and solution methods for optimal container terminal yard layouts ⋮ Combining discrete SVM and fixed cardinality warping distances for multivariate time series classification ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ On the shortest path problem with negative cost cycles ⋮ Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach ⋮ Auto-tuning strategy for evolutionary algorithms: Balancing between exploration and exploitation ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ Lagrangian relaxation for the multiple constrained robust shortest path problem ⋮ A utility measure for finding multiobjective shortest paths in urban multimodal transportation networks ⋮ An efficient exact approach for the constrained shortest path tour problem ⋮ An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP ⋮ FLOW ON DATA NETWORK AND A POSITIVE SEMIDEFINITE REPRESENTABLE DELAY FUNCTION ⋮ Two engineering applications of a constrained shortest-path model ⋮ Exact and heuristic algorithms for data sets reconstruction ⋮ A generalized linear programming model for nurse scheduling ⋮ A penalty function heuristic for the resource constrained shortest path problem ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Accelerated label setting algorithms for the elementary resource constrained shortest path problem ⋮ Dynamic programming algorithms for the elementary shortest path problem with resource constraints ⋮ An exact reduction technique for the k-colour shortest path problem ⋮ A heuristic for cumulative vehicle routing using column generation

Cites Work

• Finding the K Shortest Loopless Paths in a Network
• Unnamed Item
• Unnamed Item

This page was built for publication: An algorithm for the resource constrained shortest path problem