The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem

DOI10.1016/j.ejor.2014.04.004zbMath1338.90423OpenAlexW2034062927MaRDI QIDQ296774

Stefan Irnich, Claudia Bode

Publication date: 23 June 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.04.004

zbMATH Keywords

capacitated arc-routing problemconstrained shortest pathscycle elimination

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Task assignment with start time-dependent processing times for personnel at check-in counters ⋮ An efficiency-based path-scanning heuristic for the capacitated arc routing problem ⋮ An approach to the asymmetric multi-depot capacitated arc routing problem ⋮ The constrained shortest path problem with stochastic correlated link travel times ⋮ PGAS: privacy-preserving graph encryption for accurate constrained shortest distance queries ⋮ Branch-and-price approaches for the multiperiod technician routing and scheduling problem ⋮ Asymmetry matters: dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster ⋮ Lagrangian relaxation for the multiple constrained robust shortest path problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• Pricing routines for vehicle routing with time windows on road networks
• Exploiting sparsity in pricing routines for the capacitated arc routing problem
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• A guided local search heuristic for the capacitated arc routing problem
• A capacitated general routing problem on mixed networks
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• Resource extension functions: properties, inversion, and generalization to segments
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• 2-Path Cuts for the Vehicle Routing Problem with Time Windows
• New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
• The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
• Recent results on Arc Routing Problems: An annotated bibliography
• Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
• New dynamic programming algorithms for the resource constrained elementary shortest path problem
• The Capacitated Arc Routing Problem: Lower bounds
• Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW
• Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem
• An Exact Algorithm for the Capacitated Arc Routing Problem with Deadheading Demand
• Shortest Path Problems with Resource Constraints

This page was built for publication: The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem