On Minimum Reload Cost Cycle Cover

We consider the problem of spanning the nodes of a given colored graph G=(N,A)G=(N,A) by a set of node-disjoint cycles at minimum reload cost, where a non-negative reload cost is paid whenever passing through a node where the two consecutive arcs have different colors. We call this problem Minimum Reload Cost Cycle Cover (MinRC3 for short). We prove that it is strongly NP-hard and not approximable within 1ϵ for any ϵ>0ϵ>0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. Some IP models for MinRC3 are then presented, one well suited for a Column Generation approach. The corresponding pricing subproblem is also proved strongly NP-hard. Primal bounds for MinRC3 are obtained via local search based heuristics exploiting 2-opt and 3-opt neighborhoods. Computational results are presented comparing lower and upper bounds obtained by the above mentioned approaches.