On an exact method for the constrained shortest path problem

DOI10.1016/J.COR.2012.07.008zbMATH Open1349.90818DBLPjournals/cor/LozanoM13OpenAlexW2069667928WikidataQ58760018 ScholiaQ58760018MaRDI QIDQ339592FDOQ339592

Authors: Leonardo Lozano, Andrés L. Medaglia 

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

Recommendations

• An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Publication:2753949
• An efficient exact approach for the constrained shortest path tour problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems

zbMATH Keywords

shortest path problemcolumn generationconstrained shortest path

Mathematics Subject Classification ID

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

Cites Work

• The shortest path problem with forbidden paths
• Title not available (Why is that?)
• Multi-objective and multi-constrained non-additive shortest path problems
• Grammar-based integer programming models for multiactivity shift scheduling
• A Column Generation Approach for Large-Scale Aircrew Rostering Problems
• A \texttt{cost-regular} based hybrid column generation approach
• Bidirectional \(A^*\) search on time-dependent road networks
• An Analysis of Stochastic Shortest Path Problems
• Formal languages for integer programming modeling of shift scheduling problems
• The operational airline crew scheduling problem
• A note on branch-and-cut-and-price
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Solving Real-World Linear Programs: A Decade and More of Progress
• 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
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
• The shortest route problem with constraints
• An algorithm for the resource constrained shortest path problem
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Solving shortest path problems with a weight constraint and replenishment arcs
• Shortest paths algorithms: Theory and experimental evaluation
• Accelerating column generation for aircraft scheduling using constraint propagation
• Combinatorial optimization. Networks and matroids
• A dual algorithm for the constrained shortest path problem
• Flight Crew Scheduling

Cited In (52)

• A time-dependent subgraph-capacity model for multiple shortest paths and application to \(\text{CO}_2\)/contrail-safe aircraft trajectories
• The workforce scheduling and routing problem with park-and-loop
• A multiphase dynamic programming algorithm for the shortest path problem with resource constraints
• Vehicle routing for connected service areas -- a versatile approach covering single, hierarchical, and bi-criteria objectives
• An exact method for the biobjective shortest path problem for large-scale road networks
• Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings
• Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Enhanced methods for the weight constrained shortest path problem
• Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization
• Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster
• The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach
• A project and lift approach for a 2-commodity flow relocation model in a time expanded network
• PathWyse: a flexible, open-source library for the resource constrained shortest path problem
• A hybrid particle swarm optimization -- variable neighborhood search algorithm for constrained shortest path problems
• An exact bidirectional pulse algorithm for the constrained shortest path
• Cost-based filtering for shorter path constraints
• Upgrading edges in the graphical TSP
• Title not available (Why is that?)
• The doubly open park-and-loop routing problem
• The equity constrained shortest path problem
• Algorithms for non-linear and stochastic resource constrained shortest path
• 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
• An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem
• A heuristic approach to hard constrained shortest path problems
• 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
• Algorithms for the constrained quickest path problem and the enumeration of quickest paths
• Title not available (Why is that?)
• An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem
• Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows
• On exact solution approaches for the longest induced path problem
• Acceleration strategies for the weight constrained shortest path problem with replenishment
• Exact bidirectional algorithm for the least expected travel-time path problem on stochastic and time-dependent networks
• Integer programming models for the multidimensional assignment problem with star costs
• Primal column generation framework for vehicle and crew scheduling problems
• A practical and efficient approach to the constrained via minimization problem
• Solving resource constrained shortest path problems with LP-based methods
• The selection of an optimal segmentation region in physiological signals
• Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems
• The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm
• Exact Solution of the Evasive Flow Capturing Problem
• Lagrangian relaxation for the multiple constrained robust shortest path problem
• On the directed hop-constrained shortest path problem
• Monitoring a Fleet of Autonomous Vehicles Through A* Like Algorithms and Reinforcement Learning
• A directional heuristics pulse algorithm for a two resources constrained shortest path problem with reinitialization
• Solving shortest path problems with a weight constraint and replenishment arcs
• Constraint-based local search for constrained optimum paths problems
• Cost-based filtering for shorter path constraints

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

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