GRTgaz is the natural gas transmission system’s operator in France. To guarantee the safety of its gas infrastructures, the company conducts daily surveillance tours. These involve navigating the entire network to identify any anomalies that could damage the installations. These tours are planned and carried out every year. The network is divided into sections of pipe, each with its own surveillance mode (car, plane, etc.) and a frequency of visits per year depending on the risk involved. This problem is defined as a Periodic Capacitated Arc Routing Problem (PCARP) with a multi modal fleet. It is NP-hard because it is an extension of the CARP, which is NP-hard. To solve this problem, we develop a two-phase iterative approach supported by a machine learning model. The aim of the first phase, known as Scheduling, is to allocate the sections to be monitored to weeks of the year and to a monitoring mode, respecting the frequency constraints; the aim of the second phase, known as Routing, is to build the routes for each week of the year and each mode. A machine learning model assists the Scheduling phase by estimating the costs of the routes depending on the edges included to monitor.