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.
ANT COLONY OPTIMIZATION FOR CHINESE POSTMAN PROBLEM
GIACINTO ANGELO SGARRO;LUCA GRILLI
2023-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.