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)

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 ⋮ A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands ⋮ A new formulation and approach for the black and white traveling salesman problem ⋮ A branch-and-price approach for a multi-period vehicle routing problem ⋮ Full-shipload tramp ship routing and scheduling with variable speeds ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ A new heuristic branching scheme for the crew pairing problem with base constraints ⋮ A column generation approach for the location-routing problem with time windows ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ A branch-price-and-cut algorithm for the workover rig routing problem ⋮ A branch-price-and-cut method for a ship routing and scheduling problem with split loads ⋮ A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine ⋮ A profit-maximization location-routing-pricing problem: a branch-and-price algorithm ⋮ Exact algorithms for the double vehicle routing problem with multiple stacks ⋮ A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem ⋮ Solving resource constrained shortest path problems with LP-based methods ⋮ A branch and price approach for deployment of multi-tier software services in clouds ⋮ The arc-item-load and related formulations for the cumulative vehicle routing problem ⋮ Multi-objective and multi-constrained non-additive shortest path problems ⋮ A branch-and-price approach to the feeder network design problem ⋮ A note on branch-and-cut-and-price ⋮ Exact algorithms to minimize makespan on single and parallel batch processing machines ⋮ Design of diversified package tours for the digital travel industry: a branch-cut-and-price approach ⋮ Dynamic constraint and variable aggregation in column generation ⋮ A multi-start randomized heuristic for real-life crew rostering problems in airlines with work-balancing goals ⋮ Alternating Lagrangian decomposition for integrated airline crew scheduling problem ⋮ A branch and price algorithm for the minimum power multicasting problem in wireless sensor networks ⋮ The aircraft routing problem with refueling ⋮ Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network ⋮ Integrated airline crew scheduling: a bi-dynamic constraint aggregation method using neighborhoods ⋮ A tutorial on column generation and branch-and-price for vehicle routing problems ⋮ Divide-and-price: a decomposition algorithm for solving large railway crew scheduling problems ⋮ A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand ⋮ Liner shipping service scheduling and cargo allocation ⋮ A rotation-based branch-and-price approach for the nurse scheduling problem ⋮ Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows ⋮ Dynamic constraint aggregation for solving very large-scale airline crew pairing problems ⋮ The inventory routing problem with demand moves ⋮ Optimizing vessel fleet size and mix to support maintenance operations at offshore wind farms ⋮ Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies ⋮ A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ A robust optimization approach with probe-able uncertainty ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Routing a mix of conventional, plug-in hybrid, and electric vehicles ⋮ Column generation for vehicle routing problems with multiple synchronization constraints ⋮ The two-echelon capacitated electric vehicle routing problem with battery swapping stations: formulation and efficient methodology ⋮ The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times ⋮ Integrating rolling stock scheduling with train unit shunting ⋮ Branch-and-price-and-cut for a service network design and hub location problem ⋮ Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster ⋮ Solving the team orienteering arc routing problem with a column generation approach ⋮ Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems ⋮ Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming ⋮ A complete characterization of jump inequalities for the hop-constrained shortest path problem ⋮ Stabilized dynamic constraint aggregation for solving set partitioning problems ⋮ Perspectives on integer programming for time-dependent models ⋮ Multi-phase dynamic constraint aggregation for set partitioning type problems ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ Integer programming models for the multidimensional assignment problem with star costs ⋮ Oil production optimization solved by piecewise linearization in a branch \& price framework ⋮ Solving shortest path problems with a weight constraint and replenishment arcs ⋮ A graph partitioning strategy for solving large-scale crew scheduling problems ⋮ A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows ⋮ A hybrid scatter search heuristic for personalized crew rostering in the airline industry ⋮ Exact solution of the soft-clustered vehicle-routing problem ⋮ Mathematical models and solution methods for optimal container terminal yard layouts ⋮ An exact solution method for a rich helicopter flight scheduling problem arising in offshore oil and gas logistics ⋮ Combining discrete SVM and fixed cardinality warping distances for multivariate time series classification ⋮ A branch-and-price algorithm for an integrated production and inventory routing problem ⋮ A personalized walking bus service requiring optimized route decisions: a real case ⋮ Algorithms for the one-dimensional two-stage cutting stock problem ⋮ Stabilized branch-and-price algorithms for vector packing problems ⋮ System optimal routing of traffic flows with user constraints using linear programming ⋮ An efficient column generation approach for practical railway crew scheduling with attendance rates ⋮ Real-time bi-objective personnel re-scheduling in the retail industry ⋮ Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes ⋮ Solving bin packing problems using VRPSolver models ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Exact algorithms for the chance-constrained vehicle routing problem ⋮ Robust vehicle routing under uncertainty via branch-price-and-cut ⋮ An exact reduction technique for the k-colour shortest path problem ⋮ A unified exact approach for clustered and generalized vehicle routing problems ⋮ The orienteering problem with time windows applied to robotic melon harvesting

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