Groupe d’études et de recherche en analyse des décisions

Solving Capacitated Arc Routing Problems using a transformation to the CVRP

Marcus V.S. Poggi De Aragao – Pontifícia Universidade Católica do Rio de Janeiro, Brésil

A well known transformation by Pearn, Assad and Golden reduces a Capacitated Arc Routing Problem (CARP) into an equivalent Capacitated Vehicle Routing Problem (CVRP). However, that transformation is regarded as unpractical, since an original instance with r required edges is turned into a CVRP over a complete graph with $$3 r + 1$$ vertices. We propose a similar transformation that reduces this graph to $$2 r + 1$$ vertices, with the additional restriction that $$r$$ edges are already fixed to 1. Using a recent branch-and-cut-and-price algorithm for the CVRP, we observed that it yields an effective way of attacking the CARP, being significantly better than the exact methods created specifically for that problem. Computational experiments obtained improved lower bounds for almost all open instances from the literature. Several such instances could be solved to optimality.