Routing policy choice prediction in a stochastic network: Recursive model and solution algorithm

• Main Authors: MAI, Tien, YU, Xinlian, GAO, Song, FREJINGER, Emma
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Routing policy choice; Stochastic time-dependent networks; Recursive logit; Decomposition algorithm; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/6215; https://ink.library.smu.edu.sg/context/sis_research/article/7218/viewcontent/RoutingPolicyChoice_av.pdf
• Institution: Singapore Management University

We propose a Recursive Logit (STD-RL) model for routing policy choice in a stochastic time-dependent (STD) network, where a routing policy is a mapping from states to actions on which link to take next, and a state is defined by node, time and information. A routing policy encapsulates travelers’ adaptation to revealed traffic conditions when making route choices. The STD-RL model circumvents choice set generation, a procedure with known issues related to estimation and prediction. In a given state, travelers make their link choice maximizing the sum of the utility of the outgoing link and the expected maximum utility until the destination (a.k.a. value function that is a solution to a dynamic programming problem). Existing recursive route choice models and the corresponding solution approaches are based on the assumption that network attributes are deterministic. Hence, they cannot be applied to stochastic networks which are the focus of this paper.We propose an efficient algorithm for solving the value function and its gradient, critical for parameter estimation. It is based on partitioning the state space and decomposing costly matrix operations into a series of simpler ones. We present numerical results using a synthetic network and a network in Stockholm, Sweden. The estimation running time has a 20-30 times speed-up due to matrix decomposition. The estimated model parameters have realistic interpretations. Specifically, travelers are more likely to be adaptive to realized travel times during a longer trip, and more sensitive to travel time when travel time variability is higher. The STD-RL model performs better in predicting route choices than the RL model in a corresponding static and deterministic network.