Uma heurística baseada em colônia de formigas para o problema do carteiro chinês misto

Abstract

The Chinese Postman Problem (Chinese Postman Problem, in English) is one of the classic challenges in computer science, especially in the graphs. It is a combinatorial optimization problem well known with a multitude of practical applications. Much of the real-world problems where you need to go through a city, a map or excerpt from a network of resources, such as urban waste collection, inspection of wires, removal of ice or delivery of letters, can be modeled by the Chinese postman problem (CPP) or its variations. Basically, the aim is a minimum cost path in a graph, so that the path covering all edges and arcs of the graph at least once. This problem has a solution in polynomial time for both the oriented version to version as non-oriented. The object of this paper is the change in CPP known as Mixed Chinese Postman Problem, which co-exist in a graph edges (non-targeted) and arcs. This variation of the CPP is NP-complete [Papadimitriou, 1976]. It proposed a heuristic based on ant colonies for the MCPP (Mixed Chinese Postman Problem) as well as a procedure for continuous improvement of the solution.