Heuristics for the stochastic/dynamic user-optimal route choice problem

A stochastic/dynamic user-optimal route choice problem that assumes time-dependent route travel times Gumbel distributed is formulated by a variational inequality and the corresponding equilibrium conditions are introduced. Two K-shortest-path based heuristics called K-shortest-path (KSP) and restricted K-shortest-path (RKSP) are proposed and compared with a link-based heuristic called stochastic dynamic method (SADA). Numerical examples show that both the KSP and RKSP are superior to the SADA in terms of total CPU time. While both the KSP and RKSP have fully taken advantage of computational efficiency, the latter is more practical by taking into account the thresholds of an overlapping ratio and route travel time difference.