# Optimal Design of Cordon Sanitaire for Regular Epidemic Control

Authors: Hongzhi Lin
Journal: Advances in Civil Engineering
 (2021)

---

## Abstract

The outbreak of COVID-19 has disrupted our regular life. Many state and local authorities have enforced a cordon sanitaire for the protection of sensitive areas. Travelers can only travel across the cordon after being qualified. This paper aims to propose a method to determine the optimal deployment of cordon sanitaire in terms of the number of parallel checkpoints at each entry link for regular epidemic control. A bilevel programming model is formulated where the lower-level is the transport system equilibrium with queueing to predict traffic inflow, and the upper-level is queueing network optimization, which is an integer nonlinear programming. The objective of this optimization is to minimize the total operation cost of checkpoints with a predetermined maximum waiting time. Note that stochastic queueing theory is used to represent the waiting phenomenon at each entry link. A heuristic algorithm is designed to solve the proposed bilevel model where the method of successive averages (MSA) is adopted for the lower-level model, and the genetic algorithm (GA) is adopted for the upper-level model. An experimental study is conducted to demonstrate the effectiveness of the proposed method and algorithm. The results show that the methods can find a good heuristic optimal solution. These methods are useful for policymakers to determine the optimal deployment of cordon sanitaire for hazard prevention and control.


---

## Body

## 1. Introduction

The COVID-19 pandemic is an ongoing pandemic of the coronavirus disease 2019 caused by severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2). As of September 22, 2020, over 31.3 million cases of COVID-19 have been reported in more than 188 countries, resulting in more than 965,000 deaths.To contain the rapid spread of COVID-19, authorities worldwide have responded by implementing travel restrictions, facility closures, and lockdowns while increasing the testing capacity and tracing contacts of infected people. The first cordon sanitaire was set up on January 23, 2020, to control entry to and exit from the City of Wuhan, known as the Wuhan lockdown, and then it was extended to almost all cities in China. As the outbreak expanded, many cities in other countries enacted similar restrictions. A cordon sanitaire is used to restrict the movement of people into and/or out of a defined geographic area, such as a community, city, or region. The term denoted a barrier used to stop the spread of infectious diseases.The enforced cordon sanitaire has been demonstrated to be an effective way to prevent the infectious virus from spreading into a protected area. All travelers crossing the cordons are imposed to test body temperature to ensure they are not infected. However, it is reported that the queue length is too long, and the waiting cost is too high at the cordon sanitaire. Therefore, there is an urgent need to optimize the queueing system to improve the service level of testing. This paper aims to propose a method to deploy checkpoints at the cordon sanitaire to ensure the maximum waiting time. Our recourse is to strike a balance between the cost of offering checkpoints and the cost of waiting experienced by travelers. It is not only helpful to control and prevent epidemics but also beneficial to check other kinds of dangers such as drunk driving, terrorists, criminals, smuggling, etc.The optimal deployment of cordon sanitaire, including the location and the number of checkpoints, has not been investigated yet. However, an analogous problem, namely, cordon pricing, has been explored a lot. Cordon pricing is a toll paid by private vehicles to enter a restricted area, usually within a city center, as part of a travel demand management strategy to relieve traffic congestion within that area. It has been successfully implemented in some cities in the world, for example, London, Stockholm, and Singapore. Earlier studies have demonstrated that the performance of cordon schemes is critically dependent on toll location and toll levels [1, 2]. Therefore, the achievement of cordon pricing could inspire the research of cordon sanitaire.Both cordon pricing and cordon sanitaire operate at the entry links around a restricted area. The difference is that cordon pricing aims to determine the optimal toll levels while cordon sanitaire seeks to determine the optimal number of checkpoints. In general, queue length on a road network is highly dependent on toll levels and toll points. It is usually assumed that, in cordon pricing, the policymaker sets tolls to maximize social welfare, defined as total benefits minus total costs according to the Marshallian measure. The problem has been studied by Verhoef [2], May et al. [1], Mun et al. [3], Santos [4], Shepherd and Sumalee [5], Zhang and Yang [6], and Yang et al. [7] in the early 21st century.The principle of social welfare maximization concerns the system efficiency that tends to harm equity. The service level of some travelers could be deteriorated significantly, which could cause cordon schemes to be inaccessible. In the past, researchers have explored the equity issues related to charging schemes. To identify the optimal toll location and toll levels, Sumalee et al. [8], as well as Maruyama and Sumalee [9], developed a methodology based on genetic algorithms to achieve social welfare maximization with and without constraints on the desired level of revenue and spatial equity impact. Abulibdeh et al. [10] used origin-destination data to assess the vertical equity effects of a hypothetical cordon pricing scheme in Canada’s largest city. Souche et al. [11] and Souche et al. [12] simulated the impact of cordon pricing on equities using both social and spatial indicators (Gini, Theil, and Atkinson indices) to make a city sustainable. They concluded that introducing a toll would increase inequalities, and it was crucial to investigate any changes among different categories of transport network users. Afandizadeh and Abdolmanafi [13] examined the issue of environmental equity in cordon pricing since air pollutants may transfer from inside to outside the cordon. Camporeale et al. [14] explored the distributional effects using the Theil index, taking into account an elastic demand associated with the cordon pricing strategy. A bilevel optimization model with an equity constraint is usually developed to reduce all kinds of inequities.Besides the equity issue, environmental considerations are often included for sustainable development. Amirgholy et al. [15] presented an equilibrium model to estimate the long-run adverse traffic effects of a cordon pricing scheme on consumer welfare and air pollution. Gühnemann et al. [16] analyzed the application of cordon pricing for the reduction of local air pollution in addition to social welfare maximization. Li et al. [17] focused on an environment-friendly cordon pricing design problem, where an acceptable road network performance is promised.Cordon pricing is still a hot topic in transportation research, and there are several directions for future research. Firstly, a logsum-based welfare computation before and after a change in the travel environment is used as an essential policy evaluation measure [18, 19]. Provided that logit choice models are widely adopted to simulate the response of consumers to a policy, consumer surplus can be easily computed using the model’s logsum. Therefore, utilizing a logsum-based objective function in the design of a cordon pricing scheme would likely be feasible for most planning agencies. Secondly, stochastic user equilibrium with elastic demand is used to represent route choice [20–22]. It is not surprising that the stochastic user equilibrium is more realistic than deterministic user equilibrium. However, it is a challenge in computation. Thirdly, mixed traffic flow is considered in a cordon tolling model, including motorcycle and automobile trips [13, 23, 24]. Lastly, combination models are proposed to address cordon pricing and other issues, such as road capacity choice [25] and land-use regulation [26].Although cordon sanitaire is analogous to cordon pricing, it has different characteristics that deserve to be studied further. The contribution of this paper lies in four aspects. Firstly, the queueing theory is used to quantify the phenomenon of waiting at the sanitary cordon, but it is rarely applied to the pricing cordon. With electronic toll collection (ETC) being widely implemented, there is no need for the inflow vehicles to stop to pay tolls. Secondly, a stochastic model is used to obtain representative measures of waiting at the sanitary cordon, such as average queue length, average waiting time in queue, etc. From the standpoint of analyzing queues, the arrival of vehicles is represented by the interarrival time (time between successive arrivals), and the testing service is measured by the service time per vehicle. The interarrival and service times are assumed to be probabilistic due to various disturbance factors, such as traffic accidents, bad weather, and occupancy rate. Thirdly, the queueing network is considered at the sanitary cordon other than a single queueing system. The testing is conducted on all the entry links of one cordon around a city such that there could be many queues. Therefore, it is necessary to study the entire queueing network. Lastly, goal-oriented action planning is conducted where a minimum investment is determined to ensure an acceptable level of queueing delay.The structure of this paper is organized as follows. Section2 proposes a bilevel programming model, where the lower-level is transport system equilibrium with queueing, and the upper-level is queueing network optimization. An explicit algorithm is designed in Section 3 to solve the proposed model. Section 4 demonstrates the effectiveness of the model and algorithm through an experimental study. Section 5 concludes this paper.


## 2. Methodology

This paper aims to propose a method and an algorithm to design a cordon sanitaire in terms of checkpoint deployment at each entry link. It is a Stackelberg game with a leader-follower decision structure which is usually formulated as a bilevel programming model. The operator in the upper-level aims to minimize the operation cost of cordon sanitaire with queueing delay constraints. The operator can predict, but cannot control freeway users’ travel behaviors including destination choice and route choice, while all users make their decisions in a user optimal manner. The users’ decisions in the lower-level are made after the upper-level decisions. However, the operator must take the behavioral responses of the users into consideration to adjust decisions. The general schematization of the overall methodology is shown in Figure1. It can explicitly capture the leader-follower nature of the relationship between the operator and users. Note that the lower-level is a feedback procedure between trip distribution and traffic assignment with queueing. It is usually termed as transport system equilibrium. The detailed models are elaborated in the followed subsections.Figure 1
The general schematization of the overall methodology.


### 2.1. Network Equilibrium with Queueing

The lower-level model is a transportation system equilibrium that combines trip distribution and traffic assignment models with fixed travel demand and a given road network. It has long been criticized that travel times are inconsistent in the conventional four-step sequential model because travel times are determined endogenously in fact. Generally speaking, two ways can be used to solve the inconsistent problem to achieve transportation system equilibrium in literature. One way is to combine several steps to an equivalent mathematical programming, which can be proved to be a well-converged and consistent result [27, 28]. The other is to feedback the sequential models iteratively until travel times meet the consistency criteria [29, 30]. Although the former is commonly adopted in literature, the latter one is more flexible at each step [31, 32]. Therefore, a combined model with feedback is adopted here.Note that traffic assignment is not a traditional one here as queueing delay at cordon sanitaire is accommodated. The determination of queueing delay time is a critical problem. Generally, queueing theory is an excellent tool to analyze the cost of waiting experienced by vehicles. In most traffic situations, interarrival and service times are described randomly by the exponential distribution. This stage adopts a stochastic queueing model that combines both arrivals and departures based on the Poisson assumptions. That is, the interarrival and the service times follow the exponential distribution. The derivation of the specialized queueing model is based on the steady-state behavior of the queueing situation, achieved after the system has been in operation for a sufficiently long time.According to the conventional traffic flow theory [33], the waiting line at each toll booth can be formulated as a fundamental M/M/c queueing model, where M means Markovian (or Poisson) arrivals or departures distribution or equivalently negative exponential interarrival or service time distribution and c means the number of identical parallel servers with same average service rate per unit time. There could be one or more parallel checkpoints (i.e., servers) at each entry link. Suppose that there are m entrances at a sanitary cordon. It is necessary to study the entire queueing network performances. Assume that vehicles arrive at each entrance i (i = 1, 2, …, m) according to a Poisson process with predicted inflow λi and that each entrance i has an exponential service time distribution with an identical parameter μ for its ci parallel checkpoints, where ciμ>λi. Therefore, the elementary M/M/c queueing model can be used to analyze each entrance.Analogous to a single service facility, the most commonly used measures of queueing situation in a given entrancei are the expected number of vehicles in the queue (li) and expected waiting time in the queue (di). The relationship between li and di is known as Little’s formula, and it is formulated as li=λidi. The relationship is valid under rather general conditions. Let ρi=λi/μ; the expression li can be determined as follows:(1)li=ρici+1ci−1!ci−ρi2p0i,∀i∈A∗,(2)pi=∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1,∀i∈A∗,(3)ρici<1,∀i∈A∗,where pi is the steady-state probability of none customers in an entrance i and A∗ is the set of entry links, equation (3) is a steady-state condition. The variable di is determined through dividing li by λi according to Little’s formula. It can be formulated in detail as follows:(4)dici=ρici+1λici−1!ci−ρi2∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1,∀i∈A∗.The times taken at entry links consist of two parts. One is link travel time determined by link traffic flows. The other is queueing delay time determined by the number of parallel checkpoints. Note that the queues are assumed to have zero physical length and the spillback phenomenon is not considered, which implies that link travel time is independent of the length of the queues. The times taken at other links are only determined by their traffic flows. Let linka travel time tava,ca=tava+daca if a∈A∗ and tava,ca=tava; if otherwise, then the traffic assignment with queueing for a given checkpoint deployment pattern, c, is a conventional traffic assignment problem.In summary, the lower-level model is conducted as follows, given fixed travel demand and built road network. Trip distribution is generated by aggregating individual destination choice. The multinomial logit model is used for destination choices because it is regarded as the simplest and most practical. After the trip distribution matrix is generated, travel demands are inputted into the road network by user equilibrium with queueing to generate link traffic flows. Note that the predicted traffic flow at each entry link is regarded as the average arrival rate of queueing system. Then all of the OD pair travel times are produced by Dijkstra’s algorithm with link travel times and queueing delay times. These path travel times are fed back to the multinomial logit model to update the trip distribution matrix. This process is iterated until the trip distribution matrix is well-converged. The state is known as transportation system equilibrium. Figure2 illustrates the feedback process at the lower-level.Figure 2
The iterative process in the lower-level model.The notations are defined as follows:qrs: the travel demand between origin r and destination sOr: the travel demand at node rSr: the set of destinations departed from origin rβs: the traveler preference parameter for destination strs: the path travel time variable between origin r and destination sA: the set of links in the networkA∗: the set of entry links that is a subset of links in the networkβt: the coefficient parameter of travel time trsva: the traffic flow variable at link aca: the number of checkpoints at link awhich is a decision variable coming from the upper-leveltava,ca: the travel time at link a which is a function of traffic flow va and number of checkpoints cafkrs: the traffic flow on path k connecting origin r and destination sδa,krs: the link-path incidence relationship which is expressed as(5)δa,krs=1,if linkais on pathkconnectingrands,0,if not.


### 2.2. The Bilevel Programming Model

There is a transportation system equilibrium in the lower-level for a given checkpoint deployment decision in the upper-level. The results of queueing can be incorporated in a cost minimization mode that seeks to minimize the sum of the cost of offering checkpoints and the cost of queueing time. It is straightforward that the cost of service increases with the increase in the level of service (e.g., the number of checkpoints). At the same time, the waiting time decreases with the increase in the level of service. The cost-based model attempts to balance two conflicting costs: the cost of offering the service and vehicle waiting time. An increase in one cost automatically causes a decrease in the other. As the cost of waiting time is difficult to be determined in dollars, the waiting time is adopted as a constraint while the cost of offering checkpoints is used as an objective. Therefore, the objective function in the upper-level programming model can be expressed as(6)MinE=∑i=1mc′ci,where E is the expected cost of operating the facilities per unit time and c′ is the marginal operation cost per checkpoint per unit time. The expected total cost E in the entire system is obtained by merely summing the corresponding quantities obtained at the respective entries.Acceptable control should consider queueing time constraints. The aspiration level model works directly with the performance measures of the queueing situation. The idea is to determine an acceptable range for the service level by specifying reasonable limits on measures of performance. Such limits are the aspiration levels the decision-maker wishes to reach. Note that the service level in a given entrancei is a function of the number of parallel checkpoints, ci. The upper-level presents a decision model for determining minimal operation cost considering the acceptable average waiting time di. The model recognizes that higher operation cost reduces the waiting time in the system. The goal is to strike a balance between operation cost and waiting time. The problem reduces to determining the number of servers ci such that(7)di≤T,∀i∈A∗.The constantT is the level of aspiration specified by the decision-maker, for example, T = 3 minutes. Note that di is a function of ci. According to equation (4), the aspiration level of average waiting time di can be specified as(8)dici=ρici+1λici−1!ci−ρi2∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1≤T,∀i∈A∗.In conclusion, an integer nonlinear programming model can be proposed where the objective is to minimize the expected total cost of testing operation, the constraint is an aspiration level of the vehicle waiting time at each entrance, and the decision variables are the number of parallel checkpoints in each entrance. The upper-level programming model is formulated as(9)MinEOC=∑i=1mc′ci,(10)s.t.ρici+1λici−1!ci−ρi2∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1≤T,∀i∈A∗,(11)ρici<1,∀i∈A∗,(12)ci≤ci′,∀i∈A∗,(13)ci≥0and integer,∀i∈A∗,where ci, ∀i∈A∗, are decision variables and traffic flows λi, ∀i∈A∗, are variables determined by the lower-level model, i.e., network equilibrium model with queueing. The objective function in equation (9) is to minimize the expected total cost of checkpoints. Equation (10) is the aspiration level of the vehicle waiting time for each entrance where T is a constant determined by the policymaker. Equation (11) is the steady-state condition. Equation (12) enforces that the number of checkpoints ci is not more than the capacity constraint ci′ for each entrance. It is used to consider real-life factors, e.g., the number of inflow lanes and the size of working spaces. Equation (13) makes sure that the decision variables ci, ∀i∈A∗, are nonnegative integers. It should be noted that the integer nonlinear programming model is hard to solve by classical optimization methods so that a heuristic algorithm is designed in the followed section.


## 2.1. Network Equilibrium with Queueing

The lower-level model is a transportation system equilibrium that combines trip distribution and traffic assignment models with fixed travel demand and a given road network. It has long been criticized that travel times are inconsistent in the conventional four-step sequential model because travel times are determined endogenously in fact. Generally speaking, two ways can be used to solve the inconsistent problem to achieve transportation system equilibrium in literature. One way is to combine several steps to an equivalent mathematical programming, which can be proved to be a well-converged and consistent result [27, 28]. The other is to feedback the sequential models iteratively until travel times meet the consistency criteria [29, 30]. Although the former is commonly adopted in literature, the latter one is more flexible at each step [31, 32]. Therefore, a combined model with feedback is adopted here.Note that traffic assignment is not a traditional one here as queueing delay at cordon sanitaire is accommodated. The determination of queueing delay time is a critical problem. Generally, queueing theory is an excellent tool to analyze the cost of waiting experienced by vehicles. In most traffic situations, interarrival and service times are described randomly by the exponential distribution. This stage adopts a stochastic queueing model that combines both arrivals and departures based on the Poisson assumptions. That is, the interarrival and the service times follow the exponential distribution. The derivation of the specialized queueing model is based on the steady-state behavior of the queueing situation, achieved after the system has been in operation for a sufficiently long time.According to the conventional traffic flow theory [33], the waiting line at each toll booth can be formulated as a fundamental M/M/c queueing model, where M means Markovian (or Poisson) arrivals or departures distribution or equivalently negative exponential interarrival or service time distribution and c means the number of identical parallel servers with same average service rate per unit time. There could be one or more parallel checkpoints (i.e., servers) at each entry link. Suppose that there are m entrances at a sanitary cordon. It is necessary to study the entire queueing network performances. Assume that vehicles arrive at each entrance i (i = 1, 2, …, m) according to a Poisson process with predicted inflow λi and that each entrance i has an exponential service time distribution with an identical parameter μ for its ci parallel checkpoints, where ciμ>λi. Therefore, the elementary M/M/c queueing model can be used to analyze each entrance.Analogous to a single service facility, the most commonly used measures of queueing situation in a given entrancei are the expected number of vehicles in the queue (li) and expected waiting time in the queue (di). The relationship between li and di is known as Little’s formula, and it is formulated as li=λidi. The relationship is valid under rather general conditions. Let ρi=λi/μ; the expression li can be determined as follows:(1)li=ρici+1ci−1!ci−ρi2p0i,∀i∈A∗,(2)pi=∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1,∀i∈A∗,(3)ρici<1,∀i∈A∗,where pi is the steady-state probability of none customers in an entrance i and A∗ is the set of entry links, equation (3) is a steady-state condition. The variable di is determined through dividing li by λi according to Little’s formula. It can be formulated in detail as follows:(4)dici=ρici+1λici−1!ci−ρi2∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1,∀i∈A∗.The times taken at entry links consist of two parts. One is link travel time determined by link traffic flows. The other is queueing delay time determined by the number of parallel checkpoints. Note that the queues are assumed to have zero physical length and the spillback phenomenon is not considered, which implies that link travel time is independent of the length of the queues. The times taken at other links are only determined by their traffic flows. Let linka travel time tava,ca=tava+daca if a∈A∗ and tava,ca=tava; if otherwise, then the traffic assignment with queueing for a given checkpoint deployment pattern, c, is a conventional traffic assignment problem.In summary, the lower-level model is conducted as follows, given fixed travel demand and built road network. Trip distribution is generated by aggregating individual destination choice. The multinomial logit model is used for destination choices because it is regarded as the simplest and most practical. After the trip distribution matrix is generated, travel demands are inputted into the road network by user equilibrium with queueing to generate link traffic flows. Note that the predicted traffic flow at each entry link is regarded as the average arrival rate of queueing system. Then all of the OD pair travel times are produced by Dijkstra’s algorithm with link travel times and queueing delay times. These path travel times are fed back to the multinomial logit model to update the trip distribution matrix. This process is iterated until the trip distribution matrix is well-converged. The state is known as transportation system equilibrium. Figure2 illustrates the feedback process at the lower-level.Figure 2
The iterative process in the lower-level model.The notations are defined as follows:qrs: the travel demand between origin r and destination sOr: the travel demand at node rSr: the set of destinations departed from origin rβs: the traveler preference parameter for destination strs: the path travel time variable between origin r and destination sA: the set of links in the networkA∗: the set of entry links that is a subset of links in the networkβt: the coefficient parameter of travel time trsva: the traffic flow variable at link aca: the number of checkpoints at link awhich is a decision variable coming from the upper-leveltava,ca: the travel time at link a which is a function of traffic flow va and number of checkpoints cafkrs: the traffic flow on path k connecting origin r and destination sδa,krs: the link-path incidence relationship which is expressed as(5)δa,krs=1,if linkais on pathkconnectingrands,0,if not.


## 2.2. The Bilevel Programming Model

There is a transportation system equilibrium in the lower-level for a given checkpoint deployment decision in the upper-level. The results of queueing can be incorporated in a cost minimization mode that seeks to minimize the sum of the cost of offering checkpoints and the cost of queueing time. It is straightforward that the cost of service increases with the increase in the level of service (e.g., the number of checkpoints). At the same time, the waiting time decreases with the increase in the level of service. The cost-based model attempts to balance two conflicting costs: the cost of offering the service and vehicle waiting time. An increase in one cost automatically causes a decrease in the other. As the cost of waiting time is difficult to be determined in dollars, the waiting time is adopted as a constraint while the cost of offering checkpoints is used as an objective. Therefore, the objective function in the upper-level programming model can be expressed as(6)MinE=∑i=1mc′ci,where E is the expected cost of operating the facilities per unit time and c′ is the marginal operation cost per checkpoint per unit time. The expected total cost E in the entire system is obtained by merely summing the corresponding quantities obtained at the respective entries.Acceptable control should consider queueing time constraints. The aspiration level model works directly with the performance measures of the queueing situation. The idea is to determine an acceptable range for the service level by specifying reasonable limits on measures of performance. Such limits are the aspiration levels the decision-maker wishes to reach. Note that the service level in a given entrancei is a function of the number of parallel checkpoints, ci. The upper-level presents a decision model for determining minimal operation cost considering the acceptable average waiting time di. The model recognizes that higher operation cost reduces the waiting time in the system. The goal is to strike a balance between operation cost and waiting time. The problem reduces to determining the number of servers ci such that(7)di≤T,∀i∈A∗.The constantT is the level of aspiration specified by the decision-maker, for example, T = 3 minutes. Note that di is a function of ci. According to equation (4), the aspiration level of average waiting time di can be specified as(8)dici=ρici+1λici−1!ci−ρi2∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1≤T,∀i∈A∗.In conclusion, an integer nonlinear programming model can be proposed where the objective is to minimize the expected total cost of testing operation, the constraint is an aspiration level of the vehicle waiting time at each entrance, and the decision variables are the number of parallel checkpoints in each entrance. The upper-level programming model is formulated as(9)MinEOC=∑i=1mc′ci,(10)s.t.ρici+1λici−1!ci−ρi2∑n=0ci−1ρinn!+ρicici−1!ci−ρi−1≤T,∀i∈A∗,(11)ρici<1,∀i∈A∗,(12)ci≤ci′,∀i∈A∗,(13)ci≥0and integer,∀i∈A∗,where ci, ∀i∈A∗, are decision variables and traffic flows λi, ∀i∈A∗, are variables determined by the lower-level model, i.e., network equilibrium model with queueing. The objective function in equation (9) is to minimize the expected total cost of checkpoints. Equation (10) is the aspiration level of the vehicle waiting time for each entrance where T is a constant determined by the policymaker. Equation (11) is the steady-state condition. Equation (12) enforces that the number of checkpoints ci is not more than the capacity constraint ci′ for each entrance. It is used to consider real-life factors, e.g., the number of inflow lanes and the size of working spaces. Equation (13) makes sure that the decision variables ci, ∀i∈A∗, are nonnegative integers. It should be noted that the integer nonlinear programming model is hard to solve by classical optimization methods so that a heuristic algorithm is designed in the followed section.


## 3. Solution Algorithm

### 3.1. Equilibrium Algorithm with Queueing

To solve the proposed bilevel programming model, it is always beneficial to solve the lower-level model first as it is embedded in the upper-level model. With a fixed travel demand and a built road network, there will be a stable flow pattern in the lower-level for a given decision from the upper-level. Note that the lower-level is a feedback procedure between trip distribution and traffic assignment with queueing. The method of successive averages (MSA) can be used to achieve system equilibrium. An initial trip distribution matrix can be produced by a multinomial logit model with initialized origin-destination (OD) pair travel times. The trips are then assigned the road network by the Frank-Wolfe algorithm. The link travel flows and link travel times can be generated. In addition, queueing delay times can be determined with predicted traffic flows at entry links. The generalized travel time of each entry link includes link travel time and queueing delay time. According to Wardrop’s first principle of route choice, also known as user equilibrium, traffic arranges itself in congested networks such that all used paths between an OD pair have an equal and minimum cost. Therefore, Dijkstra’s algorithm is used to update OD pair travel times. These times are then fed back to the multinomial logit model to generate a new trip distribution matrix. However, this matrix cannot be assigned to the road network directly. The convergence of direct or naive feedback is usually impossible. An averaging of successive trip distribution matrix is necessary. Although there are some successful applications of constant weights, the convergence is usually not guaranteed. Therefore, the MSA with decreasing weight is used here to update the trip distribution matrix, which is the reciprocal of the iteration number. The updated matrix is further assigned road network. The iteration process continues until the successive matrices are quasi-equal. The convergence is generally measured by the squared root of the relative gap. If a predetermined tolerance is achieved, terminate the iteration. The stable state is known as the transportation system equilibrium. The resultant traffic inflows at all the entry links then go into the upper-level model. Figure3 shows the flowchart of the equilibrium algorithm with queueing.Figure 3
The flowchart of the MSA algorithm.The detailed MSA algorithm is specified step by step as follows:Step 1. Input a checkpoint deployment decision with fixed travel demand and built road network.Step 2. Initialize trip distribution matrix qrs0 with initial OD pair travel time trs0. Besides, let n=1 be the number of iterations.Step 3. Traffic assignment with queueing: the trip distribution matrix qrs0 is assigned to the road network by the Frank-Wolfe algorithm. The link travel flows va and link travel times ta are generated. Note that queueing delay times can be determined with flows at entry links.Step 4. Update the shortest path travel time between an OD pair rs, namely, trs1, by Dijkstra’s algorithm.Step 5. Trip distribution: the multinomial logit model is used to update the trip distribution matrix qrs1:(14)qrs1=Orexpβs+βttrs1∑s∈Srexpβs+βttrs1.Step 6. Average trip distribution matrices qrs1 and qrs0 using decreasing weight are as follows:(15)qrs1=qrs0+1nqrs1−qrs0.Step 7. Convergence identification: check the convergence of trip distribution matrix using the squared root of the relative gap:(16)∑rsqrs1−qrs0qrs02<ε,whereε is a predetermined tolerance. If the convergence condition is satisfied, terminate the iteration and go to Step 9; otherwise, go to Step 8.Step 8. Let qrs0:=qrs1 and n:=n+1. Then, go to Step 3.Step 9. The outputs are the trip distribution matrix qrs1 and the link traffic flow va.


### 3.2. Solution of the Bilevel Programming Problem

The bilevel programming problem is a well-known NP-hard problem that is hard to be solved by classical optimization algorithms. It is challenging that even the upper-level and lower-level are both linear programming, let alone the upper-level is a nonlinear programming model. For example, the traditional gradient-based approaches to solve the optimal cordon toll problem usually fail to converge for larger-scale problems due to multiple optima. This failure led to the development of a heuristic algorithm to determine the optimal toll level and toll location problem. The heuristic algorithm was shown to be successful in solving the cordon toll optimization problem, although it is found to be time-consuming, and there is no proof of global optimum. However, the successful applications of heuristic methods, especially genetic algorithms, have been growing to generate high-quality cordon schemes in the literature [5, 20, 34, 35]. Therefore, a genetic algorithm with an elite strategy is adopted here. Figure 4 shows its flowchart.Figure 4
The flowchart of a genetic algorithm with elite strategy.To be more specific, the detailed genetic algorithm with an elite strategy is specified in steps as follows:Step 1. Initialization: set the parameters used in the genetic algorithm, including population size M, the maximum number of generations Gen, crossover probability pc, mutation probability pm, the notation of generation gen=1, and the portion for elitist strategy pe. Note that the population size depends on the nature of the problem, but typically contains several hundreds of possible solutions.Step 2. Generate a feasible initial population randomly. A chromosome is a solution that consists of m genes. Integer encoding technology is used where a gene stands for the number of parallel checkpoints at an entry link. Generate a chromosome randomly. If it is not feasible, generate another one until it is feasible. A total number of M viable chromosomes are generated, scattering the entire range of possible solutions.Step 3. Selection operation: the objective function of the upper-level model is used to work as a fitness function to evaluate the performance of all chromosomes in the population. Note that it is to minimize the total number of checkpoints; the best pe is labeled for elitists, and the worst pe is discarded.Step 4. Crossover operation: the remaining 1−peM chromosomes are used for crossover operation. These parent chromosomes are matched in pairs randomly. The probability of carrying out the crossover is pc. If it is chosen for the crossover, a random gene is identified. If newborn chromosomes are not feasible according to constraints in the upper-level model, try another gene location until they are feasible. These new solutions typically share many of the characteristics of their parents.Step 5. Mutation operation: the probability of carrying out mutation is pm. A random gene is identified for mutation within the domain of definition. If the new chromosome is not feasible, try another gene location until it is feasible.Step 6. Generate the next generation population. After genetic operators, there are still 1−peM feasible chromosomes. The labeled peM elitists are added to ensure the population size M. This allows the best chromosomes from the current generation to carry over the next unaltered. It guarantees that the solution quality will not decrease from one generation to the next. Let the notation of generation be gen:=gen+1.Step 7. Termination judgment: if the maximum number of generations is achieved, that is, gen≥Gen, terminate the iteration process and output the optimal deployment of cordon sanitaire. Otherwise, turn to Step 3.


## 3.1. Equilibrium Algorithm with Queueing

To solve the proposed bilevel programming model, it is always beneficial to solve the lower-level model first as it is embedded in the upper-level model. With a fixed travel demand and a built road network, there will be a stable flow pattern in the lower-level for a given decision from the upper-level. Note that the lower-level is a feedback procedure between trip distribution and traffic assignment with queueing. The method of successive averages (MSA) can be used to achieve system equilibrium. An initial trip distribution matrix can be produced by a multinomial logit model with initialized origin-destination (OD) pair travel times. The trips are then assigned the road network by the Frank-Wolfe algorithm. The link travel flows and link travel times can be generated. In addition, queueing delay times can be determined with predicted traffic flows at entry links. The generalized travel time of each entry link includes link travel time and queueing delay time. According to Wardrop’s first principle of route choice, also known as user equilibrium, traffic arranges itself in congested networks such that all used paths between an OD pair have an equal and minimum cost. Therefore, Dijkstra’s algorithm is used to update OD pair travel times. These times are then fed back to the multinomial logit model to generate a new trip distribution matrix. However, this matrix cannot be assigned to the road network directly. The convergence of direct or naive feedback is usually impossible. An averaging of successive trip distribution matrix is necessary. Although there are some successful applications of constant weights, the convergence is usually not guaranteed. Therefore, the MSA with decreasing weight is used here to update the trip distribution matrix, which is the reciprocal of the iteration number. The updated matrix is further assigned road network. The iteration process continues until the successive matrices are quasi-equal. The convergence is generally measured by the squared root of the relative gap. If a predetermined tolerance is achieved, terminate the iteration. The stable state is known as the transportation system equilibrium. The resultant traffic inflows at all the entry links then go into the upper-level model. Figure3 shows the flowchart of the equilibrium algorithm with queueing.Figure 3
The flowchart of the MSA algorithm.The detailed MSA algorithm is specified step by step as follows:Step 1. Input a checkpoint deployment decision with fixed travel demand and built road network.Step 2. Initialize trip distribution matrix qrs0 with initial OD pair travel time trs0. Besides, let n=1 be the number of iterations.Step 3. Traffic assignment with queueing: the trip distribution matrix qrs0 is assigned to the road network by the Frank-Wolfe algorithm. The link travel flows va and link travel times ta are generated. Note that queueing delay times can be determined with flows at entry links.Step 4. Update the shortest path travel time between an OD pair rs, namely, trs1, by Dijkstra’s algorithm.Step 5. Trip distribution: the multinomial logit model is used to update the trip distribution matrix qrs1:(14)qrs1=Orexpβs+βttrs1∑s∈Srexpβs+βttrs1.Step 6. Average trip distribution matrices qrs1 and qrs0 using decreasing weight are as follows:(15)qrs1=qrs0+1nqrs1−qrs0.Step 7. Convergence identification: check the convergence of trip distribution matrix using the squared root of the relative gap:(16)∑rsqrs1−qrs0qrs02<ε,whereε is a predetermined tolerance. If the convergence condition is satisfied, terminate the iteration and go to Step 9; otherwise, go to Step 8.Step 8. Let qrs0:=qrs1 and n:=n+1. Then, go to Step 3.Step 9. The outputs are the trip distribution matrix qrs1 and the link traffic flow va.


## 3.2. Solution of the Bilevel Programming Problem

The bilevel programming problem is a well-known NP-hard problem that is hard to be solved by classical optimization algorithms. It is challenging that even the upper-level and lower-level are both linear programming, let alone the upper-level is a nonlinear programming model. For example, the traditional gradient-based approaches to solve the optimal cordon toll problem usually fail to converge for larger-scale problems due to multiple optima. This failure led to the development of a heuristic algorithm to determine the optimal toll level and toll location problem. The heuristic algorithm was shown to be successful in solving the cordon toll optimization problem, although it is found to be time-consuming, and there is no proof of global optimum. However, the successful applications of heuristic methods, especially genetic algorithms, have been growing to generate high-quality cordon schemes in the literature [5, 20, 34, 35]. Therefore, a genetic algorithm with an elite strategy is adopted here. Figure 4 shows its flowchart.Figure 4
The flowchart of a genetic algorithm with elite strategy.To be more specific, the detailed genetic algorithm with an elite strategy is specified in steps as follows:Step 1. Initialization: set the parameters used in the genetic algorithm, including population size M, the maximum number of generations Gen, crossover probability pc, mutation probability pm, the notation of generation gen=1, and the portion for elitist strategy pe. Note that the population size depends on the nature of the problem, but typically contains several hundreds of possible solutions.Step 2. Generate a feasible initial population randomly. A chromosome is a solution that consists of m genes. Integer encoding technology is used where a gene stands for the number of parallel checkpoints at an entry link. Generate a chromosome randomly. If it is not feasible, generate another one until it is feasible. A total number of M viable chromosomes are generated, scattering the entire range of possible solutions.Step 3. Selection operation: the objective function of the upper-level model is used to work as a fitness function to evaluate the performance of all chromosomes in the population. Note that it is to minimize the total number of checkpoints; the best pe is labeled for elitists, and the worst pe is discarded.Step 4. Crossover operation: the remaining 1−peM chromosomes are used for crossover operation. These parent chromosomes are matched in pairs randomly. The probability of carrying out the crossover is pc. If it is chosen for the crossover, a random gene is identified. If newborn chromosomes are not feasible according to constraints in the upper-level model, try another gene location until they are feasible. These new solutions typically share many of the characteristics of their parents.Step 5. Mutation operation: the probability of carrying out mutation is pm. A random gene is identified for mutation within the domain of definition. If the new chromosome is not feasible, try another gene location until it is feasible.Step 6. Generate the next generation population. After genetic operators, there are still 1−peM feasible chromosomes. The labeled peM elitists are added to ensure the population size M. This allows the best chromosomes from the current generation to carry over the next unaltered. It guarantees that the solution quality will not decrease from one generation to the next. Let the notation of generation be gen:=gen+1.Step 7. Termination judgment: if the maximum number of generations is achieved, that is, gen≥Gen, terminate the iteration process and output the optimal deployment of cordon sanitaire. Otherwise, turn to Step 3.


## 4. Experimental Study

An experimental study is conducted to verify the effectiveness of the proposed method and algorithm. The Nguyen-Dupuis road network, as shown in Figure5, is commonly used in transportation research to demonstrate various methods. The link characteristics, including free-flow travel time, link capacity, and link length, are shown in Table 1.Figure 5
The Nguyen-Dupuis road network.Table 1
Link characteristics of the Nguyen-Dupuis road network.
LinkaFree-flow time (min)Link capacity (pcu/h)Link length (km)17.08004.0029.08006.0039.08005.00412.08008.0053.08002.0069.08005.0075.08003.00813.08008.0095.08003.00109.08006.00119.08005.001210.08006.00139.08005.00146.08004.00159.08006.00168.08005.00177.08004.001814.08006.001911.08007.00There are two origins and two destinations in the Nguyen-Dupuis network. The predicted travel demands at origin nodes 1 and 4 are 1000 pcu/h and 1000 pcu/h, respectively. That is,O1=1000 pcu/h and O4=1000 pcu/h. All the existing links are labeled from 1 to 19. The destination nodes are 2 and 3 so that the entry links are 11, 15, 16, 19. The problem is to determine the number of checkpoints at each entry link to minimize the investment with a certain level of service.The parameters used in the lower-level model are summarized as follows. The multinomial logit model for destination choices is simplified as(17)qrs1=Orexpβs+βttrs1∑s∈Srexpβs+βttrs1,where βs is traveler preference parameter on destination s and βt is the coefficient parameter of path travel time between O-D pair rs. The values of βs and βt can be calibrated empirically. Here, we set β2=0.5, β3=0, and βt=−0.1. That is, the traveler preference on destination zone 2 is 0.5, and on destination zone 3 is 0, which means that the travelers traditionally prefer destination 2. The coefficient of travel time is −0.1, which means that the travel time is a negative utility. Besides, a traditional link impedance function, named BPR function, is used to accommodate the congestion effect in traffic assignment with the following formulation:(18)tava=ta01+αvaeaβ,a∈A,where ta0 is the free-flow travel time of link a; va is traffic volume of link a and ea is traffic capacity of link a; and α and β are volume/delay coefficient parameters which can be calibrated empirically; they are usually set as α=0.15 and β=1.5 conventionally. The convergence criterion for MSA is set as ε=0.01. A stable transportation system can be achieved for a built road network.The parameters used in the upper-level model are listed as follows. The population size isM=200. The maximum number of generations is Gen=30. The portion for elitists is pe=0.1. The crossover probability is pc=0.1, and the mutation probability is pm=0.5. Although these parameters are conventionally used in genetic algorithms, it is worth tuning parameters to find appropriate settings for the problem. The allowed maximum waiting time at each entry link is set as T=5 min. The maximum number of checkpoints can be set up at each entry link is assumed to be ci′=9,∀i∈A∗. This is for simplicity, and they can be diverse one by one according to their physical conditions. The marginal operation cost per checkpoint per unit time c′ is set to be one without affecting the decision.The calculation is programmed using a popular open-source language R 3.6.3 in a personal computer with Intel Core i7-4790 CPU@3.60 GHz. The programming code can be provided on request. The running time is 2.76 hours. The results are shown in Table2. The predicted traffic volumes at entry links work as the average arrival rates of the queueing model. Note that traffic volumes are usually measured in hours while the arrival rates are typically measured in minutes. Therefore, unit conversion is needed. The average service rate for a single checkpoint is assumed to be μ=2 pcu/min. That is, the checkpoint averagely tests two passenger car units per minute.Table 2
The predicted traffic inflow volume and determined checkpoint deployment.
Entry linkTraffic inflow volume (pcu/h)Number of checkpointsQueueing delay (min)11102891.8461529330.9771610114.4741957854.780It is shown that traffic inflow volumes are different at entry links. The maximum one is 1028 pcu/h at entry link 11, while the minimum one is only 101 pcu/h at entry link 16. As a result, the number of checkpoints needed at each entry link will be different. The maximum number is 9 at link 11, and the minimum number is 1 at link 16. The total number of checkpoints is 18, which is the minimum cost to maintain a certain level of waiting. In this way, the maximum waiting time at each entry link will not exceed 5 minutes. However, attention should be paid to the issue of choosing the best parameters for the GA based methods, i.e., generation number, population number, the probability of crossover, and the probability of mutation.It would be useful to evaluate the impact of average servicer rates and demand levels on the optimal design of cordon sanitaire. Therefore, a sensitivity analysis varying the average service rateμ for a single checkpoint and different demand levels on the total number of checkpoints is investigated. The original travel demand, O1=1000 pcu/h and O4=1000 pcu/h, is regarded as a benchmark. The demand levels are tested at 60%, 80%, 100%, 120%, and 140%, respectively. The average service rate μ usually depends on the development of technologies (e.g., the advanced testing devices). It varies from 2 pcu/min to 5 pcu/min. The adopted parameters are identical to previous experiment. The results are shown in Table 3 where the content is the desired number of checkpoints.Table 3
A sensitivity analysis varying the average service rates and demand levels.
Demand levels (pcu/h)Average service rate (pcu/min)234560%∗1000,10001186580%∗1000,10001410861000,1000181297120%∗1000,10002114119140%∗1000,100024161310The results show that the desired number of checkpoints increases with demand levels for each average service rate. It is natural that more checkpoints are needed for increased travel demand. With the development of technologies, the average service rate could keep increasing. The results show that the desired number of checkpoints decreases with average service rate for each travel demand level. It verified that less checkpoints are desired for more efficient testing.


## 5. Conclusions

The COVID-19 pandemic has caused global social and economic disruption. Many authorities set up a cordon sanitaire around an area with high population density or an area experiencing an epidemic to prevent the spreading of infectious disease. Once the cordon is established, people are no longer allowed to enter or leave the area without testing. In the most extreme form, the cordon is not lifted until the infection is extinguished. It is much more efficient to keep the disease from being introduced from the very beginning. Public health specialists have included cordon sanitaire along with quarantine and medical isolation as “nonpharmaceutical interventions” designed to prevent the transmission of microbial pathogens.The line around a cordon sanitaire is usually set up at each entry link. The cordon sanitaire is demonstrated to be an effective way to battle the affliction. However, some severe problems turn up, such as the long waiting time for checking and the massive investment for checkpoints. This is a resource allocation problem in principle that deserves to be investigated systematically. Although the cordon pricing problem is analogous to this problem, it has not been explored yet in literature.This paper proposed a method to determine the optimal deployment of checkpoints at each entry link around the cordon sanitaire with an acceptable queueing delay time constraint. A bilevel programming model is formulated where the lower-level model is transport system equilibrium with queueing, and the upper-level model is queueing network optimization. To be more specific, the lower-level is a feedback procedure between trip distribution and traffic assignment with queueing. The iteration continues until the transportation system equilibrium is achieved. Note that a multinomial logit model is used for trip distribution, and the user equilibrium model is used for traffic assignment with queueing. The traffic flow and waiting time at each entry link can be predicted. The upper-level is queueing network optimization based on the predicted traffic flow and waiting time at the lower-level. The traffic inflow at each entry link is regarded as an average arrival rate in the queueing model. Note that there could be many entry links, and theM/M/c queueing model is used to analyze each entry independently of the others. An integer nonlinear programming model is built where the objective is to minimize the total investment of checkpoints, and the constraint is to make the maximum waiting time within a predetermined service level.A heuristic algorithm is proposed to solve the bilevel optimization model. The method of successive averages (MSA) is used to achieve a transport system equilibrium with queueing at the lower-level model. Note that the conventional Frank-Wolfe algorithm is used for traffic assignment with queueing. Based on the predicted traffic flow and queueing delay time at each entry link from the lower-level model, a genetic algorithm with an elite strategy is designed to solve the integer nonlinear programming model at the upper-level.An experimental study is conducted, which is the well-known Nguyen-Dupuis road network, to demonstrate the effectiveness of the proposed method and algorithm. Although the test is only limited to a simplified network, the results show that the proposed methods can find at least a satisfying optimal heuristic solution. However, it is worth tuning parameters to find appropriate settings for the problem.The limitation of this research lies in the simplified network, i.e., the Nguyen-Dupuis road network. Without a doubt, a large-scale network with real data will be more convincing. However, the models and methods explored in this research are demonstrated to be valid. In future research, the author would like to study further a variety of related problems, including the queueing equilibrium problem with a given investment budget, the traffic control problem from upstream intersections, and the multi-objective optimization problem.



---

*Source: 5581758-2021-06-03.xml*