Algorithms for the Arc Routing Problem applied to Municipal Waste Collection

In this article, we consider the Enabled Arc Routing Problem (CARP), which consists of determining minimum cost routes for a fleet of vehicles, so that each required connection of a mixed graph is served by exactly one vehicle. An approach based on the decomposition of the graph into sectors is presented, with each sector being classified according to connectivity and degree balancing properties. For each class, specific strategies are adopted: Eulerian tracts are solved by Hierholzer's algorithm; weakly related sectors with unbalanced degrees are treated by the Hungarian Algorithm combined with Hierholzer; and disconnected sectors are addressed through an entire linear programming formulation. In this way, the approach explores the structure of the problem to integrate heuristic and exact techniques, aiming at the efficient obtaining of solutions. Experiments in literature instances and in real data from Itajubá-MG indicate that the approach is promising in practical contexts.