Navigating uncertain and disrupted road conditions in a disaster response: A consensus-based algorithm for solving the Stochastic Canadian Traveler Problem

The timely delivery of critical supplies and services in disaster-affected regions is challenged by infrastructure failures and uncertainty regarding network accessibility. This paper models this routing problem under infrastructure uncertainty as a Stochastic Canadian Traveler Problem (CTP). It introduces two adaptive routing algorithms, Maximum Likely Node (MLN) and Maximum Likely Path (MLP), which leverage probabilistic reasoning and consensus-based rollout sampling to guide online decision-making. A computational study comprising 30,000 instances across 30 graphs demonstrates the effectiveness of the proposed methods. MLN and MLP identify 21,784 and 20,882 best-known solutions (BKS), respectively, outperforming the benchmark method A ∗ -HOP, which finds 19,285 BKS. Furthermore, the proposed methods generate over 10,700 previously unknown high-quality solutions, significantly expanding the available benchmark set. Pairwise statistical analysis shows that MLN achieves significant improvements over A ∗ -HOP. The results indicate that incorporating probabilistic consensus from rollout policies improves robustness in stochastic networks. In addition to algorithmic contributions, this work provides a comprehensive benchmark dataset to support future research in stochastic routing and disaster response optimization. • Addressing transportation challenges in disaster response. • Algorithms solve Canadian Traveler Problem for efficient and timely supply. • MLN & MLP algorithms based on consensus function solve Stochastic CTP. • MLN & MLP algorithms achieve best-known solutions for 21,784 and 20,882 test instances respectively.