Learning Graph-Indexed Trajectory Patterns for Stochastic On-Time Arrival Routing

Abstract:Correlated link travel times create decision-relevant patterns in partial route histories. In stochastic on-time arrival (SOTA) routing, each route prefix forms a variable-length, graph-indexed sequence in which traversed-edge identities, realized travel times, and route order jointly indicate the reliability of downstream actions. We present GPG-HT, a history-conditioned Transformer policy that learns a trajectory representation from this structured sequence together with the current node, destination, and remaining budget. Edge-time cross-attention and sequence encoding capture dependencies within the observed history, while decoder cross-attention maps the resulting trajectory memory and decision context to an online distribution over feasible outgoing edges. A history-conditioned generalized policy-gradient objective trains the representation from terminal on-time outcomes. Experiments on the Sioux Falls and Anaheim road-network topologies with simulated correlated link times show that GPG-HT achieves higher mean on-time arrival probabilities than representative optimization and reinforcement-learning baselines. Paired common-pool evaluation confirms statistically significant gains in all six network-budget settings, reaching 2.82-3.27 percentage points on Sioux Falls and 0.36-1.04 percentage points on Anaheim. Correlated, independent, shuffled-history, no-history, and architecture controls further demonstrate that GPG-HT learns decision-relevant structure from graph-indexed route prefixes.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2508.17218 [cs.LG]

(or arXiv:2508.17218v4 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2508.17218 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.