{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T07:06:57Z","timestamp":1763536017949,"version":"3.37.3"},"reference-count":22,"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":[{"DOI":"10.13039\/501100004770","name":"Universit\u00e0 degli Studi di Parma","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004770","id-type":"DOI","asserted-by":"crossref"}]}],"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>We introduce a variant of the Shortest Path Problem (SPP), in which we impose additional constraints on the acceleration over the arcs, and call it Bounded Acceleration SPP (BASP). This variant is inspired by an industrial application: a vehicle needs to travel from its current position to a target one in minimum-time, following pre-defined geometric paths connecting positions within a facility, while satisfying some speed and acceleration constraints depending on the vehicle position along the currently traveled path. We characterize the complexity of BASP, proving its NP-hardness. We also show that, under additional hypotheses on problem data, the problem admits a pseudo-polynomial time-complexity algorithm. Moreover, we present an approximation algorithm with polynomial time-complexity with respect to the data of the original problem and the inverse of the approximation factor <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\epsilon$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03f5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we present some computational experiments to evaluate the performance of the proposed approximation algorithm.<\/jats:p>","DOI":"10.1007\/s10589-022-00403-w","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T21:02:32Z","timestamp":1660165352000},"page":"555-592","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Shortest path with acceleration constraints: complexity and approximation algorithms"],"prefix":"10.1007","volume":"83","author":[{"given":"S.","family":"Ardizzoni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Consolini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Laurini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7138-8653","authenticated-orcid":false,"given":"M.","family":"Locatelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,10]]},"reference":[{"key":"403_CR1","doi-asserted-by":"publisher","unstructured":"Ardizzoni, S., Consolini, L., Laurini, M., Locatelli, M.: Solution algorithms for the bounded acceleration shortest path problem. IEEE Trans. Autom. Control (2022) (to appear). https:\/\/doi.org\/10.1109\/TAC.2022.3172169","DOI":"10.1109\/TAC.2022.3172169"},{"key":"403_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tre.2019.11.013","volume":"133","author":"BY Chen","year":"2020","unstructured":"Chen, B.Y., Chen, X.-W., Chen, H.-P., Lam, W.H.K.: Efficient algorithm for finding $$k$$ shortest paths based on re-optimization technique. Transpt. Res. Part E: Log. Transpt. Rev. 133, 101819 (2020)","journal-title":"Transpt. Res. Part E: Log. Transpt. Rev."},{"key":"403_CR3","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.sysconle.2017.02.001","volume":"103","author":"L Consolini","year":"2017","unstructured":"Consolini, L., Locatelli, M., Minari, A., Piazzi, A.: An optimal complexity algorithm for minimum-time velocity planning. Syst. Control Lett. 103, 50\u201357 (2017)","journal-title":"Syst. Control Lett."},{"issue":"12","key":"403_CR4","doi-asserted-by":"publisher","first-page":"7617","DOI":"10.1016\/j.jfranklin.2020.05.024","volume":"357","author":"L Consolini","year":"2020","unstructured":"Consolini, L., Laurini, M., Locatelli, M., Minari, A.: A solution of the minimum-time speed planning problem based on lattice theory. J. Frankl. Inst. 357(12), 7617\u20137637 (2020)","journal-title":"J. Frankl. Inst."},{"key":"403_CR5","doi-asserted-by":"crossref","unstructured":"Cowlagi, R.V., Tsiotras, P.: Shortest distance problems in graphs using history-dependent transition costs with application to kinodynamic path planning. In: 2009 American Control Conference, pp. 414\u2013419 (2009)","DOI":"10.1109\/ACC.2009.5160149"},{"key":"403_CR6","unstructured":"Dean, B.C.: Shortest paths in FIFO time-dependent networks: theory and algorithms. In: Technical Report Massachusetts Institute of Technology (2004)"},{"key":"403_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.ejor.2004.01.032","volume":"165","author":"G Desaulniers","year":"2005","unstructured":"Desaulniers, G., Villeneuve, D.: The shortest path problem with forbidden paths. Eur. J. Oper. Res. 165, 97\u2013107 (2005)","journal-title":"Eur. J. Oper. Res."},{"key":"403_CR8","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1016\/0377-2217(88)90034-3","volume":"35","author":"M Desrochers","year":"1988","unstructured":"Desrochers, M., Soumis, F.: A reoptimization algorithm for the shortest path problem with time windows. Eur. J. Oper. Res. 35, 242\u2013254 (1988)","journal-title":"Eur. J. Oper. Res."},{"key":"403_CR9","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"S Dreyfus","year":"1969","unstructured":"Dreyfus, S.: An Appraisal of Some Shortest-Path Algorithms. Oper. Res. 17, 395\u2013412 (1969)","journal-title":"Oper. Res."},{"key":"403_CR10","doi-asserted-by":"publisher","first-page":"977","DOI":"10.1287\/opre.42.5.977","volume":"42","author":"M Dror","year":"1994","unstructured":"Dror, M.: Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. 42, 977\u2013978 (1994)","journal-title":"Oper. Res."},{"issue":"3","key":"403_CR11","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0021-9800(70)80083-7","volume":"8","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J., Fulkerson, D.R.: Bottleneck extrema. J. Comb. Theory 8(3), 299\u2013306 (1970)","journal-title":"J. Comb. Theory"},{"key":"403_CR12","doi-asserted-by":"crossref","unstructured":"Festa, P.: Constrained shortest path problems: state-of-the-art and recent advances. In: 17th International Conference on Transparent Optical Networks (ICTON), pp. 1\u201317 (2015)","DOI":"10.1109\/ICTON.2015.7193456"},{"issue":"2","key":"403_CR13","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF02837564","volume":"14","author":"R Garfinkel","year":"2006","unstructured":"Garfinkel, R., Fernandez, E., Lowe, T.J.: The $$k$$-centrum shortest path problem. TOP 14(2), 279\u2013292 (2006)","journal-title":"TOP"},{"key":"403_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"issue":"4","key":"403_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/net.3230100403","volume":"10","author":"GY Handler","year":"1980","unstructured":"Handler, G.Y., Zang, I.: A dual algorithm for the constrained shortest path problem. Networks 10(4), 293\u2013309 (1980)","journal-title":"Networks"},{"issue":"3","key":"403_CR16","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1287\/ijoc.2020.0985","volume":"33","author":"E He","year":"2021","unstructured":"He, E., Boland, N., Nehmauser, G., Savelsbergh, M.: Time-dependent shortest path problems with penalties and limits on waiting. INFORMS J. Comput. 33(3), 997\u20131014 (2021)","journal-title":"INFORMS J. Comput."},{"key":"403_CR17","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<193::AID-NET6>3.0.CO;2-A","volume":"31","author":"I Ioachim","year":"1998","unstructured":"Ioachim, I., G\u00e9linas, S., Soumis, F., Desrosiers, J.: A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31, 193\u2013204 (1998)","journal-title":"Networks"},{"issue":"3","key":"403_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1002\/net.21885","volume":"4","author":"J Omer","year":"2019","unstructured":"Omer, J., Poss, M.: Time-dependent shortest paths with discounted waits. Networks 4(3), 287\u2013301 (2019)","journal-title":"Networks"},{"key":"403_CR19","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/79147.214078","volume":"37","author":"A Orda","year":"1990","unstructured":"Orda, A., Rom, R.: Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. J. ACM 37, 607\u2013625 (1990)","journal-title":"J. ACM"},{"issue":"5","key":"403_CR20","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1287\/opre.8.5.733","volume":"8","author":"M Pollack","year":"1960","unstructured":"Pollack, M.: The maximum capacity through a network. Oper. Res. 8(5), 733\u2013736 (1960)","journal-title":"Oper. Res."},{"issue":"2","key":"403_CR21","first-page":"91","volume":"6","author":"L Turner","year":"2012","unstructured":"Turner, L.: Variants of shortest path problems. Algorithm. Oper. Res. 6(2), 91\u2013104 (2012)","journal-title":"Algorithm. Oper. Res."},{"key":"403_CR22","unstructured":"Stern, R., Sturtevant, N.R., Felner, A., Keonig, S., Ma, H., Walker, T.T., Li, J., Atzmon, D., Cohen, L., Kumar, T.S., Boyarski, E., Bartak, R.: Multi-agent pathfinding: definitions, variants, and benchmarks. In: Symposium on Combinatorial Search (SoCS) (2019)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00403-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00403-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00403-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T12:17:42Z","timestamp":1664453862000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00403-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,10]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["403"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00403-w","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2022,8,10]]},"assertion":[{"value":"4 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 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"}}]}}