GRTgaz est un gestionnaire de transport de gaz en France. Afin d’assurer la sécurité et la performance du réseau de transport de gaz, l’entreprise doit effectuer des tournées de surveillance le long des 33 000 km de canalisations. Celles-ci consistent à parcourir l’ensemble du réseau afin de détecter de potentiels dangers pouvant porter atteinte à l’intégrité des infrastructures gazières. Les tournées de surveillance sont périodiques et peuvent être effectuées à l’aide de différents modes tels que la voiture et l’avion. L’entreprise doit construire les tournées de chaque semaine de l’année, en prenant en compte les différentes fréquences de passage par portions de canalisations ainsi que différents modes de surveillance. Ce problème est défini comme un Periodic Capacitated Arc Routing Problem (PCARP) with a multimodal fleet. Il s’agit d’un problème NP-difficile qui implique des prises de décisions aux niveaux tactique et opérationnel. Afin d’accélérer les méthodes de résolution, il peut être intéressant de pouvoir calculer rapidement une approximation des coûts des tournées de chaque semaine une fois le mode de transport et l’ensemble des tronçons à surveiller fixés. Dans [2, 3] les auteurs présentent différentes fonctions d’approximation pour estimer la distance totale de problèmes de tournées de véhicules avec fenêtres temporelles, et contraintes de capacités. Dans [1, 4] les auteurs proposent de nouvelles variables permettant de décrire des instances de problèmes et développent des modèles d’apprentissage pour prédire la longueur d’une tournée pour le problème du voyageur du commerce et le problème de tournées de véhicules. Ces méthodes d’approximations n’ont jamais été étudiées pour des problèmes de tournées sur les arcs. Ainsi nous introduisons des nouvelles variables spécifiques aux problèmes de tournées sur les arcs et développons des modèles de régression linéaire pour la prévision des coûts de tournées.