# Schedule optimization and staff allocation for airport security checkpoints using guided simulated annealing and integer linear programming

Alexis Brun, Eric Feron, Sameer Alam, Daniel Delahaye

## ► To cite this version:

Alexis Brun, Eric Feron, Sameer Alam, Daniel Delahaye. Schedule optimization and staff allocation for airport security checkpoints using guided simulated annealing and integer linear programming. Journal of Air Transport Management, 2025, 124, pp.102746. 10.1016/j.jairtraman.2025.102746. hal-05398760

HAL Id: hal-05398760

https://enac.hal.science/hal-05398760v1

Submitted on 19 Jan 2026

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Schedule optimization and staff allocation for airport security checkpoints using guided simulated annealing and integer linear programming

Alexis Brun<sup>a,*</sup>, Eric Feron<sup>b</sup>, Sameer Alam<sup>c</sup>, Daniel Delahaye<sup>a</sup>

<figure><img src="image_2.png" /></figure>

## ARTICLE INFO

### Keywords:

- Airport security checkpoint
- Schedule optimization
- Simulated annealing
- Integer linear programming
- Security screening lines
- Staff allocation

## ABSTRACT

Security checkpoints are an important matter of concern for airport operators. When functioning effectively, they not only maintain the airport overall safety at a high level, but also provide passengers with a positive airport experience. The perceived quality of service at the airport greatly depends on the time spent by passengers at the security lines. To ensure optimal safety performance, screening lines have a limited capacity of passengers they can handle. Thus, to prevent extended waiting times for passengers, airports can only adjust the number of simultaneously open check lines. The airport operator must establish optimal schedules for opening security checkpoints and allocating necessary staff. Building upon a prior study focused on predicting the flow of passengers through the security checkpoints, this paper explores simulated annealing algorithm in conjunction with a queue simulator and an integer programming algorithm to establish the most effective opening schedule for security checkpoints based on the prediction given by this previous study. The presented approach also determines the best allocation for dedicated staff based on the forecasted passenger flow. This approach limits the number of open security lines and ensures a waiting time below the maximum limit of 45 min set by the airport. It also complies with the work regulations that security agents are subject to.

## 1. Introduction

In the wake of the Covid crisis, global air traffic is on the up again (International Air Transport Association, 2023). With air traffic back at full capacity, large numbers of passengers are returning to airports. Airport operators are once again having to adapt their procedures to handle the influx of travelers. The quality of service perceived by passengers is directly correlated with the time spent in queues at key points around the airport. One of the major key points that the airport operator can influence are the security checkpoints. In fact, the airport decides how many security agents to hire and how many search lines to open for each security checkpoint throughout the day. In the case of Paris Charles de Gaulle airport, decisions on security agent requirements and scheduling are taken 45 days in advance. Minor adjustments can be made to the schedule on D-7 and D-1, but these are limited and very costly. At Paris Charles de Gaulle airport (CDG), and for the Aéroport de Paris (ADP) group in general, security agents represent a major expense. For the ADP group, according to our interviews with their security teams, total yearly expenditure on security agents is around $120 million. Therefore, allocating the optimal number of security agents is necessary to guarantee low waiting times

at security checkpoints for passengers, while minimizing the number of security agents required. This paper investigates the use of guided simulated annealing to create an optimal opening schedule of the security checkpoints of Paris Charles de Gaulle airport (Fig. 1) based on the passenger flow prediction determined with our previous method (Brun et al., 2022). In addition we propose an optimal staff allocation on the opening schedule determined through annealing. Section 2 presents a brief state of the art, Section 3 summarizes how a security checkpoint is modeled and presents an implementation of a dedicated simulated annealing algorithm. Section 4 presents the method used to allocate the security agents to the checkpoints and Section 5 concludes and suggests future improvements.

## 2. State of the art

### 2.1. Modeling and simulation of security checkpoints

Security checkpoints play a key role in ensuring an airport functions efficiently. The effective functioning of security checkpoints is vital to provide adequate security measures while also ensuring quick

<footnote><sup>a</sup> École Nationale de l'Aviation Civile (ENAC), 7 Avenue Edouard Belin, Toulouse, 31400, France</footnote>

<footnote><sup>b</sup> King Abdullah University of Science and Technology (KAUST), Thuwal, 23955, Saudi Arabia</footnote>

<footnote><sup>c</sup> Nanyang Technological University (NTU), 50 Nanyang Avenue, Singapore, 639798, Singapore</footnote>

<footnote>* Corresponding author.
E-mail address: brunalexis@hotmail.fr (A. Brun).</footnote>
<table><thead><tr><th colspan="2">Nomenclature</th></tr></thead><tbody><tr><td>α</td><td>Penalty coefficient for non-compliance with a constraint</td></tr><tr><td>λ</td><td>Cooling parameter of the simulated annealing</td></tr><tr><td>D</td><td>Duration of a shift</td></tr><tr><td>E</td><td>Internal energy of a material</td></tr><tr><td>E<sub>i</sub></td><td>Energy of a state i</td></tr><tr><td>f</td><td>Criterion function of the simulated annealing</td></tr><tr><td>K</td><td>Number of state explored by the simulated annealing at each temperature step</td></tr><tr><td>k<sub>b</sub></td><td>Boltzmann constant</td></tr><tr><td>MaxLine</td><td>Maximum number of screening lines available at a checkpoint</td></tr><tr><td>N</td><td>Neighbor function</td></tr><tr><td>n<sub>s</sub></td><td>Number of shift s</td></tr><tr><td>n<sub>pt</sub></td><td>Number of security teams required to handle the passengers at checkpoint p at time t</td></tr><tr><td>N<sub>Shifts</sub></td><td>Total number of shifts</td></tr><tr><td>N<sub>tot</sub></td><td>Total number of iterations of the simulated annealing</td></tr><tr><td>P</td><td>Set of security checkpoints</td></tr><tr><td>p</td><td>Checkpoint</td></tr><tr><td>S</td><td>State space</td></tr><tr><td>s</td><td>Shift</td></tr><tr><td>s<sub>c</sub></td><td>Initial state</td></tr><tr><td>T</td><td>Internal temperature of a material</td></tr><tr><td>t</td><td>Time step</td></tr><tr><td>T<sub>0</sub></td><td>Initial temperature of the simulated annealing</td></tr><tr><td>T<sub>f</sub></td><td>Final temperature of the simulated annealing</td></tr><tr><td>T<sub>max</sub></td><td>Maximum waiting time tolerated for a passenger</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Overview of Paris CDG Airport. (A full detailed map of the airport including the different security checkpoints can be found in Groupe ADP, 2024).</figcaption></figure>

processing of passengers (Knol et al., 2019). To manage the efficiency and safety of passengers passing through a security checkpoint, it is necessary to construct a model of the checkpoint. In 2011, Leone and Liu proposed a model for the screening of passengers in the United States (Leone and Liu, 2011). In their work, they modeled the time spent on each step like X-ray scan, manual searching, explosive trace detectors etc. They measured the performance of the

security checkpoint using passenger waiting time as a metric. Their objective was to reduce this time to ten minutes or less. The proposed model tends to maximize the “primary inspection” (X-ray etc.) which are faster and reduce the number of secondary inspection (explosive detector, manual search) which take longer time, without reducing the overall level of security. As shown in Leone and Liu (2011), the overall screening procedure at the security checkpoints in airport can be split into several elements. The checkpoint’s operation can be altered to enhance performance. Objective evaluations are necessary since security screening is different among passengers. Business travelers and large families require different levels of attention and services at checkpoint. It is possible to implement different security policies for distinct passenger types if the airport’s configuration allows for it. Simulations done by Mujica Mota et al. (2021) indicate that the operational efficiency of Mexico City airport can be improved by testing a passenger categorization model. Moreover the structure of a checkpoint affects its processing capacity. Security checkpoints at airports have varying queue layouts. Li et al. (2018) describe and analyze the different queue layouts and their effects on checkpoint capacity. Their findings enable the identification of the most effective checkpoint configurations for a given airport. The large number of components of a security checkpoint makes its analysis and modeling complex. This problem of simulating the behavior of a security checkpoint can be addressed using queuing theory. Zhang et al. (2011) published a method based on this principle, for which, authors modeled queues of passengers between the US-Canadian border. They created a two stage queuing model, modeling the primary inspection and the secondary inspections as in Leone and Liu (2011). They calculated the optimal proportion of secondary inspections needed to get an optimal waiting time for passengers and a checkpoint compliant with the security requirement. However, the limitations of this kind of queuing model have been shown by Stollez on different airport queues (Stolletz, 2011). He showed that, given the very specific profile of demand in airports, standard queuing models quickly reach limitations. These limitations were also mentioned by Zhang et al. (2011), who indicated that if the distribution of passenger flow differs too much from a Poisson distribution, standard queuing models became less efficient. To go beyond the estimates that may be obtained using standard, but restricted, queueing models and associated “closed-form” results, it is profitable to create a full simulation of a security checkpoint to perform on it any type of optimization work needed. Perez et al. (2021) used a simulation approach to optimize the resources allocation at the different security checkpoints. In their paper the authors indicates that one of the major issues is the uncertainties of the passenger flow at security checkpoints. In the absence of a satisfactory passenger flow prediction model, they incorporate uncertainty directly into their simulation. In that way all the decisions about staff allocation are made taking into account the uncertainties in the passenger arrival model. Thanks to their method, authors achieved a great reduction of the passenger waiting time during screening compared to benchmark scenarios. In fact, a simple change in one of the components of a checkpoint can result in a very different operation of the checkpoint. To address such a change, Wilson et al. created the Security Checkpoint Optimizer (SCO) (Wilson et al., 2006). In their paper, the authors present a methodology capable of simulating a change in the screening process at a security checkpoint. With this method, airport operators can optimize their process without the need for testing it each time a change is introduced. To model the complete checkpoint, Ruiz and Cheu (2020) build a model of each component, allowing the simulator to be adapted to any configuration. With their approach, they can simulate diverse scenarios and determine the performance of each checkpoint configuration such as the size of the queue or the mean waiting time. Control and estimation of queue size can be achieved iteratively through methods that include Markov chain models. These processes also take into account the incorporation of probabilities associated with the number of passengers processed over time (Chiti et al., 2018). Kierzkowski and Kisiel (2017) developed
a security control system model for Wroclaw Airport, determining key parameters for passengers. Their algorithm computes the average time spent by passengers at the checkpoint and simulates security agents requirements to limit queue size. Depending on the specific criteria (such as queue size or queue time), their method can be utilized to establish varying security agent schedules. They implemented their model into the management system of the security checkpoints at the airport and, according to their computational model, they were able to increase security checkpoint capacity from 750 passengers per hour to 1025 passengers per hour.

## 2.2. Security staff allocation

Once the checkpoint's operation has been properly modeled, the necessary staff must be identified to ensure its efficient operation. The allocation of security personnel to various checkpoints can be viewed as an optimization problem. To achieve cost-effectiveness, the airport management aims at minimizing its personnel. Simultaneously, the airport aims to assign adequate personnel to manage passenger traffic while ensuring that the queue size and waiting time remain reasonable and security is warranted. To efficiently distribute staff across checkpoints, accurate passenger flow predictions are necessary. Hanumantha et al. (2020) utilized flight schedules and a learning model to enhance the estimate provided by the schedule. A mixed integer programming model was employed by the authors to determine the optimal configuration for operating security checkpoints and assigning security agents. Linear Integer optimization models are attractive because they can, in theory, run the optimization process to optimality through branch-and-bound methods, for example. However, their magnitude and complexity rise quickly with the number of variables. If problems become excessively large, alternate methods may be preferred. Metaheuristics can generate high-quality solutions for large problems in a reasonable amount of time. Valeva et al. (2017) explain how metaheuristics are utilized to optimize workforce planning for a manufacturer. Their model enables the fast computation of quality outcomes, even for large instances that would be unmanageable with an Integer Linear Programming (ILP) model even with the best solver available. More recently, Scozzaro et al. proposed a method to optimize the staff allocation at security checkpoints in case of disruptions (Scozzaro et al., 2022). In this article, the authors consider the situation of an access mode disruption at Paris Charles de Gaulle airport and describe an optimization method to re-allocate the staff at the security checkpoints. Their numerical models indicate that, in case of an access mode disruption, re-allocating the staff using their approach can reduce the passenger wait time by more than 70%.

# 3. Security checkpoints schedule

This section presents the modeling of the operation of a security checkpoint at Paris Charles de Gaulle airport. It then presents the method used to generate security checkpoint schedules, the associated results and a comparison with the method used at the airport.

## 3.1. Model

At Paris Charles de Gaulle airport, each security checkpoint is divided into screening lines, whose number depend on the size of the corresponding boarding areas. The airport operator is free to determine the desired number of lines to open for each checkpoint. The number of lines opened simultaneously during a checkpoint is dependent of the checkpoint's size and the availability of security agents at that time. At Paris CDG airport, the number of security agents to be hired for a particular day is determined 45 days in advance. Passenger flow is forecast by the airport based on data available more than 45 days in advance, which is quite limited. In addition to historical data and airport experience, the only data available that far in advance is the

flight schedule. This schedule gives a fairly accurate idea of the number of flights the airport will have to handle, but it does not include certain important tactical information, such as the gate to which each flight will be assigned. Several models have been developed to forecast passenger flow. Monmousseau et al. (2020) introduced a method that employs recurrent neural networks. The network consists of 200 Long Short Term Memory (LSTM) cells, which are designed specifically for handling time series predictions. However, one drawback of these networks is the large amount of data required for training and the high computational power needed. In this paper, we use the predictions generated by a dense neural network model that we proposed to address this particular issue (Brun et al., 2022). One of the primary advantages of the straightforward architecture of this compact, dense neural network is that it requires only minimal computational power to train effectively. This low computational power enables experimentation with multiple input and output scenarios to align with the requirements of the staff allocation problem. Using this network, it is possible to adjust the time step of the time series prediction to match the precision required for simulating the security checkpoint. To model passenger flow behavior at the security checkpoint, a straightforward model has been implemented. The checkpoint is modeled as a First in First Out (FIFO) queuing model and fed with a general FIFO queue. This model, adapted from the generic queuing model of Neufville et al. (2013), is illustrated by Fig. 2. Passengers arrive at the security checkpoint and join the general queue. They are then directed to available screening positions and wait to be processed by agents (Queue in). The next step, “Process,” is the activity of agents screening the passengers.

The screening of passengers and their luggage is shown in Fig. 3. On the one hand, passengers pass through a metal detector, which will send an alert to security staff if any metal is detected on them. The detector also activates if the passenger requires special inspection with an explosives trace detector. Finally, the detector is also activated at random, so that passengers are regularly searched by hand. There are therefore several options for a passenger passing through the checkpoint: simply pass through the metal detector, undergo an additional manual search, undergo an additional detection of explosive traces, or both. Baggage, on the other hand, systematically passes through an X-ray scanner. If the security officer looking at the scan thinks it is necessary, a manual search of the baggage will be carried out. At present, processing is represented by a constant flow, or by the number of passengers that can be handled per unit of time. According to CDG operators, one screening line can process up to 120 passengers per hour. For future studies, modifications could be made to the “Process” section to account for the potentially more complex behavior of the screening process such as differentiating processing time according to passenger type,

<figure><img src="image_4.png" /><figcaption>Fig. 2. Model of a security checkpoint at Paris CDG airport.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 3. Flow chart of a screening line of a checkpoint at Paris CDG Airport. The blue cells represent items relating to passengers and the orange cells represent items relating to their baggage. The entry and exit of the line are indicated by a green and a red cell respectively. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

or adding uncertainty to processing time, or introducing probabilities of secondary inspections (Leone and Liu, 2011). The global structure of the checkpoint model can be extended to accommodate more complex airport checkpoint configurations, including passenger differentiation approaches like those proposed by Mujica Mota et al. (2021), priority or dedicated queues for first and business class passengers, and dedicated queues for connecting or delayed passengers.

The operator's decision process can be easily modeled with this security checkpoint model. At the strategic level, the operator determines the number of lines to be opened simultaneously at each security checkpoint during each hour of the day and each day of the week. Reassigning security agents every 15, 10, or 5 min, for example, is not feasible. Asking an agent to change positions every 10 min is not only an uncomfortable working environment, but the travel time between security checkpoints makes this type of reassignment impossible. For each security checkpoint, the schedule for opening lines can be modeled as a list of 24 positive integers, with each integer representing the number of screening lines to be opened during every hour of the day. But to account for all passengers going through security on a given day a list of 24 integers is not enough. In fact, the airport's data indicates that some passengers, due to very early or very late flight hours, may go through the security checkpoint on the day before or after their flight in case it is delayed. Although most passengers arrive two hours before their flight, some arrive as early as six hours ahead or three hours late (Fig. 4). Our list of 24 integers must therefore be extended to include passengers arriving between 6 p.m. on the previous day and 3 a.m. on the following day, which increases its size to 33 positive integers. Once the problem is modeled, assuming that no more than 10 screening lines are available at each checkpoint, there are 10³³ staffing configurations per security checkpoint. While using a very efficient FIFO simulator, the large number of possible lists prevents us from employing an exhaustive approach (Brute Force) to find the best configuration. To efficiently explore this large state space, an efficient approach can be found in metaheuristics. Metaheuristics yield favorable results on combinatorial and nonlinear optimization problems while maintaining a reasonable computational time, even on large-scale instances (Gendreau and Potvin, 2010)(Hussain et al., 2018). In the following, we discuss the simulated annealing method, which we will use because of its successful implementation to solve many optimization problems (Hanafi and Kozan, 2014)(Mahmudy, 2014)(Islami et al., 2017).

## 3.2. Simulated annealing

Simulated annealing is an optimization method that draws inspiration from the process used in metallurgy, where a substance is heated

<figure><img src="image_6.png" /><figcaption>Fig. 4. Percentage of passenger arriving at security checkpoint in function of the time before the departure time of their flight.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 5. Diagram of a material reaching a state of minimum energy (crystalline) by slow cooling (Delahaye et al., 2018).</figcaption></figure>

and then gradually cooled to reduce its internal energy and increase its strength. (Fig. 5).

This industrial process was transposed into an optimization technique, enabling the identification of extrema for a given function. Kirkpatrick et al. (1983) completed this transposition in 1983. The analogy with the physical annealing method requires the minimized function to represent the material's internal energy (E) at a particular temperature (T). The methodology initiates the process from a starting point within the system and makes slight modifications to produce a new state. Once the state improves the criterion, it is accepted and becomes the new current state of the system. Simulated annealing is valuable as it permits the acceptance of points in a space that deteriorate the criterion with a set probability. Metropolis et al. (1953) described the probability of accepting a deteriorated state Eq. (1). Given an initial state i of energy Eᵢ and a new state j of energy Eⱼ, if Eⱼ ≤ Eᵢ then j improves the criterion and it is accepted. Otherwise j is accepted with probability

$$P(j \text{ accepted}) = e^{\frac{(E_j - E_i)}{k_b T}} \quad (1)$$

Where T is the temperature of the system in Kelvin and k_b is Boltzmann's constant ($k_b = 1.38 \times 10^{-23} J \cdot K^{-1}$).

Accepting a state that degrades the criterion can prevent the optimization process to be trapped in a local minimum and allows for exploration of a larger area of the state space. The probability of accepting such a state increases with higher temperature, similar to how
higher temperature leads to increased atom mobility in metals. And just like annealed metal, the algorithm's temperature *T* will decrease with every iteration, resulting in lower and lower acceptance probabilities. At each temperature stage, numerous neighboring operations and evaluations may be conducted. The greater the number of operations, the more extensive the exploration of the state space. Nevertheless, the higher the number, the longer the algorithm's execution time. This number of evaluations at each temperature step will be denoted as *K*. Under these conditions, simulated annealing is asymptotically optimal, i.e. with sufficient iteration successive solutions converge to the optimal solution (Granville et al., 1994).

### 3.2.1. Procedure

We are considering a state space *S*, an initial state $s_c \in S$, and a function *f* defined on *S* that have to be minimized. We are also considering a neighborhood function *N* which associates *N(s)* with a neighbor in *S* of the element *s*. In addition, we are considering the cooling parameter $\lambda$ and the number of states explored at each temperature step *K*.

Under these conditions the simulated annealing cooling procedure proceeds as in Algorithm 1 (Delahaye et al., 2018). The ending criterion of this method is a low enough temperature to stop the annealing process when reached by the cooling process. This final temperature is denoted $T_f$.

<caption>**Algorithm 1 Cooling Procedure of the Simulated Annealing**</caption>

Require: $s_c, T_0, T_f, N, f, \lambda, K$
while $T > T_f$ do
for $k \leftarrow 1$ to $K$ do
    $s' \leftarrow N(s_c)$
    if $f(s') < f(s_c)$ then
        $s_c \leftarrow s'$
    else
        $r \leftarrow random(0, 1)$
        if $e^{\left(\frac{f(s_c)-f(s')}{T}\right)} \ge r$ then
            $s_c \leftarrow s'$
        end if
    end if
    end for
    $T \leftarrow \lambda T$
end while
return $s_c$

### 3.2.2. Definition of the annealing parameters

As described in Section 3.1, each element of the state space for security checkpoints consists of a list of 33 integers ranging from 0 to the maximum number of simultaneous screening lines available (assumed to be 10).

The neighborhood operator *N* is defined in Algorithm 2 and displayed on Fig. 6:

<caption>**Algorithm 2 Neighborhood Operator**</caption>

Require: *s*, *MaxLine*
    *index* ← Random integer ∈ [0, *length*(*s*)]
    *s[index]* ← Random integer ∈ [0, *MaxLine*]
    *return* *s*

Similarly, the cooling process is controlled by a geometric law with the parameter $\lambda$. This parameter can be adjusted between 0 and 1, with a smaller value of $\lambda$ resulting in a faster decrease in temperature, leading to a quicker program termination. On the other hand, if it approaches 1, the program explores more states, leading to an increase in both execution time and the quality of the resulting solution.

By recording the final annealing temperature chosen by the user as $T_f$, we can calculate the total number of states explored during the process. This number is represented as $n_{tot}$. According to the geometric

<figure><img src="image_8.png" /><figcaption>Fig. 6. Neighborhood Operator application example.</figcaption></figure>

<caption>**Table 1**</caption>

Mean and standard deviation of the number of states explored per second by the simulated annealing.

<table><thead><tr><td></td><td>Mean</td><td>Standard deviation</td></tr></thead><tbody><tr><td>States explored/sec</td><td>46.12</td><td>11.14</td></tr></tbody></table>

law of cooling :

$$T_{n+1} = \lambda T_n \quad (2)$$

With $T_0$ the initial temperature, $T_f$ the final temperature and $n_T$ the total number of temperature steps :

$$T_f = \lambda^{n_T} T_0 \quad (3)$$

And the total number of states explored is then given by :

$$n_{tot} = \frac{K(\ln(T_f) - \ln(T_0))}{\ln(\lambda)} \quad (4)$$

To link the number of states explored by simulated annealing to its execution time, we need to determine the number of states explored as a function of time. The average obtained and its standard deviation are given in Table 1. Using this number of states explored per second, we can calculate the execution time of simulated annealing for each pair of $\lambda$ and $K$. These execution times are given in Fig. 7.

To choose the best pair of parameters, we need to find the right balance between the two. On the one hand, if $\lambda$ is too small, simulated annealing will quickly reach its ending criterion and explore too few states, especially towards the end of the run, when the solutions explored are generally of good quality. Similarly, if $K$ is too small, too few neighbors will be explored at each temperature step, which is problematic at the start of the run. We thus lose one of the advantages of simulated annealing, which is the exploration of states that degrade the criterion when the temperature is high. To find the best pair, we need to have the largest $\lambda$ and $K$. By limiting the execution time to 30 min and setting the ending criterion to $T_f = \frac{T_0}{10000}$, the pair chosen for this study is:

$$\lambda = 0.95$$

$$K = 500$$

The number of states explored is then:

$$n_{tot} = \frac{500(\ln(\frac{T_0}{10000}) - \ln(T_0))}{\ln(0.95)} \approx 89781. \quad (5)$$

It can be seen on Fig. 7 that this pair of parameters gives an execution time slightly in excess of 30 min, but given the high standard deviation of the number of states explored per second (see Table 1) this slight deviation can be tolerated.

The initial temperature $T_0$ should be sufficiently high to allow for broad state space exploration during annealing. Nevertheless, as the initial temperature increases, so does the final temperature. Acceptance of states that violate the criterion may occur at a high final temperature when it is no longer needed. To identify the initial temperature, a deliberately low starting temperature should gradually increase until a sufficiently high state acceptance rate is attained. This procedure for “heating” is outlined in Algorithm 3 and illustrated in Fig. 8.

The objective function utilized in annealing aims to simulate solution quality from the perspective of airport operations. A quality
<table><caption>Fig. 7. Average execution time of simulated annealing as a function of cooling parameter $\lambda$ and number of evaluations at constant temperature K. The green boxes correspond to pairs with an execution time of less than 30 min, and vice versa for the red boxes. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</caption><thead><tr><th>λ</th><th>100</th><th>200</th><th>300</th><th>400</th><th>500</th><th>600</th><th>700</th><th>800</th><th>900</th><th>1000</th></tr></thead><tbody><tr><th>0,7</th><td>56</td><td>112</td><td>168</td><td>224</td><td>280</td><td>336</td><td>392</td><td>448</td><td>504</td><td>560</td></tr><tr><th>0,75</th><td>69</td><td>139</td><td>208</td><td>278</td><td>347</td><td>417</td><td>486</td><td>555</td><td>625</td><td>694</td></tr><tr><th>0,8</th><td>89</td><td>179</td><td>268</td><td>358</td><td>447</td><td>537</td><td>626</td><td>716</td><td>805</td><td>895</td></tr><tr><th>0,85</th><td>123</td><td>246</td><td>369</td><td>492</td><td>614</td><td>737</td><td>860</td><td>983</td><td>1106</td><td>1229</td></tr><tr><th>0,9</th><td>190</td><td>379</td><td>569</td><td>758</td><td>948</td><td>1137</td><td>1327</td><td>1516</td><td>1706</td><td>1895</td></tr><tr><th>0,91</th><td>212</td><td>424</td><td>635</td><td>847</td><td>1059</td><td>1271</td><td>1482</td><td>1694</td><td>1906</td><td>2118</td></tr><tr><th>0,92</th><td>240</td><td>479</td><td>719</td><td>958</td><td>1198</td><td>1437</td><td>1677</td><td>1916</td><td>2156</td><td>2395</td></tr><tr><th>0,93</th><td>275</td><td>550</td><td>826</td><td>1101</td><td>1376</td><td>1651</td><td>1926</td><td>2201</td><td>2477</td><td>2752</td></tr><tr><th>0,94</th><td>323</td><td>646</td><td>968</td><td>1291</td><td>1614</td><td>1937</td><td>2259</td><td>2582</td><td>2905</td><td>3228</td></tr><tr><th>0,95</th><td>389</td><td>779</td><td>1168</td><td>1557</td><td>1947</td><td>2336</td><td>2725</td><td>3115</td><td>3504</td><td>3893</td></tr><tr><th>0,96</th><td>489</td><td>978</td><td>1468</td><td>1957</td><td>2446</td><td>2935</td><td>3424</td><td>3914</td><td>4403</td><td>4892</td></tr><tr><th>0,97</th><td>656</td><td>1311</td><td>1967</td><td>2623</td><td>3278</td><td>3934</td><td>4590</td><td>5245</td><td>5901</td><td>6556</td></tr><tr><th>0,98</th><td>989</td><td>1977</td><td>2966</td><td>3954</td><td>4943</td><td>5931</td><td>6920</td><td>7908</td><td>8897</td><td>9885</td></tr><tr><th>0,99</th><td>1987</td><td>3974</td><td>5961</td><td>7948</td><td>9935</td><td>11922</td><td>13909</td><td>15896</td><td>17883</td><td>19870</td></tr></tbody></table>

### Algorithm 3 Heating process

Require: $s, T, N, f, K, AcceptRate$
$r \leftarrow 0$

while $r < AcceptRate$ do

count $\leftarrow 0$

for $k \leftarrow 1$ to $K$ do

$s' \leftarrow N(s)$

if $f(s') < f(s)$ then

count $\leftarrow count + 1$

else

if $e^{(f(s)-f(s'))/T} \ge 0.5$ then

$r \leftarrow r + 1$

end if

end if

end for

$$r \leftarrow \frac{count}{K}$$
$$T \leftarrow 1.5 \times T$$

end while

return $T$

<figure><img src="image_9.png" /><figcaption>Fig. 8. Diagram of the simulated annealing heating procedure.</figcaption></figure>

solution from the operator's standpoint involves a schedule that reduces passenger wait times while also limiting the number of simultaneously opened lines. The maximum time that passengers spend in the queue can be determined using the First in First Out (FIFO) simulator, as described in Section 3.1. The objective function, which represents the

quality of the solution, can be calculated in a naive manner as

$$f(s) = \sum_{i \in s} i + FIFO(s) \quad (6)$$

where $s$ denotes the state proposed by the annealing algorithm, in our case a list of 33 integers described in Section 3.1. $i$ represents the number of simultaneously opened lines at a time step of $s$, and FIFO($s$) stands for the maximum time that passengers spend in the security checkpoint queue, calculated by the simulator using an opening schedule described by $s$. However, the current model assigns equal weight to both an open security line and an extra minute of passenger waiting time, but assigning different weights to each part of the objective function is possible. Subsequent discussions with airport operators revealed a better model that emphasizes passengers' waiting times within a specified range of acceptability, rather than solely minimizing them. The maximum allowable waiting time for a passenger is a parameter determined by the airport based on various factors. These factors include the average connecting time, airport layout, and number of passengers. For modeling purposes, we will refer to this maximum allowable waiting time as $T_{max}$. Taking into account this new parameter, the objective function for the annealing process is

$$f(s) = \sum_{i \in s} i + \alpha \max(0, FIFO(s) - T_{max}). \quad (7)$$

An extra parameter, $\alpha$, has been incorporated into the objective function. This parameter allows adjustment for penalizing overtime $T_{max}$ to a greater or lesser extent. For the remainder of the study, the value of the $\alpha$ parameter will be set to 100. In this form, the function enables the annealing process to initially decrease the waiting time below the $T_{max}$ threshold before restricting the number of simultaneously opened security lines.

To begin the simulated annealing process, the initial state $s_c$ must be defined for the simulated annealing algorithm to generate neighboring states and continue the optimization process. While initial states are typically generated randomly, a different approach can yield better results. Each security checkpoint has $10^{33}$ possible states, but with the parameters specified in Section 3.2.2, Eq. (4) gives us that only $n_{tot} \approx 89781$ states will be explored. To limit the exploration of trivially bad states and ultimately obtain a better-quality solution, it is advisable to start the simulated annealing from a good starting point rather than a randomly generated one. To be of interest, however, the starting point needs to be determined very quickly. A greedy heuristic has been used to efficiently determine the starting point for the annealing. The heuristic starts by opening all security lines at every time step, and then gradually closes them until the $T_{max}$ limit is exceeded. Algorithm 4 provides a detailed description of this heuristic.
<figure><img src="image_10.png" /><figcaption>**Fig. 9.** Example of Start Schedule for the Annealing created with the Greedy Heuristic. Each line represents a checkpoint identified by its Id. Red boxes correspond to time steps when the checkpoint is closed and green boxes correspond to time steps when the checkpoint is open. Each box contains an integer from 0 to 10 (the assumed maximum number of lines available at each checkpoint) representing the number of screening lines simultaneously open at the checkpoint at that time. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

**Algorithm 4 Greedy Heuristic for Annealing Start Point Creation**

Require: MaxLine, MaxTimeStep, FIFO, $T_{max}$

$s \leftarrow []$

for $k \leftarrow 1$ to $MaxTimeStep$ do
$s += MaxLine$

end for

$s' \leftarrow s$

while FIFO($s'$) < $T_{max}$ do
  index $\leftarrow IndexMax(s')$
  $s'[index] \leftarrow s'[index] - 1$

end while

$s'[index] \leftarrow s'[index] + 1$

$s \leftarrow s'$

return $s$

### 3.3. Results

For the numerical experiments, the simulated annealing algorithm was executed based on the parameters described in the preceding section. The chosen day is derived from our prior work's neural network test dataset (Brun et al., 2022). The initial point of the annealing process achieved through Algorithm 4 is depicted in Fig. 9. As shown in Algorithm 1, simulated annealing involves random elements. First in the generation of neighborhoods (Algorithm 2), then in the condition for accepting new states. In this study, these random elements are not seed-controlled. Thus, simulated annealing is a non-deterministic algorithm, the outcomes may vary from one execution to another. Table 2 presents the results acquired from ten trials compared with the greedy heuristic, which, being deterministic, gives the same result from one run to the next. Table 3 displays the mean and standard deviation of results and execution time. The schedule for opening the security checkpoint, obtained through simulated annealing, is displayed in Fig. 10. The open lines at a given time step are shown as green boxes, the others are shown as red boxes. Each box also contains the number of lines to be open at that time step.

#### 3.3.1. Creation of security line opening schedules

Table 3 indicates that the standard deviations produced by simulated annealing are consistently low. This observation suggests that the optima obtained via simulated annealing are consistent across experiments. Additionally, this method enables a quick determination of the number of lines that need to be opened at various airport security checkpoints. Moreover, we observe that enforcing a strong penalty for exceeding $T_{max}$ in the cost function has allowed us to uphold the corresponding constraint in a systematic manner. Overall, we believe that simulated annealing produces a functional timetable for the security checkpoints at the airport. This timetable can subsequently serve as a constraint in our study to establish specific schedules for each security team.

#### 3.3.2. Comparison of simulated annealing results with airport operational planning practices

At Paris Charles de Gaulle airport, the opening hours for security checkpoints are scheduled according to the following procedure. Airport operators create a prediction with a one-hour time step for the passenger flow, and consider a fixed handling capacity of 120 passengers per hour for each security line. The security line opening schedule is then created to meet the demand for passenger flow. Generally, the flow of passengers over an hour is not evenly divisible by 120. Therefore, the number of open lines is always rounded up to adequately meet the demand. The application of this method for one security checkpoint is illustrated on Fig. 11.

The airport's announced security line handling capacity appears overly optimistic when compared to observed reality. A processing rate of 120 passengers per hour corresponds to an ideal situation, but in reality, this capacity frequently experiences disruptions. For instance, passengers who are unfamiliar with the screening process may have kept a metallic item with them. Additionally, even when operations run smoothly, random additional checks are conducted. The secondary inspections, such as palpation and detection of traces of explosives, described by Leone and Liu (2011), require longer processing time and monopolize the security agents' time, thereby reducing their capacity to manage the flow of passengers. Consequently, the actual processing capacity of a security line falls short of the ideal limit of 120 passengers per hour currently used to plan the opening of security check lines. For the purposes of this study, we utilize a processing capacity of eight passengers per five-minute interval. Consequently, a security line has the potential to process a total of 96 passengers within the span of one hour. This method, processing 96 passengers per hour, was employed on the same test day as that of the simulated annealing approach. An example of a timetable obtained by employing the prevailing methodology at the airport is depicted in Fig. 12. A comparison of the opening schedules generated by the straightforward method of the airport and the simulated annealing method is presented in Table 4. The data was obtained by using the security checkpoint simulator (FIFO) on both schedules. One can see from Fig. 12 that the rise in the number of lines opened is reflected in the maximum number of open lines at the same time. By applying the queue simulation to the airport schedule, it becomes obvious that the maximum waiting time constraint is not met by the schedule. Specifically, one passenger waited for over 2 h, and such an extended waiting period can result in passengers missing their flights. Table 4 also shows that the simulated annealing gives a schedule that keeps the maximum waiting time below 45 min. This reduction is achieved by slightly increasing the total number of lines to be opened during the day by 6%.

With the schedule for opening security checkpoints now established, the subsequent stage of the research will involve accommodating requests to open the checkpoints while adhering to the constraints associated with the security agents' schedules.
<figure><img src="image_11.png" /><figcaption>**Fig. 12.** Example of Security Checkpoint Opening Schedule Created with the Method of CDG Airport with a capacity of 96 passenger per hour per line. Red boxes indicate when the checkpoint is closed, while the green boxes indicate when it is open and the number of simultaneous lines allowed. The yellow boxes represent time steps with a higher number of simultaneously open lines than obtained via simulated annealing. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

any agreements it has with the unions. Despite being legally mandated, these conditions are not consistently enforced. The detrimental effects of 6 h of uninterrupted work and 12 h working day on a security agent's ability to concentrate can have consequences for airport overall security. Dealing with every constraints individually for every security agent at the airport can quickly increase the model's complexity. To address this issue, a standard shift of 4 h of work, followed by a 1-hour break and then 4 more hours of work is proposed. The structure of this standard shift is displayed on Fig. 13. In addition, following interviews with our partners at Paris Charles de Gaulle airport, the suggested shifts largely align with established airport protocols. A more complex modeling that takes into account each individual regulatory constraint is possible. With this type of modeling, each team has a customized shift. However, this version significantly degrades the computation time and results in a schedule that is difficult to apply operationally. In fact, the obtained optimal schedule is very unequal between agent teams in terms of total time present at the airport, actual working time, and number of breaks. The use of standard shifts makes it possible to restore equity between security teams. For each security checkpoint $p$, the simulated annealing process provides the minimum number of security teams required to handle passenger flow for each time interval $t$. This number is denoted as $N_{pt}$. In this study, we assume that a security team represents a group of security agents who enable the operation of a screening line. In this way, we can focus on optimizing the number of teams without having to consider the constraints related to the skills of the various agents in operating the screening line. For shifts meeting the above criteria, we generate a three-dimensional array $S$ such that any element $S(i, p, t) \in S$ equals 1 if shift $i$ assigns a team of agents to position $p$ at time $t$, and 0 otherwise. Finally, we establish integer decision variables $n_s$, denoting the number of shifts $s$ necessary to meet the demand $N_{pt}$. Noting the sets of security checkpoints $P$, time steps $T$, and the total number of created shifts $N_{Shifts}$, the optimization model can be formulated as:

$$ 
\begin{array}{ll}
\min & \displaystyle\sum_{s \in [1, N_{Shifts}]} n_s \\
\text{s.t.} & \displaystyle\sum_{s \in [1, N_{Shifts}]} n_s S(s, p, t) \ge N_{pt}, \quad \forall p \in P, \forall t \in T, \\
& n_s \ge 0, \quad s = 1, \dots, N_{Shifts}
\end{array}
\qquad (8) $$

Note that the total number of shifts generated can be computed directly from the number of security checkpoints $P$, the number of time steps $T$, and the criteria for an acceptable shift with $D$ the duration of a shift. This value is given by the following expression:

$$ N_{Shifts} = P^2 \times (T - (D - 1)) \qquad (9) $$

The solver used to solve this problem is Gurobi version 10.0.2.

## 4.2. Results

### 4.2.1. Application of the method on a test day

The method is tested on a randomly selected day from the neural network's test dataset used to forecast passenger flow (Brun et al.,

<figure><img src="image_12.png" /><figcaption>**Fig. 13.** Example of the structure of the shifts used in the model.</figcaption></figure>

2022). This dataset contains the complete list of flights at Paris Charles de Gaulle airport for every day of the year. For each flight, the dataset contains its theoretical departure time and the boarding room from which it is scheduled to depart, allowing us to determine which security checkpoint will be needed to manage its passengers. The dataset also contains information derived from the chosen day, allowing to determine whether the day in question is a holiday, weekend, etc. This dataset provides good predictive performance for passenger flow at the strategic level with our neural network, but cannot help predict tactical changes such as schedule adjustments due to flight delays or connection disruptions. At this strategic level, the airport can only rely on predictive models to determine the number of passengers it will have to handle and therefore the number of lines of security checkpoints to open, which is why we use the prediction of our neural network to test our method. The minimum number of security teams required is obtained through the simulated annealing, described in Section 3.2. The day used for our experiment had 13 security checkpoints ($P$), 33 time steps ($T$), and used shifts in the format depicted in Fig. 13. In total, there were $N_{Shifts} = 4225$ possible shifts, according to Eq. (9). As shown in Fig. 14, the algorithm can generate a timetable that allocates sufficient personnel to different checkpoints. Nonetheless, the input data coming from predictions generated by the neural network, has limited accuracy and may diverge from the actual passenger flow. To compare the obtained results with the actual passenger flow at the airport on that day, a second simulation was conducted using the observed flow. Simulated annealing was used to redetermine the required number of security agents based on this data. The corresponding schedule for the security agents was then created using the linear programming algorithm. The additional curve in Fig. 14 represents the schedule of security agents created from the second simulation run on the observed flow on that day.

Although we can see directly from Fig. 14 whether a sufficient number of security agent teams have been assigned to meet the demand at each checkpoint, it is also necessary to look at the cumulative demand over the day in the entire airport. In fact, this prediction of the number of security agents is made at the strategic level, several weeks in advance. However, on the day of operation itself, since the neural network's prediction cannot be perfect, there is a gap between the need for security agents and our planning. The question is whether overestimating the need for agents at certain checkpoints can compensate for underestimates at other checkpoints. After all, if there is a
<figure><img src="image_13.png" /><figcaption>**Fig. 14.** Need of security teams, i.e. $N_{pi}$ in the model (blue) vs assigned security teams by the schedule created with the predicted flow (green) vs assigned security teams by the schedule created with the observed flow (orange) on a tested day for each of the boarding rooms of CDG airport. (To avoid overlapping, a minor vertical offset is applied to each curve.). (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

shortage of agents at one checkpoint at a given time, but there is an excess of agents elsewhere, it will always be possible to reassign those agents at the tactical level. Therefore, we need to check whether there are enough security teams at the airport at any given time of the day. Fig. 15 displays a comparison of the total demand for security agent teams and the actual number of teams present at the airport on the day of the test. Fig. 15 shows that the proposed method achieves an adequate number of security teams despite varying constraints such as working time and break schedules.

### 4.2.2. Limitations and discussions

The neural network on which the passenger flow prediction is based cannot make perfect predictions. The gap between prediction and reality could cause simulated annealing to produce an overestimated or underestimated checkpoint opening schedule. Our prior research found that the neural network passenger flow prediction tends to be underestimated (Brun et al., 2022). Therefore, simulated annealing allows opening security checkpoints to be based on an underestimated passenger flow. This issue is illustrated in Fig. 15, which shows two instances

of missing agent teams. The discrepancy is minor and distributed across multiple checkpoints, as demonstrated by Fig. 14. To validate these observations, several tests were conducted over ten consecutive days in February 2023. The method presented was applied on each of these days to predict passenger flow using our neural network. Security line opening schedules were created based on these predictions, and corresponding security agent schedules were established. Table 5 compares the differences in cumulative demand for security agents over these 10 days. This table displays the differences between the number of security agents determined using our model and the actual number required, as determined by the model. The table illustrates that the program's predicted number of required teams closely matches the actual number. The largest relative gap, at 9%, occurred on 2023/02/09. As a result, the prediction errors of the neural network lead to a relatively small discrepancy between the number of agents required and the number returned by the optimization method described. We can also observe a certain consistency in the error, as we can see from Table 5 that the difference between the number of agents required and the number calculated is always negative. It is therefore possible to limit the impact
of this operational error by systematically providing more security agents than the method predicts. For example, by adding 5 more teams of agents (i.e. the average difference of Table 5), we only degrade the result by 5% and limit the consequences of the prediction errors of the neural network. Thus, it is reasonable to conclude that this predictive error would have only a minor impact on operations. Finally, based on the increase achieved through the simulated annealing compared to the airport's previous method those additional teams can be planned without significantly diminishing this improvement.

The criterion used in simulated annealing also can be discussed. In fact, the chosen criterion tells us what the airport operator wants to focus on. In this version, the criterion strongly penalizes exceeding a maximum waiting time, in our example 45 min. This limits the worst-case scenario, but does not take into account, for example, the waiting time of the majority of passengers. This criterion could be modified to ensure that a significant percentage of passengers wait less than ten minutes, for example. The criterion would thus focus on the experience of the majority of passengers, but allow for longer waits in certain rare cases. Under the criterion presented in this study, checkpoints are sometimes opened for only a few passengers, particularly at times between 1 a.m. and 5 a.m. A criterion that focuses on the majority of passengers rather than the worst case would exclude these passengers and reduce the number of lines open in the middle of the night. In addition, the parameters used in the simulated annealing criterion to balance passenger waiting time with the number of open lines can also be discussed. In our study, the α parameter was set high enough to ensure that the maximum waiting time constraint was always met. Further discussion with airport operators, in particular to determine the cost of opening a line, would allow us to evaluate this parameter more accurately and to better balance the objective between reducing waiting time and minimizing the number of open lines. Similarly, the value of $T_{max}$ is arbitrary and it is possible that a slightly higher value could be considered tolerable by the airport and allow the number of open lines to be further reduced. In fact, our results show a slight increase in the number of lines to ensure a reduction in waiting time below the $T_{max}$ limit. In practice, it is up to the airport management to decide whether the gain is worth the cost. In this study, this increase of a few percent was considered acceptable, given the significant reduction in maximum waiting time. Finally, this model ensures that there are enough agents at the airport on that day to ensure that all checkpoints have their lines open. However, this model remains at the strategic level and cannot take into account tactical events and constraints, such as the reassignment of agents on the same day or the day before. This tactical reassignment problem is very different from the strategic version, mainly because the number of agents available on that day is fixed. What is more, if we consider additional constraints, such as a disruption, we need to do more than just reassign agents. This problem has been the subject of dedicated studies, notably Geoffrey Scozzaro's Ph.D. thesis (Scozzaro, 2024), which considers a disruption in airport access modes and optimizes checkpoint reconfiguration and security agent reassignment to minimize the impact on passengers.

## 5. Conclusion and perspectives

The study concludes that effective scheduling of security agents can alleviate passenger congestion at Charles de Gaulle airport.

A process based on predictions of the passenger flow via a neural network generates a schedule for to schedule staffing of security checkpoints. This process relies on simulated annealing. Simulated annealing can generate a schedule for opening security checkpoints, ensuring a waiting time below a predefined threshold. This optimal opening schedule serves as a constraint for an ILP algorithm that assigns security teams to various checkpoints at the tactical level while ensuring compliance with constraints related to legal work time of the agents. The number of security agents required using this method is significantly lower than that obtained by the airport's empirical method. However,

<table><caption>**Table 5**
Maximum difference observed between the cumulative demand of security teams and the number provided using the method over ten consecutive days of February 2023.</caption><thead><tr><td></td><td>Required security team</td><td>Maximum difference</td></tr></thead><tbody><tr><td>01/02/2023</td><td>100</td><td>-5</td></tr><tr><td>02/02/2023</td><td>95</td><td>-4</td></tr><tr><td>03/02/2023</td><td>95</td><td>-4</td></tr><tr><td>04/02/2023</td><td>93</td><td>-3</td></tr><tr><td>05/02/2023</td><td>106</td><td>-2</td></tr><tr><td>06/02/2023</td><td>87</td><td>-4</td></tr><tr><td>07/02/2023</td><td>78</td><td>-5</td></tr><tr><td>08/02/2023</td><td>86</td><td>-6</td></tr><tr><td>09/02/2023</td><td>91</td><td>-8</td></tr><tr><td>10/02/2023</td><td>91</td><td>-9</td></tr><tr><td>Mean</td><td>92.2</td><td>-5</td></tr><tr><td>Standard Deviation</td><td>7.72</td><td>2.16</td></tr></tbody></table>

<figure><img src="image_14.png" /><figcaption>**Fig. 15.** Cumulative demand of security agents teams for the whole airport (blue) compared to the number of security agents teams available (orange) on a tested day. (For interpretation of the references to color in this figure legend, the reader is referred to the web version of this article.)</figcaption></figure>

since the neural network's predictions cannot be perfect, there may be times when the number of predicted agents is insufficient to handle the passenger flow. This limitation presents an opportunity for future studies. The neural network could be tuned and its parameters tuned to reduce underestimation of passenger flow. Additionally, refining the simulated annealing parameters and enhancing the execution time may ultimately lead to a more optimal security screening line opening schedule. Further research could be conducted to assess the reliability of this method over an extended period, especially on days affected by disruptions such as strikes or adverse weather conditions. Additional performance metrics may be developed to measure the quality of a security checkpoint schedule. Furthermore, the security checkpoint simulator can be modified to reflect more complex passenger behavior and security procedures. This approach could also be validated at the airport, specifically on designated security checkpoints, and eventually throughout the entire airport. These tests would be difficult to carry out because ADP does not have its own security staff, but uses external service providers. It would therefore be necessary to impose line opening schedules to the security companies to see if the method works properly. It would be difficult to change the way all checkpoints work directly, so the method would probably have to be validated
at a few checkpoints first, and then extended to the whole airport. Finally, This methodology is not limited to Paris Charles de Gaulle airport. It could be adapted to any airport with a similar infrastructure, i.e. large checkpoints serving several gates in each departure room. However, in other configurations, with a small checkpoint in front of each boarding gate, such as at Singapore's Changi Airport, this method is useless because passengers no longer mix at the checkpoint, but find themselves in front of their gate and are screened just before boarding. As a result, there is no need to optimize the checkpoint opening schedule because it is similar to the flight schedule. But there is still a need to optimize the checkpoint security agent schedules, as proposed in this work.

## CRediT authorship contribution statement

**Alexis Brun:** Writing – original draft, Software, Methodology, Conceptualization.
**Eric Feron:** Writing – review & editing, Conceptualization.
**Sameer Alam:** Writing – review & editing, Conceptualization.
**Daniel Delahaye:** Writing – review & editing, Conceptualization.

## Acknowledgment

This work was supported by the Artificial and Natural Intelligence Toulouse Institute (ANITI).

## References

Brun, Alexis, Delahaye, Daniel, Feron, Eric, Alam, Sameer, 2022. Predicting passenger flow at charles de gaulle airport using dense neural networks. In: Proceedings of International Workshop on ATM/CNS, vol. 1, pp. 25–32.

Chiti, Francesco, Fantacci, Romano, Rizzo, Andrea, 2018. An integrated software platform for airport queues prediction with application to resources management. J. Air Transp. Manag. 67, 11–18.

Delahaye, Daniel, Chaimatanan, Supatcha, Mongeau, Marcel, 2018. Simulated annealing: From basics to applications. In: Handbook of Metaheuristics. Springer International Publishing, pp. 1–35.

Direction de l'information légale et administrative, 1985. Convention collective nationale des entreprises de prévention et de sécurité du 15 février 1985. Etendue par arrêté du 25 juillet 1985. J. Officiel République française https://www.legifrance.gouv.fr/conv_coll/id/KALISCTA000005725201/?idConteneur=KALCONT000005635405&origin=list.

Gendreau, Michel, Potvin, Jean-Yves, 2010. Handbook of Metaheuristics, second ed. Springer Publishing Company, Incorporated.

Granville, V., Krivanek, M., Rasson, J.-P., 1994. Simulated annealing: a proof of convergence. IEEE Trans. Pattern Anal. Mach. Intell. 16 (6), 652–656.

Groupe ADP, 2024. Plan général de l'aéroport de Paris-Charles de Gaulle et de ses terminaux, informations accès, gares SNCF et circulation entre chaque terminal. https://www.parisaeroport.fr/passagers/acces/paris-charles-de-gaulle/plans-terminaux. (Accessed 18 September 2024).

Hanafi, Rosmalina, Kozan, Erhan, 2014. A hybrid constructive heuristic and simulated annealing for railway crew scheduling. Comput. Ind. Eng. 70, 11–19.

Hanumantha, Girish Jampani, Arici, Berkin T., Sefair, Jorge A., Askin, Ronald, 2020. Demand prediction and dynamic workforce allocation to improve airport screening operations. IISE Trans. 52 (12), 1324–1342.

Hussain, Kashif, Salleh, Mohd Najib Mohd, Cheng, Shi, Shi, Yuhui, 2018. Metaheuristic research: a comprehensive survey. Artif. Intell. Rev. 52 (4), 2191–2233.

International Air Transport Association, 2023. Global Outlook for Air Transport. Technical report, International Air Transport Association.

Islami, Arianit, Chaimatanan, Supatcha, Delahaye, Daniel, 2017. Large-scale 4D trajectory planning. In: Lecture Notes in Electrical Engineering. Springer, Japan, pp. 27–47.

Kierzkowski, Artur, Kisiel, Tomasz, 2017. Simulation model of security control system functioning: A case study of the wroclaw airport terminal. J. Air Transp. Manag. 64, 173–185.

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P., 1983. Optimization by simulated annealing. Science 220 (4598), 671–680.

Knol, Arthur, Sharpanskykh, Alexei, Janssen, Stef, 2019. Analyzing airport security checkpoint performance using cognitive agent models. J. Air Transp. Manag. 75, 39–50.

Leone, Kelly, Liu, Rongfang (Rachel), 2011. Improving airport security screening checkpoint operations in the US via paced system design. J. Air Transp. Manag. 17 (2), 62–67.

Li, Yongli, Gao, Xin, Xu, Zhiwei, Zhou, Xuanrui, 2018. Network-based queuing model for simulating passenger throughput at an airport security checkpoint. J. Air Transp. Manag. 66, 13–24.

Mahmudy, Wayan, 2014. Improved simulated annealing for optimization of vehicle routing problem with time windows (VRPTW). Kursor 7, 109–116.

Metropolis, Nicholas, Rosenbluth, Arianna W., Rosenbluth, Marshall N., Teller, Augusta H., Teller, Edward, 1953. Equation of state calculations by fast computing machines. J. Chem. Phys. 21 (6), 1087–1092.

Monmousseau, Philippe, Jarry, Gabriel, Bertosio, Florian, Delahaye, Daniel, Houalla, Marc, 2020. Predicting passenger flow at charles de gaulle airport security checkpoints. In: 2020 International Conference on Artificial Intelligence and Data Analytics for Air Transportation. AIDA-AT, IEEE.

Mujica Mota, Miguel, Scala, Paolo, Murrieta-Mendoza, Alejandro, Orozco, Angel, Di Bernardi, Alejandro, 2021. Analysis of security lines policies for improving capacity in airports: Mexico city case. Case Stud. Transp. Policy 9 (4), 1476–1494.

Neufville, Richard de, Odoni, Amedeo R., Belobaba, Peter P., Reynolds, Tom G., 2013. Airport Systems: Planning, Design, and Management, second ed. McGraw-Hill Education, New York.

Perez, Eduardo, Taunton, Logan, Sefair, Jorge A., 2021. A simulation-optimization approach to improve the allocation of security screening resources in airport terminal checkpoints. In: 2021 Winter Simulation Conference. WSC, IEEE.

Ruiz, Emiliano, Cheu, Ruey Long, 2020. Simulation model to support security screening checkpoint operations in airport terminals. Transp. Res. Rec.: J. Transp. Res. Board 2674 (2), 45–56.

Scozzaro, Geoffrey, 2024. Optimisation des opérations aéroportuaires en cas de perturbation des modes d'accès afin d'améliorer l'expérience passager (Ph.D. thesis). Université de Toulouse 3 - Paul Sabatier.

Scozzaro, Geoffrey, Mancel, Catherine, Delahaye, Daniel, Feron, Eric, 2022. Optimising security screening resources during airport access mode disruptions. In: SESAR Innovation Days. Budapest, Hungary.

Stolletz, Raik, 2011. Analysis of passenger queues at airport terminals. Res. Transp. Bus. Manag. 1 (1), 144–149.

Valeva, Silviya, Hewitt, Mike, Thomas, Barrett W., 2017. A matheuristic for workforce planning with employee learning and stochastic demand. Int. J. Prod. Res. 55 (24), 7380–7397.

Wilson, Diane, Roe, Eric, So, S., 2006. Security checkpoint optimizer (SCO): An application for simulating the operations of airport security checkpoints. In: Proceedings of the 2006 Winter Simulation Conference. IEEE.

Zhang, Zhe George, Luh, Hsing Paul, Wang, Chia-Hung, 2011. Modeling security-check queues. Manage. Sci. 57 (11), 1979–1995.