A survey of resource constrained shortest path problems: exact solution approaches

DOI10.1002/NET.21511zbMATH Open1338.90432OpenAlexW1995415305WikidataQ58921139 ScholiaQ58921139MaRDI QIDQ2811308FDOQ2811308

Francesca Guerriero, Luigi Di Puglia Pugliese

Publication date: 10 June 2016

Published in: Networks (Search for Journal in Brave)

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

Recommendations

• A computational study of solution approaches for the resource constrained elementary shortest path problem
• Solving resource constrained shortest path problems with LP-based methods
• Publication:2753949
• An algorithm for the resource constrained shortest path problem
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems

zbMATH Keywords

shortest pathresource constraintselementary pathforbidden path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• The shortest path problem with forbidden paths
• A note on two problems in connexion with graphs
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
• Efficient string matching
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
• An algorithm for ranking paths that may contain cycles
• A reoptimization algorithm for the shortest path problem with time windows
• The shortest-path problem with resource constraints and \(k\)-cycle elimination for \(k\geq 3\)
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Shortest Path Problems with Resource Constraints
• The orienteering problem: a survey
• Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming
• A model to optimize placement operations on dual-head placement machines
• The Cutting-Plane Method for Solving Convex Programs
• A column generation algorithm for the vehicle routing problem with soft time windows
• Branch and price for the vehicle routing problem with discrete Split deliveries and time windows
• A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
• A computational study of solution approaches for the resource constrained elementary shortest path problem
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Resource extension functions: properties, inversion, and generalization to segments
• Vehicle routing problem with elementary shortest path based column generation
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• New route relaxation and pricing strategies for the vehicle routing problem
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• The network design problem with relays
• Lagrangian relaxation and enumeration for solving constrained shortest-path problems
• Dynamic programming approaches to solve the shortest path problem with forbidden paths
• A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation
• A penalty function heuristic for the resource constrained shortest path problem
• Three-stage approaches for optimizing some variations of the resource constrained shortest-path sub-problem in a column generation context
• Shortest path problem with forbidden paths: the elementary version
• Shortest chain subject to side constraints
• An algorithm for the resource constrained shortest path problem
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Searching for the Multiplier in One-Constraint Optimization Problems
• Arc routing problems with time-dependent service costs
• A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows
• Solving shortest path problems with a weight constraint and replenishment arcs
• Title not available (Why is that?)
• Flight string models for aircraft fleeting and routing
• A multicommodity network-flow problem with side constraints on paths solved by column generation
• Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem
• A dual algorithm for the constrained shortest path problem
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• A Set Partitioning Approach to the Crew Scheduling Problem
• Minimum cost path problems with relays
• A Column Generation Approach to the Urban Transit Crew Scheduling Problem
• A decision-theoretic approach to robust optimization in multivalued graphs
• A heuristic approach to hard constrained shortest path problems
• An Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation
• Plus court chemin avec contraintes d'horaires
• Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks
• Shortest path with time constraints on movement and parking

Cited In (45)

• A multiphase dynamic programming algorithm for the shortest path problem with resource constraints
• Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling
• On the shortest path problem with negative cost cycles
• Minimum costs paths in intermodal transportation networks with stochastic travel times and overbookings
• Robust vehicle routing under uncertainty via branch-price-and-cut
• Nodal aggregation of resource constraints in a shortest path problem
• Enhanced methods for the weight constrained shortest path problem
• The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach
• Perspectives on integer programming for time-dependent models
• An efficient exact approach for the constrained shortest path tour problem
• PathWyse: a flexible, open-source library for the resource constrained shortest path problem
• Modelling the mobile target covering problem using flying drones
• An exact bidirectional pulse algorithm for the constrained shortest path
• A dynamic programming algorithm for solving the \(k\)-color shortest path problem
• Efficient elementary and restricted non-elementary route pricing
• An exact reduction technique for the k-colour shortest path problem
• A rollout algorithm for the resource constrained elementary shortest path problem
• A profit-maximization location-routing-pricing problem: a branch-and-price algorithm
• The Constrained Reliable Shortest Path Problem in Stochastic Time-Dependent Networks
• Two-phase algorithm for solving the preference-based multicriteria optimal path problem with reference points
• A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
• Congestion avoiding heuristic path generation for the proactive route guidance
• Limited memory rank-1 cuts for vehicle routing problems
• A time-dependent subgraph-capacity model for multiple shortest paths and application to \(\text{CO}_2\)/contrail-safe aircraft trajectories
• Delay-constrained shortest paths: approximation algorithms and second-order cone models
• Title not available (Why is that?)
• An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem
• A generalized shortest path tour problem with time windows
• A heuristic for cumulative vehicle routing using column generation
• The transit time constrained fixed charge multi-commodity network design problem
• The rainbow Steiner tree problem
• Estimating the marginal cost to deliver to individual customers
• A branch and price algorithm to solve the quickest multicommodity \(k\)-splittable flow problem
• Shortest path tour problem with time windows
• Solving resource constrained shortest path problems with LP-based methods
• The arc-item-load and related formulations for the cumulative vehicle routing problem
• The structural complexity landscape of finding balance-fair shortest paths
• A computational study of solution approaches for the resource constrained elementary shortest path problem
• An auction-based approach for the re-optimization shortest path tree problem
• The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm
• A heuristic with a performance guarantee for the commodity constrained split delivery vehicle routing problem
• Lagrangian relaxation for the multiple constrained robust shortest path problem
• Multi-criteria approximation schemes for the resource constrained shortest path problem
• The last-mile delivery process with trucks and drones under uncertain energy consumption
• A unified exact approach for a broad class of vehicle routing problems with simultaneous pickup and delivery

This page was built for publication: A survey of resource constrained shortest path problems: exact solution approaches

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