Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
From MaRDI portal
Publication:2465940
DOI10.1016/J.DISOPT.2006.05.007zbMath1149.90167OpenAlexW2099391941MaRDI QIDQ2465940
Matteo Salani, Giovanni Righini
Publication date: 11 January 2008
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2006.05.007
Related Items (98)
The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ Integer programming formulations for the elementary shortest path problem ⋮ The electric fleet size and mix vehicle routing problem with time windows and recharging stations ⋮ A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands ⋮ 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 profit-maximization location-routing-pricing problem: a branch-and-price algorithm ⋮ Hybrid dynamic programming with bounding algorithm for the multi-profit orienteering problem ⋮ Simple paths with exact and forbidden lengths ⋮ Constraint-specific recovery network for solving airline recovery problems ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ A new branch-and-price algorithm for the traveling tournament problem ⋮ Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework ⋮ Improving Column Generation for Vehicle Routing Problems via Random Coloring and Parallelization ⋮ 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 and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ A symmetry-free polynomial formulation of the capacitated vehicle routing problem ⋮ Modeling and solving profitable location and distribution problems ⋮ A branch-cut-and-price algorithm for the traveling salesperson problem with hotel selection ⋮ The rainbow Steiner tree problem ⋮ The time-dependent capacitated profitable tour problem with time windows and precedence constraints ⋮ A set-covering based heuristic algorithm for the periodic vehicle routing problem ⋮ Primal column generation framework for vehicle and crew scheduling problems ⋮ Selective arc‐ng pricing for vehicle routing ⋮ Linear edge costs and labeling algorithms: The case of the time‐dependent vehicle routing problem with time windows ⋮ Branch-and-Price Approaches for Real-Time Vehicle Routing with Picking, Loading, and Soft Time Windows ⋮ Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier ⋮ A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows ⋮ Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows ⋮ Stabilized branch-price-and-cut for the commodity-constrained split delivery vehicle routing problem ⋮ A generic exact solver for vehicle routing and related problems ⋮ 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 ⋮ New Refinements for the Solution of Vehicle Routing Problems with Branch and Price ⋮ The complexity of branch-and-price algorithms for the capacitated vehicle routing problem with stochastic demands ⋮ Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network ⋮ On the exact solution of a large class of parallel machine scheduling problems ⋮ Joint optimisation of drone routing and battery wear for sustainable supply chain development: a mixed-integer programming model based on blockchain-enabled fleet sharing ⋮ A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ⋮ A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand ⋮ Heuristic and exact algorithms for the multi-pile vehicle routing problem ⋮ Solving elementary shortest-path problems as mixed-integer programs ⋮ Branch-and-price for a multi-attribute technician routing and scheduling problem ⋮ The time-dependent vehicle routing problem with time windows and road-network information ⋮ Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies ⋮ A column generation approach for the split delivery vehicle routing problem ⋮ A robust optimization approach with probe-able uncertainty ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ Finding the nucleolus of the vehicle routing game with time windows ⋮ Chvátal-Gomory Rank-1 Cuts Used in a Dantzig-Wolfe Decomposition of the Vehicle Routing Problem with Time Windows ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Route relaxations on GPU for vehicle routing problems ⋮ 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 ⋮ Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems ⋮ The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach ⋮ Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming ⋮ Real-time vehicle rerouting problems with time windows ⋮ Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints ⋮ A column generation algorithm for the vehicle routing problem with soft time windows ⋮ An efficient column-generation-based algorithm for solving a pickup-and-delivery problem ⋮ A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows ⋮ Exact solution of the soft-clustered vehicle-routing problem ⋮ Branch and price for the vehicle routing problem with discrete Split deliveries and time windows ⋮ Optimal routing with failure-independent path protection ⋮ A route decomposition approach for the single commodity split pickup and split delivery vehicle routing problem ⋮ Stabilized branch-and-price algorithms for vector packing problems ⋮ A rollout algorithm for the resource constrained elementary shortest path problem ⋮ Optimizing logistics routings in a network perspective of supply and demand nodes ⋮ Bi-criteria path problem with minimum length and maximum survival probability ⋮ Bidirectional labeling for solving vehicle routing and truck driver scheduling problems ⋮ Nested column generation for split pickup vehicle routing problem with time windows and time-dependent demand ⋮ A multiphase dynamic programming algorithm for the shortest path problem with resource constraints ⋮ Enhanced methods for the weight constrained shortest path problem ⋮ PathWyse: a flexible, open-source library for the resource constrained shortest path problem ⋮ Exact Algorithms for the Vehicle Routing Problem with Soft Time Windows ⋮ Modeling and solving a multimodal transportation problem with flexible-time and scheduled services ⋮ A heuristic with a performance guarantee for the commodity constrained split delivery vehicle routing problem ⋮ A dynamic programming algorithm for solving the \(k\)-color shortest path problem ⋮ A survey of resource constrained shortest path problems: Exact solution approaches ⋮ The split delivery capacitated team orienteering problem ⋮ A branch-price-and-cut algorithm for the min-maxk-vehicle windy rural postman problem ⋮ New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows ⋮ A branch-and-cut-and-price algorithm for the multi-trip separate pickup and delivery problem with time windows at customers and facilities ⋮ An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles ⋮ A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants ⋮ Cutting planes for branch-and-price algorithms ⋮ Robust drone selective routing in humanitarian transportation network assessment ⋮ A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows ⋮ Branch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack Uncertainty ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Robust vehicle routing under uncertainty via branch-price-and-cut ⋮ Branch-and-price for staff rostering: an efficient implementation using generic programming and nested column generation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Accelerated label setting algorithms for the elementary resource constrained shortest path problem
- Plus court chemin avec contraintes d'horaires
- A Generalized Permanent Labelling Algorithm For The Shortest Path Problem With Time Windows
- An algorithm for the resource constrained shortest path problem
- Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
- Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
- An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
- Shortest Path Problems with Resource Constraints
This page was built for publication: Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
