Constraint reformulation and a Lagrangian relaxation-based solution algorithm for a least expected time path problem.

Highlights: [•] Develop a sampling-based method to characterize temporal and spatial correlation structure in path finding problem. [•] Propose a Lagrangian substitution approach to handle non-anticipativity constraint associated with a priori path. [•] Develop solution algorithms to improve solution quality and find approximate optimal solutions. [ABSTRACT FROM AUTHOR]