Problema de enrutamiento de arcos con capacidad

En matemáticas, el problema de enrutamiento de arcos con capacidad limitada (CARP, por sus siglas en inglés) consiste en encontrar el recorrido más corto con una distancia mínima en un grafo mixto con aristas no dirigidas y arcos dirigidos, dadas las restricciones de capacidad para los objetos que se mueven a lo largo del grafo, como quitanieves, barredoras de calles, máquinas esparcidoras de sal u otros objetos del mundo real con restricciones de capacidad. La restricción puede imponerse en función del tiempo que el vehículo permanece lejos del depósito central, de la distancia total recorrida o de una combinación de ambas con diferentes factores de ponderación.

Existen muchas variaciones diferentes del CARP descritas en el libro Arc Routing: Problems, Methods, and Applications de Ángel Corberán y Gilbert Laporte. ^{[ 1 ]}

La resolución del problema CARP implica el estudio de la teoría de grafos, el enrutamiento de arcos, la investigación operativa y los algoritmos de enrutamiento geográfico para encontrar la ruta más corta de manera eficiente.

El CARP es un problema de enrutamiento de arcos NP-difícil .

El problema de enrutamiento de arcos con capacidad a gran escala (LSCARP, por sus siglas en inglés) es una variante del CARP que abarca 300 o más aristas para modelar problemas complejos de enrutamiento de arcos a gran escala.

Yi Mei et al. publicaron un algoritmo para resolver el problema de enrutamiento de arcos con capacidad a gran escala utilizando un algoritmo de coevolución cooperativa. ^{[ 2 ]}

LSCARP se puede resolver con un algoritmo de divide y vencerás aplicado a la descomposición de corte de ruta. ^{[ 3 ]}

El LSCARP también se puede resolver con una búsqueda local iterativa que mejora los límites superior e inferior de otros métodos. ^{[ 4 ]}

Se ha aplicado un algoritmo LSCARP a la recogida de residuos en Dinamarca con una heurística rápida denominada FAST-CARP. ^{[ 5 ]}

El algoritmo también se conoce como el Problema de Enrutamiento de Arcos con Capacidad de Tiempo (TCARP, por sus siglas en inglés). El TCARP se puede resolver con una metaheurística en un tiempo razonable. El TCARP suele surgir cuando no se aplican restricciones de volumen, por ejemplo, en la lectura de contadores ^{[ 6 ].}

Zhang et al. crearon una metaheurística para resolver una generalización llamada CARP multi-depósito a gran escala (LSMDCARP) denominada heurística de agrupamiento y búsqueda de rutas. ^{[ 7 ]}

En 2017 se desarrolló un algoritmo para el LSCARP llamado Paso de extensión y filtrado estadístico para CARP a gran escala (ESMAENS). ^{[ 8 ]}

El LSCARP se puede extender a un problema de enrutamiento de vehículos con capacidad limitada a gran escala con un algoritmo de descomposición jerárquica. ^{[ 9 ]} El LSCVRP se puede resolver con un método evolutivo basado en búsqueda local. ^{[ 10 ]} La resolución del LSCVRP se puede realizar mediante máquinas de vectores de soporte integradas y métodos de bosques aleatorios . ^{[ 11 ]}

^{Accorsi et al. [ 12 ]} desarrollaron un algoritmo para resolver LSCARP basado en recocido simulado llamado FILO.