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

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.