# Unmanned Aerial Vehicle Routing Problems: A Literature Review
## 2 UAV Routing with an Emphasis on the Problem Type, Transportation Mode, and Degree of Automation
### Based on Modes of Transport
#### 2.2.3. Mathematical Formulation of the Problem  
In this section, we formally define the UAV routing, the problem in which a homogeneous fleet of UAVs has to visit a set of nodes to deliver demands assuming dynamics constraints.  
In the following, we assume a homogeneous fleet \(K\) of UAVs is available at the depot 0. Let \(G=(N,E)\) be a graph, representing transportation network, where: \(N=\{0\ldots n\}\) is a set of nodes and \(E=\{[i,\ j]\}\,|\,i,\ j\in N\,,i\
eq j\}\) is a set of edges. Travel distance from node \(i\) to \(j\) (length of edge \(\{i,\ j\}\)) is \(d_{i,j}\) and travel time from node \(i\) to \(j\) is \(t_{i,j}\). Let us assume that demand at node \(i\ \in\ N\), \(i\
eq 0\) is \(D_{i}\) and maximum loading capacity of a UAV is \(Q\). Each UAV has a maximum energy capacity of \(P_{max}\), and \(P_{i,j}^{k}\) is the energy consumed by a UAV per time unit. Time that \(k^{\text{th}}\) UAV arrives at the node \(i\) is denoted by \(y_{i}^{k}\) and payload weight amount delivered to node \(i\) by \(k^{\text{th}}\) UAV is denoted by \(c_{i}^{k}\). Ground speed of a UAV from node \(i\) to \(j\) is \(vg_{i,j}\).  
Let us define the following binary variables.  
\(x_{i,j}^{k}\)\(\begin{array}{ll}\text{binary variable used to indicate if $k^{\text{th}}$ UAV}\\ \text{travels from node $i$ to node $j$}\end{array}\)  
\(x_{i,j}^{k}=\begin{cases}1&\text{if $k^{\text{th}}$ UAV }\\ 0&\text{otherwise.}\end{cases}\)  
The objective function (1) minimizes the sum of the total travel time to visit all targets for a fleet UAVs. Constraints (2) ensure the relationship between the binary decision variable of \(x_{i,j}^{k}\) and the decision variable of \(y_{i}^{k}\). where: \(w\)--time spent for take-off and landing of a UAV. If an UAV \(k\) is flying from node \(i\) to j, then arrival time \(y_{j}^{k}\) to node \(j\) is equal to the sum of travel time \(t_{i,j}\) between node \(i\) to \(j\), time spent for take up landing \(w\) and the arrival time \(y_{i}^{k}\) to node \(i\). Constraints (3) make sure that the demand assigned to a UAV should not exceed its capacity. Constraint (4) represents the flow of UAVs, which ensure that an UAV arriving at a node and that UAV must leave from that node. Constraint (5) make sure that each UAV departs from the depot (Node 0) and comes back to the depot. Constraint (6) ensures that that energy consumed by the \(k^{\text{th}}\) UAV should be less than or equal to the maximum energy capacity of the UAV. Collision avoidance between UAVs and weather conditions can be incorporated into the model as well.  
\[\min\sum_{k=1}^{K}\,\sum_{i=1}^{n}\,\sum_{j=1}^{n}\,\frac{d_{ij}}{vg_{i,j}}\cdot x _{ij}^{k}\, \tag{1}\]  
_s.t._  
\[(x_{i,j}^{k}=1)\Rightarrow\ \ (\ y_{j}^{k}=y_{i}^{k}+t_{i,j}+w)\qquad\forall(i,j) \in N,\ \forall k\in K \tag{2}\]  
\[\sum_{i\in N}\,\sum_{j\in N}\,x_{i,j}^{k}c_{j}^{k}\ \leqslant Q\qquad k=1\ldots K \tag{3}\]  
\[\sum_{j\in N}\,\,x_{i,j}^{k}-\sum_{j\in N}\,\,x_{j,i}^{k}=0\,\,\,\,\,\,\,\,k =1\ldots K,\ \forall i\in N_{0}=N\,\cup\,\{0\} \tag{4}\]  
\[(x_{i,j}^{k}>0)\Rightarrow\ \ (\sum_{i\in N}\,\,x_{0,i}^{k}=\sum_{i\in N}\,\,x_{i,0}^{k }=1\,\,)\,\,\,\,\,\,\,\,\,\,k=1\ldots K \tag{5}\]\[\sum_{i\in N}\ \sum_{j\in N}\ x_{i,j}^{k}\ P_{i,j}^{k}\ t_{i,j}\leqslant P_{max}\qquad k =1\ldots K \tag{6}\]