New dynamic programming algorithms for the resource constrained elementary shortest path problem
From MaRDI portal
Publication:3507646
DOI10.1002/net.20212zbMath1144.90514OpenAlexW1543377438MaRDI QIDQ3507646
Matteo Salani, Giovanni Righini
Publication date: 20 June 2008
Published in: Networks (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2434/5590
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Transportation, logistics and supply chain management (90B06) Dynamic programming (90C39)
Related Items (88)
Column generation algorithms for bi-objective combinatorial optimization problems with a min-max objective ⋮ A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen ⋮ Parameter-free sampled fictitious play for solving deterministic dynamic programming problems ⋮ Iterated local search for the team orienteering problem with time windows ⋮ Robust combinatorial optimization with variable cost uncertainty ⋮ 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 ⋮ Freight railway operator timetabling and engine scheduling ⋮ Two exact algorithms for the traveling umpire problem ⋮ A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times ⋮ Lifted and local reachability cuts for the vehicle routing problem with time windows ⋮ Using the primal-dual interior point algorithm within the branch-price-and-cut method ⋮ Solving the orienteering problem with time windows via the pulse framework ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ A branch-and-price algorithm for the minimum latency problem ⋮ 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 ⋮ A branch-price-and-cut algorithm for the commodity constrained split delivery vehicle routing problem ⋮ Deep infeasibility exploration method for vehicle routing problems ⋮ Constraint-specific recovery network for solving airline recovery problems ⋮ Improved branch-cut-and-price for capacitated vehicle routing ⋮ Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem ⋮ Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework ⋮ Stochastic decision diagrams ⋮ 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 ⋮ Learning-Based Branch-and-Price Algorithms for the Vehicle Routing Problem with Time Windows and Two-Dimensional Loading Constraints ⋮ An exact algorithm for Agile Earth Observation Satellite scheduling with time-dependent profits ⋮ Effective neighborhood search with optimal splitting and adaptive memory for the team orienteering problem with time windows ⋮ Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen ⋮ The joint network vehicle routing game with optional customers ⋮ The rainbow Steiner tree problem ⋮ Comments on: Routing Problems with loading constraints ⋮ The orienteering problem: a survey ⋮ A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows ⋮ An exact solution method for home health care scheduling with synchronized services ⋮ A set-covering based heuristic algorithm for the periodic vehicle routing problem ⋮ 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 ⋮ The aircraft routing problem with refueling ⋮ A survey of attended home delivery and service problems with a focus on applications ⋮ A branch‐and‐price‐and‐cut algorithm for the truck‐drone routing problem with simultaneously delivery and pickup ⋮ Clique Inequalities Applied to the Vehicle Routing Problem with Time Windows ⋮ 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 ⋮ A computational study of solution approaches for the resource constrained elementary shortest path problem ⋮ A directional heuristics pulse algorithm for a two resources constrained shortest path problem with reinitialization ⋮ A tutorial on column generation and branch-and-price for vehicle routing problems ⋮ An Exact Algorithm Based on Cut-and-Column Generation for the Capacitated Location-Routing Problem ⋮ Combined location and routing problems for drug distribution ⋮ Branch-and-price for a multi-attribute technician routing and scheduling problem ⋮ A new warmstarting strategy for the primal-dual column generation method ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ 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 ⋮ A branch-and-price algorithm for a vehicle routing with demand allocation problem ⋮ Route relaxations on GPU for vehicle routing problems ⋮ Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints ⋮ Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster ⋮ Branch-price-and-cut for the mixed capacitated general routing problem with time windows ⋮ Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming ⋮ 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 ⋮ 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 ⋮ An ILP improvement procedure for the open vehicle routing problem ⋮ An iterative dynamic programming approach for the temporal knapsack problem ⋮ On the shortest path problem with negative cost cycles ⋮ Vehicle routing with soft time windows and stochastic travel times: a column generation and branch-and-price solution approach ⋮ Discrete Optimization with Decision Diagrams ⋮ Exact Algorithms for the Vehicle Routing Problem with Soft Time Windows ⋮ Industrial and tramp ship routing problems: closing the gap for real-scale instances ⋮ The conditional \(p\)-dispersion problem ⋮ 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 ⋮ The Team Orienteering Pick-Up and Delivery Problem with Time Windows and its applications in fleet sizing ⋮ A branch-and-cut-and-price algorithm for the multi-trip separate pickup and delivery problem with time windows at customers and facilities ⋮ A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants ⋮ Using column generation to compute lower bound sets for bi-objective combinatorial optimization problems ⋮ A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints ⋮ A branch-and-cut algorithm for the capacitated profitable tour problem ⋮ Modeling and Solving Vehicle Routing Problems with Many Available Vehicle Types ⋮ The orienteering problem with time windows applied to robotic melon harvesting ⋮ Solving the shortest path tour problem
Cites Work
This page was built for publication: New dynamic programming algorithms for the resource constrained elementary shortest path problem
