# Robot Routing Problem of Last-Mile Delivery in Indoor Environments
## 4 Heuristic-Based Solution
The other parent chromosome can be chosen with the well-known roulette wheel selection method considering the following probability (\(p_{i}\)) for each chromosome \(i\)[28]:  
\[p_{i}=\frac{f_{i}}{\sum_{j=1}^{99}f_{j}},\ \forall i=1,\ldots,99 \tag{13}\]  
where \(f_{i}\)\(\rightarrow\)the fitness value of chromosome \(i\). The proportion of the fitness value of each chromosome to the sum of the fitness values of all chromosomes in the whole population can be computed except for the best option. This represents the probability of the selection of an individual chromosome. A roulette can be partitioned according to the cumulative sum of \(p_{i}\), starting from the solution with the highest value. Then, a fixed point is randomly generated between zero and one. Since the area of each chromosome was proportional to each probability to be selected, a chromosome with a corresponding generated fixed point was finally chosen as the second parent chromosome. **Step 2.3 (genetic operations):** Once the two parent chromosomes were selected via the roulette wheel selection in Step 2.2, genetic operations such as crossover and mutation operations were applied. Genetic operations play an important role in searching for a broader solution space. The partially mapped crossover (PMX) operator and improving rate-based swap mutation (ISM) operator were adopted. **Step 2.3.1:** PMX operator for the crossover operation. The crossover operator reproduces child chromosomes. However, a conventional n-point crossover is not suitable to generate child chromosomes in our case because every node must be visited once in the route plan. Therefore, the PMX operator was chosen as the crossover operator [29]. After choosing two random cut points on the parent chromosomes, the segment between the cut points was exchanged. One arbitrary point was generated for each parent and employed to establish a segment. This is called the mapping section. Then, the remaining parts with no conflicts (i.e., exhibiting no shared nodes) were maintained at their position. However, if a conflict occurs (i.e., the same node applies), the gene from the mapping section fills the position. The crossover operator created two new child chromosomes from the two parent chromosomes. Details on the PMX operator can be found in [29]. **Step 2.3.2:** ISM operator for the mutation operation. Figure 4: Generating an initial solution by the nearest-neighbor insertion heuristic. (**a**) the travel time from the depot to all nodes is calculated; (**b**) the nearest (closest) neighbor node is chosen; (**c**) the final trips (initial solution) are created. The mutation operator widely expands the exploration space by introducing attributes not present in the parent chromosomes. In this research, we employed swap mutation, which generates a certain probability for each gene, thus replacing it with another gene if the probability is lower than the mutation rate. What is important when selecting the other gene is that the demand must remain the same to preserve the length of the trip and the feasibility of the solution. For example, if the selected gene exhibits a demand of 2, all the genes with a demand of 2 from the chromosome are chosen to compile a set. From the established set, one gene is randomly chosen to implement the swap mutation operation. When initiating the GA, the initial mutation rate is set to 0.2, which is increased to 0.3 from the 50 th generation on and to 0.5 from the 100 th generation on to avoid falling into a local optimum [30]. Through the above genetic operations, two child chromosomes are obtained. Among the four chromosomes, i.e., the two parent chromosomes and two child chromosomes, the best chromosome with the lowest objective function value is chosen and sent to the new population of the next generation. Until the new population is fully filled, both Steps 2.2 and 2.3 are repeated. Once the new population is created, the next generation starts.