# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 3 Problem Description and Mathematical Models
### Indoor Robot Routing Problem (IRRP)  
An indoor network can be defined as a directed graph with a reasonable travel time. Let \(G=(V,A)\) be a graph where \(V=\{0,1,\ldots,n\}\) comprises a vertex set, and \(A=\{(i,j)|i,j\in V,\,i\
eq j\}\) is an arc set. The travel time, \(t_{ij}\), is associated with the arc set, \(A\). Additionally, vertex 0 represents a depot at which \(K\) homogeneous robots are housed, while the remaining vertices correspond to \(n\) customers. Each customer exhibits a nonnegative delivery quantity, and each robot exhibits a fixed capacity.  
To formulate the IRRP as an MTVRP model, the mathematical model reported in [25] was modified.  
The operating conditions are assumed as follows:  
* One or more robots are allowed to be launched together.
* The robot starts and ends at the depot.
* Multiple trips are allowed, as all demands must be satisfied.  
Figure 3: Travel time calculation of vertical movement with two intermediate stops.  
Since robot storage can be retrofitted to accommodate two or more compartments, a single robot can visit more than one customer up to the maximum capacity.
* Robots are considered fully autonomous and equipped, which suggests that loading and unloading operations do not require much time, which can be neglected.
* The robot possesses a sufficient battery capacity to cover one building.  
Before we formulated the model, the following parameters and variables are defined:  
1. Sets and Indices \[\begin{array}{ll}V=\{0,1,\ldots,n\}&\text{set of depots and customers }(i,\ j\in V);\\ C=\{1,\ldots,n\}&\text{set of customers, for }C\subset V;\\ K=\{1,2,\ldots,K\}&\text{set of homogeneous robots }(k\in K);\\ i,j&\text{index of nodes};\\ k&\text{index of robots}.\end{array}\]
2. Parameters \[\begin{array}{ll}t_{ij}&\text{travel time between nodes }i\text{ and }j;\\ q_{i}&\text{demand quantity at node }i;\\ Q&\text{loading capacity of a robot (unit: \# of parcels)}.\end{array}\]
3.2.3. Decision Variables \[\begin{array}{ll}x_{ij}^{k}&\text{1, set of depots and customers }(i,\ j\in V);\\ &\text{0, otherwise};\\ u_{i}^{k}&\text{carrying load quantity when robot }k\text{ arrives at node }i.\end{array}\]  
With the use of the parameters and decision variables defined above, the IRRP to minimize the total travel time of the robots can be formulated as follows:  
1. Formulation of the IRRP \[\begin{array}{ll}Minimize&\sum_{(i,j)\in A}\sum_{k\in K}t_{ij}x_{ij}^{k} \end{array}\] (5) Subject to: \[\begin{array}{ll}\sum_{\begin{subarray}{c}i\in V\\ i\
eq j\end{subarray}}\sum_{k\in K}x_{ij}^{k}=1,\ \forall j\in C\end{array}\] (6) \[\begin{array}{ll}\sum_{\begin{subarray}{c}j\in V\\ j\
eq i\end{subarray}}\sum_{k\in K}x_{ij}^{k}=1,\ \forall i\in C\end{array}\] (7) \[\begin{array}{ll}\sum_{\begin{subarray}{c}i\in V\\ i\
eq j\end{subarray}}x_{ij}^{k}=\sum_{\begin{subarray}{c}i\in V\\ j\
eq j\end{subarray}}x_{ji}^{k},\ \forall j\in C,\ \forall k\in K\end{array}\] (8) \[u_{i}^{k}-q_{i}\leq u_{j}^{k}+Q\Big{(}1-x_{ij}^{k}\Big{)},\ \forall i,\ j\in A:i\
eq 0, \forall k\in K\] (9) \[q_{i}\leq u_{i}^{k}\leq Q,\ \forall i\in V,\ \forall k\in K\] (10) \[x_{ij}^{k}\in\{0,\ 1\},\ \forall i,j\in A,\forall k\in K\] (11) \[u_{i}^{k}\geq 0,\ \forall i\in N,\forall k\in K\] (12)  
Objective function (5) minimizes the total travel time of the robots. Constraints (6)-(8) are flow conservation constraints, ensuring that each robot trip starts and ends at the depot. Additionally, these constraints guarantee that each customer is served exactly once. Constraint (9) defines the carrying load quantity flows, and Constraint (10) enforces capacity limitations on the robots. When a robot visits customer \(i\), it should at least satisfy the demand of customer \(i\), but the robot cannot carry in excess of the capacity. Note that these two constraints also eliminate subtours [26]. Finally, Constraints (11) and (12) specify the decision variables, where \(x_{ij}^{k}\) is defined as a binary variable and can only equal 0 or 1, and the carrying load quantity \(u_{i}^{k}\) is ensured to be nonnegative.