{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T19:48:46Z","timestamp":1775850526443,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T00:00:00Z","timestamp":1660089600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T00:00:00Z","timestamp":1660089600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u251c\u00e1 della Calabria"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper studies a generalization of the shortest path tour problem with time windows (<jats:italic>GSPTPTW<\/jats:italic>). The aim is to find a single-origin single-destination shortest path, which has to pass through an ordered sequence of not necessarily disjoint node-subsets. Each node has a time window for each node-subset to which it belongs. We investigate the theoretical properties of <jats:italic>GSPTPTW<\/jats:italic> and propose a dynamic programming approach to solve it. Numerical results collected on a large set of new benchmark instances highlight the effectiveness of the proposed solution approach.<\/jats:p>","DOI":"10.1007\/s10589-022-00405-8","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T20:02:46Z","timestamp":1660161766000},"page":"593-614","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A generalized shortest path tour problem with time windows"],"prefix":"10.1007","volume":"83","author":[{"given":"L.","family":"Di Puglia Pugliese","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D.","family":"Ferone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Festa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3887-1317","authenticated-orcid":false,"given":"F.","family":"Guerriero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,10]]},"reference":[{"issue":"1","key":"405_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF01939836","volume":"15","author":"CP Bajaj","year":"1971","unstructured":"Bajaj, C.P.: Some constrained shortest-route problems. Math. Methods Oper. Res. 15(1), 287\u2013301 (1971). https:\/\/doi.org\/10.1007\/BF01939836","journal-title":"Math. Methods Oper. Res."},{"key":"405_CR2","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s11590-010-0258-y","volume":"6","author":"P Festa","year":"2012","unstructured":"Festa, P.: Complexity analysis and optimization of the shortest path tour problem. Optim. Lett. 6, 163\u2013175 (2012). https:\/\/doi.org\/10.1007\/s11590-010-0258-y","journal-title":"Optim. Lett."},{"key":"405_CR3","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/j.ejor.2013.04.029","volume":"230","author":"P Festa","year":"2013","unstructured":"Festa, P., Guerriero, F., Lagan\u00e0, D., Musmanno, R.: Solving the shortest path tour problem. Eur. J. Oper. Res. 230, 464\u2013474 (2013). https:\/\/doi.org\/10.1016\/j.ejor.2013.04.029","journal-title":"Eur. J. Oper. Res."},{"key":"405_CR4","doi-asserted-by":"publisher","unstructured":"Bhat, S., Rouskas, G.N.: Service-concatenation routing with applications to network functions virtualization. In: 2017 26th International Conference on Computer Communication and Networks (ICCCN), pp. 1\u20139. (2017). https:\/\/doi.org\/10.1109\/icccn.2017.8038463","DOI":"10.1109\/icccn.2017.8038463"},{"key":"405_CR5","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/978-3-319-67308-0_53","volume-title":"Optimization and Decision Science: Methodologies and Applications","author":"F Carrabs","year":"2017","unstructured":"Carrabs, F., Cerulli, R., Festa, P., Laureana, F.: On the forward shortest path tour problem. In: Sforza, A., Sterle, C. (eds.) Optimization and Decision Science: Methodologies and Applications, pp. 529\u2013537. Springer, Berlin (2017). https:\/\/doi.org\/10.1007\/978-3-319-67308-0_53"},{"issue":"1","key":"405_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1002\/net.22010","volume":"78","author":"F Carrabs","year":"2021","unstructured":"Carrabs, F., D\u2019Ambrosio, C., Ferone, D., Festa, P., Laureana, F.: The constrained forward shortest path tour problem: mathematical modeling and grasp approximate solutions. Networks 78(1), 17\u201331 (2021). https:\/\/doi.org\/10.1002\/net.22010","journal-title":"Networks"},{"key":"405_CR7","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.cor.2016.04.002","volume":"74","author":"D Ferone","year":"2016","unstructured":"Ferone, D., Festa, P., Guerriero, F., Lagan\u00e0, D.: The constrained shortest path tour problem. Comput. Oper. Res. 74, 64\u201377 (2016). https:\/\/doi.org\/10.1016\/j.cor.2016.04.002","journal-title":"Comput. Oper. Res."},{"key":"405_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.endm.2018.07.019","volume":"69","author":"RC de Andrade","year":"2018","unstructured":"de Andrade, R.C., Saraiva, R.D.: An integer linear programming model for the constrained shortest path tour problem. Electr. Notes Discrete Math. 69, 141\u2013148 (2018). https:\/\/doi.org\/10.1016\/j.endm.2018.07.019","journal-title":"Electr. Notes Discrete Math."},{"key":"405_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/10556788.2018.1548015","volume":"35","author":"D Ferone","year":"2020","unstructured":"Ferone, D., Festa, P., Guerriero, F.: An efficient exact approach for the constrained shortest path tour problem. Optim. Methods Softw. 35, 1\u201320 (2020). https:\/\/doi.org\/10.1080\/10556788.2018.1548015","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"405_CR10","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1111\/itor.12782","volume":"28","author":"RD Saraiva","year":"2021","unstructured":"Saraiva, R.D., de Andrade, R.C.: Constrained shortest path tour problem: models, valid inequalities, and lagrangian heuristics. Int. Trans. Oper. Res. 28(1), 222\u2013261 (2021)","journal-title":"Int. Trans. Oper. Res."},{"key":"405_CR11","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105819","volume":"144","author":"S Martin","year":"2022","unstructured":"Martin, S., Magnouche, Y., Juvigny, C., Leguay, J.: Constrained shortest path tour problem: branch-and-price algorithm. Comput. Oper. Res. 144, 105819 (2022). https:\/\/doi.org\/10.1016\/j.cor.2022.105819","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"405_CR12","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/j.ejor.2019.08.052","volume":"282","author":"L Di\u00a0Puglia\u00a0Pugliese","year":"2020","unstructured":"Di\u00a0Puglia\u00a0Pugliese, L., Ferone, D., Festa, P., Guerriero, F.: Shortest path tour problem 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":"2","key":"405_CR13","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1057\/jors.2011.25","volume":"63","author":"L Moccia","year":"2012","unstructured":"Moccia, L., Cordeau, J.-F., Laporte, G.: An incremental tabu search heuristic for the generalized vehicle routing problem with time windows. J. Oper. Res. Soc. 63(2), 232\u2013244 (2012). https:\/\/doi.org\/10.1057\/jors.2011.25","journal-title":"J. Oper. Res. Soc."},{"issue":"4","key":"405_CR14","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1051\/ro\/1983170403571","volume":"17","author":"J Desrosiers","year":"1983","unstructured":"Desrosiers, J., Pelletier, P., Soumis, F.: Plus court chemin avec contraintes d\u2019horaires. RAIRO-Oper. Res. 17(4), 357\u2013377 (1983). https:\/\/doi.org\/10.1051\/ro\/1983170403571","journal-title":"RAIRO-Oper. Res."},{"issue":"3","key":"405_CR15","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). https:\/\/doi.org\/10.1002\/net.21511","journal-title":"Networks"},{"issue":"3","key":"405_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1080\/03155986.1988.11732063","volume":"26","author":"M Desrochers","year":"1988","unstructured":"Desrochers, M., Soumis, F.: A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR Inf. Syst. Oper. Res. 26(3), 191\u2013212 (1988). https:\/\/doi.org\/10.1080\/03155986.1988.11732063","journal-title":"INFOR Inf. Syst. Oper. Res."},{"issue":"1","key":"405_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/bf02288320","volume":"13","author":"G Gallo","year":"1988","unstructured":"Gallo, G., Pallottino, S.: Shortest path algorithms. Ann. Oper. Res. 13(1), 1\u201379 (1988). https:\/\/doi.org\/10.1007\/bf02288320","journal-title":"Ann. Oper. Res."},{"issue":"5","key":"405_CR18","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1080\/10556788.2018.1551391","volume":"34","author":"F Guerriero","year":"2019","unstructured":"Guerriero, F., Di Puglia Pugliese, L., Macrina, G.: A rollout algorithm for the resource constrained elementary shortest path problem. Optim. Methods Softw. 34(5), 1056\u20131074 (2019). https:\/\/doi.org\/10.1080\/10556788.2018.1551391","journal-title":"Optim. Methods Softw."},{"key":"405_CR19","doi-asserted-by":"publisher","unstructured":"Powell, W.B., Chen, Z.: A generalized threshold algorithm for the shortest path problem with time windows. In: Pardalos, P.M., Du, D. (Eds.), Network Design: Connectivity and Facilities Location, Proceedings of a DIMACS Workshop, Princetin, New Jersey, USA, April 28\u201330, 1997, Vol.\u00a040 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, DIMACS\/AMS, pp. 303\u2013318. (1998). https:\/\/doi.org\/10.1090\/dimacs\/040\/18","DOI":"10.1090\/dimacs\/040\/18"},{"issue":"1","key":"405_CR20","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/S0377-2217(99)00073-9","volume":"122","author":"G Ghiani","year":"2000","unstructured":"Ghiani, G., Improta, G.: An efficient transformation of the generalized vehicle routing problem. Eur. J. Oper. Res. 122(1), 11\u201317 (2000). https:\/\/doi.org\/10.1016\/S0377-2217(99)00073-9","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"405_CR21","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. Cybern. 4(2), 100\u2013107 (1968). https:\/\/doi.org\/10.1109\/TSSC.1968.300136","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"405_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.05.007","author":"F-J Pulido","year":"2015","unstructured":"Pulido, F.-J., Mandow, L., P\u00e9rez-de-la Cruz, J.-L.: Dimensionality reduction in multiobjective shortest path search. Comput. Oper. Res. (2015). https:\/\/doi.org\/10.1016\/j.cor.2015.05.007","journal-title":"Comput. Oper. Res."},{"key":"405_CR23","unstructured":"de\u00a0las Casas, P.M., Kraus, L., Sede\u00f1o-Noda, A., Bornd\u00f6rfer, R.: Targeted multiobjective DIJKSTRA algorithm (2021). arXiv:2110.10978"},{"issue":"6","key":"405_CR24","doi-asserted-by":"publisher","first-page":"1973","DOI":"10.1007\/s11590-020-01659-z","volume":"15","author":"D Ferone","year":"2020","unstructured":"Ferone, D., Festa, P., Fugaro, S., Pastore, T.: A dynamic programming algorithm for solving the k-color shortest path problem. Optim. Lett. 15(6), 1973\u20131992 (2020). https:\/\/doi.org\/10.1007\/s11590-020-01659-z","journal-title":"Optim. Lett."},{"key":"405_CR25","doi-asserted-by":"publisher","unstructured":"Ferone, D., Festa, P., Gruler, A., Juan, A.A.: Combining simulation with a grasp metaheuristic for solving the permutation flow-shop problem with stochastic processing times. In: Winter Simulation Conference (WSC), pp. 2205\u20132215 (2016). https:\/\/doi.org\/10.1109\/WSC.2016.7822262","DOI":"10.1109\/WSC.2016.7822262"},{"key":"405_CR26","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.cor.2019.03.010","volume":"107","author":"L Di Puglia Pugliese","year":"2019","unstructured":"Di Puglia Pugliese, L., Guerriero, F., Poss, M.: The resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approach. Comput. Oper. Res. 107, 140\u2013155 (2019). https:\/\/doi.org\/10.1016\/j.cor.2019.03.010","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"405_CR27","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1002\/net.21615","volume":"66","author":"AA Pessoa","year":"2015","unstructured":"Pessoa, A.A., Di Puglia Pugliese, L., Guerriero, F., Poss, M.: Robust constrained shortest path problems under budgeted uncertainty. Networks 66(2), 98\u2013111 (2015). https:\/\/doi.org\/10.1002\/net.21615","journal-title":"Networks"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00405-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00405-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00405-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T12:17:50Z","timestamp":1664453870000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00405-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,10]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["405"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00405-8","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,10]]},"assertion":[{"value":"15 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2022","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 conflict of interests to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}