Optimizing Group Utility in Itinerary Planning: A Strategic and Crowd-Aware Approach
This work addresses itinerary recommendation for groups in crowded environments like theme parks, offering a domain-specific improvement over single-person approaches.
The paper tackled the problem of optimizing group utility in itinerary planning by addressing the Selfish Routing issue in crowded settings, introducing the SCAIR algorithm which outperformed baselines across four theme parks.
Itinerary recommendation is a complex sequence prediction problem with numerous real-world applications. This task becomes even more challenging when considering the optimization of multiple user queuing times and crowd levels, as well as numerous involved parameters, such as attraction popularity, queuing time, walking time, and operating hours. Existing solutions typically focus on single-person perspectives and fail to address real-world issues resulting from natural crowd behavior, like the Selfish Routing problem. In this paper, we introduce the Strategic and Crowd-Aware Itinerary Recommendation (SCAIR) algorithm, which optimizes group utility in real-world settings. We model the route recommendation strategy as a Markov Decision Process and propose a State Encoding mechanism that enables real-time planning and allocation in linear time. We evaluate our algorithm against various competitive and realistic baselines using a theme park dataset, demonstrating that SCAIR outperforms these baselines in addressing the Selfish Routing problem across four theme parks.