A compact transformation of arc routing problems into node routing problems

摘要

We describe a compact method to transform arc routing problem instances into node routing problem instances. Any node routing problem instance thus created must be solved by a branch-and-price process, such as the one described in this paper. The purpose is to make the number of nodes in the resulting transformed graphs greater by only one unit than the number r of required arcs (arcs having demand) in the original graph, that is, r + 1 nodes. This low increase in the number of nodes represents an improvement compared to the methods previously presented by Pearn, Assad and Golden (3r + 1 nodes) and by Longo, Poggi de Aragao and Uchoa and also by Baldacci and Maniezzo (2r + 1 nodes). Using an adapted version of an existing branch-cut-and-price algorithm for a capacitated node routing problem on the transformed graph results in an effective approach for a capacitated arc routing problem. Computational experiments using this approach produced useful lower bounds in reasonable computational time for many challenging numerical instances from the literature. Additionally, some such previously open instances were solved to optimality for the first time.