# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 3 Problem Description and Mathematical Models
### Travel Time Calculator Considering Robot Movement  
As mentioned in Section 1, one of the two essential issues to consider robots for delivery in indoor environments is the realistic estimation of the travel time. The travel time between two points within buildings requires a few seconds up to a few minutes; thus, if errors are accumulated, then the gap between the actual travel time and the estimated travel time can increase. Therefore, a different approach is needed when a vehicle moves indoors, in contrast to the simple estimation approach of the travel time based on the average speed of the robot. In fact, in the case of truck routing problems, assuming the average speed seems reasonable. Since trucks usually require several hours to move between outdoor locations, any delay occurring due to unexpected road conditions can be offset via acceleration before reaching the destination. However, in the case of indoor robot-based delivery, robots slowly move between indoor locations similar to a human operator walking. Additionally, robots might move much slower if corners are encountered. Moreover, using an elevator inside a building results in an extra delay in the journey. All travel times of all robots within buildings are counted in seconds rather than in minutes or hours. Thus, there is insufficient opportunity to compensate for any delay resulting from corners or elevators within buildings. In this subsection, we divide the indoor movement process of the robot into segments along the horizontal and vertical directions, calculate the travel time for the horizontal (\(t_{ij}^{h}\)) and vertical (\(t_{ij}^{p}\)) movement segments separately, and then sum these travel times to determine the final travel time (\(t_{ij}\)) of the robot. First, which factor imposes the most notable influence on the robot travel time required for indoor horizontal movement? The presence of corners is the greatest obstacle to horizontal robot movement across the floor. In a typical building, corridors and corners are continuously connected, facilitating movement. Therefore, corners mainly affect the travel time because they limit the speed of robot movement. After initiation, the robot increases its speed during movement, and when a corner is encountered, the robot slows down to round the corner. Additionally, after rounding the corner, the robot again accelerates and moves through the hallway. As expected, the more corners between any two points, the more the robot must accelerate and/or decelerate to round these corners, which leads to a delay in travel time. Of course, the lag time to round a corner can comprise only a few seconds, but the lag time can be extended if there are many corners between two points. Before estimating the travel time required for the horizontal movement segment of the robot indoors, the following assumptions apply:  
* The indoor pathway of the robot consists of corridors and corners. * The robot remains stationary at the starting point before movement occurs. * The robot immediately accelerates after starting, and when it reaches an appropriate speed, the robot moves while maintaining this speed. * The robot decelerates ahead of its destination and stops upon reaching the destination. * The robot decelerates to the predetermined speed ahead of a corner and accelerates after rounding the corner. * The acceleration and deceleration ratios (the acceleration and deceleration rates per unit time) of the robot remain constant. To explain how the travel time is estimated in this research, certain situations were assumed. Figure 1 shows the example of indoor robot movement from origin to destination in a multi-story building. First, let us assume the robot only moves on a single floor (\(n^{th}\) floor) to explain the calculation procedure for the horizontal movement. There are two corners between the starting node \(i\) and the destination node, the elevator. Then, we can divide the robot's path into \(L_{1}\), \(L_{2}\), and \(L_{3}\) based on the two corners.