# Optimization of Carsharing Fleet Placement in Round-Trip Carsharing Service
## 4 Optimization Methods
### Heuristic Algorithms  
Heuristic algorithms can be simply described as a set of rules to follow. A rule can be as simple as taking whatever that is the best in that particular instance (see Algorithm 1). Numbers of variations of heuristic algorithms were used in solving both MCLP and carsharing fleet management. [PERSON] and [PERSON] [5] first proposed a heuristic algorithm, which adds one facility location at a time. The latter has also been applied to solve shared fleet placement problems [20; 21] and is used in the comparative study in this work as well. ```
Data: Number of locations (\(N\)), Potential locations(\(L\)) Result: List of selected locations(\(S\)) \(\mathrm{S}\leftarrow\emptyset\) for\(l\in L\)do  evaluate location \(l\) using a fitness function end for sort locations according to fitness score \(S\gets N\) best fitness location (\(l\)) Return \(S\)
```  
**Algorithm 1**Greedy search algorithm  
This heuristic algorithm relies on an iterative search. The algorithm starts with an empty list of locations. Then, in each iteration, each location is evaluated according to the fitness function. The algorithm then adds the location with the highest fitness score in the list and that selected location is removed from the location pool, in order not to be re-selected in the subsequent iteration. This algorithm has a complexity of \(O(sn)\) where \(s\) is the number of (desired) stations and \(n\) is the number of street nodes. The pseudocode of the algorithm is shown in Algorithm 2. ```
Data: Number of locations (\(N\)), Potential locations(\(L\)) Result: List of selected locations(\(S\)) \(S\leftarrow\emptyset\) for\(n\in\{1\ldots N\}\)do forlocation(\(l\))in\(L\)do  evaluate location \(l\) using a fitness function  end for sort location according to fitness score \(S\leftarrow\) best fitness location  remove facilities that are covered by location \(l\) end for Return \(S\)
```  
**Algorithm 2**Iterative search algorithm  
Even though the algorithm was first introduced to solve single objective optimization problems, there are several ways to adapt it to solve multi-objective problems, e.g., weighted sum, and \(\epsilon\)-constraint. These variations can be extended further to yield an approximated front as a result. Using a weighted sum approach, each objective fitness is normalized as shown in Equation (1). \[F_{n}=\frac{F_{a}-LB}{UB-LB}, \tag{1}\]  
where \(F_{n}\) is the normalised fitness and \(F_{a}\) is the actual fitness (e.g., coverage, walking distance, or bi-objective) before normalization. \(UB\) is the upper bound (the highest fitness) and \(LB\) is the lower bound (the lowest fitness). With this weighted sum approach, the priority of each objective can be adjusted as shown in Equation (2). The iterative search can be launched multiple times with different weight ratios for each optimization objective. Let us for instance assume that there is the following list of weights: [(0.1,0.8,0.1), (0.33, 0.33, 0.33), (0.1, 0.1, 0.8)]. With these weights, up to three solutions can be reached. \[F_{t}=\sum_{i=1}^{m}w_{i}F_{i} \tag{2}\]  
where \(F_{t}\) is the total fitness score from the weighted sum and \(w_{i}\) is the weight associated to the objective \(i\). Finally, \(F_{i}\) is the normalized fitness score of objective \(i\). The granularity of weights can also be adjusted at the cost of a higher computation cost since more combinations of weights require more executions of the algorithm. Once a certain amount of solutions (decided by the decision maker) is collected, an approximated front can be constructed. In this work, we study six variants of heuristic algorithms based on the greedy and iterative versions. They are;  
1. Coverage-focused greedy algorithm;
2. Distance-focused greedy algorithm;
3. Bi-objective-focused greedy algorithm;
4. Coverage-focused iterative algorithm;
5. Distance-focused iterative algorithm;
6. Bi-objective-focused iterative algorithm.