A time-dependent analytical traffic model to tackle dynamic
Bayesian optimization problems in urban transportation
T. Taya , C. Bongiovannib and C. Osoriob,∗a Institute for Infocomm Research, Singapore

timothy_tay@i2r.a-star.edu.sg
b HEC Montréal, Group for Research in Decision Analysis (GERAD), Montréal (QC), Canada

claudia.bongiovanni@hec.ca; carolina.osorio@hec.ca∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 4, 2022
Keywords: simulation-based optimization, Bayesian optimization, dynamic traffic signal control

1INTRODUCTION

Most real-world problems in transportation aim to optimize time-dependent decision variables
that live in a dynamic, stochastic, and fast-paced environment. Such problems are frequently
characterized by a stochastic, nonconvex objective function which has an unknown analyticalform. Simulation-based optimization (SO) is a popular method that allows the coupled useof analytical traffic models and complex stochastic urban traffic simulators to address various
real-world continuous transportation problems. One approach to tackle SO problems is known
as metamodel SO (Osorio & Bierlaire, 2013). In this approach, a limited number of simulation
observations is used to fit an analytical approximation of the simulation-based objective function(i.e., a metamodel or surrogate model), which is less expensive to evaluate than the underlying
simulator. The fitted surrogate model is employed to perform optimization and derive new local solutions for the decision variables. The performance of new local solutions is successivelyevaluated by the simulator, leading to new observations that can be used to improve the fit of
the surrogate model. Given the computational burden of running simulations, the SO literature
has mostly considered stationary surrogate models (i.e. with no time-dependent decision variables and no dynamic information from the simulator). These models can be enhanced through
Bayesian optimization (BO, Tay & Osorio, 2021). This leads to the development of efficient
dynamic surrogate models that can be integrated into BO to solve dynamic SO problems.
In this work, we formulate a novel analytical and dynamic traffic model. We incorporate
the model within a BO framework and use it to tackle a large-scale dynamic SO transportation
problem. The proposed traffic model is both realistic and computationally efficient enough so thatthe resulting BO framework preserves its efficiency and becomes suitable for high-dimensional
dynamic problems. This work extends the methodology of Tay & Osorio (2021), which combines
a time-independent traffic model with a BO framework, to time-dependent problems throughthe formulation and use of a time-dependent traffic model. Preliminary results on small-scale
scenarios on a toy network from the literature show that incorporating the dynamic analyticaltraffic model within BO leads to similar or better solutions than using stationary analyticaltraffic models or no problem-specific information.
TRISTAN XI Symposium

Original abstract submittal

T. Tay, C. Bongiovanni, and C. Osorio

22

METHODOLOGY

2.1

Dynamic traffic signal optimization problem

Consider a traffic signal control problem with a fixed cycle time ei for each link i ∈ L. The
problem optimizes the green splits of each periodic signal phase j ∈ P(i) during L time intervals,i.e. xl,j . The goal is to determine a fixed time signal plan for each time interval such that theexpected travel time of vehicles that end their trips during the second half of the simulation
period is minimized (i.e., time interval l = ⌊(L/2) + 1⌋ to l = L). The problem is modeled asfollows:
LX
1
min f (x, z; p) ≡E[Fl (x, z; p)](1)x1 ,...,xL⌈L/2⌉l=⌊(L/2)+1⌋

s.t.

Xxl,j =j∈P(i)

ci − ei, ∀i ∈ I, l = 1, . . . , L,cixl ≥ xLB ,l = 1, . . . , L,

(2)

(3)

where the objective function (1) is the weighted sum of the simulation-evaluated expected travel
time of vehicles during time interval l, i.e. Fl . This depends on the vector xl of green splits fortime interval l, the vector zl of endogenous link-level and network-level metrics for time intervall, and the vector p of exogenous road network topology and fixed lane attributes. Constraints (2)represent the cycle time constraints and ensure that the sum of all the green splits for a given
intersection add up to the proportion of available cycle time ci that can be optimized (i.e., notfixed). Constraints (3) impose a lower bound on xl .
Assuming a limited amount of simulation observations, we choose BO as a suitable solution
approach (Jones et al., 1998). BO consists of two main components: (i) a model of the objectivefunction, and (ii) an acquisition function. One of the most popular choice of models of theobjective function is Gaussian Processes (GP). In this work, prior information is fed to theGP model in the form of a dynamic analytical traffic network model. We refer the reader toSection 3.2 of Tay & Osorio (2021) for a discussion of how this model is incorporated into theGP model.

2.2

Dynamic analytical traffic network model

In this work, each link i ∈ L in the network is modeled as a reservoir of vehicles, with inflow
out
Qin
i,l from upstream links and outflow Qi,l from to downstream links. The term E[Fl (x, z; p)]PAA
in objective function (1) is approximated by L
l=1 αl fl , where fl represents the expected timevehicles spend in the network in time interval l. This is approximated using Little’s law (Little,2011), as follows:
M−1−1PP MP
1 P
diρi,l (m∆t)
diρi,l (m∆t)
Mm=0m=0i∈Li∈LAfl = = P MP
,M −1−1ρi,l (m∆t)ρi,l (m∆t)
1 P P
γi,l 1 − ρmax
γi,l 1 − ρmax
Mi∈L m=0i∈L m=0(4)where M represents the number of time steps in interval l, ∆t the time step length, ρmax themaximum vehicle density, and di the length of link i. Furthermore, ρi,l and γi,l represent thevehicle density and the external arrival rate to link i in interval l respectively.
Traffic dynamics are modeled through the following system of dynamical equations:µi,l (t)ρj,l (t)DQ
FD
Qij,l (t) =· Q (ρi,l (t)) · 1(Ni,l (t) > 0) · pij 1 − max ,(5)sρ
TRISTAN XI Symposium

Original abstract submittal

T. Tay, C. Bongiovanni, and C. Osorio

3

Table 1 – DemandDemand (veh/h)

AB/BA

1050 −−−−−→ 350

CD/DCEFHG
JKFigure 1 – Synthetic arterial network model.

Qini,l (t) = γi,lOD Pair

30 min30 min300 −−−−−→ 900
100100100 X
ρj,l (t)Qji,l (t),1 − max +
ρ(6)

j


Qouti,l (t) =X

DQ
Qij,l (t) + QFD (ρi,l (t)) · 1(Ni,l(t) > 0) · 1 −pij  ,(7)ρi,l (t)FFoutt − ti
1 + max− Qi,l (t) · ∆t,
ρ(8)

jDQ
DQ
Ni,l(t) = Ni,l(t − ∆t) +Xj

Qini,lρi,l ((t + ∆t) = ρi,l (t) +
1out
Qini,l (t) − Qi,l (t) ∆t.
di(9)Equation (5) represents the fraction of the saturation flow rate s that can that can flow fromlink i to link j at a given time t ∈ [0, (M − 1)∆t]. Here, QFD (ρi,l (t)) represents the maximum
outflow of link i described by the triangular fundamental diagram (Treiber & Kesting, 2013),
DQ(t) > 0) the indicator function implying that the outflow from
µi,l the service rate, and 1(Ni,llink i to link j can only be non-zero at time t if there are vehicles at the downstream end of link
i. Note that the outflow depends on the turning probabilities pij , as defined in Equation (7).
DQ
The inflows Qin
i,l are set in Equation (6) and the vehicle counter Ni,l is defined in Equation (8),where tFF
represents the free-flow travel time of link i. Finally, the vehicle density of link i isi
updated at each time step according to Equation (9). Note that the exogenous variables are s,
pij and ρmax , and µi,l . The latter depend on the signal plans that are being optimized.

3NUMERICAL RESULTS

We implement a synthetic toy network consisting of 20 single-lane and 4 intersections, as depicted
in Figure 1 (Osorio & Yamani, 2017). The travel demand, shown in Table 1, is defined such thatvehicles only have straight paths. We optimize the signal plans for a 1-hour period, with a 15minute warm-up period. As such, the objective function is the expected travel time of vehicles
that end their trips in the last 30 minutes. The minimum green times are set to 4 seconds.
The performance of our Dynamic BO is benchmarked against: (i) Vanilla BO, using noproblem-specific prior information; and (ii) Stationary BO, using the stationary traffic modelin Tay & Osorio (2021). Scenarios are constructed by varying: (i) the level of demand, as apercentage of the demand in Table 1; and (ii) the number of time intervals. Each BO method
is run 3 times for 3 different initial sets, each containing 4 randomly-drawn initial points tofit the GP posteriors. We compute the objective function estimate by taking the mean of 4
simulations, with 2 additional simulations of the best solution at the end of each iteration. EachBO run considers 26 optimization iterations. The relative expected optimization performancesof the BO methods are shown in Table 2. Each t-test considers whether Dynamic BO performs
better than Vanilla/Stationary BO for a given level of demand and number of time intervals.
The null hypothesis assumes that Dynamic BO obtained a mean performance that is worse thanor equal to the mean performance of Vanilla/Stationary BO. The t-tests with t-statistics smaller
TRISTAN XI Symposium

Original abstract submittal

T. Tay, C. Bongiovanni, and C. Osorio

4Table 2 – One-sided paired t-test results
Demand25%
50%75%100%
125%

Dynamic BO vs. Vanilla BO
L=2
L=4
t-statp-valuet-statp-value-1.107
0.150
0.391
0.647
-0.6220.276-0.5970.283-1.445
0.0933-0.408
0.347
0.468
0.674
-1.6950.0642-2.1000.03450.121
0.547(a) D=25%, L = 4(d) D=100%, L = 4

Dynamic BO vs. Stationary BO
L=2
L=4t-statp-valuet-statp-value-1.5490.0800 -1.593
0.07490.03840.515-4.0781.77e-3
0.04120.516-4.082
1.76e-3-0.5410.302-2.7260.0130-0.581
0.289-4.8156.65e-4(b) D=50%, L = 4(c) D=75%, L = 4(e) D=125%, L = 4

Figure 2 – Evolution of the expected objective function value
than the critical value (-1.397) have their null hypotheses rejected, and are displayed in bold inTable 2. Note that, for L = 4, Dynamic BO is always better than Stationary BO on all demandlevels. Figure 2 shows the evolution of the best objective function value during the search. Notethat Dynamic BO is able to: (i) find good-quality solutions within a few iterations, and (ii) findhigher-quality solutions than Vanilla/Stationary BO by the end of the search.
The proposed strategy is currently being tested on a large-scale case study consisting of 698
roads, 2756 lanes, and 444 intersections. We expect to see more benefits to employing Dynamic
BO on this more complex network. Additional results obtained by the time of the conference
will be included in the presentation.

References
Jones, Donald R, Schonlau, Matthias, & Welch, William J. 1998. Efficient global optimization of expensive
black-box functions. Journal of Global Optimization, 13(4), 455–492.
Little, John DC. 2011. OR FORUM—Little’s Law as viewed on its 50th anniversary. Operations research,59(3), 536–549.
Osorio, Carolina, & Bierlaire, Michel. 2013. A simulation-based optimization framework for urban transportation problems. Operations Research, 61(6), 1333–1345.
Osorio, Carolina, & Yamani, Jana. 2017. Analytical and Scalable Analysis of Transient Tandem Markovian Finite Capacity Queueing Networks. Transportation Science, 51(3), 823–840.
Tay, Timothy, & Osorio, Carolina. 2021. Bayesian Optimization Techniques for High-dimensional Transportation Problems. Working paper.
Treiber, Martin, & Kesting, Arne. 2013. Traffic Flow Dynamics: Data, Models and Simulation. Heidelberg: Springer, Berlin. Chap. 8, pages 81–126.

TRISTAN XI Symposium

Original abstract submittal