key: cord-0591249-ogvvimm5
authors: Guillot, Matthieu; Aghezzaf, El-Houssaine; Faouzi, Nour-Eddin El; Furno, Angelo
title: Optimal Subgraph on Disturbed Network
date: 2021-05-06
journal: nan
DOI: nan
sha: 6da778dad7481e5e543d4a0049bb032c57b15e0c
doc_id: 591249
cord_uid: ogvvimm5

During the pandemic of COVID-19, the demand of the transportation systems are drastically changed both qualitatively and quantitatively and the network has become obsolete. In this article, we study the problem of finding an optimal subnetwork that guarantee that (i) the minimal access time from any node of the urban network to the new network is not {em too large} compared to the original transportation network; (ii) for any itinerary, the delay caused by the deletion of nodes of the transportation network is not {em too big}; and (iii) the number of nodes of the transportation network has been reduced at least by a known factor. A solution is optimal if it induces a minimal global delay. We model this problem as a Mixed Integer Linear Program before applying the model on a real-case application on the Lyon's buses transportation network.

Public transportation networks in large urban areas are supporting a very large number of passengers everyday. Problems arise on a daily basis, causing more or less disruptions depending on the seriousness of the events. In most cases, the consequences are local (delays of public transportation passages, local traffic jams, etc...). Thus, even if the locality of the disturbance can be relatively large and cause significant delays, the control techniques make possible to restore a fluid state of the network at the end of the day. However, the current global pandemic linked to COVID-19 reminds us that in extreme cases, everyone's habits can be changed drastically [10] . In particular, the parameters defining urban transportation networks have been completely turned upside down [9] . On the one hand, during lockdown, the users of the network adopt completely different habits: some no longer use it (total or partial telework) and some would rather use individual types of transportation more that than collective ones. Thus, the demand linked to the transportation network has drastically changed both qualitatively and quantitatively [4] . On the other hand, the offer has also been modified. The demand's change and the right of withdrawal of the agents are part of the offer's change [12] . All the pre-existing forecasts (transit times and frequencies, start and end times of service, connections, etc.) have become obsolete. Obviously, all these modifications were experienced in practice during the lockdown that occurred following the progression of the pandemic COVID-19, but one can easily imagine that in the next decades or even the next years, other events will tend to disrupt if not all urban networks but at least part of them.

In this article, we consider an urban zone and two kinds of networks on it: a urban network (UN) which represent a grid of the urban areas and a public transportation network (PTN) which represent the current existing buses network of the corresponding urban areas. We assume that we know the traveling time on the transportation network: the minimal time between any pair of nodes of PTN, and all the access times between any node of the urban network and any node of the transportation network. We also assume that we know the modified demand, that we assume to be lower than usually (which is the case during the current pandemic). A solution to our problem is a subnetwork of the transportation network that guarantee that: (i) the minimal access time from any node of the urban network to the new network is not too large compared to the original transportation network; (ii) for any itinerary, the delay caused by the deletion of nodes of the transportation network is not too big; and (iii) the number of nodes of the transportation network has been reduced at least by a known factor. A solution is optimal if it induces a minimal global delay.

Several studies of the impact of COVID-19 on public transportation systems have begun to emerge. For the impact on the transit frequency, Gkiotsalitis et al. give a model that provides optimal vehicle redistribution accross metro lines of Washington DC for different scenarios based on different social distances rules [5] . Dakic et al. model and develop an optimization tool to determine the optimal bus frequencies and vehicle allocation to reduce the operating cost of the network. Regarding the sanitary conditions and the contamination exposures, Jia et al. identify the 'key stations' of the railway network of Beijin to avoid in order to limit the risks of contamination for the passengers [6] . With a strategic point of view, Wang et al. study the effective policies for reopening phase. These policies are biased on the work-for-home, the traffic and sanitary conditions, but also on the transit capacity and demand [11] .

Network design is a big issue too, especially in big urban areas. LeBlanc defines the network design to find the optimal frequencies of transit lines [7] . Lee et al. do the same kind of work, but with variable demand [8] . More recently Cipriani, Gori and Petrelli give case study of a resolution of network design problem in the city of Rome, with multimodal properties and complex road network topology [2] . The highlighting of an efficient subgraph has also been studied in transportation applications. Arbex and da Cunha are interested in finding an efficient 1 arXiv:2105.02600v1 [cs.DM] 6 May 2021 subgraph and the corresponding frequency using genetic algorithms. The objective in this article is to optimize both passenger's and operator's costs [1] .

Let P T N = (V, E t ) be an undirected graph representing the Public transportation Network, with |V | = n t nodes and |E t | = m t edges. The nodes V represent the bus stops and the edges E t the possible links between the corresponding bus stops. Let c : E t → R + a cost function over the edges of P T N , which represent the traveling time. We assume that we know the matrix P C ∈ R + nt×nt of the shortest paths in P T N , which means that

is the traveling time of the shortest path between v 1 and v 2 for each v 1 , v 2 ∈ V . Figure 1 is an example for six bus stops. Let U N = (U ∪ V, E u ) be a complete bipartite graph representing the Urban Network. The set of nodes U are the n u = |U | centroids of urban areas, which represent the possible origins and destinations of the demand. E u represent the possible links between the urban areas and the bus stops. As U N is complete, the users are theoretically able to walk to any bus stop. Let d : U × V → R + be the access time: d(u, v) represent the average time that the users have to walk to go from the urban area u ∈ U to the bus stop v ∈ V . For any u ∈ U , we denote by d acc (u) = min v∈V d(u, v), and by acc(u) = argmin v∈V d(u, v). Let OD ∈ Z + nu×nu the origin/destination matrix: OD[u 1 ][u 2 ] is the number of users who wish to go from urban area u 1 ∈ U to u 2 ∈ U . • p elim ∈ [0, 1] is the minimum percentage of the bus stop that has to be deleted • 1 < α ∈ R + is the admissible increase factor of the delay in the new network we want to design for each pair origin/destination

is the admissible increase factor for the access time of u ∈ U A solution of our problem is a subset V sol of V . For a solution V sol ⊆ V and an origin/destination (u 1 , u 2 ) ∈ U , the optimal travel time from u 1 to u 2 is defined as:

We also define the total weighted traveling time of a solution V sol as

In particular, in the original network PTN, the optimal traveling time between u 1 and u 2 is

and the total weighted traveling time of PTN is Assumption We assume that the delay due to the deletion of bus stops is caused by the difference of access time, and not by the difference of shortest path in the bus network. Thus, we have:

Note that with this assumption, we have

This assumption is quite strong, because we omit the difference of travel time between the original network and the choice induced by V sol . However, this simplification is realistic as most people would accept an increase of the travel time but not of the access time. Moreover, it will imply a very interesting computational benefit.

We want our solution V sol to have some properties A) the access time increase from u ∈ U induced by the choice of V sol must not increase more than by a factor k[u]

B) the delay induced by the choice of V sol must not increase more than by a factor α C) the percentage of deletion of V sol has to be at least p elim More formally, we want V sol to satisfy:

A solution V sol to our problem is said to be feasible if it satisfies the constraints above. Let us call V F the the set of all feasible solutions. As there is a finite number of bus stops, we know that |V F | is finite too. Our goal is to find a solution that minimizes the total weighted traveling time. So V * sol is said to be optimal if it verifies

The optimal subgraph on disturbed network problem (OSDNP for short) is the problem which consists of finding such a solution.

In order to find a formulation for our problem, as we want to minimize the total weighted traveling time under certain constraints, it is quite natural to consider in a first place mathematical programming, and especially linear programming.

We also define M as a upper bound on the d(u, v).

Let us consider the mathematical program (P ):

x ∈ Z + n t d x acc ∈ R + nu Let us call PF the set of feasible solutions of (P ).

Proof As the objective function, and the constraints (1), (3) and (4) are linear with regards to the decision variables, the only thing to show is the linearity of constraints (2) .

Let us take one particularû ∈ U . We will prove that the constraint d x acc (û) = min Let us define the following linear constraints:

The last constraint induces that only one variable yv * is equal to 1, and the other ones are equal to 0. The first set of constraint induces that d x acc (û) ≤ min The same method can be applied for all u ∈ U , which proves the proposition.

Theorem The two following propositions hold:

i) There is a one-to-one correspondence between the feasible solutions of (P ) and the feasible solutions of the OSDNP;

ii) There is a one-to-one correspondence between the optimal solutions of (P ) and the optimal solutions of the OSDNP.

Proof i) Let V sol ∈ VF be a feasible solution of the OSDNP. We define xV sol ∈ Z + n t a 0/1 vector describing whether or not a bus stop is in the solution. More formally, for all v ∈ V :

Note that the decision variables d x acc are entirely set by the definition of x with constraint (2) of (P ). Let us prove that (xV sol , d

x V sol acc ) is a feasible solution of (P ). As V sol ∈ VF , we know by hypothesis that

is not an empty set and constraint (1) is satisfied. From B) and equation 4, and by noticing that d

. Thus constraint (3) is satisfied. From C) we know that the number of 0 in xV sol must be more than p elim nt, so constraint (4) is satisfied. Thus, (xV sol , d

x V sol acc ) satisfies all the constraints of (P ), so it is a feasible solution for (P ). Reciprocally, let x ∈ PF be a feasible solution of (P ). We define

acc by the definition of V sol , the constraints (2), (3) and equation 4 induce that V sol satisfies B). Just like before, constraint (4) and the definition of V sol induce that |V sol | ≤ (1 − p elim )nt, C) is satisfied and (i) is proved.

ii) As there is a one-to-one correspondence between the feasible solutions of (P ) and the feasible solutions of the OSDNP, we just have to prove that the objective functions of both problems are the same. Let x be a feasible solution of (P ) and the corresponding V sol ∈ VF defined just like before. We have

Thus, if V ∈ VF minimizes T W TV , the corresponding x ∈ PF minimizes

ii) is proved, which proves the theorem.

We are now able to find an optimal solution of the OSDNP by finding an optimal solution of (P ). Such a solution can be found using standard MILP solving algorithms. We will now apply the previous results with real data on the urban zone of Lyon, France.

We give a case study of the model we described in the previous section. In this application, we consider the Lyon's urban zone, in France. We consider the bus network, which consists of 1144 bus stops and 1464 urban areas. A map of the corresponding urban zone is represented figure 5 We choose the values of the parameters as follow:

• α = 2

• for all u ∈ U , k[u] = 2

• the origin/destination matrix has been set with real observations of itineraries between the different urban areas • in our application, p elim will take values between 0.1 and 0.6 (for values above 0.6, no feasible solution exist in our case, due to the value of the other parameters)

This choice of parameter seems reasonable for real case application, since the increase of access time and travel time is acceptable for most people with this choice of parameters. 

We use the optimization software CPLEX [3] to solve the MILP on the real instances described above. We represent the solution in figure 6 by representing the deleted bus stops in red while the remaining ones stay in blue.

One interesting thing is the number of deleted bus stops with regards to p elim . We expect the number of deleted bus stops to be exactly equal to p elim nt . Figure 5 .1 shows the number of deleted node with respect to p elim We notice that for p elim = 0.1 and p elim = 0.2, we delete more stops that we are imposed to. This comes from the fact that for low values of p elim the optimal solution does not need that much number of bus stops, because the number of urban areas is limited with regards to the number of bus stops. Increasing the number of urban zones (nu) would solve this side-effect. However, this would also increase the computational time needed to find a solution.

Now that we have solved instances for several values of p elim , we would like to evaluate the impact of such solutions on the network with an operational point of view. For a public transportation network designer, the number of lines is a very important input. The number of buses, the number of bus drivers, the complexity and the number of the transit times are directly linked to it. Consequently, even if we insure a decrease of the number of stops, this does not induce such a decrease (or a decrease at all) of the number of lines. Let us analyze the number of stops that are still open for each line in order to be able to build an operational decision tool. Ideally, we want this percentages to be either close to 0 or close to 1. If it is the case, we can keep the lines which percentage is close to 1 and delete the other lines.

For some lines, the percentage of remaining open stop can drastically change. We give an example of the possible differences for p elim = 0.5 in figure 5 . 2 So the profiles of the lines can be different. We can plot the histogram of the percentages of remaining open stops for every lines that contain more than 10 bus stops, (we keep only such lines not to have too much side-effects). We represent such an histogram for p elim = 0.5 in figure 8 .

First of all, we can see that the ideal case is not reached, since most values are close to the average value. Even if we cannot conclude that the percentage of open stops follows a normal law since the p-value of the Shapiro-Wilk test is p = 0.2072, most values are neither close to 0 nor close to 1.

However, we still want to help the network designers to know which lines to keep and which ones to delete. To do so, we give him some scenarios based on a threshold t ∈ [0, 1]. This threshold represent the percentage above which we will keep the lines.

More formally, let l = {s1, s2, .., s |l| } a line which is a sequence of stops (s1, .., s |l| ∈ V ). For an optimal solution V * sol , we define the percentage of remaining open stops of l as p The strategy here is, for several values of t, to evaluate the sets L t k and L t d . If t is close to 0, then L t k will be close to L, and the percentage of lines deleted will be small, maybe too small for the network designer. If t is close to 1, then L t d will be close to L and the network efficiency will be widely degraded. So we propose different scenarios to the network designer, who will choose one of them with regards to the trade-off between cost and efficiency her prefers.

To build a scenario S, we begin with choose a p elim and we compute an optimal solution V * sol thanks to our model described in section 4. Then we choose t ∈ [0, 1] and compute the corresponding L t k and L t d . We arise with a new solution (which is not feasible in general) VS = V * sol \ L t d , which contains the stops in V * sol , minus the stops of the lines in L t d . On the one hand, we have deleted exactly |L t d | lines from L, which would help the network designer to manage the network. On the other hand, since the solution is no longer feasible (in general), there will be some u ∈ U for which the access time will be too long with regards to our original constraint (constraint (2) of (P )). Let U FS be the set of such u ∈ U . Let us call

is the minimal access time to a bus stop in VS : d V S acc(u) = minv∈V S d(u, v). Then U FS = {u ∈ U |uf (u) < 0}. From a scenario S, we also give the histogram H uf of the uf (u) which can be an interesting input for the network designer. We describe schematically the construction of a scenario S in figure 9 We present 7 scenarios for p elim = 0.5 and t values from 0.1 to 0.7 in figures 10 and 11. In this instance, we have 120 different lines containing more than 10 stops, and the number of urban zones is nu = 1464.

Note that even for t close to 1, not all urban zones are violated because there are still some stops open on bus lines that contain less than 10 stops. Moreover, if we increase the value of t (t = 0.8, t = 0.9..) we obtain the same results than for t = 0.7.

In these scenarios, we see that when t approaches the value of p elim , both |L t d | and |U FS | strongly increase, which is coherent with the fact that the percentage of remaining open stops of the lines are mostly around p elim .

With these scenarios, a network designer can evaluate the different cases and choose the one which is likely to match his 

In this paper we have been interested in the highlighting of a subgraph during disturbed conditions. After defining the problem, we have given a Mixed Integer Linear Program modeling the problem. We have solved the model on a real-case application on the Lyon's urban zone. We have presented the results for a reasonable choice of parameters, and for different values of deletion rate. We also have given a decision tool that could be useful for the network designers to choose his best trade-off between costs and efficiency. The computational running time is a big issue in our article. Indeed, we made some simplifying hypothesis in order to allow the real-case resolution. A more realistic MILP could have been written (and has been), but its resolution were in our case too long for our real-case application. To go further, it could be interesting to dig into more complex resolution algorithms to get rid of simplifying hypothesis and still get results on real instances.

Note that the choice of parameters is a real issue with regards to the computational running time too. Indeed, if we take for instance our parameter k (which describes how far the accession time is allowed to increase), then if k increases, the number of potential bus stops to look into can increase, making the corresponding instances hard to solve in reasonable time.

The guideline of this paper has been to highlight a choice of bus stops in order to choose a subset of lines at the end. However, the choice of such lines induces in the general case a set of unfeasible bus stops according to our MILP formulation. Even if we have been able to evaluate the profile of the unfeasibility, we have no guarantee a priori of the quality of our solution in term of bus lines. This could be a problem in some cases. Another solution could have been to see the problem with a "line" point of view from the beginning, and to define a solution as a subset of lines to keep. However, this could increase drastically the computational complexity. 

Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm

Transit network design: A procedure and an application to a large urban area

V12. 1: User's Manual for CPLEX

Eating habits and lifestyle changes during COVID-19 lockdown: an Italian survey

Optimal frequency setting of metro services in the age of COVID-19 distancing measures

A new global method for identifying urban rail transit key station during COVID-19: A case study of Beijing, China

Transit system network design

Transit network design with variable demand

The impacts of COVID-19 pandemic on public transit demand in the United States

COVID-19 and public transportation: Current assessment, prospects, and research needs

Impact of COVID-19 behavioral inertia on reopening strategies for New York City Transit

Impact of COVID-19 on Public Transit Accessibility and Ridership