# Solving Stochastic Orienteering Problems with Chance Constraints Using a GNN Powered Monte Carlo Tree Search

arXiv: https://arxiv.org/abs/2409.04653 · HTML: https://mlsanity.com/paper/2409.04653/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 6 Sep 2024.

## Builds on (most cited first, 11 of 11)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation](https://mlsanity.com/paper/1406.1078/) (2014)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Improving Hearthstone AI by Combining MCTS and Supervised Learning Algorithms](https://mlsanity.com/paper/1808.04794/) (2018)
- [Robust Multiple-Path Orienteering Problem: Securing Against Adversarial Attacks](https://mlsanity.com/paper/2003.13896/) (2020)
- [Solving Stochastic Orienteering Problems with Chance Constraints Using Monte Carlo Tree Search](https://mlsanity.com/paper/2409.03170/) (2024)
- [Speeding up Routing Schedules on Aisle-Graphs with Single Access](https://mlsanity.com/paper/2102.05733/) (2021)
- [Boosting Graph Search with Attention Network for Solving the General Orienteering Problem](https://mlsanity.com/paper/2109.04730/) (2021)

## Built on by (most cited first, 2 of 2)

- [Leveraging LLMs for Mission Planning in Precision Agriculture](https://mlsanity.com/paper/2506.10093/) (2025)
- [N(CO)2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering](https://mlsanity.com/paper/2606.18514/) (2026)

## Abstract (arXiv)

Leveraging the power of a graph neural network (GNN) with message passing, we present a Monte Carlo Tree Search (MCTS) method to solve stochastic orienteering problems with chance constraints. While adhering to an assigned travel budget the algorithm seeks to maximize collected reward while incurring stochastic travel costs. In this context, the acceptable probability of exceeding the assigned budget is expressed as a chance constraint. Our MCTS solution is an online and anytime algorithm alternating planning and execution that determines the next vertex to visit by continuously monitoring the remaining travel budget. The novelty of our work is that the rollout phase in the MCTS framework is implemented using a message passing GNN, predicting both the utility and failure probability of each available action. This allows to enormously expedite the search process. Our experimental evaluation shows that with the proposed method and architecture we manage to efficiently solve complex problem instances while incurring in moderate losses in terms of collected reward. Moreover, we demonstrate how the approach is capable of generalizing beyond the characteristics of the training dataset. The paper's website, open-source code, and supplementary documentation can be found at ucmercedrobotics.github.io/gnn-sop.