{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T07:29:26Z","timestamp":1753601366826,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T00:00:00Z","timestamp":1569024000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T00:00:00Z","timestamp":1569024000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s10589-019-00132-7","type":"journal-article","created":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T14:02:21Z","timestamp":1569074541000},"page":"851-893","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An auction-based approach for the re-optimization shortest path tree problem"],"prefix":"10.1007","volume":"74","author":[{"given":"P.","family":"Festa","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3887-1317","authenticated-orcid":false,"given":"F.","family":"Guerriero","sequence":"additional","affiliation":[]},{"given":"A.","family":"Napoletano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,21]]},"reference":[{"key":"132_CR1","first-page":"211","volume":"1","author":"RK Ahuja","year":"1989","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Chapter iv network flows. Handb. Oper. Res. Manag. Sci. 1, 211\u2013369 (1989)","journal-title":"Handb. Oper. Res. Manag. Sci."},{"key":"132_CR2","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms and Applications. Prentice-Hall, Englewood Cliffs, NJ (1993)"},{"issue":"3","key":"132_CR3","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1137\/0126047","volume":"26","author":"M Bazaraa","year":"1974","unstructured":"Bazaraa, M., Langley, R.: A dual shortest path algorithm. SIAM J. Appl. Math. 26(3), 496\u2013501 (1974)","journal-title":"SIAM J. Appl. Math."},{"key":"132_CR4","unstructured":"Bertsekas, D.P.: A Distributed Algorithm for the Assignment Problem. Laboratory for Information and Decision Systems Working Paper, M.I.T., Cambridge, MA (1979)"},{"issue":"4","key":"132_CR5","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1137\/0801026","volume":"1","author":"DP Bertsekas","year":"1991","unstructured":"Bertsekas, D.P.: An auction algorithm for shortest paths. SIAM J. Optim. 1(4), 425\u2013447 (1991)","journal-title":"SIAM J. Optim."},{"key":"132_CR6","unstructured":"Bertsekas, D.: Linear Networks Optimization: Algorithms and Codes. MIT Press (1991)"},{"key":"132_CR7","volume-title":"RELAX-IV: A Faster Version of the RELAX Code for Solving Minimum Cost Flow Problems","author":"DP Bertsekas","year":"1994","unstructured":"Bertsekas, D.P., Tseng, P., et al.: RELAX-IV: A Faster Version of the RELAX Code for Solving Minimum Cost Flow Problems. Massachusetts Institute of Technology, Laboratory for Information and Decision Systems Cambridge, Cambridge (1994)"},{"issue":"2","key":"132_CR8","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF01302891","volume":"4","author":"DP Bertsekas","year":"1995","unstructured":"Bertsekas, D.P., Pallottino, S., Scutell\u00e0, M.G.: Polynomial auction algorithms for shortest paths. Comput. Optim. Appl. 4(2), 99\u2013125 (1995)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"132_CR9","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02192173","volume":"88","author":"DP Bertsekas","year":"1996","unstructured":"Bertsekas, D.P., Guerriero, F., Musmanno, R.: Parallel asynchronous label-correcting methods for shortest paths. J. Optim. Theory Appl. 88(2), 297\u2013320 (1996)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"132_CR10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1287\/ijoc.1070.0231","volume":"20","author":"LS Buriol","year":"2008","unstructured":"Buriol, L.S., Resende, M.G., Thorup, M.: Speeding up dynamic shortest-path algorithms. INFORMS J. Comput. 20(2), 191\u2013204 (2008)","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"132_CR11","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/10556789408805588","volume":"4","author":"R Cerulli","year":"1994","unstructured":"Cerulli, R., De Leone, R., Piacente, G.: A modified auction algorithm for the shortest path problem. Optim. Methods Softw. 4(3), 209\u2013224 (1994)","journal-title":"Optim. Methods Softw."},{"issue":"4","key":"132_CR12","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1023\/A:1007938619997","volume":"21","author":"R Cerulli","year":"1998","unstructured":"Cerulli, R., Festa, P., Raiconi, G., Visciano, G.: The auction technique for the sensor based navigation planning of an autonomous mobile robot. J. Intell. Robot. Syst. Theory Appl. 21(4), 373\u2013395 (1998)","journal-title":"J. Intell. Robot. Syst. Theory Appl."},{"key":"132_CR13","unstructured":"Cerulli, R., Festa, P., Raiconi, G.: Shortest paths in randomly time varying networks. In: IEEE Conference on Intelligent Transportation Systems, pp. 854\u2013859 (2001)"},{"issue":"2","key":"132_CR14","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1023\/A:1025750631443","volume":"26","author":"R Cerulli","year":"2003","unstructured":"Cerulli, R., Festa, P., Raiconi, G.: Shortest path auction algorithm without contractions using virtual source concept. Comput. Optim. Appl. 26(2), 191\u2013208 (2003)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"132_CR15","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1109\/TC.2008.198","volume":"58","author":"EP Chan","year":"2009","unstructured":"Chan, E.P., Yang, Y.: Shortest path tree computation in dynamic graphs. IEEE Trans. Comput. 58(4), 541\u2013557 (2009)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"132_CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02592101","volume":"73","author":"BV Cherkassky","year":"1996","unstructured":"Cherkassky, B.V., Goldberg, A.V., Radzik, T.: Shortest paths algorithms: theory and experimental evaluation. Math. Program. 73(2), 129\u2013174 (1996)","journal-title":"Math. Program."},{"issue":"4","key":"132_CR17","doi-asserted-by":"crossref","first-page":"1326","DOI":"10.1137\/S0097539796313490","volume":"28","author":"BV Cherkassky","year":"1999","unstructured":"Cherkassky, B.V., Goldberg, A.V., Silverstein, C.: Buckets, heaps, lists, and monotone priority queues. SIAM J. Comput. 28(4), 1326\u20131346 (1999)","journal-title":"SIAM J. Comput."},{"key":"132_CR18","volume-title":"An Algorithmic Approach","author":"N Christofides","year":"1975","unstructured":"Christofides, N.: An Algorithmic Approach. Academic Press Inc., New York (1975)"},{"key":"132_CR19","doi-asserted-by":"crossref","unstructured":"D\u2019Andrea, A., D\u2019Emidio, M., Frigioni, D., Leucci, S., Proietti, G.: Dynamically maintaining shortest path trees under batches of updates. In: Moscibroda, T., Rescigno, A.A. (eds.) International Colloquium on Structural Information and Communication Complexity, pp. 286\u2013297. Springer (2013)","DOI":"10.1007\/978-3-319-03578-9_24"},{"key":"132_CR20","volume-title":"9th Dimacs Implementation Challenge-Shortest Paths","author":"C Demetrescu","year":"2006","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: 9th Dimacs Implementation Challenge-Shortest Paths. American Mathematical Society, Providence (2006)"},{"key":"132_CR21","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/074","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge","author":"C Demetrescu","year":"2009","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, vol. 74. American Mathematical Society, Providence (2009)"},{"issue":"1","key":"132_CR22","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s10479-012-1162-x","volume":"201","author":"L Di Puglia Pugliese","year":"2012","unstructured":"Di Puglia Pugliese, L., Guerriero, F.: A computational study of solution approaches for the resource constrained elementary shortest path problem. Ann. Oper. Res. 201(1), 131\u2013157 (2012)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"132_CR23","doi-asserted-by":"crossref","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"},{"issue":"2","key":"132_CR24","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0041-1647(71)90012-8","volume":"5","author":"RB Dial","year":"1971","unstructured":"Dial, R.B.: A probabilistic multipath traffic assignment model which obviates path enumeration. Transp. Res. 5(2), 83\u2013111 (1971)","journal-title":"Transp. Res."},{"issue":"1","key":"132_CR25","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269\u2013271 (1959)","journal-title":"Numer. Math."},{"key":"132_CR26","doi-asserted-by":"crossref","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\u00e1, D.: The constrained shortest path tour problem. Comput. Oper. Res. 74, 64\u201377 (2016)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"132_CR27","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1590\/0101-7438.2017.037.03.0487","volume":"37","author":"D Ferone","year":"2017","unstructured":"Ferone, D., Festa, P., Napoletano, A., Pastore, T.: Shortest paths on dynamic graphs: a survey. Pesqui. Oper. 37(3), 487\u2013508 (2017)","journal-title":"Pesqui. Oper."},{"key":"132_CR28","unstructured":"Festa, P., Pallottino, S.: A Pseudo-Random Networks Generator. Technical report, Department of Mathematics and Applications \u201cR. Caccioppoli\u201d, University of Napoli FEDERICO II, Italy (2003)"},{"issue":"4","key":"132_CR29","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1002\/net.3230110406","volume":"11","author":"M Florian","year":"1981","unstructured":"Florian, M., Nguyen, S., Pallottino, S.: A dual simplex algorithm for finding all shortest paths. Networks 11(4), 367\u2013378 (1981)","journal-title":"Networks"},{"issue":"1","key":"132_CR30","first-page":"3","volume":"3","author":"G Gallo","year":"1980","unstructured":"Gallo, G.: Reoptimization procedures in shortest path problem. Riv. Mat. Sci. Econ. Soc. 3(1), 3\u201313 (1980)","journal-title":"Riv. Mat. Sci. Econ. Soc."},{"issue":"1","key":"132_CR31","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0166-218X(82)90031-2","volume":"4","author":"G Gallo","year":"1982","unstructured":"Gallo, G., Pallottino, S.: A new algorithm to find the shortest paths between all pairs of nodes. Discrete Appl. Math. 4(1), 23\u201335 (1982). \nhttps:\/\/doi.org\/10.1016\/0166-218X(82)90031-2\n\n. ISSN: 0166218X","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"132_CR32","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0377-2217(02)00594-5","volume":"151","author":"J Granat","year":"2003","unstructured":"Granat, J., Guerriero, F.: The interactive analysis of the multicriteria shortest path problem by the reference point method. Eur. J. Oper. Res. 151(1), 103\u2013118 (2003)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"132_CR33","doi-asserted-by":"crossref","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., Gelinas, S., Soumis, F., Desrosiers, J.: A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31(3), 193\u2013204 (1998)","journal-title":"Networks"},{"issue":"3","key":"132_CR34","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0968-090X(94)90005-1","volume":"2","author":"R Jayakrishnan","year":"1994","unstructured":"Jayakrishnan, R., Mahmassani, H.S., Hu, T.-Y.: An evaluation tool for advanced traffic information and management systems in urban networks. Transp. Res. Part C Emerg. Technol. 2(3), 129\u2013147 (1994)","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"132_CR35","unstructured":"Koenig, S., Likhachev, M.: D* lite. In Proceedings of the Eighteenth National Conference on Artificial Intelligence, Edmonton, Alberta, Canada, 28 July 2002\u201301 August 2002, pp. 476\u2013483."},{"issue":"3","key":"132_CR36","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/TRO.2004.838026","volume":"21","author":"S Koenig","year":"2005","unstructured":"Koenig, S., Likhachev, M.: Fast replanning for navigation in unknown terrain. IEEE Trans. Robot. 21(3), 354\u2013363 (2005)","journal-title":"IEEE Trans. Robot."},{"issue":"1\u20132","key":"132_CR37","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.artint.2003.12.001","volume":"155","author":"S Koenig","year":"2004","unstructured":"Koenig, S., Likhachev, M., Furcy, D.: Lifelong planning a. Artif. Intell. 155(1\u20132), 93\u2013146 (2004)","journal-title":"Artif. Intell."},{"issue":"1","key":"132_CR38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/trsc.18.1.1","volume":"18","author":"TL Magnanti","year":"1984","unstructured":"Magnanti, T.L., Wong, R.T.: Network design and transportation planning: models and algorithms. Transp. Sci. 18(1), 1\u201355 (1984)","journal-title":"Transp. Sci."},{"key":"132_CR39","first-page":"1","volume":"8","author":"G Nannicini","year":"2008","unstructured":"Nannicini, G., Baptiste, P., Krob, D., Liberti, L.: Fast paths in dynamic road networks. Proc. ROADEF 8, 1\u201314 (2008)","journal-title":"Proc. ROADEF"},{"key":"132_CR40","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/978-1-4757-6871-8_14","volume-title":"Transportation and Network Analysis: Current Trends","author":"S Nguyen","year":"2002","unstructured":"Nguyen, S., Pallottino, S., Scutell\u00e0, M.G.: A new dual algorithm for shortest path reoptimization. In: Gendreau, M., Marcotte, P. (eds.) Transportation and Network Analysis: Current Trends, pp. 221\u2013235. Springer, Boston, MA (2002)"},{"key":"132_CR41","first-page":"33","volume":"60","author":"S Pallottino","year":"1991","unstructured":"Pallottino, S., Scutella, M.G.: Strongly polynomial auction algorithms for shortest paths. Ric. Op. 60, 33\u201353 (1991)","journal-title":"Ric. Op."},{"issue":"2","key":"132_CR42","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1002\/(SICI)1097-0037(199703)29:2<125::AID-NET7>3.0.CO;2-L","volume":"26","author":"S Pallottino","year":"1997","unstructured":"Pallottino, S., Scutell\u00e0, M.G.: Dual algorithms for the shortest path tree problem. Networks 26(2), 125\u2013133 (1997)","journal-title":"Networks"},{"key":"132_CR43","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/978-1-4615-5757-9_11","volume-title":"Equilibrium and Advanced Transportation Modelling","author":"S Pallottino","year":"1998","unstructured":"Pallottino, S., Scutell\u00e1, M.G.: Shortest path algorithms in transportation models: classical and innovative aspects. In: Marcotte, P., Nguyen, S. (eds.) Equilibrium and Advanced Transportation Modelling, pp. 245\u2013281. Springer, Boston, MA (1998)"},{"issue":"2","key":"132_CR44","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0167-6377(02)00192-X","volume":"31","author":"S Pallottino","year":"2003","unstructured":"Pallottino, S., Scutell\u00e1, M.G.: A new algorithm for reoptimizing shortest paths when the arc costs change. Oper. Res. Lett. 31(2), 149\u2013160 (2003)","journal-title":"Oper. Res. Lett."},{"key":"132_CR45","volume-title":"Command Line Tools Generating Various Families of Random Graphs","author":"S Pettie","year":"2006","unstructured":"Pettie, S., Ramachandran, V.: Command Line Tools Generating Various Families of Random Graphs. American Mathematical Society, Providence (2006)"},{"key":"132_CR46","unstructured":"Pham, P.P., Perreau, S.: Performance analysis of reactive shortest path and multipath routing mechanism with load balance. In: INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications. IEEE Societies, vol.\u00a01, pp. 251\u2013259. IEEE (2003)"},{"issue":"2","key":"132_CR47","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G Ramalingam","year":"1996","unstructured":"Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest-path problem. J. Algorithms 21(2), 267\u2013305 (1996)","journal-title":"J. Algorithms"},{"key":"132_CR48","volume-title":"Telecommunication Networks: Protocols, Modeling and Analysis","author":"M Schwartz","year":"1987","unstructured":"Schwartz, M.: Telecommunication Networks: Protocols, Modeling and Analysis, vol. 7. Addison-Wesley, Reading (1987)"},{"key":"132_CR49","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tre.2017.02.002","volume":"101","author":"N Shi","year":"2017","unstructured":"Shi, N., Zhou, S., Wang, F., Tao, Y., Liu, L.: The multi-criteria constrained shortest path problem. Transp. Res. Part E Logist. Transp. Rev. 101, 13\u201329 (2017)","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"132_CR50","unstructured":"Stentz, A.: Optimal and efficient path planning for partially-known environments. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA \u201994), vol.\u00a04, pp. 3310 \u2013 3317 (1994)"},{"key":"132_CR51","unstructured":"Stentz, A.: The focussed $$\\text{d}^{*}$$ algorithm for real-time replanning. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence\u2014Volume 2, IJCAI\u201995, pp. 1652\u20131659, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc. ISBN: 1-55860-363-8. \nhttp:\/\/dl.acm.org\/citation.cfm?id=1643031.1643113"},{"key":"132_CR52","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611973594","volume-title":"Vehicle Routing: Problems, Methods, and Applications","author":"P Toth","year":"2014","unstructured":"Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. SIAM, Philadelphia (2014)"},{"key":"132_CR53","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.ssci.2012.12.003","volume":"54","author":"X Zhang","year":"2013","unstructured":"Zhang, X., Zhang, Z., Zhang, Y., Wei, D., Deng, Y.: Route selection for emergency logistics management: a bio-inspired algorithm. Saf. Sci. 54, 87\u201391 (2013)","journal-title":"Saf. Sci."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00132-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-019-00132-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00132-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T23:07:51Z","timestamp":1600556871000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-019-00132-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,21]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["132"],"URL":"https:\/\/doi.org\/10.1007\/s10589-019-00132-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2019,9,21]]},"assertion":[{"value":"8 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}