## 4 Reduction to Graph Problems
For our further analysis, we need to extend the above claim to formulate it for the bi-matrix optimization Problem 3:  
Proposition 1: _Let \(\boldsymbol{c}\) be an arbitrary cycle cover of the generating graph \(G_{gen}\) with two arc weights, \(e_{ij}\) and \(k_{ij}\), where \(k_{ij}\) is the weight defined by Equation (1). Then, the total weight \(\sum_{(i,j)\in\boldsymbol{c}}k_{ij}\) of the cycle cover is equal to the number of vehicles \(K\) required to carry out all the tasks in the considered cycle cover \(\boldsymbol{c}\) in Problem 3: \(K=\sum_{(i,j)\in\boldsymbol{c}}k_{ij}\)._  
Proof: Let \(\boldsymbol{\sigma}\) be a simple cycle entering the cycle cover \(\boldsymbol{c}\) of the generating graph \(G_{gen}\) with two arc weights, and let \(s=\sum_{(i,j)\in\boldsymbol{\sigma}}k_{ij}\). Consider the periodic graph \(G_{\infty}\) that corresponds to the initial Problem 2, which has generated the generating graph \(G_{gen}\). Recall that each node \(i\in\boldsymbol{\sigma}\) corresponds to an infinite number of nodes \(i_{k}\) in graph \(G_{\infty}\), \(0\leq k<\infty\). As proven in [20], a cycle \(\boldsymbol{\sigma}\) can be unpacked into exactly \(s\) chains in graph \(G_{\infty}\) such that no node in one chain is linked to a node in another chain. From the description of Problem 2 and the definition of the cycle weight, it follows that each chain corresponds to one vehicle performing the tasks of the chain, and then the value \(\sum_{(i,j)\in\boldsymbol{\sigma}}k_{ij}\) is equal to the number of vehicles required to carry out all the tasks of the cycle \(\boldsymbol{\sigma}\). To complete the proof, it suffices to notice that the graph \(G_{gen}\) can be partitioned into a set \(\boldsymbol{c}\) composed of a finite number of simple cycles, and therefore, the total number of chains \(\sum_{(i,j)\in\boldsymbol{c}}k_{ij}\) corresponding to all simple cycles in partition \(\boldsymbol{c}\) is equal to the number of vehicles required, which proves the claim. From Proposition 1, it follows that Problem 3 reduces to the following Problem 4. Problem 4: _Find a cycle cover of the graph \(G_{gen}\) with a set of cycles \(\boldsymbol{c}\), so as to maximize the ratio \(E/K=\sum_{(i,j)\in\boldsymbol{\sigma}}e_{ij}\!\!\!/\!\!\sum_{(i,j)\in \boldsymbol{\sigma}}k_{ij}\)._The question remains: how to efficiently solve the resulting cycle-covering problem for the graph \(G_{gen}\)? We will answer this question in the following sections:  
_The illustrative example._ For the reader's convenience, consider a numerical example. It is adapted from the work of [PERSON] (2018), who studied the problem of minimizing the number of aircraft to operate a fixed daily repeating set of flights; we generalize [PERSON]'s example for the problem of maximizing the average fleet profit. While the latter numerical example was used in (Kal  
Using the flight schedule given in Table 3, it is possible to plot graph \(G_{\infty}\). A fragment of graph \(G_{\infty}\) drawn for three consecutive periods, starting with period 1, is presented in Figure 2.  
The nodes in Figure 2 depict the daily flights denoted 1, 2, 3 and repeated for three sequential periods indexed by 1, 2, and 3; node \(i_{k}\) depicts flight \(i\) (\(i\) = 1, 2, 3) during period \(k\) (\(k\) = 1, 2, 3). For simplicity of notation, Figure 2 shows only the arcs \((i_{k},j_{l})\) between the nearest iterations \(k\) and \(l\) of tasks \(j_{i}\) and \(j_{j}\). Each arc \((i_{k},j_{l})\) in \(G_{\infty}\) has the associated weight \(e(i,j)\). However, the weights are not shown in Figure 2 in order not to overload it. At this point, our initial fleet assignment problem is equivalent to finding the optimal number of infinite periodic disjoint paths covering all nodes and having a maximum average profit per path per period.