O problema do carteiro chines em grafos mistos: otimização através da metaheurística colônia de formigas

Abstract

The Mixed Chinese Postman Problem (MCPP) models routing tasks in which all edges of a network must be traversed at minimum cost, with applications in street cleaning and infrastructure inspection. Since this mixed variant is NP-complete, exact methods are restricted to small and medium-sized instances, motivating the use of heuristics and metaheuristics. This work implements and evaluates two Ant Colony variants (Ant System and Elitist Ant System) and a greedy heuristic for the MCPP, using benchmark instances from the literature. Solution cost, gap with respect to the known optimum and running time are compared. The computational results show that, under the tested configurations, the greedy heuristic outperformed the Ant Colony variants in both solution quality and CPU time, suggesting that more problem-oriented adaptations are required for Ant-based models to become competitive on mixed-edge routing problems.