Shortest Path Problems with Resource Constraints

DOI10.1007/0-387-25486-2_2zbMath1130.90315OpenAlexW311217234MaRDI QIDQ5493627

Stefan Irnich, Guy Desaulniers

Publication date: 16 October 2006

Published in: Column Generation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/0-387-25486-2_2

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Traffic problems in operations research (90B20) Discrete location and assignment (90B80)

Related Items (only showing first 100 items - show all)

Complexity of column generation in network design with path-based survivability mechanisms ⋮ Freight railway operator timetabling and engine scheduling ⋮ Optimization in Designing Complex Communication Networks ⋮ Exact Algorithms for the Chance-Constrained Vehicle Routing Problem ⋮ Vehicle routing problems with alternative paths: an application to on-demand transportation ⋮ A new branch-and-price algorithm for the traveling tournament problem ⋮ Solving a rich vehicle routing and inventory problem using column generation ⋮ An Efficient Label-Correcting Algorithm for the Multiobjective Shortest Path Problem ⋮ Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows ⋮ Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity ⋮ Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling ⋮ Multi-objective temporal bin packing problem: an application in cloud computing ⋮ Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen ⋮ An approach to the distributionally robust shortest path problem ⋮ Solution approaches for integrated vehicle and crew scheduling with electric buses ⋮ The joint network vehicle routing game with optional customers ⋮ Selective routing problem with synchronization ⋮ A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts ⋮ A column generation tailored to electric vehicle routing problem with nonlinear battery depreciation ⋮ Deep-learning-based partial pricing in a branch-and-price algorithm for personalized crew rostering ⋮ On routing and scheduling a fleet of resource-constrained vessels to provide ongoing continuous patrol coverage ⋮ Algorithms for non-linear and stochastic resource constrained shortest path ⋮ The structural complexity landscape of finding balance-fair shortest paths ⋮ Branch‐price‐and‐cut for the truck–drone routing problem with time windows ⋮ Column elimination for capacitated vehicle routing problems ⋮ Multicast routing under quality of service constraints for vehicular ad hoc networks: mathematical formulation and a relax‐and‐fix heuristic ⋮ A column‐generation‐based approach to fleet design problems mixing owned and hired vehicles ⋮ Lagrangian relaxation for maximum service in multicast routing with QoS constraints ⋮ Large‐scale zone‐based evacuation planning—Part I: Models and algorithms ⋮ A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows ⋮ Selective arc‐ng pricing for vehicle routing ⋮ Integral Column Generation for Set Partitioning Problems with Side Constraints ⋮ Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier ⋮ Exact algorithms based on a constrained shortest path model for robust serial-batch and parallel-batch scheduling problems ⋮ Stochastic crowd shipping last-mile delivery with correlated marginals and probabilistic constraints ⋮ Asymmetric probabilistic minimum-cost Hamiltonian cycle problem considering arc and vertex failures ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows ⋮ The multi-trip container drayage problem with synchronization for efficient empty containers re-usage ⋮ The Steiner bi-objective shortest path problem ⋮ Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem ⋮ Exact and heuristic approaches for maximizing flows in UAV-enabled wireless cellular networks with multi-hop backhauls ⋮ New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows ⋮ Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows ⋮ Column Generation Algorithms for the Capacitated m-Ring-Star Problem ⋮ Solving a real-world multi-depot multi-period petrol replenishment problem with complex loading constraints ⋮ A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ Learning to repeatedly solve routing problems ⋮ A Joint Vehicle Routing and Speed Optimization Problem ⋮ Solving elementary shortest-path problems as mixed-integer programs ⋮ Bi-dynamic constraint aggregation and subproblem reduction ⋮ Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints ⋮ Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows ⋮ Vehicle Routing Problems with Inter-Tour Resource Constraints ⋮ An exact algorithm for team orienteering problems ⋮ Resource extension functions: properties, inversion, and generalization to segments ⋮ On the complexity of resilient network design ⋮ Optimal routing with failure-independent path protection ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ Bidirectional labeling for solving vehicle routing and truck driver scheduling problems ⋮ A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem ⋮ A branch-and-cut-and-price approach for the pickup and delivery problem with shuttle routes ⋮ New approaches to nurse rostering benchmark instances ⋮ Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange ⋮ Dual Inequalities for Stabilized Column Generation Revisited ⋮ A branch-and-price heuristic for the crew pairing problem with language constraints ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ A branch-price-and-cut algorithm for the min-maxk-vehicle windy rural postman problem ⋮ Lagrangian relaxation for the multiple constrained robust shortest path problem ⋮ The Fixed-Charge Shortest-Path Problem ⋮ The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing ⋮ An exact solution method for the capacitated item-sharing and crowdshipping problem ⋮ Route Planning for Robot Systems ⋮ Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times ⋮ Cutting planes for branch-and-price algorithms ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty ⋮ Fast local search algorithms for the handicapped persons transportation problem ⋮ Solving the selective multi-category parallel-servicing problem ⋮ Delay-constrained shortest paths: approximation algorithms and second-order cone models ⋮ Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types ⋮ Branch-and-price for staff rostering: an efficient implementation using generic programming and nested column generation ⋮ A heuristic for cumulative vehicle routing using column generation ⋮ A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen ⋮ Task assignment with start time-dependent processing times for personnel at check-in counters ⋮ The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem ⋮ The pickup and delivery problem with time windows, multiple stacks, and handling operations ⋮ The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm ⋮ Tramp ship routing and scheduling with voyage separation requirements ⋮ An accelerated branch-and-price algorithm for multiple-runway aircraft sequencing problems ⋮ A comparison of column-generation approaches to the synchronized pickup and delivery problem ⋮ Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations ⋮ The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: a branch-and-price approach ⋮ A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times ⋮ Integer programming formulations for the elementary shortest path problem ⋮ The electric fleet size and mix vehicle routing problem with time windows and recharging stations ⋮ Managing large fixed costs in vehicle routing and crew scheduling problems solved by column generation ⋮ Lifted and local reachability cuts for the vehicle routing problem with time windows ⋮ Single liner shipping service design

This page was built for publication: Shortest Path Problems with Resource Constraints