# An Extended Model for the UAVs-Assisted Multiperiodic Crowd Tracking Problem

Authors: Skander Htiouech; Khalil Chebil; Mahdi Khemakhem; Fidaa Abed; Monaji H. Alkiani
Journal: Complexity
 (2023)

---

## Abstract

The multiperiodic crowd tracking (MPCT) problem is an extension of the periodic crowd tracking (PCT) problem, recently addressed in the literature and solved using an iterative solver called PCTs solver. For a given crowded event, the MPCT consists of follow-up crowds, using unmanned aerial vehicles (UAVs) during different periods in a life-cycle of an open crowded area (OCA). Our main motivation is to remedy an important limitation of the PCTs solver called “PCTs solvermyopia” which is, in certain cases, unable to manage the fleet of UAVs to cover all the periods of a given OCA life-cycle during a crowded event. The behavior of crowds can be predicted using machine learning techniques. Based on this assumption, we proposed a new mixed integer linear programming (MILP) model, called MILP-MPCT, to solve the MPCT. The MILP-MPCT was designed using linear programming technique to build two objective functions that minimize the total time and energy consumed by UAVs under a set of constraints related to the MPCT problem. In order to validate the MILP-MPCT, we simulated it using IBM-ILOG-CPLEX optimization framework. Thanks to the “clairvoyance” of the proposed MILP-MPCT model, experimental investigations show that the MILP-MPCT model provides strategic moves of UAVs between charging stations (CSs) and crowds to provide better solutions than those reported in the literature.


---

## Body

## 1. Introduction

Over the past years, a new infrastructure with new constraints and new characteristics is widely explored by new users, namely, the unmanned aerial vehicle (UAV) (also called drone) [1, 2]. The term UAV is used for “a pilotless aircraft which is flown without a pilot-in-command on-board and is either remotely and fully controlled from another place (ground, another aircraft, and space) or programmed and fully autonomous” [3].Many reasons explain the popularization and the wide use of UAVs these days. The most important are those related to their low costs (e.g., acquisition, maintenance, and energy) compared with other infrastructures such as manned aerial vehicles or satellites and their ability to fly at low altitudes with different speeds both indoor and outdoor [4]. Therefore, UAVs have started to be a challenging field for many researchers. Moreover, UAVs attracted many companies to invest in discovering further in their applications [5]. During the last decade, UAVs have been used in many different applications, including aerial photography [6, 7], agriculture [8, 9], control [10, 11], communications [12, 13], crop spraying and monitoring [14], emergency response [15, 16], logistics [17, 18], search and rescue [19], and product delivery [20–22]. Further fields of applications can be found in [23–29].In the midst of global urbanization and the constant population growth, the crowd phenomenon has become more frequent. This explains the reasons of having various technical and social disciplines pay attention to crowd analysis [30]. For events that are becoming more frequent and popular, such as sport events [16, 26, 31], concerts [32], and religious gatherings such as annual Islamic pilgrimage (also called Hajj) [15, 33–36] and Kumbh Mela in India [15], it is imperative to use crowd analysis to prevent crowd-related disasters and provide public safety.Considering the difficulty of movement and intervention in crowds, using UAVs represents an effective and promising low-cost solution [19, 36]. The study of crowds dynamicity has been taken as an important issue in the UAVs management [20, 22, 29, 37]. Designing an efficient crowd monitoring and analysis (CMA) system is a challenging task to ensure security and safety in crowded events [38–42]. Indeed, a strategic monitoring and tracking of crowds could give an opportunity for early decisions to prevent fatal accidents due to abnormal behavior. In addition, some people in the crowd may show critical situations, which could lead to panic and fatal accidents [15, 34]. Considerable research works have been conducted in crowd management using UAVs [22, 37]. Researchers have recently been using drones in crowd management to detect and track crowd movements [43–45]. In fact, UAVs provide powerful features such as coverage ability and flexibility over conventional static cameras previously used [40, 46–49]. Various studies have been conducted to detect and determine the density (i.e., number of people at each squared meter) and speed of crowds in order to determine their movement patterns [24, 34, 50].Regarding the crowd tracking (CT) problem using UAVs, addressed in this article, there are few works in the literature that focus on it [6, 51–55]. Each of these works considers the crowd tracking problem from a specific point of view. To the best of our knowledge, only three works are interested to the optimization aspect when tracking target objects or crowds using UAVs [52, 53].De Moraes and De Freitas [52] were the first to integrate optimization techniques in their crowd tracking mechanism using UAVs. Indeed, they proposed a UAVs-based system, that periodically monitors gathered walking individuals, where they integrate auction paradigms and genetic algorithms to distribute UAVs among crowds/targets and to calculate the best order to visit them. According to an effective simulation analysis, authors proved the capabilities, efficiency, and robustness of their system to perform the surveillance, to visit all targets during a supervising period, to minimize the transition time between targets, and to preserve performance and stability under a variety of scenarios.A second work that considers optimization features is presented by Trotta et al. [53], where authors propose an aerial tracking system that deploys a swarm of UAVs for continuous video capture of mobile ground targets. The main challenging issues raised in this work were in terms of energy management, scenario coverage, and multidevice task coordination. To solve these raised issues, they proposed a framework, named PERCEIVE, that considers a modular chain of functionalities to perform crowd mobility prediction, UAV charging scheduling, and UAVs and mobile charging stations (MCSs) mobility updates. They proved the capabilities, efficiency, and robustness of their framework via experimental measurements of a MCS prototype and an extensive and effective simulation analysis on a city-scale monitoring scenario. Regarding the integrated UAV replenishment service, they used a probabilistic charging scheduling algorithm considering both UAVs residual energy and the system Quality of Service (QoS). Furthermore, regarding the UAVs and MCSs mobility management, they used swarm mobility algorithms based on the potential field force model to maximize the number of targets covered by UAVs and minimize charging operations overhead.The two previously cited state-of-the-art contributions were proposed for a specific application of aerial video surveillance. Even if some works consider the optimization aspect to efficiently track crowds, none of them considered the minimization of the total distance/time traveled by UAVs and the total energy consumed by UAVs via assigning the best UAVs for each crowd. Moreover, in the literature, there is no formal optimization model that can be easily adapted to be used by any CMA system using crowd tracking via UAVs. The last two issues were the main challenges to face within the contribution of Chebil et al. [51]. Indeed, this work considers optimization features where, for a given open crowded area (OCA) life-cycle, crowds are closely tracked with UAVs in real-time to ensure continuous and efficient covering during a given period of time. The authors propose a solver (called PCTs solver), based on a binary linear programming (BLP) model, to solve the periodic crowd tracking (PCT) problem. PCTs solver iteratively (at each period of the OCA life-cycle) solves the PCT problem by considering two objective functions such as the minimization of the UAVs traveling time and the minimization of their energy consumption. Their model, called PLP−PCTλ, includes’different types of real word hypotheses and constraints related to UAVs’ architecture (e.g., speed, charging time, and minimum charge to fly), crowds characteristics (e.g., demand of UAVs, speed, and density), and charging stations characteristics (e.g., location and capacity). Some of these characteristics change from a given period λ to the next one λ+1. Many input parameters, related to OCA characteristics, UAVs features, and crowds behavior, are outlined and sensitively analyzed to emphasize their impact on the crowd tracking function of a given CMA system. Interested readers are referred to the conducted research by Chebil et al. [51] for further details.To the best of our knowledge, [51] is the first work that tackles the PCT problem with a detailed and formal consideration of the optimization aspect. Indeed, they provide a formal optimization model independently from any scope of application that can be easily embedded in any CMA framework. Otherwise, the authors formulate the PCT in a single period context where OCA life-cycle is divided into “periods,” and at the beginning of each period, a new assignment of UAVs to crowds is given according to the new UAVs, crowds, and charging stations characteristics. Despite its originality, the PCTs solver has some limitations that have been discussed as future challenges in [51]. The present work focuses on the following limitations that built our main motivation.(1)
The PCTs solver is considered as a greedy heuristic. Indeed, it solves thePLP−PCTλ model for a given period λ and it does not care about what will occur during the next period λ+1 and if it will be able to solve PLP−PCTλ+1 or not. This disadvantage is called “PCTs solver myopia” that directly affects the covering ability of the PCTs solver (i.e., its capacity to solve PLP−PCTλ for all periods λ of a given OCA life-cycle). Indeed, for some PCTs instances, PCTs solver gives feasible solutions for certain preliminary periods of a given OCA life-cycle, then it will no longer be able to find solutions for posterior periods. This is caused by UAVs energy constraints due to some previous wrong decisions.(2)
Even if the PCTs solver is able to provide an optimal solution of the CT at each period, the global solution (built by the solutions of allPLP−PCTλ for all periods λ of a given OCA life-cycle) is considered as feasible (not optimal). The global solution can be improved if the OCA characteristics during all periods will be known and considered from the start of the solving process.In this paper, the multiperiodic crowd tracking (MPCT) problem using UAVs is investigated. In fact, by considering multiperiodic aspect, this work is considered as a generalization or an extension of the work of Chebil et al. [51] where a mono;periodic model is considered. Solving the MPCT problem consists of finding an optimal assignment of UAVs to track crowds during the entire OCA life-cycle time. The objective is to keep all crowds covered by the required number of UAVs whilst minimizing their movements time and energy consumption. Indeed, in MPCT problem, several crowds are considered to move into different directions. Each crowd at any given time has an exact location (latitude and longitude) and needs a minimum number of UAVs to be covered according to its density. As long as the crowds are moving, every crowd could grow, shrink, change its structure, merge with other crowds, or split (unmix). To satisfy crowds demands, a set of available UAVs is supposed to be initially located in multiple charging stations. The movements of crowds are considered to be predictable. In fact, this is a realistic assumption in some situations where the behavior of the crowds is known and can be predicted. To do that, there are many proposed methods in the literature that can be used to predict crowds characteristics and behavior based on machine learning techniques [56–64]. Thanks to this prediction, a CMA system can have a “clairvoyance” and therefore more strategic assignments of the UAVs that takes into account the future behaviors of crowds. Given the energy constraints, the model should find an optimal assignment of UAVs to crowds during each period in a way that minimizes unnecessary movements and energy consumption of the UAVs.The present work proposes a mixed-integer linear programming (MILP) model to solve the MPCT (called MILP-MPCT). We maintain all hypothesis considered by Chebil et al. [51] and we enrich them by the following:(i)
The behavior and all characteristics of each crowd are predicted by using any accurate prediction algorithm from the literature (i.e., at the beginning of each period, the position, and the number of UAVs that are requested by every crowd are known). Of course, bad accuracy of a given prediction algorithm affects the results (solutions qualities) provided by the MILP-MPCT. In this paper, we deal only with the covering ability of MILP-MPCT (outlined by Chebil et al. [51] among their future challenges) compared to PCTs solver.(ii)
It is exactly known when and where two or more crowds merge/unmix and create a new crowds. Therefore, in the case of an inaccurate prediction handling, some reoptimization techniques can be applied to correct the obtained UAVs/crowds assignment provided by the used optimization model that can be outlined as future challenge.The proposed MILP-MPCT model is compared to the PCTs solver proposed by Chebil et al. [51] in terms of time/energy consumption and their ability to cover all periods of a given OCA life-cycle.The remainder of the paper is organized as follows: Section2 presents the considered system model of the MPCT problem using UAVs, the used parameters and decision variables, and the proposed MILP-MPCT composed by its linear constraints and objective functions. In order to discuss its performance and limitation, Section 3 reports the computational results obtained by the application of the suggested MILP on some MPCT instances. Finally, Section 4 outlines some suggestions for future research to solve the MPCT and concludes the paper.


## 2. Modeling the MPCT Problem Using UAVs

In this section, we formally define the MPCT problem using UAVs. Firstly, we present the context motivating us to solve the MPCT problem, followed by the considered assumptions and definitions that are illustrated by an example. Secondly, we define the parameters and decision variables used to formulate linear constraints and objective functions that build the proposed MILP-MPCT to solve the MPCT problem. The MPCT problem consists of assigning, during every period of a given OCA life-cycle, a set of requested UAVs to each crowd in order to ensure an efficient and continuous coverage of all identified mobile crowds subject to minimize the total time/energy consumption.


### 2.1. Context, Assumptions, and Definitions

Our main motivation is stimulated by the improvement of crowd tracking function of the CMA system using UAVs in the context of the annual Islamic pilgrimage (also called Hajj) that hosted about 2.5 million of pilgrims in 2019 (according to the Saudi General Authority for Statisticshttps://www.stats.gov.sa/sites/default/files/haj_40_en.%20pdf). During the Hajj period, which lasts about five days, many rites give rise to big pilgrims gatherings at the same time in five main places, such as Mina, Arafat, Muzdalifah, Jamarat, and Masjid-Al-Haram [51]. Based on this study, and to ensure cost-saving, we proposed a MILP to optimize the used UAVs when periodically tracking a set of moving crowds in a determined/bordered OCA (i.e., a geographical zone with known borders/dimensions and without obstacles where several close crowds navigate) such as religious gatherings, mass sports events, and social festivals.We assume that we already have the mechanisms and accurate prediction modules that provide the following real-time information:(i)
The characteristics of the OCA to be supervised by the CMA such as shape, area, and border dimensions.(ii)
The list of charging stations (CSs) that are considered to supply energy to UAVs. Each CS is characterized by its position (latitude and longitude), and capacity in terms of supported number of UAVs.(iii)
The number of available UAVs in the fleet and their characteristics such as current positions (latitude and longitude), statuses (flying to supervise a crowd, charging in a CS, or idle in a CS), energies (batteries) level, constant speeds, and energies (power) charging/discharging functions.(iv)
The list of identified crowds with their positions (latitude and longitude) and the number of requested UAVs to be covered.Based on the previous assumptions, the MPCT problem consists of allocating the needed number of heterogeneous UAVs to the mobile identified crowds in each period to ensure a continuous efficient coverage with minimizing the UAVs moves in order to reduce time and energy consumption. However, the UAVs/crowds assignment process must respect some rules, which is as follows:(i)
An UAV can be assigned at most to only one crowd during a given period of the OCA life-cycle.(ii)
An UAV cannot be assigned to a crowd if its energy is not enough to supervise the corresponding crowd during the whole current period and then return to the nearest available CS.(iii)
A flying UAV should return to an available CS if it is not assigned to a crowd in a given period.Figure1(a) presents an example of the initial OCA state where ten UAVs remain on the two CSs and the five crowds are not covered. After solving the MPCT problem, Figure 1(b) presents a snapshot of the OCA during the first period (Period 1) where six UAVs are used to ensure crowds coverage. Then, a second snapshot of the OCA supervised by the new UAVs/crowds assignment state during the period (Period 2) is shown in Figure 1(c). We can see that the number of crowds is reduced to four, which is caused by the merge of two crowds, then the number of needed UAVs is reduced by allowing one UAV to rejoin a CS.Figure 1
Scenario of three periods [51]. (a) Initial OCA state. (b) OCA state during period 1. (c) OCA state during period 2.
(a)(b)(c)


### 2.2. Parameters and Notations

We recall the main notations and functions used throughout the paper to build MILP-MPCT model to solve the MPCT problem. Indeed, we use almost the same notations used for theBLP−PCTλ model to solve the PCT in [51], to which the reader can refer for more details.LetC be the total time of an OCA life-cycle and Λ=1,2,⋯,λ−1,λ,λ+1,⋯,Λ a set of contiguous and nonoverlapped periods in C. We consider an additional special period (where λ=0) that represents the initial state of the OCA life-cycle where all UAVs are initially distributed over the charging stations (CSs). Supervising crowds starts at the beginning of the first period that is designated by λ=1. Without loss of generality, we assume that all periods have the same duration T, where T=C/Λ. As considered in [51], ∀λ∈Λ∪0, we considered a rectangular shaped OCA and noted Q with dimensions in meters lQ×hQ that contains the whole sets Uλ of UAVs, Wλ of crowds, and Sλ of CSs during each period λ. Let Gλ=Uλ∪Wλ∪Sλ,cwλ∪csλ be a graph that represents the CMA system and the considered OCA at the beginning of each period λ∈Λ∪0, where(i)
∀λ∈Λ∪0,cwλ represents the distances matrix between UAVs and crowds during the period λ.(ii)
∀λ∈Λ∪0,csλ represents the distances matrix between UAVs and CSs during the period λ.(iii)
∀λ∈Λ∪0,Uλ represents the set of UAVs during the period λ, where(a)
Uλ=n is the number of UAVs during the period λ.(b)
∀u∈Uλ, xcorduλ, and ycorduλ are the latitude and the longitude of the UAV u during the period λ.(c)
∀u∈Uλ and statuλ∈0,1 are the status of the UAV u during the period λ, 0 when idle/charging on CS, 1 when flying. Note that in the initial state ∀u∈U0 and statu0=0.(d)
∀u∈Uλ,ϑu is the constant speed (meter/second) of flying UAV u during all periods in Λ.(e)
∀u∈Uλ,τ−u is the flying time of the UAV u to consume (lose) 1% of its energy.(f)
∀u∈Uλ,τ+u is the charging time of the UAV u to gain 1% of its energy.(g)
∀u∈Uλ,fuλ is the loss energy function of the UAV u caused by its transition movement from its position during the previous period λ−1 to its position during the current period λ and by its supervising flight during the period λ. We consider the same formula of function fuλ used in [51].(h)
∀u∈Uλ,δ−u is the energy percentage threshold forcing UAV u to return to a base station at the end of any period in Λ. δ−u is calculated as follows:(1)δ−u=lQ2+hQ2ϑu×τ−u.(i)
∀u∈Uλ,δ+u is the energy percentage threshold allowing UAV u to leave from a base station. δ+u is calculated as follows:(2)δ+u=2×lQ2+hQ2/ϑu+Tτ−u.(iv)
∀λ∈Λ,Wλ represents the set of crowds during the period λ, where(a)
Wλ=m is the number of crowds during the the period λ.(b)
∀w∈Wλ, xcordwλ, and ycordwλ are the latitude and the longitude of the gravity center of the crowd w during the period λ.(c)
∀u∈Uλ,w∈Wλ,cwuwλ represents the distance (meter) between an UAV u during the period λ−1 and the gravity center of a crowd w during the period λ.(d)
∀w∈Wλ and dwλ∈N∗ are the number of UAVs requested by the crowd w during the period λ.(v)
∀λ∈Λ∪0,Sλ represents the set of CSs during the period λ, where(a)
Sλ=p is the number of CSs during the period λ.(b)
∀s∈Sλ, xcordsλ, and ycordsλ are the latitude and the longitude of the CS s during the period λ.(c)
∀u∈Uλ,s∈Sλ,csusλ represents the distance (meter) between an UAV u during the period λ−1 and a charging station s during the period λ.(d)
∀s∈Sλ and rs∈N∗ is the capacity of the CS s in terms of number of UAVs during all periods.(vi)
∀λ∈Λ∪0,Kλ=Wλ∪Sλ represents the set of crowds and stations during the period λ.(vii)
∀λ∈Λ,∀k1∈Kλ−1,∀k2∈Kλ,ck1k2λ represents the distance (meter) between a crowd / CS k1 of period λ−1 and a crowd / CS k2 of period λ.


### 2.3. Decision Variables

We define the following decision variables in order to build the proposed MILP-MPCT model that covers all periods inΛ:(i)
∀λ∈Λ,∀u∈Uλ,∀k1∈Kλ−1,∀k2∈Kλ,xuk1k2λ∈0,1 a binary decision variable, where(3)xuk1k2λ=1iftheUAVuwasonthecrowdorCSk1duringtheperiod,λ−1andassignedtothecrowdorCSk2duringtheperiodλ,0otherwise.(ii)
∀λ∈Λ,∀u∈Uλ,euλ∈0,100 a non-negative continuous decision variable that represents the energy percentage (battery level) of the UAV u at the beginning of period λ, where(4)euλ=mineuλ−1+ε+uλ−1,100,iftheUAVuwasinaCSduringtheperiodλ−1chargingmode,whereε+uλ−1representsitsgainedenergy,maxeuλ−1−ε−uλ−1,0,iftheUAVuwasonacrowdduringtheperiodλ−1flyingmode,whereε−uλ−1representsitsloosedenergy,whereε+uλ and ε−uλ are determined as follows:(5)ε+uλ=∑k∈Kλ−1∑s∈Sλcksλϑuτ−u+Tτu+xuksλ,∀λ∈Λ,∀u∈Uλ,ε−uλ=∑k∈Kλ−1∑w∈Wλckwλϑuτ−u+Tτ−uxukwλ,∀λ∈Λ,∀u∈Uλ.


### 2.4. Objective Functions

According to the decision maker objective, we define the following two objective functions that can be used in the proposed MILP-MPCT model:(i)
The first objective function (6) minimizes the total time consumed by all UAVs movements during their transitions from their locations at the initial period λ=0 to their locations at final period λ=Λ. Of course, all their locations through all intermediate periods should be considered.(6)minZT=∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuxuk1k2λ≈∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuxuk1k2λ.We recall thatϑu are the constant speeds of UAVs, ck1k2λ represent the distances between crowds/CSs k1 in period λ−1 and crowds/CSs k2 in the period λ. ZT determines the total time consumed by all UAVs, for all periods λ∈Λ, during their movements from an assigned crowds/CSs in period λ−1 to an assigned crowds/CSs in period λ.(ii)
The second objective function (7) minimizes of the total energy consumed by all UAVs during all periods of the OCA life-cycle.(7)minZE=∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuτ−uxuk1k2λ+∑w∈WλTτ−uxuk1wλ≈∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuτ−uxuk1k2λ+∑w∈WλTτ−uxuk1wλ.We recall thatτ−u are the flying times of UAVs to consume (lose) 1% of their energies. The first term of ZE determines the total energy consumed by UAVs when they travel from their assigned crowds/CSs during period λ−1 to their assigned crowds/CSs during period λ. The second term of ZE determines the total energy consumed by flying UAVs during period λ when they supervise assigned crowds.


### 2.5. Constraints

Using the parameters and decision variables defined in Sections2.2 and 2.3, we define the following constraints classified by categories according to the CMA system infrastructure and the OCA characteristics.


#### 2.5.1. UAV Constraints

Constraints (8) ensure that during the initial period λ=0, all UAVs are fully charged.(8)eu0=100,∀u∈U0.Constraints (9) ensure that during the initial period λ=0, each UAVs is assigned to only one CS. We add these constraints just to assert the integrity of the initial UAVs distribution in the input data. We use twice the CS index in the decision variable xuss0 because there is no period that precedes the initial period λ=0 (e.g., x1220=1 means that the UAV indexed by 1 is assigned to the CS indexed by 2 during the initial period indexed by 0).(9)∑s∈S0xuss0=1,∀u∈U0.Constraints (10) ensure that during the initial period λ=0, there is no UAVs assigned to crowds.(10)∑w∈W0xuww0=0,∀u∈U0.Constraints (11) ensure that during each period λ∈λ, every UAV is assigned to at most a crowd or a CS.(11)∑k1∈Kλ−1∑k2∈Kλxuk1k2λ=1,∀λ∈Λ,∀u∈Uλ.Constraints (12) ensure that if an UAV u is assigned to a crowd/CS k2 during the period λ−1, then its transition to a crowd/CS k3 during the period λ should be performed starting from k2. It is worthy to note that these constraints are not applied to the first period λ=1. Indeed, the first period immediately follows the initial period (λ=0), which is considered as a special period as it is already mentioned. Dedicated equivalent constraints to the first period are described by inequality (13).(12)xuk1k2λ−1≤∑k3∈Kλxuk2k3λ∀λ∈Λ−1,∀u∈Uλ,∀k1∈Kλ−2,∀k2∈Wλ−1.As it is already motioned in Section2.2 and asserted by constraints (10) and (11), the initial period (λ=0) is not considered as a standard period, given that each UAV is located in a CS belonging to S0. Constraints (13) ensure that if an UAV is assigned to a crowd/CS during the first period (λ=1), it should start from its allocated charging station s during the initial period λ=0.(13)xuss0≤∑k∈K1xusk1,∀u∈U1,∀s∈S0.At the end of each periodλ, the energy percentage (battery level) of each UAV u∈Uλ varies according to the UAV state. Constraints (14) ensure this variation by adding the gained energy if the UAV is assigned to a CS and subtracting the loosed energy if it is assigned to a crowd.(14)euλ=euλ−1+ε+uλ−ε−uλ,∀λ∈Λ,∀u∈Uλ.We note thatε+uλ (resp. ε−uλ) gets, with a complementary fashion thanks to constraints (11), a non-null value if the UAV u is assigned to a CS (resp. to a crowd) during the period λ.Constraints (15) ensure that each UAV u∈Uλ assigned to a crowd w∈Wλ has enough energy to move from its last position during period λ−1 to the assigned crowd and performing its covering task (flying) during period λ. We recall that δ−uλ is the energy percentage threshold forcing an UAV u to return to a CS during a period λ.(15)euλ−1−ε−uλ≥δ−uλ,∀λ∈Λ,∀u∈Uλ.Constraints (16) ensure that each UAV u∈Uλ, assigned to a CS during the period λ−1, has the minimum required autonomy (δ+uλ) to leave the CS.(16)euλ−1+ε+uλ≥δ+uλ,∀λ∈Λ,∀u∈Uλ.Constraints (17) ensure that the charge percentage of each UAV u∈Uλ cannot exceed 100%.(17)euλ=mineuλ−1+ε+uλ,100,∀λ∈Λ,∀u∈Uλ.


#### 2.5.2. Crowd Constraints

Constraints (18) ensure that during each period λ∈Λ and each crowd w∈Wλ demand should be satisfied.(18)∑u∈Uλ∑k∈Kλ−1xukwλ=dwλ,∀λ∈Λ,∀w∈Wλ.


#### 2.5.3. CS Constraints

Constraints (19) ensure that the number of UAVs assigned to a CS s∈Sλ in a period λ∈Λ cannot exceed the station capacity rs.(19)∑u∈Uλ∑k∈Kλ−1xuksλ≤rs,∀λ∈Λ,∀s∈Sλ.


### 2.6. MILP-MPCT Model

By considering one of the objective functions expressed by equations (6) and (7), presented in Section 2.4, and the set of the ten constraints (8)–(19), presented in Section 2.5, we can build two different MILP models to solve the MPCT problem. The MILP-MPCT model that considered the objective function ZT aimed to minimize the total time consumed by UAVs during their transitions from one period to another during the whole OCA life-cycle time. Furthermore, when we considered the same set of constraints with the objective function ZE we obtained a MILP-MPCT model that aimed to minimize the total energy consumed by all UAVs to move between their different positions and to cover crowds during the whole OCA life-cycle time.


### 2.7. How Does the MILP-MPCT Model Work?

The proposed model MILP-MPCT considers many crowds that move in different directions. At any given time, each crowd is located precisely (via latitude and longitude) and requires a minimum number of UAVs. After every period, the location of the crowd and the number of required UAVs change. Crowds are capable of growing, shrinking, changing structure, merging with other crowds, or splitting (unmixing), as long as they are moving. All the crowds should be covered by a set of available UAVs initially located in charging stations. The MILP-MPCT model aims to obtain an optimal allocation of UAVs to track crowds throughout the OCA life-cycle at the same time. By using the necessary number of UAVs, all crowds can be covered while minimizing their movements and energy consumption. We recall that, we considered that crowds future movements are predictable which is reasonable in some situations where their behaviors is known and can be accurately forecasted.The MILP-MPCT model takes, as inputs, the list of available UAVs and their positions, the number of stations and their positions, and the crowds and their needs in terms of UAVs. Then, it provides a schedule throughout the whole OCA life-cycle by assigning at the beginning of each period of certain UAVs to cover crowds and others to stations, while minimizing the total movement time and energy consumption of all UAVS.


## 2.1. Context, Assumptions, and Definitions

Our main motivation is stimulated by the improvement of crowd tracking function of the CMA system using UAVs in the context of the annual Islamic pilgrimage (also called Hajj) that hosted about 2.5 million of pilgrims in 2019 (according to the Saudi General Authority for Statisticshttps://www.stats.gov.sa/sites/default/files/haj_40_en.%20pdf). During the Hajj period, which lasts about five days, many rites give rise to big pilgrims gatherings at the same time in five main places, such as Mina, Arafat, Muzdalifah, Jamarat, and Masjid-Al-Haram [51]. Based on this study, and to ensure cost-saving, we proposed a MILP to optimize the used UAVs when periodically tracking a set of moving crowds in a determined/bordered OCA (i.e., a geographical zone with known borders/dimensions and without obstacles where several close crowds navigate) such as religious gatherings, mass sports events, and social festivals.We assume that we already have the mechanisms and accurate prediction modules that provide the following real-time information:(i)
The characteristics of the OCA to be supervised by the CMA such as shape, area, and border dimensions.(ii)
The list of charging stations (CSs) that are considered to supply energy to UAVs. Each CS is characterized by its position (latitude and longitude), and capacity in terms of supported number of UAVs.(iii)
The number of available UAVs in the fleet and their characteristics such as current positions (latitude and longitude), statuses (flying to supervise a crowd, charging in a CS, or idle in a CS), energies (batteries) level, constant speeds, and energies (power) charging/discharging functions.(iv)
The list of identified crowds with their positions (latitude and longitude) and the number of requested UAVs to be covered.Based on the previous assumptions, the MPCT problem consists of allocating the needed number of heterogeneous UAVs to the mobile identified crowds in each period to ensure a continuous efficient coverage with minimizing the UAVs moves in order to reduce time and energy consumption. However, the UAVs/crowds assignment process must respect some rules, which is as follows:(i)
An UAV can be assigned at most to only one crowd during a given period of the OCA life-cycle.(ii)
An UAV cannot be assigned to a crowd if its energy is not enough to supervise the corresponding crowd during the whole current period and then return to the nearest available CS.(iii)
A flying UAV should return to an available CS if it is not assigned to a crowd in a given period.Figure1(a) presents an example of the initial OCA state where ten UAVs remain on the two CSs and the five crowds are not covered. After solving the MPCT problem, Figure 1(b) presents a snapshot of the OCA during the first period (Period 1) where six UAVs are used to ensure crowds coverage. Then, a second snapshot of the OCA supervised by the new UAVs/crowds assignment state during the period (Period 2) is shown in Figure 1(c). We can see that the number of crowds is reduced to four, which is caused by the merge of two crowds, then the number of needed UAVs is reduced by allowing one UAV to rejoin a CS.Figure 1
Scenario of three periods [51]. (a) Initial OCA state. (b) OCA state during period 1. (c) OCA state during period 2.
(a)(b)(c)


## 2.2. Parameters and Notations

We recall the main notations and functions used throughout the paper to build MILP-MPCT model to solve the MPCT problem. Indeed, we use almost the same notations used for theBLP−PCTλ model to solve the PCT in [51], to which the reader can refer for more details.LetC be the total time of an OCA life-cycle and Λ=1,2,⋯,λ−1,λ,λ+1,⋯,Λ a set of contiguous and nonoverlapped periods in C. We consider an additional special period (where λ=0) that represents the initial state of the OCA life-cycle where all UAVs are initially distributed over the charging stations (CSs). Supervising crowds starts at the beginning of the first period that is designated by λ=1. Without loss of generality, we assume that all periods have the same duration T, where T=C/Λ. As considered in [51], ∀λ∈Λ∪0, we considered a rectangular shaped OCA and noted Q with dimensions in meters lQ×hQ that contains the whole sets Uλ of UAVs, Wλ of crowds, and Sλ of CSs during each period λ. Let Gλ=Uλ∪Wλ∪Sλ,cwλ∪csλ be a graph that represents the CMA system and the considered OCA at the beginning of each period λ∈Λ∪0, where(i)
∀λ∈Λ∪0,cwλ represents the distances matrix between UAVs and crowds during the period λ.(ii)
∀λ∈Λ∪0,csλ represents the distances matrix between UAVs and CSs during the period λ.(iii)
∀λ∈Λ∪0,Uλ represents the set of UAVs during the period λ, where(a)
Uλ=n is the number of UAVs during the period λ.(b)
∀u∈Uλ, xcorduλ, and ycorduλ are the latitude and the longitude of the UAV u during the period λ.(c)
∀u∈Uλ and statuλ∈0,1 are the status of the UAV u during the period λ, 0 when idle/charging on CS, 1 when flying. Note that in the initial state ∀u∈U0 and statu0=0.(d)
∀u∈Uλ,ϑu is the constant speed (meter/second) of flying UAV u during all periods in Λ.(e)
∀u∈Uλ,τ−u is the flying time of the UAV u to consume (lose) 1% of its energy.(f)
∀u∈Uλ,τ+u is the charging time of the UAV u to gain 1% of its energy.(g)
∀u∈Uλ,fuλ is the loss energy function of the UAV u caused by its transition movement from its position during the previous period λ−1 to its position during the current period λ and by its supervising flight during the period λ. We consider the same formula of function fuλ used in [51].(h)
∀u∈Uλ,δ−u is the energy percentage threshold forcing UAV u to return to a base station at the end of any period in Λ. δ−u is calculated as follows:(1)δ−u=lQ2+hQ2ϑu×τ−u.(i)
∀u∈Uλ,δ+u is the energy percentage threshold allowing UAV u to leave from a base station. δ+u is calculated as follows:(2)δ+u=2×lQ2+hQ2/ϑu+Tτ−u.(iv)
∀λ∈Λ,Wλ represents the set of crowds during the period λ, where(a)
Wλ=m is the number of crowds during the the period λ.(b)
∀w∈Wλ, xcordwλ, and ycordwλ are the latitude and the longitude of the gravity center of the crowd w during the period λ.(c)
∀u∈Uλ,w∈Wλ,cwuwλ represents the distance (meter) between an UAV u during the period λ−1 and the gravity center of a crowd w during the period λ.(d)
∀w∈Wλ and dwλ∈N∗ are the number of UAVs requested by the crowd w during the period λ.(v)
∀λ∈Λ∪0,Sλ represents the set of CSs during the period λ, where(a)
Sλ=p is the number of CSs during the period λ.(b)
∀s∈Sλ, xcordsλ, and ycordsλ are the latitude and the longitude of the CS s during the period λ.(c)
∀u∈Uλ,s∈Sλ,csusλ represents the distance (meter) between an UAV u during the period λ−1 and a charging station s during the period λ.(d)
∀s∈Sλ and rs∈N∗ is the capacity of the CS s in terms of number of UAVs during all periods.(vi)
∀λ∈Λ∪0,Kλ=Wλ∪Sλ represents the set of crowds and stations during the period λ.(vii)
∀λ∈Λ,∀k1∈Kλ−1,∀k2∈Kλ,ck1k2λ represents the distance (meter) between a crowd / CS k1 of period λ−1 and a crowd / CS k2 of period λ.


## 2.3. Decision Variables

We define the following decision variables in order to build the proposed MILP-MPCT model that covers all periods inΛ:(i)
∀λ∈Λ,∀u∈Uλ,∀k1∈Kλ−1,∀k2∈Kλ,xuk1k2λ∈0,1 a binary decision variable, where(3)xuk1k2λ=1iftheUAVuwasonthecrowdorCSk1duringtheperiod,λ−1andassignedtothecrowdorCSk2duringtheperiodλ,0otherwise.(ii)
∀λ∈Λ,∀u∈Uλ,euλ∈0,100 a non-negative continuous decision variable that represents the energy percentage (battery level) of the UAV u at the beginning of period λ, where(4)euλ=mineuλ−1+ε+uλ−1,100,iftheUAVuwasinaCSduringtheperiodλ−1chargingmode,whereε+uλ−1representsitsgainedenergy,maxeuλ−1−ε−uλ−1,0,iftheUAVuwasonacrowdduringtheperiodλ−1flyingmode,whereε−uλ−1representsitsloosedenergy,whereε+uλ and ε−uλ are determined as follows:(5)ε+uλ=∑k∈Kλ−1∑s∈Sλcksλϑuτ−u+Tτu+xuksλ,∀λ∈Λ,∀u∈Uλ,ε−uλ=∑k∈Kλ−1∑w∈Wλckwλϑuτ−u+Tτ−uxukwλ,∀λ∈Λ,∀u∈Uλ.


## 2.4. Objective Functions

According to the decision maker objective, we define the following two objective functions that can be used in the proposed MILP-MPCT model:(i)
The first objective function (6) minimizes the total time consumed by all UAVs movements during their transitions from their locations at the initial period λ=0 to their locations at final period λ=Λ. Of course, all their locations through all intermediate periods should be considered.(6)minZT=∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuxuk1k2λ≈∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuxuk1k2λ.We recall thatϑu are the constant speeds of UAVs, ck1k2λ represent the distances between crowds/CSs k1 in period λ−1 and crowds/CSs k2 in the period λ. ZT determines the total time consumed by all UAVs, for all periods λ∈Λ, during their movements from an assigned crowds/CSs in period λ−1 to an assigned crowds/CSs in period λ.(ii)
The second objective function (7) minimizes of the total energy consumed by all UAVs during all periods of the OCA life-cycle.(7)minZE=∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuτ−uxuk1k2λ+∑w∈WλTτ−uxuk1wλ≈∑λ∈Λ∑u∈Uλ∑k1∈Kλ−1∑k2∈Kλck1k2λϑuτ−uxuk1k2λ+∑w∈WλTτ−uxuk1wλ.We recall thatτ−u are the flying times of UAVs to consume (lose) 1% of their energies. The first term of ZE determines the total energy consumed by UAVs when they travel from their assigned crowds/CSs during period λ−1 to their assigned crowds/CSs during period λ. The second term of ZE determines the total energy consumed by flying UAVs during period λ when they supervise assigned crowds.


## 2.5. Constraints

Using the parameters and decision variables defined in Sections2.2 and 2.3, we define the following constraints classified by categories according to the CMA system infrastructure and the OCA characteristics.


### 2.5.1. UAV Constraints

Constraints (8) ensure that during the initial period λ=0, all UAVs are fully charged.(8)eu0=100,∀u∈U0.Constraints (9) ensure that during the initial period λ=0, each UAVs is assigned to only one CS. We add these constraints just to assert the integrity of the initial UAVs distribution in the input data. We use twice the CS index in the decision variable xuss0 because there is no period that precedes the initial period λ=0 (e.g., x1220=1 means that the UAV indexed by 1 is assigned to the CS indexed by 2 during the initial period indexed by 0).(9)∑s∈S0xuss0=1,∀u∈U0.Constraints (10) ensure that during the initial period λ=0, there is no UAVs assigned to crowds.(10)∑w∈W0xuww0=0,∀u∈U0.Constraints (11) ensure that during each period λ∈λ, every UAV is assigned to at most a crowd or a CS.(11)∑k1∈Kλ−1∑k2∈Kλxuk1k2λ=1,∀λ∈Λ,∀u∈Uλ.Constraints (12) ensure that if an UAV u is assigned to a crowd/CS k2 during the period λ−1, then its transition to a crowd/CS k3 during the period λ should be performed starting from k2. It is worthy to note that these constraints are not applied to the first period λ=1. Indeed, the first period immediately follows the initial period (λ=0), which is considered as a special period as it is already mentioned. Dedicated equivalent constraints to the first period are described by inequality (13).(12)xuk1k2λ−1≤∑k3∈Kλxuk2k3λ∀λ∈Λ−1,∀u∈Uλ,∀k1∈Kλ−2,∀k2∈Wλ−1.As it is already motioned in Section2.2 and asserted by constraints (10) and (11), the initial period (λ=0) is not considered as a standard period, given that each UAV is located in a CS belonging to S0. Constraints (13) ensure that if an UAV is assigned to a crowd/CS during the first period (λ=1), it should start from its allocated charging station s during the initial period λ=0.(13)xuss0≤∑k∈K1xusk1,∀u∈U1,∀s∈S0.At the end of each periodλ, the energy percentage (battery level) of each UAV u∈Uλ varies according to the UAV state. Constraints (14) ensure this variation by adding the gained energy if the UAV is assigned to a CS and subtracting the loosed energy if it is assigned to a crowd.(14)euλ=euλ−1+ε+uλ−ε−uλ,∀λ∈Λ,∀u∈Uλ.We note thatε+uλ (resp. ε−uλ) gets, with a complementary fashion thanks to constraints (11), a non-null value if the UAV u is assigned to a CS (resp. to a crowd) during the period λ.Constraints (15) ensure that each UAV u∈Uλ assigned to a crowd w∈Wλ has enough energy to move from its last position during period λ−1 to the assigned crowd and performing its covering task (flying) during period λ. We recall that δ−uλ is the energy percentage threshold forcing an UAV u to return to a CS during a period λ.(15)euλ−1−ε−uλ≥δ−uλ,∀λ∈Λ,∀u∈Uλ.Constraints (16) ensure that each UAV u∈Uλ, assigned to a CS during the period λ−1, has the minimum required autonomy (δ+uλ) to leave the CS.(16)euλ−1+ε+uλ≥δ+uλ,∀λ∈Λ,∀u∈Uλ.Constraints (17) ensure that the charge percentage of each UAV u∈Uλ cannot exceed 100%.(17)euλ=mineuλ−1+ε+uλ,100,∀λ∈Λ,∀u∈Uλ.


### 2.5.2. Crowd Constraints

Constraints (18) ensure that during each period λ∈Λ and each crowd w∈Wλ demand should be satisfied.(18)∑u∈Uλ∑k∈Kλ−1xukwλ=dwλ,∀λ∈Λ,∀w∈Wλ.


### 2.5.3. CS Constraints

Constraints (19) ensure that the number of UAVs assigned to a CS s∈Sλ in a period λ∈Λ cannot exceed the station capacity rs.(19)∑u∈Uλ∑k∈Kλ−1xuksλ≤rs,∀λ∈Λ,∀s∈Sλ.


## 2.5.1. UAV Constraints

Constraints (8) ensure that during the initial period λ=0, all UAVs are fully charged.(8)eu0=100,∀u∈U0.Constraints (9) ensure that during the initial period λ=0, each UAVs is assigned to only one CS. We add these constraints just to assert the integrity of the initial UAVs distribution in the input data. We use twice the CS index in the decision variable xuss0 because there is no period that precedes the initial period λ=0 (e.g., x1220=1 means that the UAV indexed by 1 is assigned to the CS indexed by 2 during the initial period indexed by 0).(9)∑s∈S0xuss0=1,∀u∈U0.Constraints (10) ensure that during the initial period λ=0, there is no UAVs assigned to crowds.(10)∑w∈W0xuww0=0,∀u∈U0.Constraints (11) ensure that during each period λ∈λ, every UAV is assigned to at most a crowd or a CS.(11)∑k1∈Kλ−1∑k2∈Kλxuk1k2λ=1,∀λ∈Λ,∀u∈Uλ.Constraints (12) ensure that if an UAV u is assigned to a crowd/CS k2 during the period λ−1, then its transition to a crowd/CS k3 during the period λ should be performed starting from k2. It is worthy to note that these constraints are not applied to the first period λ=1. Indeed, the first period immediately follows the initial period (λ=0), which is considered as a special period as it is already mentioned. Dedicated equivalent constraints to the first period are described by inequality (13).(12)xuk1k2λ−1≤∑k3∈Kλxuk2k3λ∀λ∈Λ−1,∀u∈Uλ,∀k1∈Kλ−2,∀k2∈Wλ−1.As it is already motioned in Section2.2 and asserted by constraints (10) and (11), the initial period (λ=0) is not considered as a standard period, given that each UAV is located in a CS belonging to S0. Constraints (13) ensure that if an UAV is assigned to a crowd/CS during the first period (λ=1), it should start from its allocated charging station s during the initial period λ=0.(13)xuss0≤∑k∈K1xusk1,∀u∈U1,∀s∈S0.At the end of each periodλ, the energy percentage (battery level) of each UAV u∈Uλ varies according to the UAV state. Constraints (14) ensure this variation by adding the gained energy if the UAV is assigned to a CS and subtracting the loosed energy if it is assigned to a crowd.(14)euλ=euλ−1+ε+uλ−ε−uλ,∀λ∈Λ,∀u∈Uλ.We note thatε+uλ (resp. ε−uλ) gets, with a complementary fashion thanks to constraints (11), a non-null value if the UAV u is assigned to a CS (resp. to a crowd) during the period λ.Constraints (15) ensure that each UAV u∈Uλ assigned to a crowd w∈Wλ has enough energy to move from its last position during period λ−1 to the assigned crowd and performing its covering task (flying) during period λ. We recall that δ−uλ is the energy percentage threshold forcing an UAV u to return to a CS during a period λ.(15)euλ−1−ε−uλ≥δ−uλ,∀λ∈Λ,∀u∈Uλ.Constraints (16) ensure that each UAV u∈Uλ, assigned to a CS during the period λ−1, has the minimum required autonomy (δ+uλ) to leave the CS.(16)euλ−1+ε+uλ≥δ+uλ,∀λ∈Λ,∀u∈Uλ.Constraints (17) ensure that the charge percentage of each UAV u∈Uλ cannot exceed 100%.(17)euλ=mineuλ−1+ε+uλ,100,∀λ∈Λ,∀u∈Uλ.


## 2.5.2. Crowd Constraints

Constraints (18) ensure that during each period λ∈Λ and each crowd w∈Wλ demand should be satisfied.(18)∑u∈Uλ∑k∈Kλ−1xukwλ=dwλ,∀λ∈Λ,∀w∈Wλ.


## 2.5.3. CS Constraints

Constraints (19) ensure that the number of UAVs assigned to a CS s∈Sλ in a period λ∈Λ cannot exceed the station capacity rs.(19)∑u∈Uλ∑k∈Kλ−1xuksλ≤rs,∀λ∈Λ,∀s∈Sλ.


## 2.6. MILP-MPCT Model

By considering one of the objective functions expressed by equations (6) and (7), presented in Section 2.4, and the set of the ten constraints (8)–(19), presented in Section 2.5, we can build two different MILP models to solve the MPCT problem. The MILP-MPCT model that considered the objective function ZT aimed to minimize the total time consumed by UAVs during their transitions from one period to another during the whole OCA life-cycle time. Furthermore, when we considered the same set of constraints with the objective function ZE we obtained a MILP-MPCT model that aimed to minimize the total energy consumed by all UAVs to move between their different positions and to cover crowds during the whole OCA life-cycle time.


## 2.7. How Does the MILP-MPCT Model Work?

The proposed model MILP-MPCT considers many crowds that move in different directions. At any given time, each crowd is located precisely (via latitude and longitude) and requires a minimum number of UAVs. After every period, the location of the crowd and the number of required UAVs change. Crowds are capable of growing, shrinking, changing structure, merging with other crowds, or splitting (unmixing), as long as they are moving. All the crowds should be covered by a set of available UAVs initially located in charging stations. The MILP-MPCT model aims to obtain an optimal allocation of UAVs to track crowds throughout the OCA life-cycle at the same time. By using the necessary number of UAVs, all crowds can be covered while minimizing their movements and energy consumption. We recall that, we considered that crowds future movements are predictable which is reasonable in some situations where their behaviors is known and can be accurately forecasted.The MILP-MPCT model takes, as inputs, the list of available UAVs and their positions, the number of stations and their positions, and the crowds and their needs in terms of UAVs. Then, it provides a schedule throughout the whole OCA life-cycle by assigning at the beginning of each period of certain UAVs to cover crowds and others to stations, while minimizing the total movement time and energy consumption of all UAVS.


## 3. Experimental Results and Analysis

In this section, we perform a set of experiments to evaluate the effectiveness and the stability of the proposed MILP-MPCT model. It is implemented using DOcplex Python Modeling API of IBM-ILOG-CPLEX (version 12.10). All simulations have been conducted on a personal computer (Intel(R) Core-(TM) i7-10700 CPU, 3.20 GHz with 16 GB RAM) running with Windows 11 and Python 3.7 compiler.Note that our goal is to show that the MILP-MPCT model gains in covering ability and improves the solution quality of PCT given by the PCTs solver proposed in [51]. For this reason, we use the same instances generated by Chebil et al. [51] (for more details according to instances generation and the metrics and the parameters used, readers can refer to [51] (section of simulation and computational results)). In Section 3.1, we present an illustrative example to demonstrate the covering ability of the MILP-MPCT model that prove our first contribution compared to the PCTs solver limitation proposed in [51]. In Section 3.2, we introduce some experimental results obtained by the simulation of the MILP-MPCT model on a set of instances. These results show the improvement made by the MILP-MPCT model, compared to PCTs solver, in terms of the objective functions values described in Section 2.4. In Section 3.3, we present the limitation of the proposed MILP-MPCT model that motivates our future challenge to optimally solve the CT problem using UAVs.


### 3.1. Illustration of MILP-MPCT Covering Ability

In order to highlight the MILP-MPCT covering ability compared to PCTs solver one, we generate a small scenario with 16 UAVs and 4 periods with durationT = 600 seconds. Table 1 summarizes the crowds demands during each period, the CSs capacities, and the initial distribution of UAVs over CSs. We recall that PCTs solver presented in [51] solves iteratively a PCT problem, for each period λ∈Λ of a given OCA life-cycle, by solving the BLP-PCT λ model.Table 1
Illustrative scenario.
CrowdsPeriodsStationsCapacitiesUAVs initial statesP1P2P3P4C133——S14U11-U12-U15C22255S25U1-U10-U13-U16C322——S36U2-U3-U6-U7-U9-U14C43334S43U4-U5-U8The objective of the CT is to assign UAVs to crowds, during the whole OCA life-cycle time, with respect to their demands. Figure2 represents the initial OCA and CMA system states of the illustrative scenario where all UAVs are fully charged and assigned to their initial CSs. The CMA system is permanently connected with (i) all CSs to periodically control the situations of all UAVs and (ii) all sensors (e.g., cameras) to receive a real-time OCA situation in terms of crowd movements and densities and their UAVs needs. These types of communications can be established using advanced technologies that ensure energy saving/minimization of autonomous devices [65, 66].Figure 2
Initial OCA life-cycle state.Figure3 represents the OCA and CMA system states after the application of the PCTs solver on the illustrative example. The first assignment of the UAVs to crowds starts during the period P1 λ=1 (see Figure 3(a)). We noticed that, when solving BLP-PCT1 by the PCTs solver, only ten UAVs are used to ensure crowds coverage. In the next period P2 λ=2 (see Figure 3(b)), when BLP-PCT2 is solved, all UAVs has the required energy to cover all the crowds during that period. In order to minimize the total energy consumption, the optimal solution of BLP-PCT2 kept using the same flying UAVs in the previous period. Unfortunately, the PCTs solver cannot solve BLP-PCT3 and BLP-PCT4. Indeed, for period P3 λ=3, all used UAVs during the previous two periods does not have the minimum required energy to perform the covering task, and thus must return to CSs for charging. With a total of eight requested UAVs by crowds during period P3, there are only six available UAVs (not used from the beginning of the OCA life-cycle) that makes the problem BLP-PCT3 infeasible. We recall that this issue, called “PCTs solver myopia” and already mentioned among our motivational factors in Section 1, is caused by the PCTs solver covering inability.Figure 3
Simulation of the solution given by PCTs solver. (a) Solution provided by BLP-PCT1. (b) Solution provided by BLP-PCT2.
(a)(b)Otherwise, the solution provided by the MILP-MPCT model (see Figure4) demonstrates its efficient covering ability to solve all periods during the whole OCA life-cycle of the illustrative scenario represented in Table 1. Indeed, the MILP-MPCT model chooses efficiently the most appropriate UAVs during each period. In fact, for every period λ, the UAVs assignment is guided by the OCA requirements in the next periods (λ+1,λ+2,⋯Λ). Contrary to the PCTs solver limitation motioned above, the MILP-MPCT model has an efficient covering ability thanks to its perspicacity that we call “clairvoyance.” In fact, the mono-periodic model proposed by Chebil et al. [51] suffers from “myopia.” Indeed, at each period it solves the PCT problem without considering the future periods’ needs that causes its inability to solve many PCT instances. However, the MILP-MPCT model handles with the interactions between all periods, of the whole OCA life-cycle, by considering all their requirements at the same time. Thanks to this “clairvoyance,” the solutions provided by the MILP-MPCT should be better (or equal, in the worst case) to those provided by the mono-periodic model.Figure 4
Simulation of the solution given by MILP-MPCT model. (a) Assigning UAVs period 1. (b) Assigning UAVs period 2. (c) Assigning UAVs period 3. (d) Assigning UAVs period 4.
(a)(b)(c)(d)The PCTs solver can be viewed as an approximate algorithm based on decomposing the MPCT problem intoΛ subproblems, where each subproblem represents an independent CT problem for a given period. Having a global vision on all the life-cycle system allows the MILP-MPCT to make choices that seems illogical by considering only the current period (e.g., an UAV coming back to a charging station with a sufficient charge autonomy allowing it to continue monitoring for the next periods), but we understand later that these choices were necessary to satisfy the demand of the crowds during all the OCA life-cycle time.


### 3.2. MILP-MPCT Performance Analysis

In this section, we present and discuss the computational results obtained by MILP-MPCT model to solve the CT using UAVs. We tested the MILP-MPCT model on the benchmark instances generated by Chebil et al. [51] in which the authors proposed a set of 840 instances under diversified scenarios during a fixed one-hour OCA life-cycleC=3600 seconds and a rectangular shaped OCA Q with fixed area equal to 2.106m2. All the instances are generated according to different parameters as the number of periods Λ during the OCA life-cycle C, the number of charging stations Sλ=p, the maximum number of crowds in each period, and the number of required UAVs per 5000m2. There are some other parameters that are fixed randomly or according to some formulas given in details in [51].After solving the instances mentioned above using the MILP-MPCT model, we noticed that 35%, 60%, and 78% of them are solved (without guaranteeing the optimality for all of them) after one, two, and three hours of CPU computing, respectively. 22% of the instances are not solved due to the memory limitation “Out of Memory Error.” It is worthy to note that IBM-ILOG-CPLEX provides a feasible solution (i.e., optimality not guaranteed) after reaching a preset limitation computation time. Indeed, for the majority of the 840 instances, the MILP-MPCT generates a huge number of variables and constraints in the ranges3.37×103,1.64×107 and 3.55×103,1.82×107, respectively.Without loss of generality and in order to have a significant and comparable results to those provided by the PCTs solver, we select only the instances where the MILP-MPCT is optimally solved. Table2 shows the obtained objective values obtained by the MILP-MPCT model and the PCTs solver for each selected instance. The significations of the table headers are as follows:(i)
MPCTZT and MPCTZE: the objective function value obtained by MILP-MPCT when the total time/energy objective (see equations (6) and (7)) is considered, respectively.(ii)
PCTZT and PCTZE: the objective function value obtained by PCTs solver when the total time/energy objective is considered, respectively.(iii)
Dev%: the deviation gap percentage between objective functions values provided by MILP-MPCT and PCTs solver (i.e., the improvement made by MILP-MPCT comparing to PCTs solver).(iv)
Average: the improvement average.Table 2
Results of MILP-MPCT model vs. PCTs solver.
InstancesPCTZTMPCTZTDev (%)PCTZEMPCTZEDev (%)11819158612.8199188510.702211621060.47126711717.5832017172614.431337108718.704228121097.541472111824.0552984237120.54171216712.3963402260023.572218199610.0173820343010.21227622491.1984061316622.04234321458.459427141004.002403193919.3110557654542.192855218323.54116834573216.13369336670.701210149826218.595985523412.5513136441062322.147222578019.971414082822441.60760072574.5115182191559314.41833379424.69Average15.3811.22From Table2 that is also reflected by Figures 5(a) and 5(b), we can easily notice that the MILP-MPCT model outperforms the PCTs solver for all selected instances with an improvement between 0.47% and 41.60% when the time minimization (objective function (6)) is considered with an average of 15.38% and between 0.70% and 24.05% when the energy minimization (objective function (7)) is considered with an average of 11.22%. We justify these results by the fact that the MILP-MPCT model has a wide visibility comparing to the PCTs solver one. Indeed, for a given period of an OCA life-cycle, the MILP-MPCT considers all other periods’ needs when deciding what UAVs should be assigned to a given crowd. Then, a good decision of UAVs movements is made to minimize the time and energy. This MILP-MPCT strength point, already discussed in the previous section, is not owned by the PCTs solver that solve each BLP-PCT λ separately for each period.Figure 5
Results of MILP-MPCT model vs. PCTs solver [51]. (a) Time minimization. (b) Energy minimization.
(a)(b)Figure6 shows comparisons between the total consumed times and between the total consumed energies when we apply the MILP-MPCT model with one of the defined objective functions (i.e., time minimization equation (1) or energy minimization equation (7)), then we compare its value with the total time or energy, consumed by all UAVs during the whole OCA life-cycle, when the other objective function is considered, respectively (e.g., if we apply MILP-MPCT with the objective function that minimizes the time, then we calculate the total consumed energy of the obtained solution and compare it to the consumed energy when the objective function that minimizes the energy is considered, and vice versa). The aims of this comparison are mainly (i) to provide information about the gap between the total consumed time/energy when we have different objectives, (ii) to evaluate the influenced relationship between the two objective functions, and (iii) to allow us to select the objective to consider in priority when certain contexts are given.Figure 6
Times and energies comparison by changing the considered objective function. (a) Total consumed times relative to different objective functions. (b) Total consumed energies relative to different objective functions.
(a)(b)Figure6(a) presents a comparison between the total consumed times by all UAVs when we consider the objective function (6) designated by the blue plot and when we consider the objective function (7) designated by the orange plot. We notice that for most instances the two plots are very close which is explained by the fact that the flying time requires implicitly an energy consumption. It is also worthy to note that the average deviation is equal to 21.83%, which is relatively high and is caused by some exceptions such as instances 10, 11, 14, and 15. We justify this anomaly by the fact that UAVs fleet is heterogeneous for each instance. Indeed, some UAVs characteristics, such as their energy consumption rates τ−u and their speeds ϑu, affect the founded solution given by the MILP-MPCT model. For example, in instance 11, the speed of the UAV U50 is 158m/s and the speed of the UAV U35 is 51m/s (around 3 times) with τ−U50=39 and τ−U35=34. It is easy to conclude that when the objective function (6) is considered, the MILP-MPCT favors the use of UAV U50 than UAV U35. On the other hand, when the objective function (6) is considered, the MILP-MPCT gives advantage to use UAV U35 than UAV U50. In the same manner, Figure 6(b) presents a comparison between the total consumed energies by all UAVs when we consider individually the objective functions (7) or (6) designated by orange and blue plot, respectively.


### 3.3. MILP-MPCT Limitation

This section intends to provide readers with meaningful information to ensure research transparency, which is an ethical element of scientific inquiry to facilitate future research.As discussed in Section3.2, for some large instances, we found that IBM-ILOG-CPLEX crashes with an “Out of memory” message before reaching the time limit. For other instances, this limit time is insufficient to find even one feasible solution. Despite the performance of the MILP-MPCT model in terms of planning and assigning strategic moves of the UAVs to crowds thanks to its “clairvoyance,” it is still not able to solve large-size instances. It is clear that increasing the number of periods, UAVs, CSs, and crowds involves directly an increasing number of decisions variables and constraints, and then an overhead of CPU-time. Since the computational time is extremely data-dependent, some instances cannot be solved at all within the time limits. It is worthy to note that the long execution time due to the large number of variables of some instances cannot be considered as a real limit of the model. Indeed, we remind that MILP-MPCT is a multiperiodic model based on prediction that can allow the decision maker to launch it before a large amount of time from the beginning of crowds’ supervision.Regarding the objectives to be optimized, we find that there is a trend to minimize time, distance, and energy. However, some of the optimization objectives were closely related. One interesting direction would be to study the problem of minimizing the number of UAVs needed to cover the crowds, which also reduces the model integration cost in real-life problems. Consequently, the objective function can be designated as a trade-off between the flight distance, the energy consumption, the number of required UAVs, and the QoS.


## 3.1. Illustration of MILP-MPCT Covering Ability

In order to highlight the MILP-MPCT covering ability compared to PCTs solver one, we generate a small scenario with 16 UAVs and 4 periods with durationT = 600 seconds. Table 1 summarizes the crowds demands during each period, the CSs capacities, and the initial distribution of UAVs over CSs. We recall that PCTs solver presented in [51] solves iteratively a PCT problem, for each period λ∈Λ of a given OCA life-cycle, by solving the BLP-PCT λ model.Table 1
Illustrative scenario.
CrowdsPeriodsStationsCapacitiesUAVs initial statesP1P2P3P4C133——S14U11-U12-U15C22255S25U1-U10-U13-U16C322——S36U2-U3-U6-U7-U9-U14C43334S43U4-U5-U8The objective of the CT is to assign UAVs to crowds, during the whole OCA life-cycle time, with respect to their demands. Figure2 represents the initial OCA and CMA system states of the illustrative scenario where all UAVs are fully charged and assigned to their initial CSs. The CMA system is permanently connected with (i) all CSs to periodically control the situations of all UAVs and (ii) all sensors (e.g., cameras) to receive a real-time OCA situation in terms of crowd movements and densities and their UAVs needs. These types of communications can be established using advanced technologies that ensure energy saving/minimization of autonomous devices [65, 66].Figure 2
Initial OCA life-cycle state.Figure3 represents the OCA and CMA system states after the application of the PCTs solver on the illustrative example. The first assignment of the UAVs to crowds starts during the period P1 λ=1 (see Figure 3(a)). We noticed that, when solving BLP-PCT1 by the PCTs solver, only ten UAVs are used to ensure crowds coverage. In the next period P2 λ=2 (see Figure 3(b)), when BLP-PCT2 is solved, all UAVs has the required energy to cover all the crowds during that period. In order to minimize the total energy consumption, the optimal solution of BLP-PCT2 kept using the same flying UAVs in the previous period. Unfortunately, the PCTs solver cannot solve BLP-PCT3 and BLP-PCT4. Indeed, for period P3 λ=3, all used UAVs during the previous two periods does not have the minimum required energy to perform the covering task, and thus must return to CSs for charging. With a total of eight requested UAVs by crowds during period P3, there are only six available UAVs (not used from the beginning of the OCA life-cycle) that makes the problem BLP-PCT3 infeasible. We recall that this issue, called “PCTs solver myopia” and already mentioned among our motivational factors in Section 1, is caused by the PCTs solver covering inability.Figure 3
Simulation of the solution given by PCTs solver. (a) Solution provided by BLP-PCT1. (b) Solution provided by BLP-PCT2.
(a)(b)Otherwise, the solution provided by the MILP-MPCT model (see Figure4) demonstrates its efficient covering ability to solve all periods during the whole OCA life-cycle of the illustrative scenario represented in Table 1. Indeed, the MILP-MPCT model chooses efficiently the most appropriate UAVs during each period. In fact, for every period λ, the UAVs assignment is guided by the OCA requirements in the next periods (λ+1,λ+2,⋯Λ). Contrary to the PCTs solver limitation motioned above, the MILP-MPCT model has an efficient covering ability thanks to its perspicacity that we call “clairvoyance.” In fact, the mono-periodic model proposed by Chebil et al. [51] suffers from “myopia.” Indeed, at each period it solves the PCT problem without considering the future periods’ needs that causes its inability to solve many PCT instances. However, the MILP-MPCT model handles with the interactions between all periods, of the whole OCA life-cycle, by considering all their requirements at the same time. Thanks to this “clairvoyance,” the solutions provided by the MILP-MPCT should be better (or equal, in the worst case) to those provided by the mono-periodic model.Figure 4
Simulation of the solution given by MILP-MPCT model. (a) Assigning UAVs period 1. (b) Assigning UAVs period 2. (c) Assigning UAVs period 3. (d) Assigning UAVs period 4.
(a)(b)(c)(d)The PCTs solver can be viewed as an approximate algorithm based on decomposing the MPCT problem intoΛ subproblems, where each subproblem represents an independent CT problem for a given period. Having a global vision on all the life-cycle system allows the MILP-MPCT to make choices that seems illogical by considering only the current period (e.g., an UAV coming back to a charging station with a sufficient charge autonomy allowing it to continue monitoring for the next periods), but we understand later that these choices were necessary to satisfy the demand of the crowds during all the OCA life-cycle time.


## 3.2. MILP-MPCT Performance Analysis

In this section, we present and discuss the computational results obtained by MILP-MPCT model to solve the CT using UAVs. We tested the MILP-MPCT model on the benchmark instances generated by Chebil et al. [51] in which the authors proposed a set of 840 instances under diversified scenarios during a fixed one-hour OCA life-cycleC=3600 seconds and a rectangular shaped OCA Q with fixed area equal to 2.106m2. All the instances are generated according to different parameters as the number of periods Λ during the OCA life-cycle C, the number of charging stations Sλ=p, the maximum number of crowds in each period, and the number of required UAVs per 5000m2. There are some other parameters that are fixed randomly or according to some formulas given in details in [51].After solving the instances mentioned above using the MILP-MPCT model, we noticed that 35%, 60%, and 78% of them are solved (without guaranteeing the optimality for all of them) after one, two, and three hours of CPU computing, respectively. 22% of the instances are not solved due to the memory limitation “Out of Memory Error.” It is worthy to note that IBM-ILOG-CPLEX provides a feasible solution (i.e., optimality not guaranteed) after reaching a preset limitation computation time. Indeed, for the majority of the 840 instances, the MILP-MPCT generates a huge number of variables and constraints in the ranges3.37×103,1.64×107 and 3.55×103,1.82×107, respectively.Without loss of generality and in order to have a significant and comparable results to those provided by the PCTs solver, we select only the instances where the MILP-MPCT is optimally solved. Table2 shows the obtained objective values obtained by the MILP-MPCT model and the PCTs solver for each selected instance. The significations of the table headers are as follows:(i)
MPCTZT and MPCTZE: the objective function value obtained by MILP-MPCT when the total time/energy objective (see equations (6) and (7)) is considered, respectively.(ii)
PCTZT and PCTZE: the objective function value obtained by PCTs solver when the total time/energy objective is considered, respectively.(iii)
Dev%: the deviation gap percentage between objective functions values provided by MILP-MPCT and PCTs solver (i.e., the improvement made by MILP-MPCT comparing to PCTs solver).(iv)
Average: the improvement average.Table 2
Results of MILP-MPCT model vs. PCTs solver.
InstancesPCTZTMPCTZTDev (%)PCTZEMPCTZEDev (%)11819158612.8199188510.702211621060.47126711717.5832017172614.431337108718.704228121097.541472111824.0552984237120.54171216712.3963402260023.572218199610.0173820343010.21227622491.1984061316622.04234321458.459427141004.002403193919.3110557654542.192855218323.54116834573216.13369336670.701210149826218.595985523412.5513136441062322.147222578019.971414082822441.60760072574.5115182191559314.41833379424.69Average15.3811.22From Table2 that is also reflected by Figures 5(a) and 5(b), we can easily notice that the MILP-MPCT model outperforms the PCTs solver for all selected instances with an improvement between 0.47% and 41.60% when the time minimization (objective function (6)) is considered with an average of 15.38% and between 0.70% and 24.05% when the energy minimization (objective function (7)) is considered with an average of 11.22%. We justify these results by the fact that the MILP-MPCT model has a wide visibility comparing to the PCTs solver one. Indeed, for a given period of an OCA life-cycle, the MILP-MPCT considers all other periods’ needs when deciding what UAVs should be assigned to a given crowd. Then, a good decision of UAVs movements is made to minimize the time and energy. This MILP-MPCT strength point, already discussed in the previous section, is not owned by the PCTs solver that solve each BLP-PCT λ separately for each period.Figure 5
Results of MILP-MPCT model vs. PCTs solver [51]. (a) Time minimization. (b) Energy minimization.
(a)(b)Figure6 shows comparisons between the total consumed times and between the total consumed energies when we apply the MILP-MPCT model with one of the defined objective functions (i.e., time minimization equation (1) or energy minimization equation (7)), then we compare its value with the total time or energy, consumed by all UAVs during the whole OCA life-cycle, when the other objective function is considered, respectively (e.g., if we apply MILP-MPCT with the objective function that minimizes the time, then we calculate the total consumed energy of the obtained solution and compare it to the consumed energy when the objective function that minimizes the energy is considered, and vice versa). The aims of this comparison are mainly (i) to provide information about the gap between the total consumed time/energy when we have different objectives, (ii) to evaluate the influenced relationship between the two objective functions, and (iii) to allow us to select the objective to consider in priority when certain contexts are given.Figure 6
Times and energies comparison by changing the considered objective function. (a) Total consumed times relative to different objective functions. (b) Total consumed energies relative to different objective functions.
(a)(b)Figure6(a) presents a comparison between the total consumed times by all UAVs when we consider the objective function (6) designated by the blue plot and when we consider the objective function (7) designated by the orange plot. We notice that for most instances the two plots are very close which is explained by the fact that the flying time requires implicitly an energy consumption. It is also worthy to note that the average deviation is equal to 21.83%, which is relatively high and is caused by some exceptions such as instances 10, 11, 14, and 15. We justify this anomaly by the fact that UAVs fleet is heterogeneous for each instance. Indeed, some UAVs characteristics, such as their energy consumption rates τ−u and their speeds ϑu, affect the founded solution given by the MILP-MPCT model. For example, in instance 11, the speed of the UAV U50 is 158m/s and the speed of the UAV U35 is 51m/s (around 3 times) with τ−U50=39 and τ−U35=34. It is easy to conclude that when the objective function (6) is considered, the MILP-MPCT favors the use of UAV U50 than UAV U35. On the other hand, when the objective function (6) is considered, the MILP-MPCT gives advantage to use UAV U35 than UAV U50. In the same manner, Figure 6(b) presents a comparison between the total consumed energies by all UAVs when we consider individually the objective functions (7) or (6) designated by orange and blue plot, respectively.


## 3.3. MILP-MPCT Limitation

This section intends to provide readers with meaningful information to ensure research transparency, which is an ethical element of scientific inquiry to facilitate future research.As discussed in Section3.2, for some large instances, we found that IBM-ILOG-CPLEX crashes with an “Out of memory” message before reaching the time limit. For other instances, this limit time is insufficient to find even one feasible solution. Despite the performance of the MILP-MPCT model in terms of planning and assigning strategic moves of the UAVs to crowds thanks to its “clairvoyance,” it is still not able to solve large-size instances. It is clear that increasing the number of periods, UAVs, CSs, and crowds involves directly an increasing number of decisions variables and constraints, and then an overhead of CPU-time. Since the computational time is extremely data-dependent, some instances cannot be solved at all within the time limits. It is worthy to note that the long execution time due to the large number of variables of some instances cannot be considered as a real limit of the model. Indeed, we remind that MILP-MPCT is a multiperiodic model based on prediction that can allow the decision maker to launch it before a large amount of time from the beginning of crowds’ supervision.Regarding the objectives to be optimized, we find that there is a trend to minimize time, distance, and energy. However, some of the optimization objectives were closely related. One interesting direction would be to study the problem of minimizing the number of UAVs needed to cover the crowds, which also reduces the model integration cost in real-life problems. Consequently, the objective function can be designated as a trade-off between the flight distance, the energy consumption, the number of required UAVs, and the QoS.


## 4. Conclusions

The periodic crowd tracking (PCT) problem consists of assigned UAVs to crowds in order to minimize the consumed time and energy during a given period of time. This paper deals with the multiperiodic crowd tracking (MPCT) problem, an extension of the PCT, where all crowds behaviors are known in advance and the PCT is studied from the multiperiodic aspect.To tackle the problem with a detailed and formal consideration of the optimization aspect, we proposed a new mathematical model (called MILP-MPCT) and test it on different scenarios. Computational experiments were conducted to show that MILP-MPCT is more efficient than PCTs solver proposed in [51] that considers an iterative resolution strategy. The MILP-MPCT provides better solutions in terms of covering ability and the objective function quality, but it is slower in terms of CPU time. This is not considered as a limit for the model because of its multiperiodic context where the schedule can be provided before a sufficient time from the starting of crowds’ supervision. Moreover, we illustrate a scenario when the MILP-MPCT is able to find feasible solutions while the PCTs solver cannot. Thanks to the “clairvoyance” of the model, strategic moves of the UAVs take into account the future behaviors of crowds that allows it to avoid deadlocked situations that make the instance nonfeasible. In order to be objective, we have reserved a whole section to make a self-criticism of our model and to present its limits. Hence, a possible future research direction is to devise new heuristics to solve more larger and more real-life scenarios. Future work may also include the MILP-MPCT adaptation to find the optimal locations of the static CSs or to study the scenario where the CSs are dynamic and can change their locations during the OCA life-cycle. Finally, an open research challenge can be considered to detect and predict different crowded areas by using a new supervised machine learning techniques.



---

*Source: 3001812-2023-02-01.xml*