# Optimization of Carsharing Fleet Placement in Round-Trip Carsharing Service
## 6 Results
### Result of MU1 Instance  
Due to the larger input size of the MU1 instance and FPP being NP-hard, PolySCIP cannot be employed. It takes 17 h to come up with one solution for iterative heuristic algorithms, while it takes 26 min for NSGA-II to come up with an estimated front (read Table 9). Their respective results are presented in Figure 10. The obtained results are consistent with LU1 and LU2 instances. Table 9 presents the execution time of all algorithms. Although simple heuristic algorithms take only 7 min to find a solution, the results are not comparable to the others, which are more complex. From the results, NSGA-II also achieves higher user coverage and shorter walking distance than the heuristics.  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{**Algorithm**} & \multicolumn{2}{c}{**Coverage Oriented**} & \multicolumn{2}{c}{**Distance Oriented**} \\  & **Covered Users** & **Walking Distance** & **Covered Users** & **Walking Distance** \\ \hline Simple Heuristic & 2100 & 399.8 & 47 & 135.7 \\ Iterative Heuristic & 47 & 135.7 & 231 & 300 \\ NSGA-II & 8421 & 399.8 & 47 & 135.7 \\ \hline \hline \end{tabular}
\end{table}
Table 8: Comparing best results from each algorithm categories in LU2 instance.  
\begin{table}
\begin{tabular}{l c} \hline \hline
**Algorithm** & **Execution Time** \\ \hline NSGA-II & 26 min \\ Coverage Heuristic & 7 min \\ Distance Heuristic & 7 min \\ Bi-objective Heuristic & 7 min \\ Coverage Iterative Heuristic & 17 h \\ Distance Iterative Heuristic & 17 h \\ Bi-objective Iterative Heuristic & 17 h \\ \hline \hline \end{tabular}
\end{table}
Table 9: Execution time for NSGA-II and heuristic algorithms on MU1. The measured time depicts the execution time each algorithm takes to locate 100 stations.  
Figure 9: NSGA-II’s Pareto front and heuristic algorithms’ solutions for LU2. The higher the value on the x axis (moving towards the right), the better the distance objective is. The higher the value on the y axis, the better the user coverage objective is.  
Figure 11 illustrates the NSGA-II fleet placement solution, which maximizes the number of covered users. Red pins mark locations of the carsharing stations, while green polygons show designated parking areas in inner Munich. All heuristic algorithms and NSGA-II are also compared using 72 stations in MU1 instance to compare with the manual allocation. Figure 12 shows that the manual allocation is of a lesser quality than some of the (meta-)heuristic algorithms, the iterative coverage and bi-objective version in particular, and NSGA-II. The comparison between the best results from each category of algorithm and manual allocation is also shown in Table 10. The difference in results in terms of user coverage is up to 50% (manual allocation being on the lower end), while the walking distance is similar. The results also further stress the benefit of Pareto front in decision making since it offers more options to choose from compared to the heuristic algorithms.  
Figure 11: NSGA-II fleet placement solution which maximises user coverage in the city of Munich. Red pins are locations of the carsharing station. Green zones indicate the inner area of Munich.  
Figure 10: NSGA-II Pareto front and solutions of heuristic algorithms for the MU1 instance.  
From the MU1 instance results, iterative heuristic approaches may still be possible but usually at the expense of extremely high computation time. Moreover, discovering suitable heuristics is problematic in its own. This is where the use of metaheuristic algorithms (e.g., NSGA-II) is proven to be more effective in term of solution qualities and computation time.