A Compact ILP Formulation for the Multi-Trip Capacitated Arc Routing Problem

The Multi-Trip Capacitated Arc Routing Problem (MTCARP) is an arc routing problem in which a fleet of vehicles must service required edges while respecting vehicle-capacity and route-time constraints, with each vehicle allowed to perform multiple trips. This paper proposes a compact 2-index Integer Linear Programming (ILP) formulation for the MTCARP, based on a transformed graph representation. A benchmark set of instances was also generated to evaluate the proposed model and compare it with the formulation of Tirkolaee. Computational experiments show that the proposed formulation outperforms the reference model by proving optimality for more instances and by obtaining stronger primal and dual bounds overall.