{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T17:32:20Z","timestamp":1781803940258,"version":"3.54.5"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T00:00:00Z","timestamp":1700870400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T00:00:00Z","timestamp":1700870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100016112","name":"Universit\u00e0 di Foggia","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016112","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Neural Comput &amp; Applic"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper aims to solve the Chinese Postman Problem (CPP) using an Ant Colony Optimization (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 applications, including route optimization, interactive system analysis, and flow design. Although numerous algorithms aimed at solving CPP are present in the literature, very few meta-heuristic algorithms are proposed, and no ACO applications have been proposed to solve them. This paper tries to fill this gap by presenting an ACO algorithm that solves CPP (ACO-CPP). To prove its consistency and effectiveness, ACO-CPP is compared with a Genetic Algorithm (GA) and a recursive algorithm throughout three experiments: (1) recursive-ACO-GA comparisons over randomly generated graphs for the attainment of the global optimum; (2) ACO-GA statistical comparisons over specifically generated graphs; (3) recursive-ACO-GA comparisons by changing ACO hyperparameters over randomly generated graphs for the attainment of the global optimum. The experiments prove that the ACO-CPP algorithm is efficient and exhibits a consistency similar to GA when the number of possible solutions to explore is relatively low. However, when that number greatly exceeds those explored, ACO outperforms GA. This suggests that ACO is more suitable for solving problems with a CPP structure.<\/jats:p>","DOI":"10.1007\/s00521-023-09195-4","type":"journal-article","created":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T16:02:10Z","timestamp":1700928130000},"page":"2901-2920","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Ant colony optimization for Chinese postman problem"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4189-0674","authenticated-orcid":false,"given":"Giacinto Angelo","family":"Sgarro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Grilli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,11,25]]},"reference":[{"key":"9195_CR1","first-page":"273","volume":"1","author":"M Kwan","year":"1962","unstructured":"Kwan M (1962) Graphic programming using odd or even points. Chinese Math 1:273\u2013277","journal-title":"Chinese Math"},{"key":"9195_CR2","doi-asserted-by":"crossref","unstructured":"Jiang H, Kang L, Zhang S, Zhu F (2010) Genetic algorithm for mixed chinese postman problem. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol 6382 LNCS, pp 193\u2013199. 10.1007\/978-3-642-16493-4_20","DOI":"10.1007\/978-3-642-16493-4_20"},{"key":"9195_CR3","doi-asserted-by":"crossref","unstructured":"Filho MG, De\u00a0\u00c1vila Ribeiro\u00a0Junqueira R (2010) Chinese postman problem (cpp): solution methods and computational time. Int J Logist Syst Manage 7(3):324\u2013344","DOI":"10.1504\/IJLSM.2010.035038"},{"issue":"4","key":"9195_CR4","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/MCI.2006.329691","volume":"1","author":"M Dorigo","year":"2006","unstructured":"Dorigo M, Birattari M, St\u00fctzle T (2006) Ant colony optimization artificial ants as a computational intelligence technique. IEEE Comput Intell Mag 1(4):28\u201339","journal-title":"IEEE Comput Intell Mag"},{"issue":"1","key":"9195_CR5","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/BF02899501","volume":"8","author":"J Hua","year":"2003","unstructured":"Hua J, Li-shan K (2003) Genetic algorithm for chinese postman problems. Wuhan Univ J Nat Sci 8(1):316\u2013318","journal-title":"Wuhan Univ J Nat Sci"},{"issue":"2","key":"9195_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1287\/opre.43.2.231","volume":"43","author":"HA Eiselt","year":"1995","unstructured":"Eiselt HA, Gendreau M, Laporte G (1995) Arc routing problems, part i: the chinese postman problem. Oper Res 43(2):231\u2013242","journal-title":"Oper Res"},{"issue":"1","key":"9195_CR7","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds J, Johnson EL (1973) Matching, euler tours and the chinese postman. Math Programm 5(1):88\u2013124","journal-title":"Math Programm"},{"key":"9195_CR8","unstructured":"Larson RC, Odoni AR (1981) Urban operations research vol. monograph"},{"key":"9195_CR9","doi-asserted-by":"crossref","unstructured":"Christofides N, Benavent E, Campos V, Corber\u00e1n A, Mota E (1984) An optimal method for the mixed postman problem. In: Proceedings of the 11th IFIP conference copenhagen system modelling and optimization, pp 641\u2013649. Springer, Denmark, 25\u201329 July 1983","DOI":"10.1007\/BFb0008937"},{"issue":"1","key":"9195_CR10","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/0215009","volume":"15","author":"Z Galil","year":"1986","unstructured":"Galil Z, Micali S, Gabow H (1986) An o(ev$$\\backslash$$logv) algorithm for finding a maximal weighted matching in general graphs. SIAM J Comput 15(1):120\u2013130","journal-title":"SIAM J Comput"},{"issue":"1","key":"9195_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF01594929","volume":"50","author":"U Derigs","year":"1991","unstructured":"Derigs U, Metz A (1991) Solving (large scale) matching problems combinatorially. Math Programm 50(1):113\u2013121","journal-title":"Math Programm"},{"key":"9195_CR12","volume-title":"Combinatorial optimization: networks and matroids","author":"EL Lawler","year":"2001","unstructured":"Lawler EL (2001) Combinatorial optimization: networks and matroids. Courier Corporation, New York"},{"key":"9195_CR13","doi-asserted-by":"crossref","unstructured":"Yang J, Huang K, Yin Z, Cui J (2018) The chinese postman problem based on molecular beacon strand displacement. In: 2018 14th International conference on natural computation, fuzzy systems and knowledge discovery (ICNC-FSKD), pp 519\u2013523. IEEE. 10.1109\/FSKD.2018.8686916","DOI":"10.1109\/FSKD.2018.8686916"},{"issue":"4","key":"9195_CR14","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6501\/acb075","volume":"34","author":"L Shen","year":"2023","unstructured":"Shen L, Tao H, Ni Y, Wang Y, Stojanovic V (2023) Improved yolov3 model with feature map cropping for multi-scale road object detection. Measure Sci Technol 34(4):045406","journal-title":"Measure Sci Technol"},{"key":"9195_CR15","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/s10957-015-0706-z","volume":"168","author":"V Stojanovic","year":"2016","unstructured":"Stojanovic V, Nedic N (2016) A nature inspired parameter tuning approach to cascade control for hydraulically driven parallel robot platform. J Opt Theory Appl 168:332\u2013347","journal-title":"J Opt Theory Appl"},{"key":"9195_CR16","doi-asserted-by":"crossref","unstructured":"Zhuang Z, Tao H, Chen Y, Stojanovic V, Paszke W (2022) An optimal iterative learning control approach for linear systems with nonuniform trial lengths under input constraints. IEEE Trans Syst Man Cybernet Syst","DOI":"10.1109\/TSMC.2022.3225381"},{"key":"9195_CR17","doi-asserted-by":"publisher","first-page":"201606","DOI":"10.1109\/ACCESS.2020.3035899","volume":"8","author":"C Wu","year":"2020","unstructured":"Wu C, Fu X (2020) An agglomerative greedy brain storm optimization algorithm for solving the tsp. IEEE Access 8:201606\u2013201621","journal-title":"IEEE Access"},{"key":"9195_CR18","doi-asserted-by":"publisher","first-page":"164820","DOI":"10.1109\/ACCESS.2021.3133493","volume":"9","author":"BAS Emambocus","year":"2021","unstructured":"Emambocus BAS, Jasser MB, Hamzah M, Mustapha A, Amphawan A (2021) An enhanced swap sequence-based particle swarm optimization algorithm to solve tsp. IEEE Access 9:164820\u2013164836","journal-title":"IEEE Access"},{"issue":"29","key":"9195_CR19","first-page":"1","volume":"8","author":"N Sathya","year":"2015","unstructured":"Sathya N, Muthukumaravel A (2015) A review of the optimization algorithms on traveling salesman problem. Ind J Sci Technol 8(29):1\u20134","journal-title":"Ind J Sci Technol"},{"issue":"14","key":"9195_CR20","doi-asserted-by":"publisher","first-page":"2431","DOI":"10.3390\/math10142431","volume":"10","author":"AR Antunes","year":"2022","unstructured":"Antunes AR, Matos MA, Rocha AMA, Costa LA, Varela LR (2022) A statistical comparison of metaheuristics for unrelated parallel machine scheduling problems with setup times. Mathematics 10(14):2431","journal-title":"Mathematics"},{"key":"9195_CR21","doi-asserted-by":"crossref","unstructured":"Wang W, Zhao J, Huang J (2020) Improved ant colony genetic algorithm for solving traveling salesman problem. J Phys Conf Ser 1693:012085. IOP Publishing","DOI":"10.1088\/1742-6596\/1693\/1\/012085"},{"key":"9195_CR22","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1007\/s10957-015-0706-z","volume":"168","author":"V Stojanovic","year":"2016","unstructured":"Stojanovic V, Nedic N (2016) A nature inspired parameter tuning approach to cascade control for hydraulically driven parallel robot platform. J Opt Theory Appl 168:332\u2013347","journal-title":"J Opt Theory Appl"},{"key":"9195_CR23","doi-asserted-by":"publisher","DOI":"10.3389\/fpsyt.2022.939411","volume":"13","author":"D Xia","year":"2022","unstructured":"Xia D, Quan W, Wu T (2022) Optimizing functional near-infrared spectroscopy (fnirs) channels for schizophrenic identification during a verbal fluency task using metaheuristic algorithms. Front Psychiatry 13:939411","journal-title":"Front Psychiatry"},{"issue":"3","key":"9195_CR24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0954-1810(01)00005-X","volume":"15","author":"KC Tan","year":"2001","unstructured":"Tan KC, Lee LH, Zhu Q, Ou K (2001) Heuristic methods for vehicle routing problem with time windows. Artif Intell Eng 15(3):281\u2013295","journal-title":"Artif Intell Eng"},{"key":"9195_CR25","volume":"16","author":"JA Abdor-Sierra","year":"2022","unstructured":"Abdor-Sierra JA, Merch\u00e1n-Cruz EA, Rodr\u00edguez-Ca\u00f1izo RG (2022) A comparative analysis of metaheuristic algorithms for solving the inverse kinematics of robot manipulators. Res Eng 16:100597","journal-title":"Res Eng"},{"issue":"8","key":"9195_CR26","doi-asserted-by":"publisher","first-page":"12212","DOI":"10.1002\/eng2.12212","volume":"2","author":"I Gagnon","year":"2020","unstructured":"Gagnon I, April A, Abran A (2020) A critical analysis of the bat algorithm. Eng Rep 2(8):12212","journal-title":"Eng Rep"},{"key":"9195_CR27","doi-asserted-by":"crossref","unstructured":"Nejad AS, Fazekas G (2022) Solving a traveling salesman problem using meta-heuristics. IAES Int J Artif Intell (IJ-AI) 11(1):41","DOI":"10.11591\/ijai.v11.i1.pp41-49"},{"issue":"1","key":"9195_CR28","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.jda.2011.06.002","volume":"10","author":"D Sudholt","year":"2012","unstructured":"Sudholt D, Thyssen C (2012) Running time analysis of ant colony optimization for shortest path problems. J Discrete Algorithms 10(1):165\u2013180","journal-title":"J Discrete Algorithms"},{"issue":"5","key":"9195_CR29","doi-asserted-by":"publisher","first-page":"3403","DOI":"10.1016\/j.aej.2021.08.058","volume":"61","author":"D Di Caprio","year":"2022","unstructured":"Di Caprio D, Ebrahimnejad A, Alrezaamiri H, Santos-Arteaga FJ (2022) A novel ant colony algorithm for solving shortest path problems with fuzzy arc weights. Alexandria Eng J 61(5):3403\u20133415","journal-title":"Alexandria Eng J"},{"key":"9195_CR30","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group"},{"key":"9195_CR31","doi-asserted-by":"crossref","unstructured":"Gunderson DS (2014) Handbook of mathematical induction: theory and applications. CRC Press, New York, p 240. 9781420093650","DOI":"10.1201\/b16005"},{"key":"9195_CR32","unstructured":"Hein JL (2015) Discrete structures, logic, and computability, example 3: the handshaking problem, p 703. Jones & Bartlett Publishers, LLC. ISBN: 9781284070408"},{"issue":"55","key":"9195_CR33","first-page":"2511","volume":"10","author":"LJ Simenthy","year":"2015","unstructured":"Simenthy LJ, Bobanand R, Soumya Krishnan M (2015) A comparison based analysis of euler circuit finding algorithms. Int J Appl Eng Res 10(55):2511\u20132514","journal-title":"Int J Appl Eng Res"},{"issue":"2","key":"9195_CR34","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1162\/106454699568728","volume":"5","author":"M Dorigo","year":"1999","unstructured":"Dorigo M, Di Caro G, Gambardella LM (1999) Ant algorithms for discrete optimization. Artif Life 5(2):137\u2013172","journal-title":"Artif Life"},{"issue":"5","key":"9195_CR35","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1177\/0734242X211003975","volume":"40","author":"Y-C Liang","year":"2022","unstructured":"Liang Y-C, Minanda V, Gunawan A (2022) Waste collection routing problem: a mini-review of recent heuristic approaches and applications. Waste Manage Res 40(5):519\u2013537","journal-title":"Waste Manage Res"},{"key":"9195_CR36","doi-asserted-by":"crossref","unstructured":"Wang C, Zhu R, Jiang Y, Liu, W., Jeon, S.-W., Sun, L., Hang, H (2023) A scheme library-based ant colony optimization with 2-opt local search for dynamic traveling salesman problem. CMES Comput Model Eng Sci 135(2)","DOI":"10.32604\/cmes.2022.022807"},{"issue":"2","key":"9195_CR37","doi-asserted-by":"publisher","first-page":"28","DOI":"10.3390\/logistics5020028","volume":"5","author":"PN Ky Phuc","year":"2021","unstructured":"Ky Phuc PN, Phuong Thao NL (2021) Ant colony optimization for multiple pickup and multiple delivery vehicle routing problem with time window and heterogeneous fleets. Logistics 5(2):28","journal-title":"Logistics"},{"issue":"1","key":"9195_CR38","doi-asserted-by":"publisher","first-page":"12518","DOI":"10.1038\/s41598-023-38855-7","volume":"13","author":"MI Azeez","year":"2023","unstructured":"Azeez MI, Abdelhaleem A, Elnaggar S, Moustafa KA, Atia KR (2023) Optimized sliding mode controller for trajectory tracking of flexible joints three-link manipulator with noise in input and output. Sci Rep 13(1):12518","journal-title":"Sci Rep"},{"issue":"2","key":"9195_CR39","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s42452-022-05271-x","volume":"5","author":"N Mehmood","year":"2023","unstructured":"Mehmood N, Umer M, Asgher U (2023) Application of hybrid sfla-aco algorithm and cam softwares for optimization of drilling tool path problems. SN Appl Sci 5(2):61","journal-title":"SN Appl Sci"},{"key":"9195_CR40","doi-asserted-by":"crossref","unstructured":"Al Bataineh A, Kaur D, Jalali SMJ (2022) Multi-layer perceptron training optimization using nature inspired computing. IEEE Access 10:36963\u201336977","DOI":"10.1109\/ACCESS.2022.3164669"},{"key":"9195_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2021.102353","volume":"111","author":"H Singh","year":"2021","unstructured":"Singh H, Tyagi S, Kumar P, Gill SS, Buyya R (2021) Metaheuristics for scheduling of heterogeneous tasks in cloud computing environments: analysis, performance evaluation, and future directions. Simul Modell Pract Theory 111:102353","journal-title":"Simul Modell Pract Theory"},{"issue":"12","key":"9195_CR42","doi-asserted-by":"publisher","first-page":"1437","DOI":"10.3390\/electronics8121437","volume":"8","author":"M Beschi","year":"2019","unstructured":"Beschi M, Mutti S, Nicola G, Faroni M, Magnoni P, Villagrossi E, Pedrocchi N (2019) Optimal robot motion planning of redundant robots in machining and additive manufacturing applications. Electronics 8(12):1437","journal-title":"Electronics"},{"key":"9195_CR43","doi-asserted-by":"crossref","unstructured":"Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybernet Part b (cybernetics) 26(1):29\u201341","DOI":"10.1109\/3477.484436"},{"issue":"8","key":"9195_CR44","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","volume":"16","author":"T St\u00fctzle","year":"2000","unstructured":"St\u00fctzle T, Hoos HH (2000) Max-min ant system. Future Generation Comput Syst 16(8):889\u2013914","journal-title":"Future Generation Comput Syst"},{"key":"9195_CR45","doi-asserted-by":"crossref","unstructured":"Dorigo M, Gambardella LM (1997) Ant colonies for the travelling salesman problem. Biosystems 43(2):73\u201381","DOI":"10.1016\/S0303-2647(97)01708-5"},{"key":"9195_CR46","doi-asserted-by":"crossref","unstructured":"Gambardella LM, Dorigo M (1996) Solving symmetric and asymmetric tsps by ant colonies. In: Proceedings of IEEE international conference on evolutionary computation, pp 622\u2013627. IEEE","DOI":"10.1109\/ICEC.1996.542672"},{"key":"9195_CR47","volume-title":"Biologically inspired optimization methods: an introduction","author":"M Wahde","year":"2008","unstructured":"Wahde M (2008) Biologically inspired optimization methods: an introduction. WIT press, Boston"},{"key":"9195_CR48","volume-title":"Graph theory, 1736\u20131936","author":"N Biggs","year":"1986","unstructured":"Biggs N, Lloyd EK, Wilson RJ (1986) Graph theory, 1736\u20131936. Oxford University Press, Oxford"},{"issue":"1","key":"9195_CR49","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(01)00123-0","volume":"137","author":"DF Jones","year":"2002","unstructured":"Jones DF, Mirrazavi SK, Tamiz M (2002) Multi-objective meta-heuristics: an overview of the current state-of-the-art. Eur J Oper Res 137(1):1\u20139","journal-title":"Eur J Oper Res"}],"container-title":["Neural Computing and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00521-023-09195-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00521-023-09195-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00521-023-09195-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,3]],"date-time":"2024-11-03T10:02:02Z","timestamp":1730628122000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00521-023-09195-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,25]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["9195"],"URL":"https:\/\/doi.org\/10.1007\/s00521-023-09195-4","relation":{},"ISSN":["0941-0643","1433-3058"],"issn-type":[{"value":"0941-0643","type":"print"},{"value":"1433-3058","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,25]]},"assertion":[{"value":"6 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no actual or potential conflict of interest in relation to this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}