Dynamic Stochastic Orienteering Problems for Risk-Aware Applications

Hoong Chuin Lau, William Yeoh, Pradeep Varakantham, Duc Thien Nguyen, HuaXing Chen

Abstract

Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations: travel times between cities are assumed to be time-independent and the route provided is independent of the risk preference of the user. To address these issues, we introduce: (1) a dynamic SOP (DSOP) model, which extends SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. We evaluated our algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets.

Introduction

Standard path planning in orienteering problems often fails in real-world environments like theme parks or urban traffic because it ignores two critical factors: uncertainty and dynamics. Travel times are rarely fixed; they are random variables that fluctuate throughout the day. For instance, a ride's queue at 2:00 PM is vastly different from its queue at 10:00 AM. Furthermore, different users have different risk tolerances. A "risk-averse" traveler might prioritize reaching a destination on time, while a "risk-seeking" traveler might accept a higher probability of delay to visit more attractions.

This paper introduces the Dynamic Stochastic Orienteering Problem (DSOP) framework to address these challenges, providing a way to maximize rewards while adhering to user-defined risk constraints.

Methodology

The primary challenge in DSOPs is the computational complexity of calculating arrival time distributions across a sequence of time-dependent nodes. The authors propose two main strategies:

Matrix-based Approximation

This core innovation discretizes time into ranges and assumes a Markovian property where the arrival time at a node depends only on the arrival time at the previous node. By pre-computing "transition matrices," the probability of completing a path is reduced to a series of efficient matrix multiplications. This method offers a significant speedup over traditional integral calculations.

Local Search Algorithm

To optimize the path, a two-phase local search is employed:

  1. Construction: A greedy heuristic inserts nodes based on a reward-to-risk ratio.
  2. Improvement: A hybrid of 2-Opt edge swapping and Simulated Annealing refines the path. The pre-computed matrices allow the algorithm to quickly validate if a proposed swap violates the risk constraint ($P(arrival \le Deadline) \ge 1 - \epsilon$).

Experimental Evaluation

The framework was tested on synthetic benchmarks and a real-world theme park dataset containing actual queuing and transit times.

Risk Sensitivity and Feasibility

A key finding is the effectiveness of the matrix-based approach in maintaining feasibility. As shown in Figure 2, the matrix-based approach ($P_M$) consistently satisfies the risk constraints across different values of $\epsilon$, whereas sampling-based methods ($P_S$) can sometimes return paths that exceed the allowed risk level.

Performance comparison across different risk tolerance levels ($\epsilon$).

Real-World Application: Theme Park Navigation

On the theme park dataset, the model distinguishes between "Peak" and "Non-Peak" days. Non-peak days exhibit not only shorter wait times but also lower variance. The algorithm successfully adapts, suggesting more conservative routes during high-congestion periods and more aggressive itineraries when conditions are stable.

Rewards on Peak vs. Non-Peak days for varying deadlines ($H$) and risk levels ($\epsilon$).

Conclusion

The DSOP framework successfully integrates time-dependent uncertainty and risk preference into orienteering problems. While the matrix-based approach introduces some memory overhead, it provides the computational efficiency and feasibility guarantees necessary for real-time applications. Future work will explore scaling these methods to city-wide logistics and emergency vehicle routing.

Summary updated

Abstract

Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, we make the following contributions: We introduce (1) a dynamic SOP (DSOP) model, which is an extension of SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. We evaluated our algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets employed in the literature.
BibTeX
@inproceedings{lau2012dynamic,
  author = {Hoong Chuin Lau and William Yeoh and Pradeep Varakantham and Duc Thien Nguyen and HuaXing Chen},
  title = {{Dynamic Stochastic Orienteering Problems for Risk-Aware Applications}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2012},
  url = {https://openreview.net/forum?id=9jHQUsMAkl9N},
}
Figure