Классическая задача коммивояжера (TSP) требует объехать заданный набор точек (вершин графа). Однако существует гигантский класс логистических проблем, где целью является обслуживание не узлов, а самих дорог (ребер графа). Сбор мусора, уборка снега, заливка битума, патрулирование улиц полицией и инспекция железнодорожных путей требуют, чтобы техника прошла по каждой улице города как минимум один раз. Этот класс задач в исследовании операций называется Маршрутизацией по дугам (Arc Routing Problem). Самой известной базовой моделью этого семейства является Задача китайского почтальона, впервые сформулированная математиком Мэй-Ко Кваном в 1962 году.