Heuristics for the Profitable Close-Enough Arc Routing Problem.

In this paper we solve a practical variant of an arc routing problem. We target the close enough model in which clients can be served from relatively close arcs. This variant, known as the profitable close-enough arc routing problem, models real situations, such as inventory management or automated meter reading. We propose a heuristic based on the variable neighborhood search methodology to maximize the sum of profits of the clients served (penalized with the distance traveled). Our method incorporates efficient search strategies to speed up the optimization process, as required in practical applications. We present extensive experimentation over a benchmark of previously reported instances. Specifically, we first set the key search parameters of our method, and then compare it with the state-of-the-art heuristics for this problem. Our heuristic outperforms the previous algorithms published for this problem, as confirmed by the statistical analysis, which permits to draw significant conclusions. • A literature overview on close-enough is carried out. • A MultiStart-VNS algorithm is proposed and adapted to solve the PCEARP. • The experimental results proved the efficiency of the proposed algorithm. • The metaheuristic algorithm outperforms other existing methods for the problem. • The method has a great potential to be applied in emerging real-life problems. [ABSTRACT FROM AUTHOR]