Optimal downsizing of the bus network in Lyon during the
COVID-19 pandemic
M. Guillota , A. Furnoa , E-H. Aghezzafb,c and N-E. El Faouzia
a Univ. Gustave Eiffel, Univ. Lyon, ENTPE, LICIT,

F-69518, Lyon, France.
matthieu.guillot@univ-eiffel.fr
angelo.furno@univ-eiffel.fr
nour-eddin.elfaouzi@univ-eiffel.fr
b Department of Industrial Systems Engineering and Product Design
Faculty of Engineering and Architecture, Ghent University, Belgium
c Industrial Systems Engineering (ISyE), Flanders Make.
elhoussaine.aghezzaf@ugent.beExtended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

April 11, 2022
Keywords: (Network Downsizing, Discrete optimization, Decreasing demand, Linear Programming, Case study)

1

INTRODUCTION

The COVID-19 pandemic has impacted drastically the transportation networks in general, andthe transit demand in particular. The demand has changed both quantitatively, since the total
number of network users has decreased, and qualitatively, as some people feel more secure inprivate rather than public transport (see Tirachini & Cats (2020), Di Renzo et al. (2020) andSNCF Réseau (2021)). In this extreme case, network redesign techniques are not flexible enoughto rapidly cope with such possible changes of the demand, and transit timetabling or scheduling
can be adapted only to small variations of the demand. Consequently, the transportation networks are not capable of following such dynamic variations of offer and demand, and need to beresized dynamically in order to match the new lower demand while offering a guarantee of service
quality. When such a modification of the demand occurs, what can transport operators do inorder to make the supply match the demand? We propose a novel approach that joins topologicalmodifications of the network (see Guihaire & Hao (2008) and Ukkusuri & Patil (2009)) to theflexibility of re-planning techniques (see D’Acierno et al. (2014)). Transit network design is avery widely studied research field, as widely discussed in the work of Barra et al. (2007) and theseminal work of Newell (1979)
Our approach considers a urban area (segmented in multiple zones) with a public bus transportation network that traverses the latter. We assume that the reduced demand is known.
Our objective is to identify a sub-network (in terms of bus stops) of the original bus transport
network that guarantees that: (i) the size (in term of bus stops) of the sub-network is reduced bya known preset factor pelim ; (ii) the access time between all urban zones and their closest nodeof the sub-network is not increased by more than a known preset factor k; (iii) for all possible
pairs of origin/destination, the traveling time on the sub-network is not increased by more thana known preset factor α. We highlight that the previous constraints operate in two opposite
TRISTAN XI Symposium

Original abstract submittal

M. Guillot, A. Furno, E-H. Aghezzaf and N-E. El Faouzi

2Figure 1 – Map of Lyon’s urban area
Notation
Vnt = |V |SP (v1 , v2 )Unu = |U |d(u, v)
dacc (u)acc(u)
OD(u1 , u2 )
pelim
αk(u)
Vsol ⊆ V

Description
Set of bus nodes available in the analyzed urban area
Number of bus nodes
Traveling time of the shortest path between v1 ∈ V and v2 ∈ V
Set of urban zone’s centroids
Number of urban zones
Access time between u ∈ U and v ∈ V
Minimum access time from u ∈ U to the public transport network
Closest bus stop from u ∈ U
Demand from u1 ∈ U to u2 ∈ U
Minimum ratio of bus node to exclude
Admissible increase factor of the delay
Admissible increase factor of the the access time of u ∈ U
Subset of V which represents a solution

ways. On the one hand, the size of the network shall be reduced. On the other hand, both theaccess time and travel time over the reduced network shall not deteriorate significantly.
Therefore, a sub-network is considered to be optimal if it induces a minimal global delay,
weighted by the reduced demand. Finding such an optimal sub-network is the problem we areinterested in. In this paper, we propose a general MILP (Mixed Integer Linear Program) solving
the problem above, that we apply on the real case of Lyon’s urban area (France) with the public
bus network (see Figure 1).

2

MIXED-INTEGER LINEAR FORMULATION

We divide the urban area of Lyon into 1, 464 zones that approximately contain the same numberof inhabitants. We assume that we know the access time between the centroids of each urban zone
and its closest node of the bus network. We also assume that we know the modified reduced
demand that we model as an origin/destination matrix as well as the traveling time of theshortest path between any origin and any destination on the bus network. The possible origins
and destinations of the demand are the centroids of the urban zones of U . Let us introduce somenotations before defining the MILP.
For the topology of the network, we use the data of the transit network of Lyon (TCL) (seeDinsic (2021)). This database contains 1144 geographic positions of all the bus stops. The roadsegments and intersections are retrieved from Open Street Map, which is a collaborative projectthat maps the topology of the roads all around the world. The cost c of the edges corresponds
to the length of these roads. Consequently, the matrix SP of the shortest paths between all
TRISTAN XI Symposium

Original abstract submittal

M. Guillot, A. Furno, E-H. Aghezzaf and N-E. El Faouzi

3pairs of bus stops is computed from these real distances. For the urban zones, we have taken theIRIS zones defined by the French institute of statistics and economic studies (INSEE). We divide
the IRIS zones into smaller ones, and compute the centroids of these zones. The access time dbetween the bus nodes and the centroids of the urban zones is the haversine distance between
the corresponding geographic points.
Let us define, for all u ∈ V and all k ∈ R+ nu , Duk = {v ∈ V |d(u, v) ≤ k(u)dacc (u)}. We also
define M as an upper bound on the d(u, v).
Let us consider the mathematical program (P ), with the decision variables x and dxacc (u).
The decision variables x represent the characteristic vector of a sub-network Vsol : x(v) = 1 ifv ∈ Vsol and x(v) = 0 otherwise. For each u ∈ U , dxacc (u) represents the access time from u tothe closest node of V that remains in the subnetwork: dxacc (u) = minv′ ∈v,x(v′ )=1 d( u, v).

minPOD(u1 , u2 )(dxacc (u1 ) + dxacc (u2 ))(u1 ,u2 )∈Us.t.

Px(v)kv∈Dudxacc (u)xxdPacc (u1 ) + dacc (u2 ) + SP (acc(u1 ), acc(u2 ))x(v)≥=1∀u ∈ Umin d(u, v) + (1 − x(v))M∀u ∈ Ukv∈Du≤≤α(dacc (u1 ) + dacc (u2 ) + SP (acc(u1 ), acc(u2 )))(1 − pelim )nt

∈∈

Z+ nt
R+ nu

∀(u1 , u2 ) ∈ Uv∈Vxdxacc

First of all, one can prove that (P ) can be written as a MILP, because the minimum function inconstraints (2) can be linearized. We give the following interpretation of constraints. Constraint(1) ensures that from any urban zone u, the access time to the closest node of the sub-network
does not exceed k(u), i.e. there is at least one node in the bus network at distance lower thank(u)dacc (u). Indeed, from u ∈ U , Duk are the bus stops that are accessible in an acceptable
time w.r.t the pre-defined requirements. Constraint (2) defines dxacc (u) as the new access timefrom u to its closest node of the sub-network. These decision variables are entirely defined by xsince we have equality constraints. Constraint (3) ensures that any itinerary’s travel time does
not increase more than by a factor α. Constraint (4) ensures that the elimination ratio of bus
nodes is at least pelim . Finally, we conclude that the optimal solution of (P ) are the optimal
sub-networks according to our criteria defined in the first section.

3CASE STUDY IN LYON’S URBAN AREA

We choose the parameter’s values as follows: α = 2, meaning that for each trip, the travelingtime one the reduced network can not exceed twice the original one. For all u ∈ U , k(u) = 2,
meaning that for each urban zone, the access time to the network cannot exceed twice the originalone. In our application, pelim takes values between 0.1 and 0.6, meaning that we ensure to delete
between 10% and 60% of the bus stops.
This choice of parameters is a reasonable one for our real case-study, since the increase ofaccess time is acceptable for most people (especially for the lower access times). Note that if theincrease of access time or travel time is reduced, then some high values of pelim would make theproblem unfeasible.
We use the optimization software CPLEX to solve the MILP on the real instances describedabove. We represent the solution in Figure 2 by representing the deleted bus stops in red while
the remaining ones stay in blue.
TRISTAN XI Symposium

Original abstract submittal

(1)
(2)
2

(3)
(4)

M. Guillot, A. Furno, E-H. Aghezzaf and N-E. El Faouzi

4Figure 2 – Map of remaining open stops in blue, and deleted stops in red for different values ofpelim .
The optimal sub-networks we found with different values of pelim can act as an interesting
raw material for further optimizations with other criteria. It can be useful, for instance, todecrease the number of lines in the network. One can decide of a threshold t, and close all thelines for which the percentage of remaining open stops is lower than t. This would provide thenetwork designers with a decision tool that can help them evaluate which lines to keep open andwhich ones to close. One can also completely redesign the lines from the optimal sub-network.
In both cases, the goal is to end up with a number of lines lower than before, inducing a lower
operational cost without significantly degrading the level of service.
The optimal sub-network in terms of bus stops can also be useful to change the service
frequency on the most impacted lines. If a bus line has many stops closed, then the frequency on
this line can be increased in order to match the increasing demand on the remaining open stops.
As a final remark, note that the evaluation of the delay are here static, but we are currently working on a dynamic way to evaluate a solution, taking into account the dynamic trafficconditions. We would be pleased to present these updated results during the conference.

4REFERENCES

References
Barra, Alexandre, Carvalho, Luis, Teypaz, Nicolas, Cung, Van-Dat, & Balassiano, Ronaldo. 2007. Solving
the transit network design problem with constraint programming. In: 11th World Conference inTransport Research-WCTR 2007.
Di Renzo, Laura, Gualtieri, Paola, Pivari, Francesca, Soldati, Laura, Attinà, Alda, Cinelli, Giulia, Leggeri,Claudia, Caparello, Giovanna, Barrea, Luigi, Scerbo, Francesco, et al. 2020. Eating habits and lifestylechanges during COVID-19 lockdown: an Italian survey. Journal of translational medicine, 18, 1–15.
Dinsic. 2021. Réseau urbain TCL SYTRAL.
D’Acierno, L, Gallo, M, Biggiero, L, & Montella, B. 2014. Replanning public transport services in thecase of budget reductions. WIT transaction on the Built Environment, 138, 77–88.
Guihaire, Valérie, & Hao, Jin-Kao. 2008. Transit network design and scheduling: A global review.
Transportation Research Part A: Policy and Practice, 42(10), 1251–1273.
Newell, Gordon F. 1979. Some issues relating to the optimal design of bus routes. Transportation Science,13(1), 20–35.
SNCF Réseau. 2021. Analyse comparée du trafic francilien et international pendant la crise de la Covid-19.
Tirachini, Alejandro, & Cats, Oded. 2020. COVID-19 and public transportation: Current assessment,prospects, and research needs. Journal of Public Transportation, 22(1), 1–21.
Ukkusuri, Satish V, & Patil, Gopal. 2009. Multi-period transportation network design under demand
uncertainty. Transportation Research Part B: Methodological, 43(6), 625–642.

TRISTAN XI Symposium

Original abstract submittal