A Flow Formulation for the Close-Enough Arc Routing Problem

Description

The close-enough arc routing problem is a generalization of the classic arc routing problem and it has many interesting real-life applications. In this paper, we propose some techniques to reduce the size of the input graph and a new effective mixed integer programming formulation for the problem. Our experiments on directed graphs show the effectiveness of our reduction techniques. Computational results obtained by comparing our MIP model with the existing exact methods show that our algorithm is really effective in practice.

Additional details