{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T00:54:51Z","timestamp":1762390491859},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,12,30]],"date-time":"2011-12-30T00:00:00Z","timestamp":1325203200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,12]]},"DOI":"10.1007\/s00453-011-9606-2","type":"journal-article","created":{"date-parts":[[2011,12,29]],"date-time":"2011-12-29T11:12:53Z","timestamp":1325157173000},"page":"643-672","source":"Crossref","is-referenced-by-count":53,"title":["A Simple Ant Colony Optimizer for Stochastic Shortest Path Problems"],"prefix":"10.1007","volume":"64","author":[{"given":"Dirk","family":"Sudholt","sequence":"first","affiliation":[]},{"given":"Christian","family":"Thyssen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,12,30]]},"reference":[{"key":"9606_CR1","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1137\/1.9781611973075.64","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"I. Abraham","year":"2010","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.F.: Highway dimension, shortest paths, and provably efficient algorithms. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910), pp. 782\u2013793. SIAM, Philadelphia (2010)"},{"issue":"3","key":"9606_CR2","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.ipl.2007.08.013","volume":"105","author":"N. Attiratanasunthron","year":"2008","unstructured":"Attiratanasunthron, N., Fakcharoenphol, J.: A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs. Inf. Process. Lett. 105(3), 88\u201392 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"5824","key":"9606_CR3","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1126\/science.1137521","volume":"316","author":"H. Bast","year":"2007","unstructured":"Bast, H., Funke, S., Sanders, P., Schultes, D.: Fast routing in road networks with transit nodes. Science 316(5824), 566 (2007)","journal-title":"Science"},{"key":"9606_CR4","first-page":"59","volume-title":"Proceedings of the International Workshop on Foundations of Genetic Algorithms (FOGA\u201909)","author":"S. Baswana","year":"2009","unstructured":"Baswana, S., Biswas, S., Doerr, B., Friedrich, T., Kurur, P.P., Neumann, F.: Computing single source shortest paths using single-objective fitness functions. In: Proceedings of the International Workshop on Foundations of Genetic Algorithms (FOGA\u201909), pp. 59\u201366. ACM, New York (2009)"},{"issue":"3","key":"9606_CR5","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1287\/moor.16.3.580","volume":"16","author":"D.P. Bertsekas","year":"1991","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: An analysis of stochastic shortest path problems. Math. Oper. Res. 16(3), 580\u2013595 (1991)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9606_CR6","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s11721-008-0024-2","volume":"3","author":"V. Borkar","year":"2009","unstructured":"Borkar, V., Das, D.: A novel ACO algorithm for optimization via reinforcement and initial bias. Swarm Intell. 3(1), 3\u201334 (2009)","journal-title":"Swarm Intell."},{"key":"9606_CR7","first-page":"895","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901)","author":"J.A. Boyan","year":"2001","unstructured":"Boyan, J.A., Mitzenmacher, M.: Improved results for route planning in stochastic transportation. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201901), pp. 895\u2013902. SIAM, Philadelphia (2001)"},{"key":"9606_CR8","first-page":"590","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201907)","author":"T.M. Chan","year":"2007","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201907), pp. 590\u2013598. ACM, New York (2007)"},{"key":"9606_CR9","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9606_CR10","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/1830483.1830618","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910)","author":"B. Doerr","year":"2010","unstructured":"Doerr, B., Johannsen, D.: Edge-based representation beats vertex-based representation in shortest path problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910), pp. 759\u2013766. ACM, New York (2010)"},{"key":"9606_CR11","first-page":"247","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201909)","author":"B. Doerr","year":"2009","unstructured":"Doerr, B., Theile, M.: Improved analysis methods for crossover-based algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201909), pp. 247\u2013254. ACM, New York (2009)"},{"key":"9606_CR12","doi-asserted-by":"crossref","first-page":"1890","DOI":"10.1109\/CEC.2007.4424704","volume-title":"Proceedings of the IEEE Congress on Evolutionary Computation (CEC\u201907)","author":"B. Doerr","year":"2007","unstructured":"Doerr, B., Happ, E., Klein, C.: A tight analysis of the (1+1)-EA for the single source shortest path problem. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC\u201907), pp. 1890\u20131895. IEEE Press, New York (2007)"},{"key":"9606_CR13","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1145\/1389095.1389202","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908)","author":"B. Doerr","year":"2008","unstructured":"Doerr, B., Happ, E., Klein, C.: Crossover can provably be useful in evolutionary computation. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201908), pp. 539\u2013546. ACM, New York (2008)"},{"key":"9606_CR14","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/978-3-642-15844-5_19","volume-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN\u201910)","author":"B. Doerr","year":"2010","unstructured":"Doerr, B., Johannsen, D., K\u00f6tzing, T., Neumann, F., Theile, M.: More effective crossover operators for the all-pairs shortest path problem. In: Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN\u201910), pp. 184\u2013193. Springer, Berlin (2010)"},{"issue":"17","key":"9606_CR15","doi-asserted-by":"crossref","first-page":"1629","DOI":"10.1016\/j.tcs.2010.12.030","volume":"412","author":"B. Doerr","year":"2011","unstructured":"Doerr, B., Neumann, F., Sudholt, D., Witt, C.: Runtime analysis of the 1-ANT ant colony optimizer. Theor. Comput. Sci. 412(17), 1629\u20131644 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"9606_CR16","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.tcs.2005.05.020","volume":"344","author":"M. Dorigo","year":"2005","unstructured":"Dorigo, M., Blum, C.: Ant colony optimization theory: a survey. Theor. Comput. Sci. 344(2\u20133), 243\u2013278 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9606_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1109\/4235.585892","volume":"1","author":"M. Dorigo","year":"1997","unstructured":"Dorigo, M., Gambardella, L.M.: Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1(1), 53\u201366 (1997)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"9606_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/b99492","volume-title":"Ant Colony Optimization","author":"M. Dorigo","year":"2004","unstructured":"Dorigo, M., St\u00fctzle, T.: Ant Colony Optimization, 1st edn. MIT Press, Cambridge (2004)","edition":"1"},{"key":"9606_CR19","unstructured":"Dorigo, M., Maniezzo, V., Colorni, A.: The ant system: an autocatalytic optimizing process. Technical Report 91-016 Revised, Politecnico di Milano (1991)"},{"issue":"1\u20132","key":"9606_CR20","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","volume":"276","author":"S. Droste","year":"2002","unstructured":"Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276(1\u20132), 51\u201381 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9606_CR21","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"issue":"3","key":"9606_CR22","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s10957-005-7498-5","volume":"127","author":"Y.Y. Fan","year":"2005","unstructured":"Fan, Y.Y., Kalaba, R.E., Moore, J.E.: Arriving on time. J. Optim. Theory Appl. 127(3), 497\u2013513 (2005)","journal-title":"J. Optim. Theory Appl."},{"issue":"4","key":"9606_CR23","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U. Feige","year":"2006","unstructured":"Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35(4), 964\u2013984 (2006)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9606_CR24","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s11009-007-9047-1","volume":"10","author":"W.J. Gutjahr","year":"2008","unstructured":"Gutjahr, W.J., Sebastiani, G.: Runtime analysis of ant colony optimization with best-so-far reinforcement. Methodol. Comput. Appl. Probab. 10(3), 409\u2013433 (2008)","journal-title":"Methodol. Comput. Appl. Probab."},{"issue":"3","key":"9606_CR25","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1162\/EVCO_a_00014","volume":"18","author":"C. Horoba","year":"2010","unstructured":"Horoba, C.: Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem. Evol. Comput. 18(3), 357\u2013381 (2010)","journal-title":"Evol. Comput."},{"key":"9606_CR26","first-page":"76","volume-title":"Proceedings of the International Workshop on Engineering Stochastic Local Search Algorithms (SLS\u00a0\u201909)","author":"C. Horoba","year":"2009","unstructured":"Horoba, C., Sudholt, D.: Running time analysis of ACO systems for shortest path problems. In: Proceedings of the International Workshop on Engineering Stochastic Local Search Algorithms (SLS\u00a0\u201909), pp. 76\u201391. Springer, Berlin (2009)"},{"key":"9606_CR27","doi-asserted-by":"crossref","first-page":"1465","DOI":"10.1145\/1830483.1830750","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910)","author":"C. Horoba","year":"2010","unstructured":"Horoba, C., Sudholt, D.: Ant colony optimization for stochastic shortest path problems. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910), pp. 1465\u20131472. Springer, Berlin (2010)"},{"key":"9606_CR28","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-00393-6_5","volume-title":"Network Control and Optimization","author":"S.R. Kolavali","year":"2009","unstructured":"Kolavali, S.R., Bhatnagar, S.: Ant colony optimization algorithms for shortest path problems. In: Altman, E., Chaintreau, A. (eds.) Network Control and Optimization, pp. 37\u201344. Springer, Berlin (2009)"},{"key":"9606_CR29","doi-asserted-by":"crossref","first-page":"1393","DOI":"10.1145\/1830483.1830741","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910)","author":"T. K\u00f6tzing","year":"2010","unstructured":"K\u00f6tzing, T., Lehre, P.K., Oliveto, P.S., Neumann, F.: Ant colony optimization and the minimum cut problem. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910), pp. 1393\u20131400. ACM, New York (2010)"},{"key":"9606_CR30","first-page":"324","volume-title":"Proceedings of the International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS\u201910)","author":"T. K\u00f6tzing","year":"2010","unstructured":"K\u00f6tzing, T., Neumann, F., R\u00f6glin, H., Witt, C.: Theoretical properties of two ACO approaches for the traveling salesman problem. In: Proceedings of the International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS\u201910), pp. 324\u2013335. Springer, Berlin (2010)"},{"key":"9606_CR31","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/1967654.1967673","volume-title":"Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011)","author":"T. K\u00f6tzing","year":"2011","unstructured":"K\u00f6tzing, T., Neumann, F., Sudholt, D., Wagner, M.: Simple Max-Min ant systems and the optimization of linear pseudo-Boolean functions. In: Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011), pp.\u00a0209\u2013218. ACM, New York (2011)"},{"issue":"2","key":"9606_CR32","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1287\/trsc.34.2.198.12304","volume":"34","author":"E.D. Miller-Hooks","year":"2000","unstructured":"Miller-Hooks, E.D., Mahmassani, H.S.: Least expected time paths in stochastic, time-varying transportation networks. Transp. Sci. 34(2), 198\u2013215 (2000)","journal-title":"Transp. Sci."},{"key":"9606_CR33","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1007\/978-3-642-15844-5_67","volume-title":"Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN\u201910)","author":"F. Neumann","year":"2010","unstructured":"Neumann, F., Theile, M.: How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem. In: Proceedings of the International Conference on Parallel Problem Solving from Nature (PPSN\u201910), pp. 667\u2013676. Springer, Berlin (2010)"},{"issue":"25","key":"9606_CR34","doi-asserted-by":"crossref","first-page":"2406","DOI":"10.1016\/j.tcs.2010.02.012","volume":"411","author":"F. Neumann","year":"2010","unstructured":"Neumann, F., Witt, C.: Ant colony optimization and the minimum spanning tree problem. Theor. Comput. Sci. 411(25), 2406\u20132413 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9606_CR35","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s00453-007-9134-2","volume":"54","author":"F. Neumann","year":"2009","unstructured":"Neumann, F., Witt, C.: Runtime analysis of a simple ant colony optimization algorithm. Algorithmica 54(2), 243\u2013255 (2009)","journal-title":"Algorithmica"},{"key":"9606_CR36","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1007\/978-3-540-87527-7_12","volume-title":"Proceedings of the International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS\u201908)","author":"F. Neumann","year":"2008","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Rigorous analyses for the combination of ant colony optimization and local search. In: Proceedings of the International Conference on Ant Colony Optimization and Swarm Intelligence (ANTS\u201908), pp. 132\u2013143. Springer, Berlin (2008)"},{"issue":"1","key":"9606_CR37","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s11721-008-0023-3","volume":"3","author":"F. Neumann","year":"2009","unstructured":"Neumann, F., Sudholt, D., Witt, C.: Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intell. 3(1), 35\u201368 (2009)","journal-title":"Swarm Intell."},{"key":"9606_CR38","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/1830483.1830493","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910)","author":"F. Neumann","year":"2010","unstructured":"Neumann, F., Sudholt, D., Witt, C.: A few ants are enough: ACO with iteration-best update. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201910), pp. 63\u201370. ACM, New York (2010)"},{"key":"9606_CR39","first-page":"131","volume-title":"Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS\u201906)","author":"E. Nikolova","year":"2006","unstructured":"Nikolova, E., Brand, M., Karger, D.R.: Optimal route planning under uncertainty. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS\u201906), pp. 131\u2013141. AAAI Press, Menlo Park (2006)"},{"issue":"2","key":"9606_CR40","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/j.jda.2009.03.001","volume":"8","author":"J.B. Orlin","year":"2010","unstructured":"Orlin, J.B., Madduri, K., Subramani, K., Williamson, M.: A faster algorithm for the single source shortest path problem with few distinct positive lengths. J. Discrete Algorithms 8(2), 189\u2013198 (2010)","journal-title":"J. Discrete Algorithms"},{"issue":"1","key":"9606_CR41","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127\u2013150 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9606_CR42","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1023\/B:JMMA.0000049379.14872.f5","volume":"3","author":"J. Scharnow","year":"2004","unstructured":"Scharnow, J., Tinnefeld, K., Wegener, I.: The analysis of evolutionary algorithms on sorting and shortest paths problems. J. Math. Model. Algorithms 3(4), 349\u2013366 (2004)","journal-title":"J. Math. Model. Algorithms"},{"key":"9606_CR43","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1145\/1967654.1967667","volume-title":"Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA\u00a02011)","author":"D. Sudholt","year":"2011","unstructured":"Sudholt, D.: Using Markov-chain mixing time estimates for the analysis of ant colony optimization. In: Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA\u00a02011), pp. 139\u2013150. ACM, New York (2011)"},{"key":"9606_CR44","doi-asserted-by":"crossref","unstructured":"Sudholt, D., Thyssen, C.: Running time analysis of ant colony optimization for shortest path problems. J. Discrete Algorithms. doi: 10.1016\/j.jda.2011.06.002 (2011, to appear)","DOI":"10.1016\/j.jda.2011.06.002"},{"issue":"5","key":"9606_CR45","doi-asserted-by":"crossref","first-page":"1083","DOI":"10.1109\/TEVC.2009.2016570","volume":"13","author":"Y. Zhou","year":"2009","unstructured":"Zhou, Y.: Runtime analysis of an ant colony optimization algorithm for TSP instances. IEEE Trans. Evol. Comput. 13(5), 1083\u20131092 (2009)","journal-title":"IEEE Trans. Evol. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9606-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9606-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9606-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:09Z","timestamp":1559123109000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9606-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,30]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["9606"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9606-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,30]]}}}