{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:38:13Z","timestamp":1759847893435,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T00:00:00Z","timestamp":1604707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T00:00:00Z","timestamp":1604707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007069","name":"Universit\u00e0 della Calabria","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007069","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Several variants of the classical Constrained Shortest Path Problem have been presented in the literature so far. One of the most recent is the<jats:italic>k-Color Shortest Path Problem<\/jats:italic>(<jats:inline-formula><jats:alternatives><jats:tex-math>$$k$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-CSPP), that arises in the field of transmission networks design. The problem is formulated on a weighted edge-colored graph and the use of the colors as edge labels allows to take into account the matter of path reliability while optimizing its cost. In this work, we propose a dynamic programming algorithm and compare its performances with two solution approaches: a Branch and Bound technique proposed by the authors in their previous paper and the solution of the mathematical model obtained with CPLEX solver. The results gathered in the numerical validation evidenced how the dynamic programming algorithm vastly outperformed previous approaches.<\/jats:p>","DOI":"10.1007\/s11590-020-01659-z","type":"journal-article","created":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T15:02:44Z","timestamp":1604761364000},"page":"1973-1992","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A dynamic programming algorithm for solving the k-Color Shortest Path Problem"],"prefix":"10.1007","volume":"15","author":[{"given":"Daniele","family":"Ferone","sequence":"first","affiliation":[]},{"given":"Paola","family":"Festa","sequence":"additional","affiliation":[]},{"given":"Serena","family":"Fugaro","sequence":"additional","affiliation":[]},{"given":"Tommaso","family":"Pastore","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,7]]},"reference":[{"issue":"8","key":"1659_CR1","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1002\/net.3230230808","volume":"23","author":"DP Bertsekas","year":"1993","unstructured":"Bertsekas, D.P.: A simple and fast label correcting algorithm for shortest paths. Networks 23(8), 703\u2013709 (1993). https:\/\/doi.org\/10.1002\/net.3230230808","journal-title":"Networks"},{"key":"1659_CR2","first-page":"299","volume":"31","author":"H Broersma","year":"2005","unstructured":"Broersma, H., Li, X., Woeginger, G.J., Zhang, S.: Paths and cycles in colored graphs. Australas. J. Comb. 31, 299\u2013312 (2005)","journal-title":"Australas. J. Comb."},{"key":"1659_CR3","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.cor.2018.08.005","volume":"101","author":"F Carrabs","year":"2019","unstructured":"Carrabs, F., Cerulli, R., Felici, G., Singh, G.: Exact approaches for the orderly colored longest path problem: performance comparison. Comput. Oper. Res. 101, 275\u2013284 (2019)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1659_CR4","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.ejor.2019.08.052","volume":"282","author":"L Di Puglia Pugliese","year":"2020","unstructured":"Di Puglia Pugliese, L., Ferone, D., Festa, P., Guerriero, F.: Shortest path tour with time windows. Eur. J. Oper. Res. 282(1), 334\u2013344 (2020). https:\/\/doi.org\/10.1016\/j.ejor.2019.08.052","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"1659_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1002\/net.21511","volume":"62","author":"L Di Puglia Pugliese","year":"2013","unstructured":"Di Puglia Pugliese, L., Guerriero, F.: A survey of resource constrained shortest path problems: exact solution approaches. Networks 62(3), 183\u2013200 (2013)","journal-title":"Networks"},{"key":"1659_CR6","doi-asserted-by":"publisher","DOI":"10.6084\/m9.figshare.11762163.v1","author":"D Ferone","year":"2020","unstructured":"Ferone, D., Festa, P., Fugaro, S., Pastore, T.: Instances for the k-color shortest path problem (2020). https:\/\/doi.org\/10.6084\/m9.figshare.11762163.v1","journal-title":"Instances for the k-color shortest path problem"},{"key":"1659_CR7","doi-asserted-by":"publisher","unstructured":"Ferone, D., Festa, P., Pastore, T.: The k-color shortest path problem. In: Paolucci, M., Sciomachen, A., Uberti, P. (eds.) Advances in Optimization and Decision Science for Society, Services and Enterprises: ODS, Genoa, Italy, September 4\u20137, 2019, pp. 367\u2013376. Springer International Publishing, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34960-8_32","DOI":"10.1007\/978-3-030-34960-8_32"},{"issue":"8","key":"1659_CR8","doi-asserted-by":"publisher","first-page":"1362","DOI":"10.1080\/01605682.2018.1494527","volume":"70","author":"D Ferone","year":"2019","unstructured":"Ferone, D., Gruler, A., Festa, P., Juan, A.A.: Enhancing and extending the classical GRASP framework with biased randomisation and simulation. J. Oper. Res. Soc. 70(8), 1362\u20131375 (2019). https:\/\/doi.org\/10.1080\/01605682.2018.1494527","journal-title":"J. Oper. Res. Soc."},{"key":"1659_CR9","unstructured":"Festa, P., Pallottino, S.: A pseudo-random networks generator. Technical report, Department of Mathematics and Applications \u201cR. Caccioppoli\u201d, University of Naples FEDERICO II, Italy (2003)"},{"key":"1659_CR10","doi-asserted-by":"publisher","unstructured":"Festa, P., Pastore, T., Ferone, D., Juan, A.A., Bayliss, C.: Integrating biased-randomized GRASP with Monte Carlo simulation for solving the vehicle routing problem with stochastic demands. In: 2018 Winter Simulation Conference (WSC), pp. 2989\u20133000 (2019). https:\/\/doi.org\/10.1109\/WSC.2018.8632348","DOI":"10.1109\/WSC.2018.8632348"},{"issue":"2","key":"1659_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybernet. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybernet."},{"key":"1659_CR12","unstructured":"Powell, W.B., Chen, Z.: A generalized threshold algorithm for the shortest path problem with time windows. DIMACS Series Discrete Math. Theor. Comput. Sci. 40, 303\u2013318 (1998)"},{"issue":"3","key":"1659_CR13","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/J.DISOPT.2006.05.007","volume":"3","author":"G Righini","year":"2006","unstructured":"Righini, G., Salani, M.: Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3), 255\u2013273 (2006). https:\/\/doi.org\/10.1016\/J.DISOPT.2006.05.007","journal-title":"Discrete Optim."},{"issue":"3","key":"1659_CR14","first-page":"32","volume":"3","author":"S Yuan","year":"2002","unstructured":"Yuan, S., Jue, J.P., et al.: Shared protection routing algorithm for optical network. Opt. Netw. Mag. 3(3), 32\u201339 (2002)","journal-title":"Opt. Netw. Mag."},{"key":"1659_CR15","doi-asserted-by":"crossref","unstructured":"Yuan, S., Varma, S., Jue, J.P.: Minimum-color path problems for reliability in mesh networks. In: IEEE INFOCOM, vol.\u00a04, p. 2658 (2005)","DOI":"10.1109\/INFCOM.2005.1498549"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01659-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-020-01659-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01659-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T02:57:58Z","timestamp":1723863478000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-020-01659-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,7]]},"references-count":15,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["1659"],"URL":"https:\/\/doi.org\/10.1007\/s11590-020-01659-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2020,11,7]]},"assertion":[{"value":"29 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2020","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original online version of this article was revised: The open access funding note was updated","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}