# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 4 Heuristic-Based Solution  
As mentioned in Section 1, commercial optimization solvers cannot always provide the optimal solution for large-sized MILP problems within reasonable computation times. The same problem should be addressed in our case because the problem size can easily become large when considering more floors and customers within buildings. Therefore, an efficient heuristic is needed to address the computational tractability in actual applications, which can quickly generate optimal or near-optimal solutions in terms of the objective value of the IRRP. In this regard, we proposed a heuristic comprising two basic steps: (1) initial solution generation using nearest-neighbor insertion and (2) solution improvement with the GA. The GA is a popular metaheuristic method that can find solutions for NP-hard problems within a reasonable time [27]. This study employed the floor-splitting heuristic to determine whether the initial solution obtained in Step 1 can be updated with the GA. Additionally, certain well-known and validated approaches, such as roulette wheel selection, partially mapped crossover operator for reproduction, and improving rate-based swap operator for mQtation, were adopted. Each step of the proposed heuristic approach can be explained as follows:  
* **Step 1:** Initial solution generation with the nearest-neighbor insertion heuristic. * **Step 1.1 (preparation):** The travel time is calculated from the depot to every node with the travel time matrix obtained with the travel time calculator presented in Section 3.1 (as shown in Figure 4a). * **Step 1.2 (starting node selection):** From the current set of nodes (an initial set containing all nodes), the node with the longest travel time from the depot is chosen. However, if there are no more nodes in the set of nodes, Step 1 is terminated. * **Step 1.3 (loading capacity check and trip generation):** If the loading capacity of the robot is not violated by considering the demand of the chosen node, the chosen node is added to the current trip (initially, there are no nodes constituting the trip), and the chosen node is eliminated from the set of nodes for update purposes. The process then proceeds to Step 1.4. Conversely, this trip is terminated by inserting the depot (i.e., node 0) at both the beginning and end of this trip, and the chosen node is eliminated from the set of nodes for update purposes. The process proceeds to Step 1.2. * **Step 1.4 (nearest-neighbor insertion):** The nearest (closest) neighbor node is selected among the nodes chosen during Step 1.2 in terms of the travel time with the travel time matrix, as shown in Figure 4b. The process proceeds to Step 1.3 with this chosen neighbor node. Figure 4c shows an initial solution containing five trips generated by Step 1. Robots are assigned to these trips once a final solution is obtained in Step 2. * **Step 2: Solution improvement using the GA.**
* **Step 2.1 (initial population creation):** In this research, the chromosome was represented similarly to the initial solution, as shown in Figure 4c, and the population consisted of one hundred chromosomes. The initial solution obtained in Step 1 was added to the population first. Then, the other ninety-nine chromosomes were randomly generated. * **Step 2.2 (roulette wheel selection for genetic operations):** Two parent chromosomes must be selected to generate offspring that could potentially represent better solutions. The chromosome with the highest fitness value (i.e., the lowest total travel time, which is the objective function value of the IRRP) was chosen as one of the two parent chromosomes. The fitness value of any chromosome can be easily calculated by adding the travel times of all trips and determining the inverse value.