Efficient Routing for Disaster Scenarios in Uncertain Networks: A Computational Study of Adaptive Algorithms for the Stochastic Canadian Traveler Problem with Multiple Agents and Destinations
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
The primary objective of this research is to develop adaptive online algorithms for solving the Canadian Traveler Problem (CTP), which is a well-studied problem in the literature that has important applications in disaster scenarios. To this end, we propose two novel approaches, namely Maximum Likely Node (MLN) and Maximum Likely Path (MLP), to address the single-agent single-destination variant of the CTP. Our computational experiments demonstrate that the MLN and MLP algorithms together achieve new best-known solutions for 10,715 instances. In the context of disaster scenarios, the CTP can be extended to the multiple-agent multiple-destination variant, which we refer to as MAD-CTP. We propose two approaches, namely MAD-OMT and MAD-HOP, to solve this variant. We evaluate the performance of these algorithms on Delaunay and Euclidean graphs of varying sizes, ranging from 20 nodes with 49 edges to 500 nodes with 1500 edges. Our results demonstrate that MAD-HOP outperforms MAD-OMT by a considerable margin, achieving a replan time of under 9 seconds for all instances. Furthermore, we extend the existing state-of-the-art algorithm, UCT, which was previously shown by Eyerich et al. (2010) to be effective for solving the single-source single-destination variant of the CTP, to address the MAD-CTP problem. We compare the performance of UCT and MAD-HOP on a range of instances, and our results indicate that MAD-HOP offers better performance than UCT on most instances. In addition, UCT exhibited a very high replan time of around 10 minutes. The inferior results of UCT may be attributed to the number of rollouts used in the experiments but increasing the number of rollouts did not conclusively demonstrate whether UCT could outperform MAD-HOP. This may be due to the benefits obtained from using multiple agents, as MAD-HOP appears to benefit to a greater extent than UCT when information is shared among agents.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.001 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it