# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
###### Abstract  
With the development of robot technology, trials adopting robots for last-mile delivery are continuing, and the final destination of last-mile delivery is further expanding into indoor environments. Unlike existing studies conducted for robot-based last-mile delivery in outdoor environments, two main issues must be solved to enable last-mile delivery in indoor environments using robots. First, it is necessary to reasonably and realistically estimate the robot travel time considering horizontal and vertical movement segments within a given building. Second, optimizing the robot routing problem based on the estimated robot travel time is necessary. In this paper, we proposed a new method to estimate the robot travel time considering robot movement characteristics and an elevator in a building. In addition, we developed a mathematical model of the robot routing problem and problem-specific heuristic based on a genetic algorithm to quickly solve the proposed mathematical model. It obtained the exact solutions when the problem size was small and near-optimal solutions in the medium- and large-sized problems (average optimality gap: 0.11% and 0.18%, respectively). Through extensive experiments assuming various building structures, it was determined that the proposed model and heuristic can quickly yield realistic solutions for indoor robot-based last-mile delivery. robot routing problem; last-mile delivery; indoor environments; genetic algorithm; heuristics +
Footnote †: journal: Accepted: 9 September 2022  
Footnote †: journal: Accepted: 10 September 2022  
Footnote †: journal: Accepted: 9 September 2022  
acceleration, deceleration, and cornering aspects should be considered. They might delay last-mile delivery and affect the overall delivery time. Additionally, the vertical movement of robots between floors might require an elevator, which has different movement issues from horizontal movement. Thus, horizontal and vertical movement aspects should be reflected when calculating the robot's travel time, which can be used as input into any planning model. Next, once the robot travel time is calculated, it is necessary to formulate and solve the robot routing problem. This depends on the purpose of the service and the type of robot, but, in general, multi-trip should be possible because the robot has a small loading capacity. In addition, we should develop an efficient heuristic that can quickly solve large problems (i.e., task assignment to many robots), entailing many corners and stories in buildings. Although any off-the-shelf solvers can generate solutions with a sophisticated algorithm considering various mathematical problems, it is difficult to provide solutions within a reasonable time for practical problems involving many decision variables and constraints [3]. Therefore, in this paper, regarding robot-based last-mile delivery in an indoor environment, we propose a new method to estimate the robot travel time considering horizontal and vertical movement aspects in a building. Hence, the robot's travel time was calculated by dividing the horizontal and vertical segments. The robot's acceleration, deceleration, and cornering movement characteristics were considered in the horizontal segment. The additional time due to using an elevator, such as waiting, getting on/off, and intermediate stops, was also reflected in the vertical segment. Realistically-estimated travel times then were input into a mathematical model of the robot routing problem based on the existing multiple trip vehicle routing problem (MTVRP). In addition, we developed a problem-specific heuristic based on a genetic algorithm (GA) to quickly solve the proposed mathematical model. Extensive experiments assuming various indoor environments were conducted to validate the proposed model and heuristics in terms of the optimality gap and computation time.