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

Abstract

Public transport is one of the most disrupted sectors of the COVID-19 pandemic with reported ridership drops up to 90% in majorly affected countries. As many government authorities strive to partially resume activities, public transport operators are in an urgent need for models that can evaluate the impact of different social distancing policies on operational and passenger-related costs. In this study, we introduce a mixed-integer quadratic programming model for the redesign of public transport services considering the operational, passenger, and revenue loss-related costs by evaluating the effects of different social distancing policies. Our model is applied at the metro network of Washington DC and provides optimal redistribution of vehicles across lines for different social distancing scenarios. This model can be used as a decision support tool by other policymakers and public transport operators that are in need of evaluating the costs related to the implementation of different social distancing policies.

Keywords:

• Public transport
• metro
• social distancing
• COVID-19
• operational costs
• revenue losses

1. Introduction

The spread of COVID-19 has forced public authorities to implement strict distancing measures in closed spaces, such as schools, shops, working places, and public transport. The COVID-19 epidemic was first reported to the World Health Organization (WHO) on 31 December 2019 and it was recognized as a pandemic on 11 March 2020 (WHO 2020). Public transport is one of the most disrupted sectors of the COVID-19 pandemic with early estimates suggesting that the drop has been as much as 80–90% in major cities in China, Iran and the US, and as much as 70% for some operators in the UK (UITP 2020).

Several public transport operators have reduced their service span (e.g. have canceled night services), have reduced service frequencies, and have closed selected public transport stations (Tirachini and Cats 2020; Gkiotsalitis and Cats 2020). For example, Transport for London (TfL) has suspended the night tube service and closed 40 metro stations that do not interchange with other lines (TfL 2020). Similarly, the Washington Metropolitan Area Transit Authority (WMATA) closed 19 metro stations out of 91 and requested all passengers to wear a cloth face-covering (WMATA 2020b). In addition, it has reduced the service frequencies from 10 trains per hour to 3 or 4 trains per hour during peak hours and has imposed early rail closures at 9pm (WMATA 2020a).

Government authorities propose social distancing rules ranging from 1- to 2-m distancing in closed spaces because large droplets do not travel further than 2 m (Bahl et al. 2020; Jarvis et al. 2020). Consequently, public transport service providers have to re-design their services while considering the local distancing regulations. This calls for the development of novel methods for managing the limited capacity available and allocating resources accordingly so as to minimize the ramifications of the newly imposed constraints driven by public health considerations.

The limited capacity implied by the corona-related distancing measures requires the reallocation of public transport resources so as to cater most efficiently and effectively for the prevailing demand patterns while maintaining the functionality of the public transport system. Notwithstanding this, even when all available resources (vehicles, drivers) are deployed, it is expected that not all passenger demand can be absorbed along the busiest service segments. Determining the optimal reallocation of service resources, which also implies the determination of which demand segments may not be satisfied, is not trivial. Most public transport networks are denser in their high-demand core and become thinner as they branch out. During peak periods, passenger load levels in the core of the network are often such that it is not possible to safely transport all passengers. Moreover, passengers boarding at the edges of the central area may not be able to board as the occupancy level is already approaching the new corona-era capacity standard, leaving many stranded passengers. Should one cater for the long-distance low-volume travel from the branches to the core and vice-versa or for the short-distance high-volume demand within the network core?

Existing public transport network design (Mandl 1980; Ceder and Wilson 1986; Pattnaik, Mohan, and Tom 1998; Borndörfer, Grötschel, and Pfetsch 2007; Szeto and Wu 2011; Ul Abedin et al. 2018) and frequency setting (Gkiotsalitis and Cats 2018; Sun and Szeto 2019; Gkiotsalitis, Wu, and Cats 2019) methods cannot answer the above-mentioned research question because they consider only the trade-off between operational costs (e.g. running costs, in-vehicle occupancy levels) and passenger-related costs (e.g.waiting times at stations, total trip travel times). Thus, these models do not account for the implications of the implementation of social distancing measures and cannot, therefore, support public transport service providers in the planning of their services in the era of COVID-19.

To this end, we develop a method that supports the re-design of mass transit services in the context of complying with COVID-19 distancing measures. More specifically, we formulate and solve a network-wide model that can set the optimal frequencies of services lines under different social distancing scenarios. The proposed model extends on the classic trade-off between operational-related and passenger-related costs by considering the revenue losses associated with the unaccommodated passenger demand when complying with the distancing measures. Our network-wide frequency setting model can be used by public transport operators that seek to re-design their services under different distancing scenarios and investigate their performance in terms of passenger waiting time costs, operational costs, in-vehicle occupancy levels, violations of distancing standards, and revenue losses due to denied boarding. In this study, our objective is to develop a frequency planning model that can be applied when the passenger demand has almost returned to its pre-pandemic levels yet public transport operators need to comply with the social distancing regulations to avoid the spreading of the virus.

The remainder of this study is structured as follows: in Section 2 we review frequency setting models and introduce the well-established model of Furth and Wilson (1981) which is adopted and adapted in this study. Section 3 presents our network-wide frequency setting model that considers the impacts of distancing measures. Our model is formulated as a mixed-integer nonlinear program (MINLP) and it is reformulated to an easier-to-solve mixed-integer quadratic program (MIQP) that can be applied to different case studies. In our case study (Section 4), we apply our model to compute the optimal service frequencies of the Washington DC metro lines under different distancing policies (no distancing, 1-m distancing, 1.5-m distancing, 2-m distancing). In addition, we investigate the impact of different distancing policies on operational costs, passenger-related costs, vehicle occupancy levels, and revenue losses due to denied boarding. This is instrumental for public transport service providers that need to plan their operations while taking into consideration public health risks and the operational/passenger-related costs, as elaborated in our discussion (Section 5).

2. Literature review and baseline frequency setting model

In this study, we propose a frequency setting model for planning the frequencies of service lines under the pandemic-imposed capacity limitations. The setting of service frequencies is performed at the tactical planning stage and it is followed by the timetabling (Cao and Ceder 2019; Su et al. 2019) and the operational control stages that might include short-turning (Tirachini, Cortés, and Jara-Díaz 2011), stop-skipping (Gkiotsalitis 2021), vehicle insertion or bus holding options (Gkiotsalitis 2020a; Gkiotsalitis and Van Berkum 2020; Gkiotsalitis 2020b). These additional operational control options are described in the literature review paper of Gkiotsalitis and Cats (2021). Frequency setting models determine the allocation of the available fleet to different line services by considering the trade-off between productivity and operational costs (Ibarra-Rojas et al. 2015). Earlier works were limited to determining the frequency of a single line at a time (Furth and Wilson 1981; Ceder 1984, 2002). Ceder (1984) proposed closed-form expressions that do not need to solve complex mathematical programs when determining the frequency of a single line (namely, the maximum load and the load profile methods).

In the last decade, a series of models have been proposed for setting service frequencies network-wide by determining the optimal resource allocation subject to limited resources. Yu, Yang, and Yao (2010) proposed a bi-level programming model for the frequency setting problem which determines the optimal frequencies by minimizing the total travel time of passengers subject to overall fleet size limitations. The optimal frequency setting and allocation of a mixed-fleet was considered by Cats and Glück (2019) and dell–Olio, Ibeas, and Ruisánchez (2012). Using meta-heuristics, the frequency setting problem was integrated with the route design by Szeto and Wu (2011) and Arbex and da Cunha (2015). Cipriani, Gori, and Petrelli (2012) also addressed the frequency setting problem as an exercise of balancing the passenger demand with the available supply. Verbas and Mahmassani (2013), Verbas et al. (2015), Verbas and Mahmassani (2015) and Gkiotsalitis, Wu, and Cats (2019) developed frequency setting models that consider flexible virtual lines (e.g. short-turning/interlining lines) to exploit the available vehicle/driver resources as much as possible. The works of Delle Site and Filippi (1998) and Cortés, Jara-Díaz, and Tirachini (2011) also focus on generating short-turning lines to serve the excessive demand at crowded line segments.

In this study we adopt the model formulation proposed by Furth and Wilson (1981) as a baseline. This formulation is limited to a single line and considers the operational costs expressed by the number of vehicles required and the passenger-related costs expressed by the total passenger waiting times.

To describe the approach of Furth and Wilson (1981), let us consider a time period of 1 h and a number of available vehicles, N. Let also x be the number of vehicles allocated to the service line and f the resulting frequency. Finally, let T be the round-trip travel time and $B_{sy}$ the expected passenger demand between the origin station s and the destination station y within the 1-h time period (note that $B_{sy}$ corresponds to the hourly passenger arrival rate). Then, the optimal service frequency is determined by the model of Furth and Wilson (1981) by solving the following mixed-integer nonlinear program (MINLP): (1) $\begin{array}{rl}(\mathrm{MINLP})& \underset{x,f}{min}W\cdot x+\sum _{s=1}^{|\mathcal{S}|-1}\sum _{y=s+1}^{|S|}{B}_{sy}\frac{1}{f}\end{array}$(1) (2) $\begin{array}{rl}\mathrm{subject}\mathrm{to}& x\le N\end{array}$(2) (3) $\begin{array}{rl}& f\le f_a^{max}\end{array}$(3) (4) $\begin{array}{rl}& f\le \frac{x}{T}\end{array}$(4) (5) $\begin{array}{rl}& x\in {\mathbb{Z}}_{\ge 0}\end{array}$(5) (6) $\begin{array}{rl}& f\in {\mathbb{R}}_{\ge 1}\end{array}$(6)

The objective function of the above program minimizes two components: (i) Wx which is the operational cost expressed by the number of assigned vehicles x multiplied by a weight factor W associated with the cost of operating an extra vehicle, and (ii) $\sum _{s=1}^{|\mathcal{S}|-1}\sum _{y=s+1}^{|S|}{B}_{sy}\frac{1}{f}$ which is the passenger-related cost expressed by the number of passengers traveling between each origin-destination pair sy multiplied by the inverse of the service frequency f (note that the higher the service frequency, the less passengers $B_{sy}$ will have to wait at stations thus reducing the passenger-related costs).

Constraint (2(2) $\begin{array}{rl}\mathrm{subject}\mathrm{to}& x\le N\end{array}$(2) ) ensures that we will not assign more vehicles than the total number of vehicles available, N, constraint (3(3) $\begin{array}{rl}& f\le f_a^{max}\end{array}$(3) ) ensures that the selected frequency is not higher than the maximum allowed frequency, constraint (4(4) $\begin{array}{rl}& f\le \frac{x}{T}\end{array}$(4) ) ensures that the service frequency is lower than the number of vehicles divided by the round-trip travel time. Constraint (5(5) $\begin{array}{rl}& x\in {\mathbb{Z}}_{\ge 0}\end{array}$(5) ) ensures that each line is operated by a non-negative, integer number of trains and constraint (6(6) $\begin{array}{rl}& f\in {\mathbb{R}}_{\ge 1}\end{array}$(6) ) that the determined frequency can only take values greater than 1 vehicle per hour. In the next section, we expand the approach of Furth and Wilson (1981) to a network-wide frequency settings problem by allowing the redistribution of vehicles among lines and adding elements to the problem formulation in order to account for the impact of distancing measures. The main extensions of our work are:

• we consider multiple lines solving the frequency setting problem at the network-wide level, and not at the single-line level;

• we explicitly model the pandemic-imposed capacity limits and the safety-related constraints when multiple lines use the same track (arc);

• we explicitly model the revenue losses from refused passenger trips due to the pandemic-imposed capacity limits;

• we incorporate an assignment step to allow passengers to use alternative lines running along overlapping corridors to arrive at their final destination.

3. Network-wide frequency setting model that considers distancing

3.1. Model formulation

Let us consider a set of lines $L=\{1,\dots ,l,\dots ,|L|\}$ operating in a metro network. Each line l serves a number of metro stations $S_l=\{1,2,\dots ,|S_l|\}$. Let $B_{l,sy}$ be the expected passenger demand between station $s\in S_l\setminus \{|S_l|\}$ and station $y\in S_l|y>s$ of line l within an 1-h period (corresponding to the passenger arrival rate). Before introducing our nomenclature, we list the main assumptions of our study:

1. The passenger arrival rate $B_{l,sy}$ is stable within each 1-h period of the day. That is, passenger arrivals at stations are uniformly distributed within the 1-h period (see Furth and Wilson 1981; Fu and Yang 2002).

2. The obtained passenger demand patterns from historical data are inelastic to the changes made in service frequencies.

3. Passengers may choose the rail car of preference for their boarding (e.g. a central rail car or a rail car on a convenient spot within close proximity to an egress or ingress mode) as long as this rail car does not reach its pandemic-imposed capacity limit.

The detailed nomenclature of our network-wide frequency setting model that considers distancing measures is presented in Table 1.

Table 1. Nomenclature.

Sets
$L=⟨1,\dots ,l,\dots |L|⟩$	ordered set of metro lines (note that a bi-directional line is considered as a single line that continues its service in the opposite direction)
$S_l=⟨1,2,\dots ,|S_l|⟩$	ordered set of metro stations served by line $l\in L$
$S=⟨1,2,\dots ,|S|⟩$	unordered set of all stations in the metro network
$A=⟨1,2,\dots ,|A|⟩$	set of arcs in the metro network system. An arc connects successive stations and can be served by more than one line if they share the same track corridor
$\mathcal{F}$	$\mathcal{F}=⟨1,2,3,4,5,8,10,12,15,20,30,60⟩$ is the set of allowed line frequencies to ensure a periodic service. The frequencies are expressed in vehicles per hour
Indices
l	train line
s	metro station
Parameters
$B_{sy}$	hourly passenger arrival rate at station s for passengers whose destination is y
$T_l$	round-trip travel time of line $l\in L$ considering both directions in case of a bi-directional line
$c_l$	capacity of trains operating in line l
$k_l$	maximum passenger load inside each train operating in line l to conform with social distancing
W	cost of deploying an extra train
V	value of passenger's time
M	fare price per km traveled
$d_{l,sy}$	traveling distance between stations s and y of line $l\in L$
$f_a^{max}$	maximum hourly number of vehicles that are allowed to pass the same arc $a\in A$ for safety reasons
N	number of available trains that can be distributed among all lines
$g_{l,a}$	binary parameter where $g_{l,a}=1$ if line $l\in L$ serves arc $a\in A$ and zero otherwise
${\delta }_{l,sy}$	binary parameter where ${\delta }_{l,sy}=1$ if line l serves origin-destination pair $(s,y)$ and zero otherwise
Variables
$B_{l,sy}$	expected hourly passenger arrival rate at station s for passengers whose destination is y and are willing to use line l
$x_l$	number of trains assigned to line $l\in L$
$f_l$	hourly frequency of line $l\in L$
$h_l$	time headway among successive trains of line $l\in L$
${\gamma }_{l,s}$	train load of each train serving line l when it departs from station s
$b_{l,sy}$	hourly passenger demand between stations s and y of line l that can be served by the trains of line l while conforming to distancing requirements
${\tilde{b}}_{l,sy}$	hourly passenger demand between stations s and y of line l that cannot be accommodated by the metro services due to distancing requirements

Let $x_l$ be the number of trains assigned to each line $l\in L$ within a certain time period. Let also $T_l$ be the round-trip travel time of line l. Then, the hourly frequency of line l should satisfy the inequality constraint (7(7) $f_l\le \frac{x_l}{T_l}(\mathrm{\forall }l\in L)$(7) ) because the service frequency is limited by the number of assigned vehicles to line l: (7) $f_l\le \frac{x_l}{T_l}(\mathrm{\forall }l\in L)$(7)

In addition, the number of vehicles of all lines $l\in L$ that pass arc $a\in A$ over the course of 1 h should not exceed the maximum permitted number of vehicles to ensure safe headways between trains operating along the same corridor (i.e. we cannot allow trains operating too close to each other because tracks are split into blocks into which only one train can enter at a time due to traffic safety constraints). That is, (8) $\sum _{l\in L}{g}_{l,a}\frac{x_l}{T_l}\le f_a^{max}(\mathrm{\forall }a\in A)$(8)

Next, let ${\gamma }_{l,s}$ be the average train load of each train serving line l when it departs from station s. We hereby assume that:

1. passengers within each train try to maintain the maximum possible distance between each other,

2. and all trains serving line l have the same capacity, $c_l$.

This implies a new corona-era capacity limit, $k_l$, where $k_l<c_l$ is the maximum train load for trains of line l below which all passengers can keep a safe distance with each other. This corona-era capacity limit should not be exceeded at any station to ensure that the risk of COVID-19 infections is minimized. This can be expressed by the following inequality constraint: (9) ${\gamma }_{l,s}\le k_l(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l)$(9)

If $b_{l,sy}\le B_{l,sy}$ is the actual passenger demand between stations s and y that can be accommodated by the allocated trains to line l without exceeding the corona-era capacity limit, then (10) $b_{l,sy}=B_{l,sy}-{\tilde{b}}_{l,sy}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l,\mathrm{\forall }y\in S_l|y\ge s)$(10) where ${\tilde{b}}_{l,sy}$ is the unaccommodated passenger demand that should be served outside our metro system. The passenger demand that is not accommodated by the metro system represents a loss. When refusing to accommodate demand ${\tilde{b}}_{l,sy}$, the public transport service provider incurs a loss. From a societal perspective this loss can mean reduced accessibility. From the service provider perspective this may mean offering a compensation, arranging alternative means of transport, or simply the revenue loss of ticket sales. We hereby assume that the loss is proportional to the travel distance and we adopt the distance-based fare as a proxy of the loss per unserved passenger-km. If $d_{l,sy}$ is the distance between stations s and y of metro line l, the operator will lose a revenue of $M\cdot {\tilde{b}}_{l,sy}\cdot d_{l,sy}$ because ${\tilde{b}}_{l,sy}$ passengers are refused service and M is the average ticket fee per km traveled. Then, our objective function for the network-wide frequency setting problem that considers social distancing becomes: (11) $z(x,f,b,\tilde{b}):=W\sum _{l\in L}{x}_l+\sum _{l\in L}\sum _{s\in S_l\setminus \{|S_l|\}}\sum _{y\in S_l|y>s}(V{b}_{l,sy}\frac{1}{f_l}+M{d}_{l,sy}{\tilde{b}}_{l,sy})$(11)

The first term is the cost of operating the vehicles, the second term, $V{b}_{l,sy}$, is the cost related to passengers' waiting times and the third term, $M{d}_{l,sy}{\tilde{b}}_{l,sy}$, is the cost of the revenue losses associated with the passengers that are refused service. The objective function is formulated as a compensatory monetary term and expresses a generalized cost. Considering the above formulation, the mathematical program for the network-wide frequency setting problem that considers distancing measures is formulated as follows: (12) $\begin{array}{rl}(\mathrm{Q})& minz(x,f,b,\tilde{b})\end{array}$(12) (13) $\begin{array}{rlr}& \mathrm{s}.\mathrm{t}.\sum _{l\in L}{x}_l\le N& \end{array}$(13) (14) $\begin{array}{rl}& f_l\le \frac{x_l}{T_l}(\mathrm{\forall }l\in L)\end{array}$(14) (15) $\begin{array}{rl}& \sum _{l\in L}{g}_{l,a}\frac{x_l}{T_l}\le f_a^{max}(\mathrm{\forall }a\in A)\end{array}$(15) (16) $\begin{array}{rl}& {\gamma }_{l,s}\le k_l(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l)\end{array}$(16) (17) $\begin{array}{rl}& {\gamma }_{l,1}=\sum _{y\in S_l}{b}_{l,1y}\frac{1}{f_l}(\mathrm{\forall }l\in L)\end{array}$(17) (18) $\begin{array}{rl}& {\gamma }_{l,s}={\gamma }_{l,s-1}-\sum _{y\in S_l|y<s}{b}_{l,ys}\frac{1}{f_l}+\sum _{y\in S_l|y>s}{b}_{l,sy}\frac{1}{f_l}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l\setminus \{1\})\end{array}$(18) (19) $\begin{array}{rl}& b_{l,sy}=B_{l,sy}-{\tilde{b}}_{l,sy}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l,\mathrm{\forall }y\in S_l|y\ge s)\end{array}$(19) (20) $\begin{array}{rl}& \sum _{l\in L}{\delta }_{l,sy}{B}_{l,sy}=B_{sy}(\mathrm{\forall }s\in S,\mathrm{\forall }y\in S)\end{array}$(20) (21) $\begin{array}{rl}& x_l\in {\mathbb{Z}}_{\ge 0}(\mathrm{\forall }l\in L)\end{array}$(21) (22) $\begin{array}{rl}& f_l\in \mathcal{F}(\mathrm{\forall }l\in L)\end{array}$(22)

Note that constraint (13(13) $\begin{array}{rlr}& \mathrm{s}.\mathrm{t}.\sum _{l\in L}{x}_l\le N& \end{array}$(13) ) ensures that the number of all assigned trains within our time period does not exceed N. In addition, constraint (17(17) $\begin{array}{rl}& {\gamma }_{l,1}=\sum _{y\in S_l}{b}_{l,1y}\frac{1}{f_l}(\mathrm{\forall }l\in L)\end{array}$(17) ) determines the train load when a train departs the terminal as the number of passengers that board at station 1 and will alight at any other station y within our 1-h time period, $b_{l,sy}$, divided by the hourly frequency, $f_l$. Similarly, the recursive equation (18(18) $\begin{array}{rl}& {\gamma }_{l,s}={\gamma }_{l,s-1}-\sum _{y\in S_l|y<s}{b}_{l,ys}\frac{1}{f_l}+\sum _{y\in S_l|y>s}{b}_{l,sy}\frac{1}{f_l}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l\setminus \{1\})\end{array}$(18) ) determines the train load when a train belonging to line l departs from station $s\in S_l\setminus \{1\}$. This is a passenger flow conservation equation where the train load is equal to the train load when departing from the previous station, ${\gamma }_{l,s-1}$, minus the number of passengers that alight at station s, $\sum _{y\in S_l|y<s}{b}_{l,ys}\frac{1}{f_l}$, plus the number of passengers that board at station s and will alight at any other station y>s of line l. Finally, constraint (20(20) $\begin{array}{rl}& \sum _{l\in L}{\delta }_{l,sy}{B}_{l,sy}=B_{sy}(\mathrm{\forall }s\in S,\mathrm{\forall }y\in S)\end{array}$(20) ) ensures that the sum of expected hourly boardings of all lines that serve the origin-destination pair $s\in S$ and $y\in S$ is equal to the observed hourly passenger arrival rate at station s for passenger whose destination is y. This constraint allows distributing passengers over different lines that serve the origin-destination pair $(s,y)$ in order to balance the passenger load among overlapping lines.

The mathematical program for the network-wide frequency setting problem that considers distancing measures, $(Q)$, is a mixed-integer nonlinear programming problem (MINLP) because of its fractional objective function and its fractional constraints (17(17) $\begin{array}{rl}& {\gamma }_{l,1}=\sum _{y\in S_l}{b}_{l,1y}\frac{1}{f_l}(\mathrm{\forall }l\in L)\end{array}$(17) ) and (18(18) $\begin{array}{rl}& {\gamma }_{l,s}={\gamma }_{l,s-1}-\sum _{y\in S_l|y<s}{b}_{l,ys}\frac{1}{f_l}+\sum _{y\in S_l|y>s}{b}_{l,sy}\frac{1}{f_l}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l\setminus \{1\})\end{array}$(18) ).

3.2. Reformulation to a mixed-integer quadratic program (MIQP)

The MINLP problem $(Q)$ can be transformed to an easier-to-solve mixed-integer quadratic program (MIQP) that neither contains a fractional objective function nor fractional constraints. Let us consider a line headway of $h_l=\frac{1}{f_l},\mathrm{\forall }l\in L$. Then, the fractional constraint in Equation (17(17) $\begin{array}{rl}& {\gamma }_{l,1}=\sum _{y\in S_l}{b}_{l,1y}\frac{1}{f_l}(\mathrm{\forall }l\in L)\end{array}$(17) ) becomes ${\gamma }_{l,1}=\sum _{y\in S_l}{b}_{l,1y}{h}_l(\mathrm{\forall }l\in L)$. In addition, the fractional constraint (18(18) $\begin{array}{rl}& {\gamma }_{l,s}={\gamma }_{l,s-1}-\sum _{y\in S_l|y<s}{b}_{l,ys}\frac{1}{f_l}+\sum _{y\in S_l|y>s}{b}_{l,sy}\frac{1}{f_l}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l\setminus \{1\})\end{array}$(18) ) becomes ${\gamma }_{l,s}={\gamma }_{l,s-1}-\sum _{y\in S_l|y<s}{b}_{l,ys}{h}_l+\sum _{y\in S_l|y>s}{b}_{l,sy}{h}_l(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l\setminus \{1\})$.

Constraint (14(14) $\begin{array}{rl}& f_l\le \frac{x_l}{T_l}(\mathrm{\forall }l\in L)\end{array}$(14) ) is transformed into the following quadratic constraint: $h_l{x}_l\ge T_l(\mathrm{\forall }l\in L)$. Finally, the objective function takes the following form: (23) $z(x,h,b,\tilde{b}):=W\sum _{l\in L}{x}_l+\sum _{l\in L}\sum _{s\in S_l\setminus \{|S_l|\}}\sum _{y\in S_l|y>s}(V{b}_{l,sy}{h}_l+M{d}_{l,sy}{\tilde{b}}_{l,sy})$(23) where the headway of each line l, $h_l$, is expressed in minutes and it can receive values from the set $\mathcal{H}=⟨2,3,4,5,6,7.5,10,12,15,20,30,60⟩$ given that the service frequencies receive values from set $\mathcal{F}$. This reformulation results in the following MIQP: (24) $\begin{array}{rl}(\tilde{\mathrm{Q}})& minz(x,h,b,\tilde{b})\end{array}$(24) (25) $\begin{array}{rl}& \mathrm{s}.\mathrm{t}.\sum _{l\in L}{x}_l\le N\end{array}$(25) (26) $\begin{array}{rl}& h_l{x}_l\ge T_l(\mathrm{\forall }l\in L)\end{array}$(26) (27) $\begin{array}{rl}& \sum _{l\in L}{g}_{l,a}\frac{x_l}{T_l}\le f_a^{max}(\mathrm{\forall }a\in A)\end{array}$(27) (28) $\begin{array}{rl}& {\gamma }_{l,s}\le k_l(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l)\end{array}$(28) (29) $\begin{array}{rl}& {\gamma }_{l,1}=\sum _{y\in S_l}{b}_{l,1y}{h}_l(\mathrm{\forall }l\in L)\end{array}$(29) (30) $\begin{array}{rl}& {\gamma }_{l,s}={\gamma }_{l,s-1}-\sum _{y\in S_l|y<s}{b}_{l,ys}{h}_l+\sum _{y\in S_l|y>s}{b}_{l,sy}{h}_l(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l\setminus \{1\})\end{array}$(30) (31) $\begin{array}{rl}& b_{l,sy}=B_{l,sy}-{\tilde{b}}_{l,sy}(\mathrm{\forall }l\in L,\mathrm{\forall }s\in S_l,\mathrm{\forall }y\in S_l|y\ge s)\end{array}$(31) (32) $\begin{array}{rl}& \sum _{l\in L}{\delta }_{l,sy}{B}_{l,sy}=B_{sy}(\mathrm{\forall }s\in S,\mathrm{\forall }y\in S)\end{array}$(32) (33) $\begin{array}{rl}& x_l\in {\mathbb{Z}}_{\ge 0}(\mathrm{\forall }l\in L)\end{array}$(33) (34) $\begin{array}{rl}& h_l\in \mathcal{H}(\mathrm{\forall }l\in L)\end{array}$(34)

4. Model application

4.1. Case study description

We apply our model to the case study of the Washington DC Metro system of the Washington Metropolitan Area Transit Authority (WMATA). It is a rapid transit system serving the Washington metropolitan area in the United States. The network consists of 6 lines, 91 metro stations. The metro system serves the District of Columbia, as well as several jurisdictions in the states of Maryland and Virginia. It is the second busiest rapid transit system in the United States with 295 million passenger trips in 2018 (WMATA 2019a). In 2019, the average weekday ridership was 626 thousand trips (WMATA 2019b). Passengers validate their smart card (SmartTrip) upon entering an origin station and leaving a destination station, and the fee is determined based on the traveled distance of the origin-destination combination. The network configuration consisting of the six metro lines is presented in Figure 1.

Figure 1. Washington DC metro network map. Source: www.wmata.com

Due to infrastructure capacity limits, the maximum allowed frequency per track segment is $f_a^{max}=30$ vehicles per hour for each arc a, resulting in a minimum permitted headway of 2 min at common track corridors. From Figure 1 one can note that there are several track corridors that are traversed by vehicles serving more than one line. For the purpose of our case study, we assume the availability of N = 140 trains. Table 2 provides information on each of the service lines, including the number of stations, total bi-directional track length, and the names of the terminal stations.

Table 2. Terminals and line distances.

			Terminals
	Stations	Distance in km
	(per direction)	(both directions)	Western/Southern	Eastern/Northern
Orange line	26	85	Vienna	New Carrollton
Blue line	27	97.6	Franconia–Springfield	Largo Town Center
Silver line	28	95.2	Wiehle–Reston East	Largo Town Center
Green line	21	74.16	Branch Avenue	Greenbelt
Red line	26	102.6	Shady Grove	Glenmont
Yellow line	22	48.5	Huntington	Greenbelt

In order to investigate the impact of distancing measures, we concentrate on the rush hour (8:00–9:00 am) of a typical weekday. In particular, we examine the need to deploy additional trains and possibly refuse boardings. The expected hourly rate of passengers arriving at station s of line l and destined to station y is derived from the analysis of historical smart card data with complete information regarding passenger boarding and alighting locations from 20 working days in September 2018. The line-specific origin-destination matrices have been inferred using the origin, destination, and transfer inference (ODX) method as detailed in Sánchez-Martínez (2017). We use peak demand data from the pre-pandemic era because our objective is to investigate the effect of our frequency planning model when the passenger demand has almost returned to its pre-pandemic levels yet there is still a need to comply with the social distancing regulations.

The distances traveled by each of the metro lines vary considerably. Figure 2 shows the share of passenger trips of a certain traveled distance for each of the lines. This share is calculated as the number of passenger trips of a line for a specific travel distance divided by the total number of trips performed by all lines. As can be seen in Figure 2 the Red line has up to three times more passenger trips than other lines and passengers trips on the Red, Orange and Silver lines travel longer distances than those on the Blue, Yellow and Green lines.

Figure 2. Share of passenger trips of each metro line from 8 am to 9 am with respect to the traveled distance.

The values of the remaining model parameters are given in Table 3. Each metro train consists of 6–8 rail cars, with an average maximum capacity of 1700 people. During the morning period (5 am–12 pm) a metro train carries an average of 133 travelers at any given time. This value, however, varies greatly with some central segments reaching capacity limits. Assuming that passengers are evenly spaced across platforms, each train operating in any line $l\in L$ can carry only $k_l=703$ people at any given time to satisfy a 1-m distancing requirement, $k_l=312$ to fulfill a 1.5-m distance, and $k_l=176$ to comply with a 2-m distance. These values are estimated using the calculation made in Krishnakumari and Cats (2020). In this work the effective capacity under each social-distancing requirement is calculated based on the total square meters of each train car, the number of cars per train and the total area required per person to maintain the distance-keeping regulations. In reality, passenger crowding may vary also among rail cars as shown in Peftitsi, Jenelius, and Cats (2020). Such variations may result in an under utilization of the limited capacity available, further reducing the effective capacity.

Table 3. Parameter values.

	Lines
	Orange	Blue	Silver	Green	Red	Yellow
$T_l$ (minutes)	150	156	170	122	160	120
$c_l$ (passengers per train)	1700	1700	1700	1700	1700	1700
$k_l$ without social distancing	1700	1700	1700	1700	1700	1700
$k_l$ with 1 m social distancing	703	703	703	703	703	703
$k_l$ with 1.5 m social distancing	312	312	312	312	312	312
$k_l$ with 2 m social distancing	176	176	176	176	176	176

Passengers' value of time in our case study is $V=14.67\mathrm{\$}$ per hour, or, equivalently, 24.4 cents per minute (based on the value of travel time reported in White (2016) and adjusting the value by 1% per year). In addition, we have two parameters W and M corresponding to the operational cost of using an extra train and the cost associated with the travel distances of passengers who are refused service, respectively. The value of parameter W depends on the preferences of the metro operator since some operators might be willing to use all their available trains to reduce the passenger waiting times, whereas other operators might seek an economically beneficial trade-off between operational costs and passenger waiting times. We tested our model with different values of W and selected a cost of $W=36.675\mathrm{\$}$ per extra train since this cost returns the same train allocation to lines when solving program $(\tilde{Q})$ for the case of no distancing (i.e. normal capacity levels) as the planned train allocation actually performed by the metro operator. Further, the passenger fare at the metro system depends on the travel distance and the time period (peak/off-peak periods). The 8 am–9 am is a peak hour and the fare cost per passenger is found to have an average value of $M=0.7\mathrm{\$}$ per km traveled.

4.2. Scenario design and implementation

The topic of distancing is currently contested as the transmission of COVID-19 is not yet well characterized. It is likely to be similar to SARS, which was spread by contact, droplet, and airborne routes (Yu et al. 2004). The World Health Organization and most countries recommend an 1.5–2-m social distancing. In a study with 94 patients of influenza, Bischoff et al. (2013) showed that the virus can be transmitted up to ∼1.9 m from patients during non-aerosol-generating patient-care activities. It is important to note that increasing the distance among passengers does not proportionally decrease the probability of transmitting COVID-19.

To assess the impact of distancing measures, we consider the following 4 scenarios:

1. the do-nothing scenario that does not consider distancing measures and can utilize the full capacity of 1700 passengers per train;

2. the 1-m distancing scenario that allows train loads of up to 703 passengers per train;

3. the 1.5-m distancing scenario that allows train loads of up to 312 passengers per train;

4. the 2-m distancing scenario that allows train loads of up to 176 passengers per train.

We solve our MIQP model in program $(\tilde{Q})$ using Gurobi 9.0.3. The software code of our mathematical model is programmed in Python 3. Gurobi 9.0.3. is an optimization solver which is appropriate for mixed-integer quadratically constrained programs and it has an interface with Python (the gurobipy module). Our numerical experiments are executed in a general-purpose computer with Intel Core i7-7700HQ CPU @ 2.80GHz and 16 GB RAM. To facilitate the reproduction of our model to other networks, its source code is publicly released at GitHub (2020).

4.3. Results and analysis

The objective function score(s) of the solution of each scenario as well as the computation times are presented in Table 4.

Table 4. Objective function value of the respective solution, iterations until convergence, and computational costs.

	Objective function score ($)	Iterations until convergence	Computation time (min)
(I) Do-nothing	4553	6	0.01
(II) 1-m	5688	39	0.96
(III) 1.5-m	134,698	42	4.62
(IV) 2-m	291,518	164	34.52

Note that the optimal score of the objective function for cases III and IV increases significantly in Table 4 because for such social distancing cases we have unserved passengers and revenue losses despite deploying all available trains. The decision variable values in the optimal solutions under each distancing scenario are reported in Table 5 and present the allocated vehicles per line and the resulting service headway.

Table 5. Assigned trains, $x_l$, and headway (in minutes), $h_l$, per line $l\in L$ at each one of the social distancing scenarios.

	Social distancing scenarios
	(I) Do-nothing		(II) 1-m		(III) 1.5-m		(IV) 2-m
	Trains	Headway	Trains	Headway	Trains	Headway	Trains	Headway
Orange	15	10	30	5	38	4	20	7.5
Blue	8	20	16	10	16	10	16	10
Silver	6	30	9	20	17	10	17	10
Green	7	20	7	20	7	20	5	30
Red	16	10	40	4	54	3	80	2
Yellow	10	12	20	6	8	15	2	60
Total	62	n/a	122	n/a	140	n/a	140	n/a

In case IV we deploy 80 trains to the red line because it has the highest passenger demand. The red line does not have an overlapping corridor with any other line and it requires more trains because its passengers cannot use alternative lines. The number of vehicles passing different arcs over 1 h in the worst case (case IV where we deploy all vehicles) is presented in Figure 3. Even though all vehicles are deployed, no arc is visited by more than 30 vehicles per hour because of our safety-imposed frequency per arc of 30 vehicles per hour (see constraint (8(8) $\sum _{l\in L}{g}_{l,a}\frac{x_l}{T_l}\le f_a^{max}(\mathrm{\forall }a\in A)$(8) )).

Figure 3. Joint vehicle frequency per track segment expressed in vehicles per hour.

From Table 5 one can note that at the do-nothing case we only deploy 62 trains out of the $N=140$. The same passenger demand requires the utilization of 122 trains in the case of 1-m distancing (case II). Finally, scenarios III and IV require the deployment of all available trains.

In addition to the increase in operational costs due to the deployment of more vehicles and train drivers, a number of passengers are also refused service in scenarios III and IV. In Figure 4 we present the train load at each station for each one of the six lines. The normal vehicle capacity of $c_l=1700$ passengers is not reached at the base case scenario once the fleet is optimally allocated. It can also be observed that the optimal allocation results with trains loads not exceeding 703 passengers per train on the Green line in the base case (scenario I). Consequently, there is sufficient residual capacity to also accommodate the demand when subject to 1-m distancing (scenario II). In contrast, all other lines require re-allocating trains to ensure that the new capacity limit is not violated when switching from scenario I to scenario II, as can be seen in Table 5.

Figure 4. Passenger load of each train operating from 8 am to 9 am at each metro station in scenarios I, II, III and IV. A load of 176 passengers ensures 2-m distancing, 312 an 1.5-m distancing, 703 an 1-m distancing, whereas 1700 indicates the nominal capacity.

As specified in the problem constraints, the optimal solution for case II does not allow train loads of more than 703 passengers, for case III of more than 312, and for case IV of more than 176. This results in different train occupancy levels for each distancing scenario. Let the seated train occupancy be defined as the train load divided by the number of seats (in our case study, each train has ${\tilde{c}}_l=616$ available seats): (35) $\mathrm{Seated}\mathrm{Occupancy}=\frac{1}{|S_l|}\sum _{s_{\in }{S}_l}\frac{{\gamma }_{l,s}}{{\tilde{c}}_l}(\mathrm{\forall }l\in L)$(35)

The average train occupancy level per line for each one of the distancing scenarios is presented in Table 6. The occupancy level averaged over all line segments ranges in the optimal solution for the base case from 30% for the Green line to 125% for the Yellow line. A seated occupancy of more than 100% indicates that all seats are occupied and we have a number of standees. These levels drop to 19–28% for all lines when complying with 2-m distancing (scenario IV).

Table 6. Average seated occupancy for each distancing scenario.

	Social distancing scenarios
	(I) Do-nothing	(II) 1-m	(III) 1.5-m	(IV) 2-m
Orange	114%	56%	35%	21%
Blue	91%	46%	29%	19%
Silver	122%	81%	39%	24%
Green	30%	30%	23%	19%
Red	125%	50%	32%	19%
Yellow	68%	34%	41%	28%

When enforcing distancing measures of 1.5- or 2-m, even after optimally reallocating the fleet, some passengers are refused service. In Figure 5 we report the number of refused boardings at each metro station for the 1.5- and 2-m distancing policies. The Orange and Yellow lines exhibit the highest numbers of refused passenger boardings. Note that allocating more trains to the service lines is not possible given that we utilized all 140 trains in both the 1.5- and 2-m social distancing scenarios.

Figure 5. Refused passenger boardings at each station during the 8–9 am period in 1.5- and 2-m distancing scenarios-

To summarize the results of the impact of considering social distancing in the planning phase of metro operations, we use the following key performance indicators:

1. the average value of the maximum possible passenger waiting times, ${\mathcal{O}}_1:=\sum _{l\in L}\sum _{s\in S_l}\sum _{y\in S_l|y\ge s}{b}_{l,sy}\frac{1}{f_l}$

2. the number of trains that are needed to operate the metro service, which indicate the operational costs, ${\mathcal{O}}_2:=\sum _{l\in L}{x}_l$

3. the average train occupancy, ${\mathcal{O}}_3(\mathrm{\%})$

4. the number of instances where passengers cannot maintain a distance of at least 1.5 m from each other, ${\mathcal{O}}_4:=\sum _{l\in L}\sum _{s\in S_l}{r}_{l,s}$ where $r_{l,s}=0$ if ${\gamma }_{l,s}\le 312$, and $r_{l,s}=1$ otherwise.

5. the number of passengers who are refused service multiplied by their traveled distance, ${\mathcal{O}}_5:=\sum _{l\in L}\sum _{s\in S_l}\sum _{y\in S_l|y>s}{\tilde{b}}_{l,sy}\cdot d_{l,sy}$

6. the number of passengers who are refused service, ${\mathcal{O}}_6:=\sum _{l\in L}\sum _{s\in S_l}\sum _{y\in S_l|y>s}{\tilde{b}}_{l,sy}$

5. Discussion and conclusion

We propose a network-wide model that can set the optimal frequencies of services lines under different distancing scenarios and apply it to the case study network of the Washington DC metro. The model determines the optimal fleet allocation while considering unsatisfied demand in the event that not all demand can be absorbed due to the varying capacity limits of different distancing policies.

The results of our model indicate that the normal capacity limit is not binding in the optimal solution for the base case scenario with no distancing requirements. Moreover, all passenger demand can be satisfied when deploying 62 out of the 140 trains available so as to optimally balance between the operational costs and the passenger waiting times at stations. Furthermore, it is possible to comply with the 1m distancing requirements while still accommodating all passengers by increasing the service frequency, hence requiring a larger fleet size of 122 vehicles. This also yields shorter passenger waiting times. This does imply, however, that in about 75 instances, a distancing of less than 1.5 m occurs, potentially inducing public health risks (see the graph of the key performance indicator ${\mathcal{O}}_4$ in Figure 6).

Figure 6. Values of key performance indicators under different social distancing scenarios.

Stricter distancing policies come at a greater cost. Enforcing 1.5 m distancing requires deploying the maximum number of trains assumed available in our case study. Even though the entire fleet of 140 vehicles is utilized, 15,002 passenger-trips of more than 184,124 passenger-km cannot be accommodated. These numbers increase by more than half (24,869 pass trips) and almost two-fold (408,444 pass-km), respectively, when imposing 2 m distancing. In the latter case, the average train occupancy considering only the seated capacity plummets below 30% for all metro lines (see Table 6).

As can be expected, our model allocates as many vehicles as possible to the most heavily-utilized line (i.e. Red line) given the safety-related 30-min minimum arc frequency constraint. In contrast, for some other lines (e.g. Yellow), there are more allocated vehicles in the scenario with 1m distancing than in the scenarios with 1.5 and 2 m distancing where $12-18$ more vehicles are deployed (see Table 5). This is an interesting finding since one might have expected that the number of trains assigned to each line will increase (or at least will not decrease) when allocating an overall larger fleet and imposing stricter capacity constraints. However, when the permitted vehicle capacity is enough to satisfy the passenger demand (i.e. in the 1m scenario where we allocate only 122 out of the 140 available trains), the relatively lightly-utilized lines receive more vehicles to reduce passenger waiting times at stations since this is one of our main objectives. Notwithstanding, when the permitted capacity is reduced to comply with the distancing policies and we cannot anymore accommodate all passengers despite having employed all available resources, then vehicles are redistributed from lightly-utilized lines to heavily-utilized lines that already have to refuse many passengers (see Figure 2). That is, the inability to accommodate the passenger demand in some lines results in the redistribution of vehicles because of the higher priority given to reducing the number of refused passengers compared to shortening waiting times.

Our model formulation strives to minimize the refused pass-km so as to mitigate the associated loss revenues or costs inflicted. The reallocation of trains over lines under stricter distancing policies is hence not only driven by the wish to reduce the number of denied boardings, but more specifically the objective to reduce unsatisfied passenger-km. This implies that the model seeks to prioritize the allocation of resources to lines characterized by longer passenger trips over lines that are mostly used for shorter trips. This effect is visible in Table 5 as vehicles are reallocated from lines characterized by short passenger trips (e.g. Green, majority of the trips are less than 10 km, see Figure 2) to lines characterized by longer passenger trips (e.g. Red, many trips are between 10 and 30 km) when switching from 1.5 to 2 m distancing. This change in resource allocation is hence driven by the underlying demand patterns -- passenger volumes and travel distance.

The aforementioned findings of our network-wide frequency setting approach that considers distancing measures can support planning decisions made by public transport service providers in the phasing of exit strategies and the aftermath of the corona crisis. Model formulation strives to balance between operational, passenger, revenue loss, and health-risk related considerations. Depending on the local circumstances, planners and policymakers may assign different terms to the different objectives and compare the resulting performance under different distancing requirements. The model can also be used to dimension service supply for different demand levels during lock-down periods and potential changes associated with the outbreak and evolution of an epidemic.

Primary directions for further research pertain to refining and modeling the impact of refused demand. The cost associated with unsatisfied demand can be modified to account for aspects extending beyond revenue losses, such as reduced access to activities, customer retention effect, externalities caused by switching to using a car, or the cost of offering compensation or an alternative mean of transport. Future analysis may consider the equity implications of alternative solutions. The potential of partnerships with on-demand service providers to cater for the unsatisfied demand that exceeds the permitted capacity limits by offering them a (shared)ride as well as the operations of such services can possibly be the subject of further investigation.

Finally, although our frequency planning approach is implemented at the tactical planning stage, quasi real-time control approaches -- such as deadheading, stop-skipping or vehicle injection -- can be part of future research because they will require substantial changes regarding service provision that cannot be addressed directly at the frequency settings stage. Furthermore, we believe it is important to study next to supply management in the form of resource allocation, also measures such as real-time crowding information (Drabicki et al. 2021) to facilitate a more even distribution of passenger demand across services.

Acknowledgments

The authors thank Washington Metropolitan Area Transit Authority and in particular Jordan Holt for their invaluable cooperation and for providing the data that made this study possible.

Disclosure statement

No potential conflict of interest was reported by the authors.