ANT COLONY OPTIMIZATION FOR CHINESE POSTMAN PROBLEM

This paper aims to solve the Chinese Postman Problem (CPP) using an Ant Colony Op-timization (ACO) algorithm. In graph theory, the CPP looks for the shortest closed path that visits every edge of a connected undirected graph. This problem has many applica-tions, including route optimization, interactive system analysis, and flow design. Alt-hough numerous algorithms aimed at solving CPP are present in the literature, there are very few meta-heuristic algorithms proposed, and no ACO applications have been pro-posed to solve it. This paper tries to fill this gap by presenting an ACO algorithm that solves CPP (ACO-CPP). In addition, it compares its performances with a Genetic Algo-rithm (GA) and a recursive algorithm that explores all the possible solutions and selects the best one. Experiments show that the ACO-CPP algorithm is efficient and can maintain consistency even when the number of possible solutions is much greater than the number of solutions explored.