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.^[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.

Large-scale capacitated 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.^[2]

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

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

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

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^[6]

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

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

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

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