# Optimization of Carsharing Fleet Placement in Round-Trip Carsharing Service
## 4 Optimization Methods
### Non-Dominated Sorting Genetic Algorithm-II (NSGA-II)  
In the Evolutionary Algorithm (EA) approach to solving a problem, a well known concept called'metaheuristic' can be concisely defined as a higher-level procedure or strategy for a partial search. Hence, a global optimum is not guaranteed, but it generally yields acceptable results. Metaheuristics usually contain a stochastic process, which make them non-deterministic. NSGA-II is a metaheuristic optimization algorithm that is based on Pareto-dominance [45]. Pareto-dominance is defined as follows:  
\[z\succ z^{\prime}\Leftrightarrow \forall i\in\{1,2,\ldots,n\},z_{i}\leq z_{i}^{\prime}\ \cup\] \[\exists j\in\{1,2,\ldots,n\},z_{j}<z_{i}^{\prime}\,\]  
where \(z\) and \(z^{\prime}\) are vectors of objectives in \(Z\) and \(z\succ z^{\prime}\) means \(z\) dominates \(z^{\prime}\). If the selected solutions are both non-dominated, one of the parent solutions is selected at uniformly random. Other metaheuristic algorithms in this category are Simple Evolution Algorithm for multi-objective Optimization (SEAMO) [60], Strength Pareto Evolutionary Algorithm II (SPEA2) [46], and Pareto Envelope-based Selection Algorithm (PESA) [61]. NSGA-II was shown to be more efficient than the previously mentioned algorithms in a GSM antenna location problem (a variant of FLP) [17]. Among these algorithms, NSGA-II is renowned due to its numerous proven applications. It is largely based on the Genetic Algorithm (GA), starting from population initialization, selection of parents, crossover, and mutation to obtain a new population of solutions. Individuals in both the parent and offspring populations are sorted according to their rank, and the best solutions are chosen to create a new population. If individuals have the same rank, a density estimation based on the crowding distance to the surrounding individuals of the same rank is used. A new reference-point-based NSGA-II called NSGA-III is proposed, with the intention on solving problems with three or more objectives [62]. Hence, in this work, NSGA-II is selected as the problem is bi-objective. The pseudocode of NSGA-II is shown in Algorithm 3. ```
1 population \(\leftarrow\) InitializePopulation (size)
2 Evaluate (population)
3 NondominatedSort (population)
4 CrowdingDistance (population)
5 whiletermination criteria are not yet satisfieddo
6 parents \(\leftarrow\) TournamentDCD (population)
7 offspring \(\leftarrow\) recombination+mutation(parents)
8 Evaluate (offspring)
9 NondominatedSort (population + offspring)
10 CrowdingDistance (population + offspring)
11 population \(\leftarrow\) CrowdedComparison (population + offspring)
12
13 end while
14 Return population
```  
**Algorithm 3**Nondominated Sorting Genetic Algorithm (NSGA-II)  
Next, the solution encoding population initialization and evolutionary operators employed in NSGA-II to solve the fleet placement problem are presented in detail. More details on NSGA-II's specific operators can be found in [45]. **Solution Encoding:** A solution is a string of fleet locations denoted by 'id numbers' from Openstreetmap. An example is shown in Figure 3, blue dots are candidate fleet locations on the streets. The shown numbers are ids from Openstreetmap. An example solution contains five locations (location number \(1\) to \(5\)). Naturally, it is one of many possibilities in this example area. This encoding is more suitable than the binary encoding due to the size of the problem instances, which can be exceedingly large (more than 100,000 street nodes is possible in reality). The encoding contains no order and swapping genes in the chromosome does not change the fitness of the solution. **Population Initialization:** A solution is initialized by randomly choosing (based on a uniform distribution law) street nodes from all street nodes in a problem instance. Note that each street node in the algorithm may at most be selected once in each solution during the initialization. **Crossover:** A two-point crossover is adopted in this work.