Highlights • Seek optimal paths in networks with stochastic time-varying correlated link travel times. • The routes can be improved as more information is revealed along the way. • The approach can be used to find both optimal and approximate solutions. • It incorporates individual-specific risk preferences. • Paths can be found faster if the user is willing to tolerate higher risk of suboptimality. • Approach finds adaptive strategy solutions that consistently outperform a priori solutions.

Abstract This paper focuses on the problem of finding optimal trajectory-adaptive routing strategies in stochastic time-varying networks with generalized spatio-temporal correlations. A representation for jointly distributed continuous link travel times across the entire network with time-varying distributions and correlation structures is presented, and the crucial characteristics and methodological difficulties of the problem are discussed. The paper presents a generalized 2-stage path and strategy finding solution approach that can serve for finding both exact and approximate solutions with the tuning of a risk-level tolerance parameter. The first stage of the solution approach generates eligible paths, where the risk-level parameter is used to eliminate paths that are likely to be inefficient. The second stage finds reliable trajectory-adaptive strategies, using the eligible paths only, based on one or multiple reliability-based optimality conditions. Thus, the approach allows the user to determine the optimal strategy for one or multiple groups of travelers with different reliability preferences. Numerical experiments show that the average running time of the algorithm reduces super-linearly with the increase of the risk-tolerance parameter $∊$, while incurring some loss to the objective function relative to the exact solution. Thus, the heuristic can offer significant benefits in reducing the run time of the solution algorithm, while finding adaptive strategy solutions that consistently maintain better objective function values compared to the a priori (i.e., non-adaptive) solutions.