## 2 Previous Work  
Since we realize that the general problem under study is very complex (NP-hard in fact) and large in size, making it difficult to solve exactly, the challenge is to decompose it into smaller and simpler sub-problems that can be solved efficiently and thus provide the \"building blocks\" for solving the overall problem. We are interested in finding a special case that, on the one hand, makes the problem solvable and, on the other hand, gives good upper/lower bounds on the objective functions of the general optimization problem.  
The special case studied in this paper is an extension of the problem of minimizing the number of vehicles (airplanes, drones, robots, cars, etc.) needed to meet a fixed, periodically repeating schedule of tasks. This optimization problem has a long history in operations research. A non-periodic, finite-horizon version of the problem, concerned with minimizing the number of tankers to meet a fixed schedule, was solved in 1954 by [PERSON] and [PERSON] [16]. A few years later, [PERSON] and [PERSON] [17] reduced that problem to finding a chain cover of minimum cardinality for finitely partially ordered sets. Using an infinite periodic graph model and a chain covering, [PERSON] and [PERSON] [18] elegantly reduced the periodic minimum-size vehicle problem to an assignment problem solvable in polynomial time. [PERSON] [19] has modified and slightly simplified the Karzanov-Livshits algorithm. [PERSON] [20] proposed a chain-covering algorithm for the periodic case, where a finite number of tasks must be executed periodically over an infinite horizon to efficiently solve the problem as a finite network flow problem. [PERSON] and [PERSON] [21; 22] proposed a periodic graph model that solved a similar scheduling problem with non-Euclidean distances. [PERSON] [23] has solved the more general problem of minimizing the average fleet cost per day of flying subject to a fixed number of aircraft; however, this optimization problem is different from the problem in this study, and besides this, it involves a solution technique induced from dynamic minimum-cost network flows that is substantially different from the technique presented here. [PERSON] and [PERSON] [24] considered the problem of minimizing the number of vehicles required to make periodic deliveries to a set of customers under the assumption that each delivery requires the use of a vehicle for a full day; they thoroughly examined the problem structure, evaluated its complexity, and presented an algorithm that optimally solved the problem for some special cases. Extensive reviews of UAV fleet size optimization techniques and industrial applications are presented, for example, in [12; 13; 14; 15].  
In this paper, we present and explore a more general case of the vehicle scheduling problem; namely, our goal is to find the optimal number of vehicles that maximizes the average environmental fleet benefit per vehicle and, thereby, the UAV fleet's environmental efficiency. This problem is a continuation and extension of the models studied in [16; 17; 18; 19; 20; 21; 22; 23]. Note that the optimal number of vehicles in the latter problem may be strictly greater than the minimum number of vehicles required to meet a given periodic schedule. We propose a new fast algorithm, the logic and main stages of which are presented in Figure 1.