Capacitated arc routing problem

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.

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.

A large-scale capacitated arc routing problem (LSCARP) is a variant of the CARP that covers 300 or more edges to model complex arc routing problems at large scales.

Yi Mei et al. published an algorithm for solving the large-scale capacitated arc routing problem using a cooperative co-evolution algorithm.

LSCARP can be solved with a divide and conquer algorithm applied to route cutting off decomposition.

The LSCARP can also be solved with an iterative local search that improves on upper and lower bounds of other methods.

An LSCARP algorithm has been applied to waste collection in Denmark with a fast heuristic named FAST-CARP.

The algorithm is also often referred to as the Time Capacitated Arc Routing Problem often referred to as TCARP. The TCARP can be solved with a metaheuristic in a reasonable amount of time. The TCARP often arises when volume constraints do not apply for example meter reading

Zhang et al. created a metaheuristic to solve a generalization named the large-scale multi-depot CARP (LSMDCARP) named route clustering and search heuristic.

An algorithm for the LSCARP named Extension step and statistical filtering for large-scale CARP (ESMAENS) was developed in 2017.

The LSCARP can be extended to a large-scale capacitated vehicle routing problem with a hierarchical decomposition algorithm. The LSCVRP can be solved with an evolutionary method based on local search. Solving the LSCVRP can be done by integrated support vector machines and random forest methods.

An algorithm to solve LSCARP based on simulated annealing named FILO was developed by Accorsi et al.