# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 2 Literature Review  
The interest in freight distribution with robots has surged over the past several years, producing numerous field tests and studies [4; 5; 6; 7]. Since this research is related to last-mile delivery in indoor environments, we aimed to focus on service robots that can move and deliver indoors. Continental illustrated a pack of robotic dogs exiting an autonomous vehicle and entering a building for final delivery [8]. A robotic dog is an autonomous, four-legged robot that can manage obstacles in indoor environments. The robotic dog can traverse challenging terrains such as curbs and stairs and can deliver a package in front of the door [9]. Additionally, there exists a bipedal robot, approximately the size and shape of a small adult human, that can navigate indoor environments with the help of light detection and ranging (LIDAR) technology and other sensors [10]. Even though both concepts have yet to be pilot tested with customers, they have indicated the possibility of employing robots to deliver ordered items in buildings. Along with the development of relevant robot technology, academia has shown interest in last-mile delivery using robots for the past couple of years [11]. Most related research utilized the existing vehicle routing problem (VRP) to adopt robots in outdoor environments [12; 13; 14; 15; 16; 17]. Last-mile delivery problems have been solved with various VRP formulations via mixed integer linear programming (MILP), and efficient algorithms have been developed to address larger problems due to the inherent complexity of the VRP. Of course, it might occur that the outdoor environment remains a more general solution for delivery services because technical difficulties are encountered indoors where the global positioning system (GPS) is inoperable [18]. However, owing to advances in simultaneous localization and mapping (SLAM) and the control of robots [19; 20; 21], research on VRP with robots in indoor environments has been initiated. The studies [22; 23] attempted to optimize a task allocation problem (e.g., patrol and delivery services) and plan routes for indoor robots. They suggested a general framework and algorithm, referred to as the fixed destination multi-depot multiple traveling salesman problem. Their study demonstrated that the approach should differ between indoor and outdoor routing. Additionally, [24] introduced an operation design of a robot logistics system for the hotel industry. They assumed that the robot could serve dual jobs, such as delivering and retrieving dishes within a hotel. They calculated the minimum number of required robots, considering a hotel with a long hallway on each floor, and then built a mathematical model to minimize the number of unassigned tasks to robots within the unit execution cycle, e.g., 15 min. Table 1 summarizes the recent research related to robot-based delivery problems. Although the adoption of robots for last-mile delivery is an emerging field in both the industry and academia, almost all attention in academia remains focused on the outdoor routing problem. In other words, there is a lack of research focusing on the indoor routing problem, as indicated in Table 1. Although [24] considered vertical movement using an elevator in their travel time calculation procedure, they did not capture the possibility of intermediate stops or any characteristics of horizontal robot movement (e.g., acceleration, deceleration, and cornering). Unlike outdoor truck routing problems, the indoor robot routing problem (IRRP) requires a more plausible and sophisticated travel time calculation. Applying the existing  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline  
method to IRRP will reduce the reliability of the derived results. To the best of our knowledge, this paper is the first attempt to tackle the IRRP while considering the realistic travel time of robots moving both horizontally and vertically during last-mile delivery. A general but powerful GA-based heuristic also increases the practicality of the research.