The Windy Clustered Prize‐Collecting Arc‐Routing Problem

This paper introduces the windy clustered prize‐collecting arc‐routing problem. It is an arc‐routing problem where each demand edge is associated with a profit that is collected once if the edge is serviced, independent of the number of times the edge is traversed. It is further required that if a demand edge is serviced, then all the demand edges of its component are also serviced. A mathematical programming formulation is given and some polyhedral results including several facet‐defining and valid inequalities are presented. The separation problem for the different families of inequalities is studied. Numerical results from computational experiments are analyzed.