# Optimization of Carsharing Fleet Placement in Round-Trip Carsharing Service
## 2 Related Work
### Existing Resolution Approaches  
Several algorithms were proposed to solve the aforementioned problems, ranging from exact methods, to heuristic and metaheuristic algorithms. Exact methods guarantee optimality, however, once the size of an NP-hard problem is too large, such methods (e.g., branch-and-bound, exhaustive search) cannot find solutions in reasonable time. In contrast, heuristic algorithms (e.g., greedy algorithms) are problem specific methods that permit to obtain an approximate solution in reasonable time. Finally, metaheuristic algorithms (e.g., genetic algorithm or simulated annealing), are general purpose algorithms, which can lead to very satisfactory solutions. A true benefit is their acceptable execution time, which for middle to large size instances is several orders of magnitude smaller than for exact methods [33]. For generic location problems such as MCLP and FLP, exact methods are usually used [7; 8; 12; 16; 34; 35; 36]. It is important to note that the problem instances tackled in the reported articles were of limited size. In fact, [PERSON] et al. [36] reported that IBM CPLEX [37] cannot handle a problem with a large size of input (e.g., a city). Hence, once the problem size is too large, heuristic and metaheuristic algorithms are usually employed. [PERSON] and [PERSON] [5] first compared two variations of heuristic algorithms (which add one facility location one at a time) and a branch and bound algorithm. The next attempt in solving MCLP was using a Lagrangian heuristic algorithm, which is a combination of the Lagrangian Relaxation approach and a greedy method [38]. Heuristic algorithms are still being used nowadays as shown in [39] to solve the FLP problem. Lastly, several works reported on the efficiency of metaheuristics in solving FLP and MCLP. Tabu Search (TS), Simulated Annealing (SA), Variable Neighborhood Search (VNS), and Genetic Algorithms (GA) were also considered in solving MCLP [36; 40; 41; 42; 43]. Metaheuristics were not only used to solve single-objective versions of these problems but also multi-objective ones. [PERSON] et al. [10] employed a Multi-Objective Evolutionary Algorithm (MOEA) to solve the bi-objective MCLP, which focused on facility cost and proximity minimization using a specific encoding scheme and dedicated operators. [PERSON] and [PERSON] [11] solved the bi-objective reliability-focused MCLP where it aimed to maximize primary and backup locations coverage with a heuristic algorithm and a Multi-Objective Genetic Algorithm (MOGA). [PERSON] and [PERSON] [44] utilized the crowding distance function from the Non-dominated Sorting Genetic Algorithm II (NSGA-II) [45] in the Strength Pareto Evolutionary Algorithm II (SPEA2) [46] and reported that the new algorithm outperformed the original NSGA-II and SPEA-II. [PERSON] et al. [47] proposed their modified version of NSGA-II and used it to solve bi-objective MCLP. In shared fleet placement, the most common approach is to model it as a single-objective problem (weighted sum) and to rely on exact solvers such as CPLEX or MATLAB [20; 21; 25; 48; 49]. Several path-based heuristic algorithms were proposed [24; 26]. In fact, due to the problem complexity, heuristic and metaheuristic algorithms have been attracting more attention recently [50]. Another approach is to determine the fleet locations through agent-based simulation [51]. To date, metaheuristic algorithms have not been applied to shared fleet placement problem. Previous works mainly either consider small-size instances of the problem (at most 800 potential locations by curation) and apply exact methods, or propose heuristic algorithms. The location curation is normally conducted by field experts and is essential to facilitate the applications of exact methods and proposed heuristic algorithms, but it can be very time consuming and prone to error. Therefore, we aim to eliminate the curation process (to be fully automated) which in turn, leaves decision makers to consider over 100,000 locations (in cities like Munich).