A polynomial time solvable capacitated arc routing problem on regular grid graphs

DOI10.1002/NET.22262MaRDI QIDQ7012859zbMATH OpenFDO

Authors Qian Wan, Andreas T. Ernst, Rodolfo Garcia-Flores, Simon A. Bowly, Philip Kilby

Publication date 14 March 2025

Published in Networks (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1002/NET.22262

zbMATH Keywords

capacitated arc routing problem (CARP)multi-layerpolynomial-time solvableregular grid graphssingle-layersolution patterns

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Transportation, logistics and supply chain management (90B06) Programming involving graphs or networks (90C35)

Cites work

• A cutting plane algorithm for the capacitated arc routing problem
• A deterministic tabu search algorithm for the capacitated arc routing problem
• A hybrid metaheuristic approach for the capacitated arc routing problem
• A new branch-and-cut algorithm for the capacitated vehicle routing problem
• A shortest path algorithm for grid graphs
• An exact algorithm for the capacitated arc routing problem with deadheading demand
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Arc routing problems: A review of the past, present, and future
• Capacitated arc routing problems
• Exact methods based on node-routing formulations for undirected arc-routing problems
• Fast upper and lower bounds for a large‐scale real‐world arc routing problem
• Hamilton Paths in Grid Graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 568802 (Why is no real title available?)
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Solving capacitated arc routing problems using a transformation to the CVRP
• Split-delivery routeing heuristics in livestock feed distribution
• The traveling salesman problem and its variations
• Traveling salesman problem, theory and applications.

Cited in

(1)

• Exploring roadside management optimisation opportunities: a systematic review on arc routing problems applications and modelling

This page was built for publication: A polynomial time solvable capacitated arc routing problem on regular grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7012859)