Open data and open-source software are vital for fostering scientific research transparency, reproducibility, and collaboration. By leveraging open data, researchers can access high-quality information without barriers, while open-source tools provide the flexibility and customization needed for innovative solutions. In this study, we used Python to freely download urban maps of some Italian municipalities belonging to the Daunian Mountains area (province of Foggia, Apulia, Italy), represented as graphs. These maps served as the basis for addressing the Mixed Chinese Postman Problem (MCPP), a well-known NP-complete problem in graph theory. The MCPP involves finding the shortest route that traverses all the edges of a mixed graph at least once, with the challenge of considering the difference between directed and undirected edges. To solve the MCPP, we implemented an artificial intelligence approach using Ant Colony Optimization (ACO), a bio-inspired metaheuristic that simulates the behavior of ants in searching for efficient paths. Our article details the entire workflow, from data acquisition and preprocessing of urban graphs to the optimization and analysis of ACO hyperparameters. Through an extensive optimization process, we identified the most effective hyperparameter configurations for solving the MCPP on these graphs. We also assessed the strengths and limitations of metaheuristics when applied to NP-complete problems. Aligned with the principles of open science, we release the original graph datasets of the Subappennino Dauno municipalities, together with the Python codes used for graph extraction and the best solutions obtained in the experiments, making them available for reuse and testing of alternative optimization methodologies by other researchers. This work demonstrates how integrating open data and open-source tools can address complex scientific challenges and foster collaborative research. Moreover, using ACO enhances the model’s explainability by enabling the identification and analysis of hyperparameter patterns concerning the problem’s structural characteristics. This approach allows for a deeper structural understanding of the problem itself and provides insights into the theoretically optimal techniques that can be employed to address it.
Ant colony optimization for solving mixed Chinese postman problem on open real world data
Domenico Santoro;
2026-01-01
Abstract
Open data and open-source software are vital for fostering scientific research transparency, reproducibility, and collaboration. By leveraging open data, researchers can access high-quality information without barriers, while open-source tools provide the flexibility and customization needed for innovative solutions. In this study, we used Python to freely download urban maps of some Italian municipalities belonging to the Daunian Mountains area (province of Foggia, Apulia, Italy), represented as graphs. These maps served as the basis for addressing the Mixed Chinese Postman Problem (MCPP), a well-known NP-complete problem in graph theory. The MCPP involves finding the shortest route that traverses all the edges of a mixed graph at least once, with the challenge of considering the difference between directed and undirected edges. To solve the MCPP, we implemented an artificial intelligence approach using Ant Colony Optimization (ACO), a bio-inspired metaheuristic that simulates the behavior of ants in searching for efficient paths. Our article details the entire workflow, from data acquisition and preprocessing of urban graphs to the optimization and analysis of ACO hyperparameters. Through an extensive optimization process, we identified the most effective hyperparameter configurations for solving the MCPP on these graphs. We also assessed the strengths and limitations of metaheuristics when applied to NP-complete problems. Aligned with the principles of open science, we release the original graph datasets of the Subappennino Dauno municipalities, together with the Python codes used for graph extraction and the best solutions obtained in the experiments, making them available for reuse and testing of alternative optimization methodologies by other researchers. This work demonstrates how integrating open data and open-source tools can address complex scientific challenges and foster collaborative research. Moreover, using ACO enhances the model’s explainability by enabling the identification and analysis of hyperparameter patterns concerning the problem’s structural characteristics. This approach allows for a deeper structural understanding of the problem itself and provides insights into the theoretically optimal techniques that can be employed to address it.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
