System optimum formulation for departure time choice problem
in the generalized bathtub model
J. P. Lebacquea , M. Amelia,∗ and L. Leclercqb
a Université Gustave Eiﬀel, COSYS-GRETTIA, Paris, France

jean-patrick.lebacque@univ-eiﬀel.fr, mostafa.ameli@univ-eiﬀel.fr
b Université Gustave Eiﬀel, Université Lyon, ENTPE, LICIT, Lyon, Franceludovic.leclercq@univ-eiﬀel.fr∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium onTransportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: traﬃc congestion, peak-hour traﬃc dynamics, macroscopic model, social optimum,
generalized bathtub model1

INTRODUCTION

Traﬃc congestion occurs when the traﬃc density increases while the traﬃc ﬂow remains constantor decreases. Macroscopic models aim to rule out urban traﬃc congestion by holding several
assumptions. The common assumption between all macroscopic models is the homogeneity ofthe speed at a single zone with respect to its traﬃc density (i.e., accumulation). Seminal workof Geroliminis & Daganzo (2008) showed that single-unit macroscopic models could represent
the congestion of an urban area independently of the demand. In order to better understand thecongestion, accurate calculation of traﬃc network optimums are crucial. Network operators aimto minimize the sum of all user costs. The solution is called system optimum (SO) (Wardrop,1952). To accurately calculate SO at the macroscopic level, we need to consider the characteristics of trips. In the context of macroscopic models, a given trip has limited attributes. Insimpliﬁed models, e.g., bottleneck models (Li et al., 2020), a trip is only deﬁned by its departuretime and desired arrival time. However, the characteristics of the user trip (path choice) have to
be considered. Macroscopic fundamental diagram (MFD)/bathtub models are able to overcome
this drawback by considering trip-length distribution in addition to departure time and desired
arrival time distributions. Classic bathtub model Vickrey (1991) assumes that time-independent
negative exponential distribution represents the remaining trip distance of all trips traveling inthe system. This assumption is cannot represent a real test case based on the empirical studies(cf. e.g. Liu et al. (2012)). Recently, Jin (2020) proposed the generalized bathtub model that
extends the classic bathtub model to capture various distributions of the trip length by introducing a new state variable: the number of active trips at time t with remaining distances greaterthan or equal to threshold x, denoted by K(x, t). He formulates the traﬃc dynamics by four
equivalent partial diﬀerential equations that track the distribution of the remaining trip lengths(Jin, 2020). This study aims to formulate and solve system optimum, also known as social optimum, for departure time choice model based on generalized bathtub model with heterogeneous
trip attributes. In particular, the proposed framework is able to address any distribution fordesired arrival time and trip length.
TRISTAN XI Symposium

Original abstract submittal

J. P. Lebacque, M. Ameli and L. Leclercq

22METHODOLOGYThe notations are collected in table 1. Bathtub models assume that at time t, the velocity(vt ) is the same for all traveling users. vt is a function of the network characteristics and thenetwork load, that is to say, the number of travellers in the network, H(t). Let us deﬁne thecharacteristic travel distance z(t) as the distance traveled by a virtual user up until time t:Z t(1)z(t) :=vs ds.
0Where vt = V (H(t)), and V is assumed bounded from above and below: 0 < Vmin ≤ V ≤Vmax . Since vt > 0 ∀t ∈ T , z is an invertible function. Let z −1 denote the inverse functionof z. Then, we have z −1 z(t) = t and z −1 (x) represents the time at which the virtual user
has reached x. Note that the negative exponential distribution of the trip length transforms
the generalized bathtub model to the classic bathtub model (Jin, 2020). Therefore, the resultsfrom both models will be identical. It is worth mentioning that the assumption of exponential
distribution for the demand proﬁle also transforms other common macroscopic models (e.g.,
MFD or trip-based MFD models) to the simple accumulation model and results in the samesolution (see Lamotte et al. 2018 for the details).
Now, let T (tid , xi ) denote the travel time of a player departing at time tid with trip length xi .
Considering (1), T (tid , xi ) can be determined by,
T (tid , xi ) = z −1 xi + z(tid ) − tid .
(2)
In assignment problems, the travel cost is usually deﬁned based on α-β-γ scheduling preferences (Fosgerau, 2015). That means the cost function is deﬁned as the sum of the travel timeand a penalty cost for arriving at tid + T (tid , xi ) instead of the desired arrival time. Speciﬁcally,
we assume that each player’s cost function is given by,−iiiiiiiiiiiJi (tid , tia ; t−i(3)d , x ) = αT (td , x ) + β ta − td − T (td , x ) + + γ td + T (td , x ) − ta + ,where α denotes the cost of traveling per unit of time, β and γ denote, respectively, the costof earliness and lateness for the traveller arrival. We assume that the penalty for travel time ishigher than the penalty for early arrival time, i.e., α > β. Note that (y)+ = max{y, 0} as well
−i respectively express the dependency of J on the departure times and trip lengthst−id and xof the other users (̸= i) via their travel times.
The cost function deﬁned in (3) captures the fact that travellers prefer not to deviate fromtheir desired arrival time (i.e., arrive as close as possible to their desired arrival time) while theyTABLE 1 – List of notations
Tix
ta
K(x, t)
H(t)
v(t)
z(t)
T (tid , xi , t)m(ta , x)h(x)f (ta , x, t)Time horizon.
Index of trips, i ∈ N .
Vector of trip lengths.
Vector of desired arrival times.
Number of agents at time t with remaining trip distance greater than x.
:= K(0, t). Number of agents at time t in the network.
= V (H(t). Common velocity of agents at time t.
Characteristic travel distance.
Travel time of a trip started at tid with trip length xi at time t.
distributions of demand with trip length x and desired arrival time ta .
distributions of initial agents with trip length x.
distributions of departure times t with desired arrival time ta and trip
length x. This is the unknown of the problem.

TRISTAN XI Symposium

Original abstract submittal

J. P. Lebacque, M. Ameli and L. Leclercq

3

do not spend too much time on the traﬃc. Note that the dependency of the cost function on
the trip lengths are not emphasized in the notation, while it holds implicitly.
Let us now complete the description of the bathtub model. The data is given by the distribution of travel demand m(ta , x)dta dx wrt desired arrival time ta ∈ Xa and trip length x ∈ X .
The unknown in the SO problem is the distributions of departure times t ∈ T with desired
arrival time ta ∈ Ta and trip length x ∈ X . The resulting distribution of traveller demand isdenoted as f (ta , x, t)dta dxdt. Thus f satisﬁes to the following convex set of constraints (K):RT f (ta , x, t)dt = m(ta , x)(K)(4)
f (ta , x, t) ≥ 0
The dynamics of the bathtub system result from the following processes: i) travellers are conserved, ii) travellers travel at speed vt = V (H(t)), iii) travellers exit the system when they
have travelled the trip length x (thus yielding the outﬂow of the system), iv) the travel demand f (ta , x, t) yields the inﬂow into the system. The distribution of initial agents with trip
length x provides the initial condition of the system. z(t) and H(t) constitute the main dynamicvariables. The following set of equations describes the dynamics of the system:
Rtz(t) := 0 dtV (H(t))
(5.1)
Rt(5)
H(t) = h(z(t))
+dsF̄
(z(t)
−z(s),s)(5.2)
0RF̄ (x, t) = Ta dta f (ta , x, t)(5.3)
It can be shown (refer to Ameli et al. (2021a)) that (5) admits a unique solution in z and H
which depends continuously on the data and initial conditions, given some regularity conditions
on the data m.
The objective of the SO problem is to optimize the total travel cost of travellers. Thus theobjective, denoted as J , can be viewed as the sum over all travellers (i) of Ji given by (3), andthe Ji s must be calculated using (5). Thus J is given bydef R

J =Ta ×X ×T dta dx dt f (ta , x, t)J(ta , x, t)J(ta , x, t) = αT (t, x) + β ta − t − T (t, x) + + γ t + T (t, x) − ta + (6.1)
T (t, x) = z −1 (x + z(t) − t)
(6.2)z(.) solution of (5)
(6.3)

(6)

Actually J is a function of ta , x, t through z which itself is a function of f, h through (5). Thus
we can also denote J as J(f, h). It can be shown that J is weakly continuous wrt f , choosing
as a functional setting for f either the space of bounded positive ﬁnite measures, or the spaceof square integrable functions L2 (Ta × X × T ). For applications and numerical approximations
we shall opt for the latter functional space. Noteof J given in (6) we also that in the deﬁnitioncould substitute the block β ta − t − T (t, x) + + γ t + T (t, x) − ta + with any other suitable
convex function L. Thus the SO problem can be stated as:
Zmin J =dta dx dt f J(f, h)
(7)
f ∈K

Ta ×X ×Twith J(f, h) being calculated from (5) by (6.2) ,(6.3). By a Weierstrass-type argument, it isshown that (7) admits a solution (not necessarily unique) in any of the two functional spaces
mentioned above. A solution in the measure space should have a better criterion value but
exhibit less regularity than a solution in the L2 -space.
It can be shown that in the space L2 (Ta × X × T ), J admits a gradient. Further, theprojector on the convex set K is well-deﬁned and easy to calculate. These two facts open theway for ﬁnding numerical solutions of (7). Several discretization methods are available, based
either on a particle discretization or on a cell discretization of (5), which is then used for thenumerical approximation of (7).
TRISTAN XI Symposium

Original abstract submittal

J. P. Lebacque, M. Ameli and L. Leclercq

34PRELIMINARY RESULTS AND DISCUSSION

The numerical example illustrated by Figure 1 was calculated based on a cell discretization(discrete values of ta , cells for x and t values). The desired arrival time takes 7 discrete values(starting 7.30 am, separated by half-an-hour). For this relatively small-sized example, convergence is achieved after some 25 iterations and ﬁnds the optimal. Convergence depends on
network characteristics level of congestion.

Demand f818

Demand m
1917

409
233

959
14.50

116
7.25

Departure time0
7.0

Trip length
8.5
Desired arrival time

10.0

0.00

0
0.00

0
7.25
Trip length

14.50

FIGURE 1 – Example of calculation based on continuous approximation of the Lyon data
(Ameli et al., 2021b). The resolution is imposed by the original data. On the left: the demandm. On the right: the density of departure times f for a single arrival time (9 am).
The SO distribution of the departure time for the trips with the desired arrival time of 9
am is shown in Figure 1. The results show that the solution for the SO does not follow any
sorting pattern, e.g., FIFO and LIFO. In order to investigate further the sorting pattern andthe solution characteristic, we are currently running simulations on a real scenario (Ameli et al.,2021b) for the large-scale network of Lyon North (representing the morning peak hours with62,450 trips) with trip-based dynamic implementation, and the results are consistence with thecontinuous test case.

References
Ameli, Mostafa, Faradonbeh, Mohamad Sadegh Shirani, Lebacque, Jean-Patrick, Abouee-Mehrizi, Hossein, & Leclercq, Ludovic. 2021a. Departure Time Choice Models in Congested Transportation Systems
Based on Mean Field Games. arXiv preprint arXiv:2101.02238.
Ameli, Mostafa, Alisoltani, Negin, & Leclercq, Ludovic. 2021b. Lyon North realistic trip data set during
the morning peak.
Fosgerau, Mogens. 2015. Congestion in the bathtub. Economics of Transportation, 4(4), 241–255.
Geroliminis, Nikolas, & Daganzo, Carlos F. 2008. Existence of urban-scale macroscopic fundamental
diagrams: Some experimental ﬁndings. Transportation Research Part B, 42(9), 759–770.
Jin, Wen-Long. 2020. Generalized bathtub model of network trip ﬂows. Transportation Research Part B:
Methodological, 136, 138–157.
Lamotte, Raphaël, Murashkin, Mikhail, Kouvelas, Anastasios, & Geroliminis, Nikolas. 2018. Dynamic
modeling of trip completion rate in urban areas with mfd representations. Pages 18–06192 of: 2018
TRB Annual Meeting Online. Transportation Research Board.
Li, Zhi-Chun, Huang, Hai-Jun, & Yang, Hai. 2020. Fifty years of the bottleneck model: A bibliometric
review and future research directions. Transportation Research Part B: Methodological, 139, 311–342.
Liu, Yu, Kang, Chaogui, Gao, Song, Xiao, Yu, & Tian, Yuan. 2012. Understanding intra-urban trip
patterns from taxi trajectory data. Journal of geographical systems, 14(4), 463–483.
Vickrey, WS. 1991. Congestion in Manhattan in relation to marginal cost pricing. Memo, Columbia
University. Notational Glossary.
Wardrop, John Glen. 1952. ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFICRESEARCH. Proceedings of the institution of civil engineers, 1(3), 325–362.

TRISTAN XI Symposium

Original abstract submittal