On an exact method for the constrained shortest path problem

DOI10.1016/j.cor.2012.07.008zbMath1349.90818OpenAlexW2069667928WikidataQ58760018 ScholiaQ58760018MaRDI QIDQ339592

Andrés L. Medaglia, Leonardo Lozano

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.07.008

zbMATH Keywords

column generationshortest path problemconstrained shortest path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (32)

An exact method for the biobjective shortest path problem for large-scale road networks ⋮ The doubly open park-and-loop routing problem ⋮ Column generation based approaches for a tour scheduling problem with a multi-skill heterogeneous workforce ⋮ The constrained shortest path problem with stochastic correlated link travel times ⋮ Solving the orienteering problem with time windows via the pulse framework ⋮ Bi-dimensional knapsack problems with one soft constraint ⋮ A new heuristic branching scheme for the crew pairing problem with base constraints ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Solving resource constrained shortest path problems with LP-based methods ⋮ An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem ⋮ An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows ⋮ Exact bidirectional algorithm for the least expected travel-time path problem on stochastic and time-dependent networks ⋮ Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ Upgrading edges in the graphical TSP ⋮ The selection of an optimal segmentation region in physiological signals ⋮ Primal column generation framework for vehicle and crew scheduling problems ⋮ An exact bidirectional pulse algorithm for the constrained shortest path ⋮ Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems ⋮ Monitoring a Fleet of Autonomous Vehicles Through A* Like Algorithms and Reinforcement Learning ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ A directional heuristics pulse algorithm for a two resources constrained shortest path problem with reinitialization ⋮ Exact Solution of the Evasive Flow Capturing Problem ⋮ Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions ⋮ Acceleration strategies for the weight constrained shortest path problem with replenishment ⋮ The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach ⋮ Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster ⋮ A hybrid particle swarm optimization -- variable neighborhood search algorithm for constrained shortest path problems ⋮ Integer programming models for the multidimensional assignment problem with star costs ⋮ Lagrangian relaxation for the multiple constrained robust shortest path problem

Cites Work

• Unnamed Item
• Unnamed Item
• The shortest path problem with forbidden paths
• Multi-objective and multi-constrained non-additive shortest path problems
• A note on branch-and-cut-and-price
• A \texttt{cost-regular} based hybrid column generation approach
• A new approach for crew pairing problems by column generation with an application to air transportation
• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• Restricted dynamic programming: a flexible framework for solving realistic VRPs
• Solving shortest path problems with a weight constraint and replenishment arcs
• Shortest paths algorithms: Theory and experimental evaluation
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
• Formal languages for integer programming modeling of shift scheduling problems
• Accelerating column generation for aircraft scheduling using constraint propagation
• The shortest route problem with constraints
• The Operational Airline Crew Scheduling Problem
• Bidirectional A* search on time-dependent road networks
• Grammar-Based Integer Programming Models for Multiactivity Shift Scheduling
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Solving Real-World Linear Programs: A Decade and More of Progress
• An algorithm for the resource constrained shortest path problem
• A dual algorithm for the constrained shortest path problem
• An Analysis of Stochastic Shortest Path Problems
• Flight Crew Scheduling
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• A Column Generation Approach for Large-Scale Aircrew Rostering Problems

This page was built for publication: On an exact method for the constrained shortest path problem