Jump to content

Capacitated arc routing problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Altenmann (talk | contribs) at 04:36, 12 April 2025. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In mathematics, the capacitated arc routing problem (CARP) is that of finding the shortest tour with a minimum graph/travel distance of a mixed graph with undirected edges and directed arcs given capacity constraints for objects that move along the graph that represent snow-plowers, street sweeping machines, or winter gritters, or other real-world objects with capacity constraints. The constraint can be imposed for the length of time the vehicle is away from the central depot, or a total distance traveled, or a combination of the two with different weighting factors.

There are many different variations of the CARP described in the book Arc Routing:Problems, Methods, and Applications by Ángel Corberán and Gilbert Laporte.[1]

Solving the CARP involves the study of graph theory, arc routing, operations research, and geographical routing algorithms to find the shortest path efficiently.

The CARP is NP-hard arc routing problem.

References

  1. ^ Prins, Christian (2015-02-05), "Chapter 7: The Capacitated Arc Routing Problem: Heuristics", Arc Routing, MOS-SIAM Series on Optimization, Society for Industrial and Applied Mathematics, pp. 131–157, doi:10.1137/1.9781611973679.ch7, ISBN 978-1-61197-366-2, retrieved 2022-07-14