# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 3 Problem Description and Mathematical Models
### Travel Time Calculator Considering Robot Movement
Figure 2 shows a graph of the robot's moving speed and travel time at that moment. The three sections we divided are further divided into three parts again (acceleration (\(A\)), constant (\(U\)), and deceleration (\(D\)), respectively) to follow the above assumptions applied for the horizontal movement segment. The mathematical notations in Figures 1 and 2 are defined as follows: \begin{tabular}{l l} \(A\) & The rate of acceleration; \\ \(U\) & The constant speed; \\ \(D\) & The rate of deceleration; \\ \(L_{i^{\prime}}\) & The portion of the moving distance between two nodes for \(i^{\prime}=1,2,3\); \\ \(L_{i^{\prime}\prime}\) & The moving distance at the different rates for \(i^{\prime}=1,2,3\) and \(j^{\prime}=A,U,D\); \\ \(T_{i^{\prime}\prime}\) & The travel time corresponding to the moving distance \(L_{i^{\prime}\prime}\) for \(i^{\prime}=1,2,3\) and \(j^{\prime}=A,U,D\); \\ \(V_{safe}\) & The safe robot speed obtained via deceleration to safely round a corner; \\ \(V_{max}\) & The maximum speed that a robot can maintain to travel through a corridor. \\ \end{tabular}   
Figure 1: Example of the indoor robot movement from origin to destination in a multi-story building. Figure 2: Graph of moving speed and travel time of robot. \[ \begin{array}{ll}t_{ij}^{h}=\frac{V_{max}}{A}+\frac{V_{max}}{D}+&c_{ij}(\frac{V_ {max}-V_{safe}}{A}+\frac{V_{max}-V_{safe}}{D})\\ &+\frac{\sum_{m}^{c_{ij}+1}L_{m}-\sum_{m=1}^{c_{ij}+1}\left\{\frac{\left(V_{max }-V_{min}^{m}\ A\right)^{2}}{2^{A}}+\frac{V_{min}^{m}\ A\left(V_{max}-V_{min}^ {m}\ A\right)}{A}+\frac{\left(V_{max}-V_{min}^{m}\ D\right)^{2}}{2^{D}}+\frac{V _{min}^{m}\ D\left(V_{max}-V_{min}^{m}\ D\right)}{D}\right\}}{V_{max}}\\ \end{array}  \tag{1}\]  
where:  
\[ \begin{array}{ll}\text{If }c_{ij}=0,\ V_{min,A}^{m}=V_{min,D}^{m}=0\\ \text{If }c_{ij}=1,\ V_{min,A}^{m}=0,\ V_{min,D}^{1}=V_{safe}\\ \text{ }V_{min,A}^{c_{ij}+1}=V_{safe},\text{ and }V_{min,D}^{c_{ij}+1}=0\\ \text{ If }c_{ij}\geq 2,\ V_{min,A}^{1}=0,\ V_{min,D}^{1}=V_{safe},\\ \text{ }V_{min,A}^{m}=V_{min,D}^{m}=V_{safe},\\ \text{ }V_{min,A}^{c_{ij}+1}=V_{safe},\text{ and }V_{min,D}^{c_{ij}+1}=0\\ \end{array} \]  
Once the travel time required for horizontal movement is calculated with Equation (1), the vertical movement segment (\(L_{4}\)) of the robot should be considered because most buildings in cities are multistory buildings. Usually, robots can move between different floors by taking the elevator, as shown in Figure 1.  
As expected, it is difficult to calculate the travel time related to the elevator due to its variability. More specifically, it is difficult to capture the elevator waiting time and the number of intermediate stops. Although we can simply calculate the travel time required for vertical movement by dividing the height by the average elevator speed, similar to other studies [22; 23; 24], there remains a gap between the mathematical model and the actual situation. Therefore, we adopted three scenarios (i.e., peak, normal, and off-peak scenarios) and binomial distribution assumptions to address these scenarios. Before explaining how to calculate the moving distances and travel times required for vertical movement under the various scenarios, the following notations are defined:  
\[ \begin{array}{ll}h&\text{The distance between floors;}\\ L_{4}&\text{The moving distance of vertical movement between the }n^{th}\text{ floor and }m^{th}\text{ floors;}\\ w_{\omega}&\text{The average elevator waiting time under scenario }\omega\text{, for }\omega\in\{\text{peak, normal, off-peak}\};\\ s&\text{The time spent at a stop;}\\ s^{\prime}&\text{The time spent when an intermediate stop occurs;}\\ V_{e}&\text{The speed of the elevator;}\\ T_{4}^{\prime}&\text{The travel time to traverse all floors between the }n^{th}\text{ and }m^{th}\text{ floors on the elevator;}\\ t_{ij}^{\omega}&\text{The total travel time for vertical movement between the }n^{th}\text{ and }m^{th}\text{ floors.}\\ \end{array}