## 5 Reduction to the Fractional Assignment Problem  
In this section, we reformulate Problem 4 as a fractional assignment problem. Recall that an _assignment_ can be stated in the form of an \(n\times n\) matrix \(A\) whose entries, denoted \(a_{ij}\), are 0 or 1, and \(a_{ij}=1\) occurs in each row and each column of the matrix \(A\) exactly once. Consider Problem 4, defined in the previous section, and the corresponding cycle cover of the graph \(G_{gen}\). **Proposition 2**. : _The set of all cycles in the cycle cover \(\boldsymbol{c}=(C_{1},C_{2},\ldots,C_{q})\) of the graph \(G_{gen}\), where \(q\) is the number of cycles in \(\boldsymbol{c}\), can be considered as an \(n\times n\) assignment \(A\) in the matrix form defined as follows:_  
\[a_{ij}=1\text{ if and only if the arc (i,j) from }G_{gen}\text{ belongs to }\boldsymbol{c},\text{ and }a_{ij}=0\text{ otherwise}. \tag{2}\]  
Indeed, from the definition of the cycle cover, it follows that the matrix \(A\) contains \(n\) rows and \(n\) columns, its elements are 1 or 0, and each \(a_{ij}=1\) occurs exactly once for each row \(i\) and each column \(j\) (\(i,j=1,\ldots,n\)), which proves the claim. Given a profit matrix \(\boldsymbol{E}\), a weight matrix \(\boldsymbol{K}\), and an arbitrary assignment matrix \(A\), the profit and weight values corresponding to the assignment \(A\) are defined, respectively, as follows:  
\[E(A)=\sum_{(i,j)\in A}e_{ij}a_{ij}\ \text{ and }\ K(A)=\sum_{(i,j)\in A}k_{ij}a_{ij}.\]  
In the above expression and wherever necessary, the notation \((i,j)\in A\) denotes all pairs of indices \(i\), \(j\) corresponding to entries \(a_{ij}=1\) of the assignment matrix \(A\). For ease of notation, in the expressions \(E(A)\) and \(K(A)\) below, we will omit the symbol \(a_{ij}\). In what follows, in accordance with (2), instead of maximizing \(P=\sum_{(i,j)\in\boldsymbol{c}}e_{ij}\!\!/\sum_{(i,j)\in\boldsymbol{c}}k_{ij}\) over all cycle covers of the graph \(G_{gen}\) (Problem 4), we will focus on finding the _optimal assignment_ that maximizes \(P=E(A)/K(A)=\sum_{(i,j)\in A}e_{ij}/\sum_{(i,j)\in A}k_{ij}\). Let us denote by \(\boldsymbol{C}\) the set of all assignments \(A\) in the form of \(n\times n\) matrices. Now Problem 4 in Section 2 reduces to the following fractional assignment Problem 5 (**FAP**):  
**Problem 5 (**Fap**). : _Given two \(n\times n\) matrices \(\boldsymbol{E}\) and \(\boldsymbol{K}\), find the optimal assignment \(A^{*}\), common to the matrices \(\boldsymbol{E}\) and \(\boldsymbol{K}\), that is, the one that maximizes the average fleet profit per vehicle \(P=E(A)/K(A)\):_  
\[P^{*}=E(A^{*})/K(A^{*})=\max_{A\in\boldsymbol{C}}E(A)/K(A)=\max_{A\in \boldsymbol{C}}\sum_{(i,j)\in A}e_{ij}/\sum_{(i,j)\in A}k_{ij}.\]  
The following statement shows that the elements of matrix \(\boldsymbol{K}\) in the considered problem are the small positive integers not exceeding 3; in fact, this is an important property that reduces the complexity of the problem by a factor of \(n\). **Proposition 3**. : _If the arc (\(i,j\)) \(\in G_{gen}\), then, for any element \(k_{ij}\) of matrix \(\boldsymbol{K}\), it holds that \(k_{ij}\leq 3\)._Proof. : Consider the \(k(i)\)th iteration of task \(J_{i}\) that starts at time \(a_{i}+k(i)\cdot p\), and let \(l(j)\) be the nearest iteration of task \(J_{j}\) that the vehicle can perform after the \(k(i)\)th iteration of task \(J_{i}\). Consider two cases: \(a_{i}<b_{i}\) and \(a_{i}>b_{i}\). (i) \(a_{i}<b_{i}\). In this case, the \(k(i)\)th iteration of task \(J_{i}\) ends at time \(b_{i}+k(i)\cdot p\). Then, the nearest iteration of task \(J_{j}\) satisfies the following inequalities:  
\[a_{j}+[l(j)-1]\cdot p<b_{i}+k(i)\cdot p+r_{ij}\leq a_{j}+l(j)\cdot p,\]  
or  
\[a_{j}+[l(j)-k(i)-1]\cdot p<b_{i}+r_{ij}\leq a_{j}+[l(j)-k(i)]\cdot p.\]  
(ii) \(a_{i}>b_{i}\). In this case, the \(k(i)\)th iteration of task \(J_{i}\) ends at time \(b_{i}+[k(i)+1]\cdot p\).