{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T22:33:59Z","timestamp":1762900439463,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"13","license":[{"start":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T00:00:00Z","timestamp":1680307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T00:00:00Z","timestamp":1680307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 del Salento"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soft Comput"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Hierarchical Windy Postman Problem (HWPP) is an arc routing problem in which an order relation is imposed on the arcs\/edges of the graph, and one has to pass through each edge at least once while adhering to the hierarchical priority relations. The tour starts from and ends at a specific node and the aim is to minimize the length of the tour. We consider a variant of the HWPP in which (i) the precedence order of the edge hierarchies is linear and edges within each hierarchy are connected and (ii) the cost of serving each edge decreases with the number of times it is traversed, and we refer to it as HWPP with variable service costs. An integer non-heuristic linear mathematical formulation is proposed, and a solution approach is designed. Our solution heuristic adapts the layer algorithm of Dror et al. (Networks 17:283\u2013294, 1987) but employs an integer mathematical formulation as a sub-procedure instead of the blossom algorithm to find the least cost path between the nodes of the graph. This choice is based on the fact that the blossom algorithm requires a symmetric cost structure while we deal here with the general case of asymmetric cost structure, which makes our problem a windy variant of the postman problem. It should be noted that our problem is not asymmetric in the sense that there are no opposite arcs with different costs but there are edges which have different costs depending on the traversal direction. In order to compare the performance of our heuristic algorithm with respect to the performance of the mathematical model that is solved by the commercial solver Gurobi, 84 test instances are generated having varying sizes and densities and with different number of hierarchies. These test instances are solved by both methods and the generated results show that the proposed heuristic method is much faster and generates better quality solutions.<\/jats:p>","DOI":"10.1007\/s00500-023-08032-z","type":"journal-article","created":{"date-parts":[[2023,4,3]],"date-time":"2023-04-03T05:57:57Z","timestamp":1680501477000},"page":"8789-8805","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Solving the hierarchical windy postman problem with variable service costs using a math-heuristic algorithm"],"prefix":"10.1007","volume":"27","author":[{"given":"Muhammed Emre","family":"Keskin","sequence":"first","affiliation":[]},{"given":"Mustafa","family":"Y\u0131lmaz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8750-2470","authenticated-orcid":false,"given":"Chefi","family":"Triki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,1]]},"reference":[{"issue":"2","key":"8032_CR1","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.orl.2021.01.017","volume":"49","author":"VA Afanasev","year":"2021","unstructured":"Afanasev VA, van Bevern R, Tsidulko OY (2021) The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable. Oper Res Lett 49(2):270\u2013277","journal-title":"Oper Res Lett"},{"key":"8032_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.trb.2021.05.017","volume":"150","author":"V Akbari","year":"2021","unstructured":"Akbari V, Shiri D, Salman FS (2021) An online optimization approach to post-disaster road restoration. Transp Res Part b Methodol 150:1\u201325","journal-title":"Transp Res Part b Methodol"},{"issue":"2","key":"8032_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1080\/03052158808941206","volume":"14","author":"AS Alfa","year":"1988","unstructured":"Alfa AS, Liu DQ (1988) Postman routing problem in a hierarchical network. Eng Optim 14(2):127\u2013138","journal-title":"Eng Optim"},{"issue":"2","key":"8032_CR4","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10732-011-9183-1","volume":"19","author":"J Ar\u00e1oz","year":"2013","unstructured":"Ar\u00e1oz J, Fern\u00e1ndez E, Franquesa C (2013) GRASP and path relinking for the clustered prize-collecting arc routing problem. J Heuristics 19(2):343\u2013371","journal-title":"J Heuristics"},{"issue":"1","key":"8032_CR5","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/S0377-2217(02)00813-5","volume":"155","author":"EA Cabral","year":"2004","unstructured":"Cabral EA, Gendreau M, Ghiani G, Laporte G (2004) Solving the hierarchical chinese postman problem as a rural postman problem. Eur J Oper Res 155(1):44\u201350","journal-title":"Eur J Oper Res"},{"issue":"1","key":"8032_CR6","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s10100-018-0598-8","volume":"28","author":"MK \u00c7odur","year":"2020","unstructured":"\u00c7odur MK, Y\u0131lmaz M (2020) A time-dependent hierarchical Chinese postman problem. CEJOR 28(1):337\u2013366","journal-title":"CEJOR"},{"issue":"2","key":"8032_CR7","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1287\/trsc.2016.0686","volume":"51","author":"M Colombi","year":"2017","unstructured":"Colombi M, Corber\u00e1n A, Mansini R, Plana I, Sanchis JM (2017a) The hierarchical mixed rural postman problem. Transp Sci 51(2):755\u2013770","journal-title":"Transp Sci"},{"issue":"1","key":"8032_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.07.026","volume":"257","author":"M Colombi","year":"2017","unstructured":"Colombi M, Corber\u00e1n A, Mansini R, Plana I, Sanchis JM (2017b) The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm. Eur J Oper Res 257(1):1\u201312","journal-title":"Eur J Oper Res"},{"key":"8032_CR9","doi-asserted-by":"crossref","unstructured":"Corber\u00e1n \u00c1, Plana I, Sanchis JM (2014) The Chinese postman problem on directed, mixed and windy graphs. Arc routing problems, methods, and applications, MOS-SIAM Series on Optimization (Chapter 4), In: Corber\u00e1n \u00c1, Laporte G (eds), SIAM Publications, Philadelphia, 2014, pp 65\u201384","DOI":"10.1137\/1.9781611973679.ch4"},{"issue":"1","key":"8032_CR10","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1002\/net.21965","volume":"77","author":"\u00c1 Corber\u00e1n","year":"2021","unstructured":"Corber\u00e1n \u00c1, Eglese R, Hasle G, Plana I, Sanchis JM (2021) Arc routing problems: a review of the past, present, and future. Networks 77(1):88\u2013115","journal-title":"Networks"},{"issue":"1","key":"8032_CR11","first-page":"36","volume":"15","author":"P Damodaran","year":"2008","unstructured":"Damodaran P, Krishnamurthi M, Srihari K (2008) Lower bounds for Hierarchical Chinese postman problem. Int J Ind EngTheory Appl Pract 15(1):36\u201344","journal-title":"Int J Ind EngTheory Appl Pract"},{"issue":"1","key":"8032_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271","journal-title":"Numer Math"},{"key":"8032_CR13","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1002\/net.3230170304","volume":"17","author":"M Dror","year":"1987","unstructured":"Dror M, Stern H, Trudeau P (1987) Postman tour on a graph with precedence relation on arcs. Networks 17:283\u2013294","journal-title":"Networks"},{"volume-title":"Arc routing: theory, solutions and applications","year":"2000","key":"8032_CR14","unstructured":"Dror M (ed) (2000). Kluwer Academic Publishers, Norwell"},{"issue":"4","key":"8032_CR15","doi-asserted-by":"publisher","first-page":"1047","DOI":"10.1016\/j.cor.2012.10.013","volume":"40","author":"B Dussault","year":"2013","unstructured":"Dussault B, Golden B, Gro\u00ebr C, Wasil E (2013) Plowing with precedence: a variant of the windy postman problem. Comput Oper Res 40(4):1047\u20131059","journal-title":"Comput Oper Res"},{"key":"8032_CR16","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds J (1965) Paths, trees, and flowers. Can J Math 17:449\u2013467","journal-title":"Can J Math"},{"issue":"2","key":"8032_CR17","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"},{"key":"8032_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.cor.2015.06.001","volume":"64","author":"M Gendreau","year":"2015","unstructured":"Gendreau M, Ghiani G, Guerriero E (2015) Time-dependent routing problems: a review. Comput Oper Res 64:189\u2013197","journal-title":"Comput Oper Res"},{"issue":"1","key":"8032_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0167-6377(99)00046-2","volume":"26","author":"G Ghiani","year":"2000","unstructured":"Ghiani G, Improta G (2000) An algorithm for the hierarchical Chinese postman problem. Oper Res Lett 26(1):27\u201332","journal-title":"Oper Res Lett"},{"issue":"2","key":"8032_CR20","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/S0305-0548(03)00213-2","volume":"32","author":"G Ghiani","year":"2005","unstructured":"Ghiani G, Musmanno R, Paletta G, Triki C (2005) A heuristic for the periodic rural postman problem. Comput Oper Res 32(2):219\u2013228","journal-title":"Comput Oper Res"},{"issue":"1","key":"8032_CR21","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1080\/09720529.2008.10698167","volume":"11","author":"G Ghiani","year":"2008","unstructured":"Ghiani G, Manni E, Triki C (2008) The lane covering problem with time windows. J Discrete Math Sci Cryptogr 11(1):67\u201381","journal-title":"J Discrete Math Sci Cryptogr"},{"issue":"3","key":"8032_CR22","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1002\/net.3230110308","volume":"11","author":"BL Golden","year":"1981","unstructured":"Golden BL, Wong RT (1981) Capacitated arc routing problems. Networks 11(3):305\u2013315","journal-title":"Networks"},{"key":"8032_CR23","unstructured":"Gurobi optimizer 9.0 (2020). High-end libraries for math programming. http:\/\/www.gurobi.com\/. Accessed Nov 2020."},{"issue":"16","key":"8032_CR24","doi-asserted-by":"publisher","first-page":"7359","DOI":"10.1007\/s00500-018-3382-8","volume":"23","author":"ME Keskin","year":"2019","unstructured":"Keskin ME, Y\u0131lmaz M (2019) Chinese and windy postman problem with variable service costs. Soft Comput 23(16):7359\u20137373","journal-title":"Soft Comput"},{"issue":"2","key":"8032_CR25","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s00500-021-06213-2","volume":"26","author":"ME Keskin","year":"2022","unstructured":"Keskin ME, Triki C (2022) On the periodic hierarchical Chinese postman problem. Soft Comput 26(2):709\u2013724","journal-title":"Soft Comput"},{"key":"8032_CR26","unstructured":"Korteweg, P. (2002). Postman problems priorities and the concept of servicing.\u00a0Salamanca."},{"issue":"1","key":"8032_CR27","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.ejor.2004.06.003","volume":"169","author":"P Korteweg","year":"2006","unstructured":"Korteweg P, Volgenant T (2006) On the hierarchical Chinese postman problem with linear ordered classes. Eur J Oper Res 169(1):41\u201352","journal-title":"Eur J Oper Res"},{"issue":"1","key":"8032_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2014.07.048","volume":"241","author":"R Lahyani","year":"2015","unstructured":"Lahyani R, Khemakhem M, Semet F (2015) Rich vehicle routing problems: from a taxonomy to a definition. Eur J Oper Res 241(1):1\u201314","journal-title":"Eur J Oper Res"},{"issue":"3","key":"8032_CR29","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10732-015-9280-7","volume":"21","author":"SK Mandal","year":"2015","unstructured":"Mandal SK, Pacciarelli D, L\u00f8kketangen A, Hasle G (2015) A memetic NSGA-II for the bi-objective mixed capacitated general routing problem. J Heuristics 21(3):359\u2013390","journal-title":"J Heuristics"},{"issue":"4\u20135","key":"8032_CR30","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1016\/j.dam.2011.05.014","volume":"161","author":"IM Monroy","year":"2013","unstructured":"Monroy IM, Amaya CA, Langevin A (2013) The periodic capacitated arc routing problem with irregular services. Discret Appl Math 161(4\u20135):691\u2013701","journal-title":"Discret Appl Math"},{"issue":"3","key":"8032_CR31","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1002\/net.21762","volume":"70","author":"MC Mour\u00e3o","year":"2017","unstructured":"Mour\u00e3o MC, Pinto LS (2017) An updated annotated bibliography on arc routing problems. Networks 70(3):144\u2013194","journal-title":"Networks"},{"key":"8032_CR32","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.trb.2018.08.002","volume":"116","author":"BE Oruc","year":"2018","unstructured":"Oruc BE, Kara BY (2018) Post-disaster assessment routing problem. Transp Res Part b Methodol 116:76\u2013102","journal-title":"Transp Res Part b Methodol"},{"issue":"1","key":"8032_CR33","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1287\/trsc.1070.0195","volume":"42","author":"N Perrier","year":"2008","unstructured":"Perrier N, Langevin A, Amaya CA (2008) Vehicle routing for urban snow plowing operations. Transp Sci 42(1):44\u201356","journal-title":"Transp Sci"},{"issue":"12","key":"8032_CR34","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1139\/cjce-2017-0185","volume":"44","author":"O Quirion-Blais","year":"2017","unstructured":"Quirion-Blais O, Langevin A, Tr\u00e9panier M (2017) A case study of combined winter road snow plowing and de-icer spreading. Can J Civ Eng 44(12):1005\u20131013","journal-title":"Can J Civ Eng"},{"key":"8032_CR35","doi-asserted-by":"crossref","unstructured":"Sayata UB, Desai NP (2015) An algorithm for Hierarchical Chinese postman problem using minimum spanning tree approach based on Kruskals\u2019s algorithm. In: Souvenir of the 2015 IEEE International Advance Computing Conference, IACC 7154702, pp 222\u2013227","DOI":"10.1109\/IADCC.2015.7154702"},{"key":"8032_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.trb.2019.12.004","volume":"133","author":"S Shao","year":"2020","unstructured":"Shao S, Xu SX, Huang GQ (2020) Variable neighborhood search and tabu search for auction-based waste collection synchronization. Transp Res Part b Methodol 133:1\u201320","journal-title":"Transp Res Part b Methodol"},{"issue":"3","key":"8032_CR37","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10878-014-9755-8","volume":"29","author":"J Sun","year":"2015","unstructured":"Sun J, Meng Y, Tan G (2015) An integer programming approach for the Chinese postman problem with time-dependent travel time. J Comb Optim 29(3):565\u2013588","journal-title":"J Comb Optim"},{"issue":"03","key":"8032_CR38","doi-asserted-by":"publisher","first-page":"1740015","DOI":"10.1142\/S0217595917400152","volume":"34","author":"C Triki","year":"2017","unstructured":"Triki C (2017) Solving the periodic edge routing problem in the municipal waste collection. Asia Pacific J Oper Res 34(03):1740015","journal-title":"Asia Pacific J Oper Res"},{"issue":"2","key":"8032_CR500","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1504\/IJOR.2017.081478","volume":"28","author":"C Triki","year":"2017","unstructured":"Triki C, Akil J, Al-Azri N (2017) Optimising the periodic distribution of gas cylinders with customers priority. Int J Oper Res 28(2):279\u2013289","journal-title":"Int J Oper Res"},{"issue":"3","key":"8032_CR39","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1287\/trsc.2020.1035","volume":"55","author":"T Vidal","year":"2021","unstructured":"Vidal T, Martinelli R, Pham TA, H\u00e0 MH (2021) Arc routing with time-dependent travel times and paths. Transp Sci 55(3):706\u2013724","journal-title":"Transp Sci"}],"container-title":["Soft Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-023-08032-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00500-023-08032-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00500-023-08032-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,29]],"date-time":"2023-05-29T06:05:32Z","timestamp":1685340332000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00500-023-08032-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,1]]},"references-count":40,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["8032"],"URL":"https:\/\/doi.org\/10.1007\/s00500-023-08032-z","relation":{},"ISSN":["1432-7643","1433-7479"],"issn-type":[{"type":"print","value":"1432-7643"},{"type":"electronic","value":"1433-7479"}],"subject":[],"published":{"date-parts":[[2023,4,1]]},"assertion":[{"value":"10 March 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors of this research certify that there is no any affiliation with or involvement in any organization or entity with financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}