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.
2023
978-84-1351-264-8
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11369/445116
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact