{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:20:58Z","timestamp":1759666858782,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T00:00:00Z","timestamp":1655856000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T00:00:00Z","timestamp":1655856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study routing and searching decisions of a search-and-detection (SDT) team on a road network under online uncertainty setting. Given an undirected edge-weighted bounded graph, a static target is positioned at an unknown vertex among potential target vertices in the graph. A non-negative search cost is given on each of the potential target vertices. The target is detected once the SDT searches its corresponding vertex. There may be some non-recoverable online blockages in the graph, but the existence of blockages is unknown to the SDT initially. If a blockage exists in the graph, it is disclosed online once the SDT visits one of its end-vertices. The graph stays connected when the blockages are omitted from it. The SDT begins from a certain vertex and aims to identify a route without any blocked edges which detects the target with minimum total traveling and search cost. We analyze this problem from a competitive analysis perspective under two scenarios with and without blockages. For the scenario with blockages, we provide a tight lower bound on the competitive ratio of deterministic solutions, an optimal deterministic solution, a randomized solution with a bounded expected competitive ratio, together with lower and upper bounds on the expected competitive ratio of the optimal randomized solutions. For the scenario without blockages, we provide tight lower bounds as well as optimal deterministic and randomized solutions.<\/jats:p>","DOI":"10.1007\/s10878-022-00876-9","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T08:14:49Z","timestamp":1655885689000},"page":"1039-1059","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online routing and searching on graphs with blocked edges"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2884-0047","authenticated-orcid":false,"given":"Davood","family":"Shiri","sequence":"first","affiliation":[]},{"given":"Hakan","family":"Tozan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"876_CR1","doi-asserted-by":"crossref","unstructured":"Akbari Vahid, Shiri Davood (2021) Weighted online minimum latency problem with edge uncertainty. Eur. J. Oper. Res.","DOI":"10.1016\/j.ejor.2021.02.038"},{"key":"876_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105533","volume":"137","author":"Vahid Akbari","year":"2022","unstructured":"Akbari Vahid, Shiri Davood (2022) An online optimization approach for post-disaster relief distribution with online blocked edges. Comput. & Oper. Res. 137:105533","journal-title":"Comput. & Oper. Res."},{"key":"876_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.trb.2021.05.017","volume":"150","author":"Vahid Akbari","year":"2021","unstructured":"Akbari Vahid, Shiri Davood, Sibel Salman F (2021) An online optimization approach to post-disaster road restoration. Trans. Res. Part B: Meth. 150:1\u201325","journal-title":"Trans. Res. Part B: Meth."},{"key":"876_CR4","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1016\/j.ejor.2020.04.003","volume":"286","author":"Spyros Angelopoulos","year":"2020","unstructured":"Angelopoulos Spyros, Lidbetter Thomas (2020) Competitive search in a network. Eur. J. Oper. Res. 286:781\u2013790","journal-title":"Eur. J. Oper. Res."},{"key":"876_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.dam.2019.01.039","volume":"260","author":"Spyros Angelopoulos","year":"2019","unstructured":"Angelopoulos Spyros, D\u00fcrr Christoph, Lidbetter Thomas (2019) The expanding search ratio of a graph. Dis. Appl. Math. 260:51\u201365","journal-title":"Dis. Appl. Math."},{"key":"876_CR6","doi-asserted-by":"crossref","unstructured":"Ausiello Giorgio, Leonardi Stefano, Marchetti-Spaccamela Alberto (2000) On Salesmen, Repairmen, Spiders, and Other Traveling Agents. Pages 1\u201316 of: Bongiovanni, Giancarlo, Petreschi, Rossella, & Gambosi, Giorgio (eds), Algorithms and Complexity. Berlin, Heidelberg: Springer Berlin Heidelberg","DOI":"10.1007\/3-540-46521-9_1"},{"key":"876_CR7","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"Anatole Beck","year":"1970","unstructured":"Beck Anatole, Newman DJ (1970) Yet more on the linear search problem. Israel J. Math. 8:419\u2013429","journal-title":"Israel J. Math."},{"key":"876_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10878-013-9634-8","volume":"30","author":"Marko Bender","year":"2015","unstructured":"Bender Marko, Westphal Stephan (2015) An optimal randomized online algorithm for the $$k$$-Canadian Traveller Problem on node-disjoint paths. J. Comb. Optim. 30:87\u201396","journal-title":"J. Comb. Optim."},{"issue":"5","key":"876_CR9","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"Timothy M Chan","year":"2010","unstructured":"Chan Timothy M (2010) More Algorithms for All-Pairs Shortest Paths in Weighted Graphs. SIAM J. Comput. 39(5):2075\u20132089","journal-title":"SIAM J. Comput."},{"key":"876_CR10","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.tcs.2006.05.018","volume":"361","author":"Erik D Demaine","year":"2006","unstructured":"Demaine Erik D, Fekete Sandor P, Gal Shmuel (2006) Online searching with turn cost. Theor. Comput. Sci. 361:342\u2013355","journal-title":"Theor. Comput. Sci."},{"key":"876_CR11","doi-asserted-by":"publisher","first-page":"1524","DOI":"10.1007\/s00453-020-00792-6","volume":"83","author":"Erik D Demaine","year":"2021","unstructured":"Demaine Erik D, Huang Yamming, Liao Chung-Shou, Sadakane Kunihiko (2021) Approximating the Canadian Traveller Problem with Online Randomization. Algorithmica 83:1524\u20131543","journal-title":"Algorithmica"},{"key":"876_CR12","doi-asserted-by":"crossref","unstructured":"Fleischer Rudolf, Kamphans Tom, KLEIN, Rolf, Langetepe, Elmar, & Trippien, Gerhard. (2009) Competitive online approximation of the optimal search ratio. SIAM J. Comput. 38(3):881\u2013898","DOI":"10.1137\/060662204"},{"key":"876_CR13","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF02764811","volume":"12","author":"Shmuel Gal","year":"1972","unstructured":"Gal Shmuel (1972) A general search game. Israel J. Math. 12:32\u201345","journal-title":"Israel J. Math."},{"issue":"1","key":"876_CR14","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/0127002","volume":"27","author":"Shmuel Gal","year":"1974","unstructured":"Gal Shmuel (1974) Minimax Solutions for Linear Search Problems. SIAM J. Appl. Math. 27(1):17\u201330","journal-title":"SIAM J. Appl. Math."},{"key":"876_CR15","doi-asserted-by":"crossref","unstructured":"Jaillet P, Wagner MR (2008a) Online Vehicle Routing Problems: A Survey. Chap. 10, pages 221\u2013237 of: Golden B, Raghavan S, Wasil E (ed), The Vehicle Routing Problem: Latest Advances and New Challenges. Boston, MA: Springer","DOI":"10.1007\/978-0-387-77778-8_10"},{"key":"876_CR16","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1287\/opre.49.4.501.11227","volume":"49","author":"Patrick Jaillet","year":"2001","unstructured":"Jaillet Patrick, Stafford Matthew (2001) Online Searching. Oper. Res. 49:501\u2013515","journal-title":"Oper. Res."},{"issue":"2","key":"876_CR17","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/trsc.1060.0147","volume":"40","author":"Patrick Jaillet","year":"2006","unstructured":"Jaillet Patrick, Wagner Michael R (2006) Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios. Transp. Sci. 40(2):200\u2013210","journal-title":"Transp. Sci."},{"key":"876_CR18","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1287\/opre.1070.0450","volume":"56","author":"Patrick Jaillet","year":"2008","unstructured":"Jaillet Patrick, Wagner Michael R (2008) Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses. Oper. Res. 56:745\u2013757","journal-title":"Oper. Res."},{"key":"876_CR19","doi-asserted-by":"crossref","unstructured":"Koutsoupias Elias, Papadimitriou Christos, Yannakakis Mihalis (1996) Searching a fixed graph. Pages 280\u2013289 of: Meyer, Friedhelm, & Monien, Burkhard (eds), Automata, Languages and Programming. Berlin, Heidelberg: Springer Berlin Heidelberg","DOI":"10.1007\/3-540-61440-0_135"},{"key":"876_CR20","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2014.02.026","volume":"530","author":"Chung-Shou Liao","year":"2014","unstructured":"Liao Chung-Shou, Huang Yamming (2014) The Covering Canadian Traveler Problem. Theor. Comput. Sci. 530:80\u201388","journal-title":"Theor. Comput. Sci."},{"key":"876_CR21","doi-asserted-by":"crossref","unstructured":"Liu Henan, Zhang Huili, Xu Yi (2021) The m-Steiner Traveling Salesman Problem with online edge blockages. J. Comb. Optim","DOI":"10.1007\/s10878-021-00720-6"},{"key":"876_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"Christos Papadimitriou","year":"1991","unstructured":"Papadimitriou Christos, Yannakakis Mihalis (1991) Shortest paths without a map. Theor. Comput. Sci. 84:127\u2013150","journal-title":"Theor. Comput. Sci."},{"key":"876_CR23","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1007\/s10878-018-0324-4","volume":"37","author":"Davood Shiri","year":"2019","unstructured":"Shiri Davood, Salman F. Sibel (2019) Competitive analysis of randomized online strategies for the online multi-agent $$k$$-Canadian Traveler Problem. J. Comb. Optim. 37:848\u2013865","journal-title":"J. Comb. Optim."},{"key":"876_CR24","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/s10878-019-00378-1","volume":"38","author":"Davood Shiri","year":"2019","unstructured":"Shiri Davood, Salman F. Sibel (2019) On the randomized online strategies for the $$k$$-Canadian traveler problem. J. Comb. Optim. 38:254\u2013267","journal-title":"J. Comb. Optim."},{"key":"876_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1147\/JRD.2019.2947002","volume":"64","author":"Davood Shiri","year":"2020","unstructured":"Shiri Davood, Salman F. Sibel (2020) Online Optimization of First-responder Routes in Disaster Response Logistics. IBM J. Res. Dev. 64:1\u20139","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"876_CR26","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/s00291-020-00594-w","volume":"42","author":"Davood Shiri","year":"2020","unstructured":"Shiri Davood, Akbari Vahid, Salman F. Sibel (2020) Online routing and scheduling of search-and-rescue teams. OR Spectrum 42(3):755\u2013784","journal-title":"OR Spectrum"},{"key":"876_CR27","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"Daniel Sleator","year":"1985","unstructured":"Sleator Daniel, Tarjan Robert (1985) Amortized efficiency of list update and paging rules. Com. ACM 28:202\u2013208","journal-title":"Com. ACM"},{"issue":"3","key":"876_CR28","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.ipl.2007.10.004","volume":"106","author":"Stephan Westphal","year":"2008","unstructured":"Westphal Stephan (2008) A note on the k-Canadian Traveller Problem. Inf. Processing Letters 106(3):87\u201389","journal-title":"Inf. Processing Letters"},{"key":"876_CR29","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10878-008-9156-y","volume":"18","author":"Yinfeng Xu","year":"2009","unstructured":"Xu Yinfeng, Hu Maolin, Su Bing, Zhu Binhai, Zhu Zhijun (2009) The Canadian Traveller Problem and its competitive analysis. J. Com. Optim. 18:195\u2013205","journal-title":"J. Com. Optim."},{"key":"876_CR30","doi-asserted-by":"crossref","unstructured":"Yao Andrew Chi-Chin. (1977) Probabilistic computations: Toward a unified measure of complexity. Pages 222\u2013227 of: 18th Ann. Symp. Found. Comput. Sci. (sfcs 1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"876_CR31","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1007\/s10878-017-0227-9","volume":"35","author":"Huili Zhang","year":"2018","unstructured":"Zhang Huili, Xu Yinfeng (2018) Online covering salesman problem. J. Comb. Optim. 35:941\u2013954","journal-title":"J. Comb. Optim."},{"key":"876_CR32","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.ejor.2014.11.013","volume":"243","author":"Huili Zhang","year":"2015","unstructured":"Zhang Huili, Tong Weitian, Xu Yinfeng, Lin Guohui (2015) The Steiner Traveling Salesman Problem with online edge blockages. Eur. J. Operat. Res. 243:30\u201340","journal-title":"Eur. J. Operat. Res."},{"key":"876_CR33","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.cor.2015.12.013","volume":"70","author":"Huili Zhang","year":"2016","unstructured":"Zhang Huili, Tong Weitian, Xu Yinfeng, Lin Guohui (2016) The Steiner Traveling Salesman Problem with online advanced edge blockages. Comput. & Operat. Res. 70:26\u201338","journal-title":"Comput. & Operat. Res."},{"key":"876_CR34","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.ejor.2018.08.017","volume":"273","author":"Huili Zhang","year":"2019","unstructured":"Zhang Huili, Tong Weitian, Lin Guohui, Xu Yinfeng (2019) Online minimum latency problem with edge uncertainty. Eur. J. Operat. Res. 273:418\u2013429","journal-title":"Eur. J. Operat. Res."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00876-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00876-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00876-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T06:16:23Z","timestamp":1660371383000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00876-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,22]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["876"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00876-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,6,22]]},"assertion":[{"value":"11 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}