# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 5 Experimental Results
### Performance Validation of the Heuristic Approach  
In the previous example of two robots and a six-story building with twelve customers, Gurobi, a commercial solver, quickly obtained the optimal solution. However, if the problem size is increased by adding more customers and robots, we must assess whether Gurobi can obtain the optimal solution rapidly.  
Three cases with different numbers of floors and robots were designed to evaluate and compare the performance between the proposed heuristic approach and Gurobi. The small-sized problem case consisted of six floors and two robots, and the medium-sized problem case was composed of nine floors and three robots. Finally, the large-sized problem case involved twelve floors and four robots.  
It was further assumed that there can occur at least zero to at most two corners between any pair of nodes, and the normal density scenario was applied. Ten test instances were randomly generated in each of the three cases. The proposed heuristic was coded in Python 3.7.1 on the same computer. All system parameters and data generation methods followed the illustrative example above to streamline our analysis. Additionally, the computational time was limited to sixty minutes (i.e., 3600 s) because there are many buildings where delivery services should be completed on the next day. All robot route plans should be generated during the night. Thus, it seems unacceptable if more than an hour is needed to generate a plan for a single building. The objective values and computation time of both the proposed heuristic and Gurobi for the test instances are summarized in Table 7.  
As indicated in Table 7, the performance of the proposed heuristic was investigated by dividing the whole process into two main steps: (1) initial solution generation via nearest-neighbor node insertion and (2) solution improvement via the GA. This approach determined the contribution of the GA-based solution improvement step to the performance of the final solution.  
As demonstrated in Table 7, in the small-sized problem case, the average computation time of Step 1 of the proposed heuristic was 0.002 s, while Gurobi obtained the optimal solution within 12.61 s on average. Thus, Step 1 of the proposed heuristic seems to be very swift, but the quality of the solution still requires improvement because the average percentage gap with the Gurobi solution in terms of the objective value was 5.78%. In other words, the quality of the initial solution resulting from Step 1 is not yet satisfactory and requires improvement. That is why Step 2 of the proposed heuristic was developed to improve the solution. Step 2 of the proposed heuristic certainly took longer, namely, 52.89 s on average, but it obtained the exact solutions to the Gurobi solutions in every instance. Although it is more effective to employ Gurobi for small-sized problems in terms of the computation time, the need for heuristics increased in regard to medium- and large-sized problems considering both the computation time and solution quality.  
As indicated in Table 7, the proposed heuristic required 143.16 s (for the medium-sized problem) and 200.09 s (for the large-sized problem) on average to derive the solutions. In contrast, Gurobi required 813.94 s (for the medium-sized problem) and 2196.32 s (for the large-sized problem) on average and sometimes failed to obtain a solution within the running time (e.g., instances 14 and 17 for the medium-sized problem and instances 22, 24, 26, 27, 29, and 30 for the large-sized problem).  
Additionally, the proposed heuristic could obtain near-optimal solutions in the medium- and large-sized problem cases. The average optimality gap between the proposed heuristic and Gurobi in the medium-and large-sized problem cases reached 0.11% and 0.18%, respectively.  
In summary, the proposed heuristic seems to be a viable tool to generate a suitable and feasible route more rapidly than commercial optimization software with increasing problem size.