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:
- Construction: A greedy heuristic inserts nodes based on a reward-to-risk ratio.
- 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.
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.
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