Finding a shortest path between two locations on stochastic time-dependent road network is an important constituent in vehicle guidance system. However, it is difficult for traditional heuristic algorithm to handle the complexity and stochasticity within the road network. In this paper, we model the stochastic time-dependent routing problem as a Markov decision process and utilize several reinforcement learning methods to solve this problem, such as Sarsa, Q-learning and Double Q-learning method. Sarsa method uses the actual Q value for iteration instead of the maximum value function used by Q-Learning, while Double Q-learning utilizes two estimators to compute the value function, which can overcome the shortcoming of overestimation. Evaluated on ten stochastic time-dependent road networks, we can draw the conclusion that Double Q-learning method outperforms other methods. Finally, the optimal paths acquired at different epochs are visualized to display the process of agent exploration.

CICTP