Arc-Routing-Probleme oder auch kantenorientierte Routingprobleme sind eine Klasse von Tourenplanungsproblemen, bei denen die Dienstleistung entlang einer Kante und nicht in einem Knoten erbracht werden. Kanten in Graphen entsprechen zumeist Straßenabschnitten in der Realität.
Typische Beispiele für Arc-Routing-Probleme sind die Müllabfuhr oder die Straßenreinigung.
Ob ein Problem knoten- oder kantenorientiert modelliert wird, hängt oft auch vom Betrachtungsstandpunkt des Modellierers ab. So kann man beispielsweise in der Entsorgung auch eine knotenorientierte Modellierung wählen, wenn man die Standorte der einzelnen Mülltonnen kennt.
Da z. B. die Zahl der Mülltonnen entlang eines Straßenabschnitts in der Regel viel größer als eins ist, wird das knotenorientierte Problem in der Regel viel größer als das kantenorientierte sein.