{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:27:52Z","timestamp":1760243272174,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T00:00:00Z","timestamp":1664409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This paper presents a new heuristic algorithm tailored to solve large instances of an NP-hard variant of the shortest path problem, denoted the cost-balanced path problem, recently proposed in the literature. The problem consists in finding the origin\u2013destination path in a direct graph, having both negative and positive weights associated with the arcs, such that the total sum of the weights of the selected arcs is as close to zero as possible. At least to the authors\u2019 knowledge, there are no solution algorithms for facing this problem. The proposed algorithm integrates a constructive procedure and an improvement procedure, and it is validated thanks to the implementation of an iterated neighborhood search procedure. The reported numerical experimentation shows that the proposed algorithm is computationally very efficient. In particular, the proposed algorithm is most suitable in the case of large instances where it is possible to prove the existence of a perfectly balanced path and thus the optimality of the solution by finding a good percentage of optimal solutions in negligible computational time.<\/jats:p>","DOI":"10.3390\/a15100364","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T21:03:10Z","timestamp":1664485390000},"page":"364","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Constructive Heuristics and an Iterated Neighborhood Search Procedure to Solve the Cost-Balanced Path Problem"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6532-2287","authenticated-orcid":false,"given":"Daniela","family":"Ambrosino","sequence":"first","affiliation":[{"name":"Department of Economics and Business Studies, University of Genoa, 16126 Genoa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6243-4512","authenticated-orcid":false,"given":"Carmine","family":"Cerrone","sequence":"additional","affiliation":[{"name":"Department of Economics and Business Studies, University of Genoa, 16126 Genoa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7934-6992","authenticated-orcid":false,"given":"Anna","family":"Sciomachen","sequence":"additional","affiliation":[{"name":"Department of Economics and Business Studies, University of Genoa, 16126 Genoa, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0167-6377(84)90061-0","article-title":"Balanced optimization problems","volume":"3","author":"Martello","year":"1984","journal-title":"Oper. Res. Lett."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0167-6377(91)90085-4","article-title":"Minimum deviation and balanced optimization: A unified approach","volume":"10","author":"Duin","year":"1991","journal-title":"Oper. Res. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"692","DOI":"10.1016\/j.ejor.2005.03.055","article-title":"A balancing method and genetic algorithm for disassembly line balancing","volume":"179","author":"McGovern","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1016\/j.ejor.2004.07.030","article-title":"A genetic algorithm for robotic assembly line balancing","volume":"168","author":"Levitin","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0925-5273(00)00056-6","article-title":"Minimizing WIP inventory in reliable production lines","volume":"70","author":"Papadopoulos","year":"2001","journal-title":"Int. J. Prod. Econ."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF00167523","article-title":"Workload balance and part-transfer minimization in flexible manufacturing systems","volume":"3","author":"Arbib","year":"1991","journal-title":"Int. J. Flex. Manuf. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1080\/09537280701614407","article-title":"Performance measurement of supply chain management using the analytical hierarchy process","volume":"18","author":"Bhagwat","year":"2007","journal-title":"Prod. Plan. Control."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.dss.2004.08.008","article-title":"Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation","volume":"39","author":"Babaioff","year":"2005","journal-title":"Decis. Support Syst."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1080\/00207540110079761","article-title":"Optimal solution for the flow path design problem of a balanced unidirectional AGV system","volume":"40","author":"Kaspi","year":"2002","journal-title":"Int. J. Prod. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1287\/opre.1110.0998","article-title":"Asymptotic optimality of balanced routing","volume":"60","author":"Chen","year":"2012","journal-title":"Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.cor.2016.07.010","article-title":"Matheuristics for the single-path design-balanced service network design problem","volume":"77","author":"Li","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ambrosino, D., and Cerrone, C. (2022). The Cost-Balanced Path Problem: A Mathematical Formulation and Complexity Analysis. Mathematics, 10.","DOI":"10.3390\/math10050804"},{"key":"ref_13","first-page":"91","article-title":"Variants of the shortest path problem","volume":"6","author":"Turner","year":"2011","journal-title":"Alg. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Greco, S., Pavone, M.F., Talbi, E.-G., and Vigo, D. (2021). Metaheuristics for combinatorila optimization. Advances in Intelligent Systems and Computing, Springer.","DOI":"10.1007\/978-3-030-68520-1"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Akbay, M., and Kalayci, C. (2021). A variable neighborhood search algorithm for cost-balanced travelling salesman problem. Metaheuristics for Combinatorila Optimization Advances\u2014Intelligent Systems and Computing, Springer.","DOI":"10.1007\/978-3-030-68520-1_3"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1016\/j.cor.2010.09.016","article-title":"The balanced traveling salesman problem","volume":"38","author":"Larusic","year":"2011","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Pierotti, J., Ferretti, L., Pozzi, L., and van Essen, J.T. (2021). Adaptive Iterated Local Search with Random Restarts for the Balanced Travelling Salesman Problem. Metaheuristics for Combinatorila Optimization Advances\u2014Intelligent Systems and Computing, Springer.","DOI":"10.1007\/978-3-030-68520-1_4"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"107330","DOI":"10.1016\/j.knosys.2021.107330","article-title":"IT algorithm with local search for large scale multiple balanced traveling salesmen problem","volume":"229","author":"Dong","year":"2021","journal-title":"Knowl.-Based Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.swevo.2016.06.005","article-title":"Genetic algorithms to balanced tree structures in graphs","volume":"32","author":"Moharam","year":"2017","journal-title":"Swarm Evol. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1016\/j.tcs.2015.08.025","article-title":"Two paths location of a tree with positive or negative weights","volume":"607","author":"Zhou","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/j.sbspro.2013.12.827","article-title":"An Algorithmic Framework for Computing Shortest Routes in Urban Multimodal Networks with Different Criteria","volume":"108","author":"Ambrosino","year":"2014","journal-title":"Procedia Soc. Behav. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.jda.2017.01.001","article-title":"Hybrid Bellman\u2013Ford\u2013Dijkstra algorithm","volume":"42","author":"Dinitz","year":"2017","journal-title":"J. Discret. Alg."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Lewis, R. (2020). Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties. Algorithms, 13.","DOI":"10.3390\/a13110269"},{"key":"ref_25","first-page":"203","article-title":"Modified Dijkstra Shortest Path Algorithm for SD Networks","volume":"13","author":"Abdelghany","year":"2022","journal-title":"Int. J. Electr. Comput. Eng. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2765","DOI":"10.1007\/s00500-017-2540-8","article-title":"The rainbow spanning forest problem","volume":"22","author":"Carrabs","year":"2018","journal-title":"Soft Comput."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"ref_28","unstructured":"(2022, September 12). Test Instances. Available online: https:\/\/github.com\/CarmineCerrone\/CostBalancedPathProblem."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/10\/364\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:42:12Z","timestamp":1760143332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/10\/364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,29]]},"references-count":28,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2022,10]]}},"alternative-id":["a15100364"],"URL":"https:\/\/doi.org\/10.3390\/a15100364","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,9,29]]}}}