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
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, 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 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
