A reinforcement learning framework for the adaptive routing problem in stochastic time-dependent network. (August 2018)

• Record Type: Journal Article
• Authors: Mao, Chao; Shen, Zuojun
• Is Part Of: Transportation research. Volume 93(2018)
• Page Start: 179
• Page End: 197
• Publication Date: 2018-08
• Subjects: Adaptive routing -- Reinforcement learning -- Q learning -- Fitted Q iteration -- Tree-based function approximation; Transportation -- Periodicals; Transportation -- Technological innovations -- Periodicals; 388.011
• DOI: 10.1016/j.trc.2018.06.001
• Languages: English
• ISSNs: 0968-090X

Abstract

Highlights: Model-based methods might be impractical in solving the adaptive routing problem. Reinforcement learning is an effective non-parametric model-free method to solve it. Both the Q learning method and fitted Q iteration method are presented. Fitted Q iteration algorithm in continuous state space shows better performance. Abstract: Most previous work in addressing the adaptive routing problem in stochastic and time-dependent (STD) network has been focusing on developing parametric models to reflect the network dynamics and designing efficient algorithms to solve these models. However, strong assumptions need to be made in the models and some algorithms also suffer from the curse of dimensionality. In this paper, we examine the application of Reinforcement Learning as a non-parametric model-free method to solve the problem. Both the online Q learning method for discrete state space and the offline fitted Q iteration algorithm for continuous state space are discussed. With a small case study on a mid-sized network, we demonstrate the significant advantages of using Reinforcement Learning to solve for the optimal routing policy over traditional stochastic dynamic programming method. And the fitted Q iteration algorithm combined with tree-based function approximation is shown to outperform other methods especially during peak demand periods.