Progressive Tree Expansion and Vertex-Based Pruning in UCT Strategies for the Stochastic Canadian Traveller Problem
Abstract
The Stochastic Canadian Traveller Problem (SCTP) models adaptive routing on a known graph in which the availability of an edge is revealed only after the traveller reaches an incident vertex, while edge-specific blocking probabilities are known in advance. This paper investigates simulation-based strategies for minimizing the expected travel cost. After summarizing the Optimistic Policy, Hindsight Optimization, Optimistic Rollout, and established UCT-based approaches, the paper formalizes and evaluates two original heuristic variants of Optimistic UCT, UCTO2 and UCTP, which had previously been proposed and implemented in a master's thesis. UCTO2 replaces complete depth-oriented rollout trajectories with progressive tree expansion and batch rollout evaluation of selected nodes. UCTP augments UCTO2 with a pruning mechanism that retains the more promising of alternative tree nodes associated with the same graph vertex. The methods are evaluated on two families of randomly generated graphs with 50 vertices, using ten graphs per family and 500 stochastic realizations per graph. In the reported experiments, UCTP achieved lower mean travel costs than the Optimistic Policy and UCTO while requiring substantially less computation time than the other evaluated UCT variants. HOP and ORO nevertheless attained the lowest overall mean costs. The evidence therefore supports the complete UCTP configuration as a favourable finite-budget alternative within the UCT family, not as a generally superior SCTP policy.
References
Alkaya, A. F., Yildirim, S., and Aksakalli, V. Heuristics for the canadian traveler problem with neutralizations. Computers & Industrial En-
gineering 159 (2021), 107488.
Bar-Noy, A., and Schieber, B. The canadian traveller problem. In Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms (1991), Citeseer, pp. 261–270.
Beaudou, L., Berg´e, P., Chernyshev, V., Dailly, A., G´erard, Y., Lagoutte, A., Limouzy, V., and Pastor, L. The canadian traveller problem on outerplanar graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) (2024), vol. 306 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum fur Informatik, pp. 19:1–19:16.
Bnaya, Z., Felner, A., Fried, D., Maksin, O., and Shimony, S. E. Repeated-task canadian traveler problem. AI Communications 28, 3 (2015), 453–477.
Bnaya, Z., Felner, A., and Shimony, S. E. Canadian traveler problem with remote sensing. In IJCAI (2009), pp. 437–442.
Eyerich, P., Keller, T., and Helmert, M. High-quality policies for the Canadian Traveler’s Problem. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (2010), pp. 51–58.
Filip, S. Reseni problemu Kanadskeho cestujiciho (in Czech) [Solving Canadian Traveller Problem]. Master’s thesis, Brno University of Technology, Faculty of Mechanical Engineering, Institute of Automation and Computer Science, Brno, Czech Republic, 2017. Supervisor: Jiri Dvorak. Available: http://hdl.handle.net/11012/67982.
Fried, D., Shimony, S. E., Benbassat, A., and Wenner, C. Complexity of canadian traveler problem variants. Theoretical Computer Science 487 (2013), 1–16.
Kocsis, L., and Szepesv´ari, C. Bandit based monte-carlo planning. In Machine Learning: ECML 2006 (2006), Springer, pp. 282–293.
Nikolova, E., and Karger, D. R. Route planning under uncertainty: The canadian traveller problem. In AAAI (2008), pp. 969–974.
Papadimitriou, C. H., and Yannakakis, M. Shortest paths without a map. Theoretical Computer Science 84, 1 (1991), 127–150.
Shiri, D., and Salman, F. S. On the on-line multi-agent o–d k-canadian traveler problem. Journal of Combinatorial Optimization 34, 2 (2017), 453–461.
Su, B., and Xu, Y. Online recoverable canadian traveller problem. In Proceedings of the interna tional conference on management science and engineering (2004), pp. 633–639.
Su, B., Xu, Y., Xiao, P., and Tian, L. A risk-reward competitive analysis for the recoverable canadian traveller problem. In Combinatorial Optimization and Applications: Second International Conference, COCOA 2008, St. John’s, NL, Canada, August 21-24, 2008. Proceedings 2 (2008), Springer, pp. 417–426.
Westphal, S. A note on the k-canadian traveller problem. Information Processing Letters 106, 3 (2008), 87–89.
Xu, Y., Hu, M., Su, B., Zhu, B., and Zhu, Z. The canadian traveller problem and its competitive analysis. Journal of combinatorial optimization 18, 2 (2009), 195–205.
Yildirim, S., Aksakalli, V., and Alkaya, A. F. Canadian traveler problem with neutralizations. Expert Systems with Applications 132 (2019), 151–165.
Zhang, H., Xu, Y., and Qin, L. The k-canadian travelers problem with communication. Journal of Combinatorial Optimization 26 (2013), 251–265.
Copyright (c) 2025 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
