Problème de routage de véhicules capacités dans des métriques graphiques

Nous étudions le problème de routage de véhicules capacités dans des métriques graphiques (CVRP graphique). Notre principale contribution est une nouvelle borne inférieure sur le coût d'une solution optimale. Pour les métriques graphiques, cette borne inférieure est serrée et significativement plus forte que la borne bien connue pour les métriques générales. La preuve de la nouvelle borne inférieure est simple et combinatoire. En utilisant cette borne inférieure, nous analysons le ratio d'approximation de l'algorithme classique de partitionnement d'itinéraire itéré combiné avec les algorithmes TSP pour les métriques graphiques de Christofides 1976, de Mömke-Svensson JACM 2016 et de Sebő-Vygen Combinatorica 2014. En particulier, nous obtenons une approximation de 1,95 pour le CVRP graphique.