Behavior Modeling in Transportation Networks Lecture Series #3-1 (16:00-16:30) Reinforcement Learning and Network Design Yuki Oyama Shibaura Institute of Technology Activity Landscape Design Lab. September 17, 2021
The planner who aims to maximize efficiency wants to answer: . if a new road should be constructed . where and how large parking spaces should be placed . on which road and how much tolls should be charged . etc. These decisions will impact on travelers’ behavior Let’s generalize the framework An example of pricing (on which road a toll is installed)
Planner (Supply)
Design variables   y New toll installed on road A Behavior distribution    P Drivers change route choices to avoid road A Objective function  Z(y) Wants to minimize total travel time Network traffic   x Alternative route of using road A is congested Users (Demand) Let’s generalize the framework An example of pricing (on which road a toll is installed)
Planner (Supply)
Design variables   y New toll installed on road A Behavior distribution    P Drivers change route choices to avoid road A Objective function   Z(x(p(y))) Total travel time in the network increased as a result Network traffic   x Alternative route of using road A is congested Users (Demand)
is a demand-based planning of network topology & systems Follows Magnanti and Wong (1984); Farahani et al. (2013) Planner (Supply) Design variables   y the planner decides under some constraints [network topology & conditions] [indicators] Behavior distribution    P travelers decide/change in reaction to the design of network How to predict the impact on behavior in a network? Objective function   Z(x(p(y))) the planner wants to maximize [review] What you (the planner) want to achieve by the project Network traffic   x that appears as a collective state Users (Demand)
Path choice model (logit)
R  : choice set (set of paths) Traffic flow on paths (in the static case)
Not as easy as it looks…

This is because a path is a combination of links in the network
* A description of more complex choices (e.g., time) needs additional dimensions of network, which further increases the network size.
An approach is modeling based on Reinforcement Learning (RL) that models sequential decisions of agents.
Sequence of choices This presentation shows a special case of RL for network path choice modeling How to model a sequence ? A path r can be described as:
Path choice probability:
p(aj+1|aj)  : Link choice probability conditional on the previous link ⇒ what is link choice probability exactly?
the outcome given by the product of link choice probabilities to be consistent with the original model, i.e.,
*when assuming logit model This is achieved by considering forward-looking mechanism Goal is modeling Myopic 1. 2. Forward-looking mechanisms of behavior
: Link choice utility V d : Value function (β = 1)
α j+1 c.f. Shortest Path (SP) problem: Generalization Value function is the SP cost from aj to destination
Value function is the solution to:
a system of linear equations. (Recurrence relation)
Let’s check the consistency! Link choice probability is given by:
Then we have:
⇒ Consistent with logit model with the universal path set Now you can model path choice behavior without explicitly defining choice set 1. Decompose path choice into sequential link choices: 2. Describe forward-looking behavioral mechanism by value function: ecursively computed This (efficient) computational method of modeling is called: “Recursive Logit (RL) model” Named by Fosgerau et al. (2013)
To more generalize, define . Action : choice behavior (what agent does) . State: situation (where agent is) that changes as result of action *In path choice (recursive) modeling: Action is directly choice of State
MDP General modeling framework of sequential decisions Stochastic Reinforcement Learning Learn optimal action probability by a number of trials & results Dynamic Discrete Choice Model Boltzmann policy (temp. = 1/scale) Action = State Gumbel Recursive Logit Modeling action probability under RUM assumption Parameter estimation Inverse Reinforcement Learning Learn utility (reward) function from actions of experts
See also: Mai and Jaillet (2020)
Now, we have link transition probabilities   {p(a) Given OD demand q, we compute network traffic flows
[1] and [2] reduces to:
aEL Another dimension may be needed e.g., a planner may expect changes of visitors’ time-use in a city center Time-structured network allows for integrated modeling of route, activity place and duration. A path  r = [s1, s2, . . . , sj]  represents multiple activities X a Xta Network traffic: t : no. people who visited space a : total time spent at space a
Examples:
Remark (again): The choice of objective reflects what you (the planner) want to achieve through the project Minimizing negative indicators is enough?   What is a better/ideal city you think?
A road closure may increase travel time of the network. Barcelona superblock But the space can be utilized as a park that is good for activities, health and environment. Of course, it requires a large capital cost, and the budget is limited. Weighted sum is enough ? Z = α1Z1 + α2Z2 + α3Z3 + ··· . Often, there is a clear trade-off between two objectives Weight selection may lead to a biased policy decision .
Capital cost (to be minimized) Social welfare (to be maximized) 0

City center of Matsuyama city
. . Design : expansion of walking space on each street [m.] Expectation : resistance decreases, and more places are visited
Goal I: Sojourn time maximization Goal II: Expected utility maximization Clear trade-offs between goals and budget are observed. . Pareto frontier offers a variety of policies based on the investment level .
Goal I: Sojourn time Goal II: Expected utility [Upper level problem] Network (solution) +x : increased width [m] [Lower level problem] Link flow : 100 : diff. > +10 : diff. < -10 20 Activity duration [*60sec./person] : diff. > +0.5 : diff. < -0.5 Staying node number • Reinforcement Learning is a general framework of modeling sequential decisions in networks. • You can model any “state-action network” • “State = action = space” is just an example • Network design is a mathematical problem of behavior (in a network) based planning •  Be thoughtful when you set an objective • Multi-objective design may fit in public projects Questions ? oyama@shibaura-it.ac.jp