An Upper Partial Moment Framework for Pathfinding Problem Under Travel Time Uncertainty - Xu Zhang; Mei Chen (Systems, 2025)
Route planning under uncertain traffic conditions requires accounting for not only expected travel times but also the risk of late arrivals. This study proposes a mean-upper partial moment (MUPM) framework for pathfinding that explicitly considers travel time unreliability. The framework incorporates a benchmark travel time to measure the upper partial moment (UPM), capturing both the probability and severity of delays. By adjusting a risk parameter (<semantics>θ</semantics>), the model reflects different traveler risk preferences and unifies several existing reliability measures, including on-time arrival probability, late arrival penalty, and semi-variance. A bi-objective model is formulated to simultaneously minimize mean travel time and UPM. Theoretical analysis shows that the MUPM framework is consistent with the expected utility theory (EUT) and stochastic dominance theory (SDT), providing a behavioral foundation for the model. To efficiently solve the model, an SDT-based label-correcting algorithm is adapted, with a pre-screening step to reduce unnecessary pairwise path comparisons. Numerical experiments using GPS probe vehicle data from Louisville, Kentucky, USA, demonstrate that varying <semantics>θ</semantics> values lead to different non-dominated paths. Lower <semantics>θ</semantics> values emphasize frequent small delays but may overlook excessive delays, while higher <semantics>θ</semantics> values effectively capture the tail risk, aligning with the behavior of risk-averse travelers. The MUPM framework provides a flexible, behaviorally grounded, and computationally scalable approach to pathfinding under uncertainty. It holds strong potential for applications in traveler information systems, transportation planning, and network resilience analysis.