Problem z trasowaniem łuku pojemnościowego

W matematyce problem trasowania łuku pojemnościowego (CARP) polega na znalezieniu najkrótszej trasy z minimalnym wykresem / odległością podróży wykresu mieszanego z nieukierunkowanymi krawędziami i łukami skierowanymi, biorąc pod uwagę ograniczenia wydajności dla obiektów poruszających się wzdłuż wykresu, które reprezentują pługi śnieżne, zamiatarki uliczne, piaskarki zimowe lub inne rzeczywiste obiekty o ograniczonej wydajności. Ograniczenie może zostać nałożone na długość czasu, w którym pojazd znajduje się z dala od centralnej zajezdni, na całkowitą przebytą odległość lub na kombinację tych dwóch czynników z różnymi współczynnikami wagowymi.

Istnieje wiele różnych odmian CARP opisanych w książce Arc Routing: Problems, Methods, and Applications autorstwa Ángela Corberána i Gilberta Laporte.

Rozwiązanie CARP obejmuje badanie teorii grafów, trasowanie łuków, badania operacyjne i algorytmy trasowania geograficznego w celu efektywnego znalezienia najkrótszej ścieżki .

CARP to NP-twardy problem prowadzenia łuku .

CARP można rozwiązać za pomocą optymalizacji kombinatorycznej, w tym wypukłych łusek .

Problem routingu łuku pojemnościowego na dużą skalę (LSCARP) jest wariantem problemu routingu łuku pojemnościowego, który dotyczy setek krawędzi i węzłów w celu realistycznej symulacji i modelowania dużych, złożonych środowisk.