# Optimization of Carsharing Fleet Placement in Round-Trip Carsharing Service
## 3 Optimization Model
### NP-Hardness Proof  
According to [PERSON] and [PERSON] [55], any decision problem that can be reduced from an NP-complete problem, whether it is a member of NP or not, is not solvable in polynomial time unless P = NP since it is as hard as the NP-complete problem. In order to prove the NP-hardness of FPP, its computational complexity is analyzed. Therefore, the decision counterpart of the fleet placement problem (FPP)-FPP-D is introduced. The decision counterpart FPP-D inherits all parameters from FPP.  
In this section, the NP-hardness of FPP, through proving the NP-completeness of FPP-D, is demonstrated. For FPP-D, the question is to determine whether there exists a solution with \(f\) station(s) such that all buildings are covered.  
**Proposition 1**.: _The FPP is NP-hard in the strong sense even if there is only one user in each building._  
Proof.: We introduce a polynomial-time transformation to the FPP-D from the strongly NP-complete problem \"Set Cover Problem (Minimum Cover Problem)\" [55,56].  
Set Cover Problem or SCP can be defined as follows: given a universe U of R elements, a collection of subsets of \(U\), \(G=\{g_{1},g_{2},g_{3},...,g_{L}\}\) and a positive integer \(K\leq|G|\), the question is \"Does G contain a cover for U of size K or less, i.e., a subset \(G^{\prime}\subset G\) with \(|G^{\prime}|\leq K\) such that every element of U belongs to at least one member of \(G^{\prime}\gamma^{\prime\prime}\)  
Given an instance of SCP, we introduce the following instance of FPP-D. Firstly, let all buildings in \(B\) be the equivalence of universe \(U\) in SCP and \(|B|=R\). Then, let S be the direct transformation of collection G where \(S=\{s_{1},s_{2},s_{3},...,s_{L}\}\), such that \(s_{l}=g_{l},l=1,2,3,\ldots,L\). In addition, we let \(w,z=1\) and \(r=0\) so that the building is covered if it is connected to the street node (\(s_{l}\)). With the prior assumption, the distances in matrix \(D\) are assumed to be one if the street node is a 1-hop neighbour of the building and zero, otherwise. Therefore matrix \(D\) reflects the membership of \(S\) and is used to constitute the membership of collection \(S\) in FPP-D. We also assume that there are L stations, hence \(n=L\). Next, we assume \(p_{j}=1;j\in\{1,2,3,\ldots,|B|\}\) which means there is only user in building \(j\). Let \(c_{j}\) be one if a collection \(s_{i}\) contains a building \(b_{j}\) where \(i\in\{1,2,3,\ldots,n\}\) and \(j\in\{1,2,3,\ldots,|B|\}\). With the aforementioned assumptions, \(\sum_{j=1}^{R}(c_{j}\times p_{j})=|B|\). Finally, we let the threshold value \(f=K\).  
Let X be a solution to SCP. A solution for FPP-D is constructed in which the buildings in \(B\) (\(U\)) are covered by \(f\) stations where \(s^{\prime}_{l}=g_{l}\in X\), such that \(x_{l}=s^{\prime}_{l}\), if \(s^{\prime}_{l}\in X\) and \(x_{l}=\emptyset\) if \(s^{\prime}_{l}\
otin X\). Since X is a cover of \(U\) (in SCP), all buildings in \(B\) are covered and the number of stations in the corresponding solution (for FPP-D) is \(f=|X|\).  
Now assume that there exists a solution Y in FPP-D with \(|Y|\leq K\) and \(|Y|\) should not exceed \(K\), otherwise, \(|Y|>K\) and the condition will not hold. Therefore, there are at most \(K\) station(s) with \(y_{i}\
eq\emptyset\). Since all buildings form \(B\) and all buildings in \(B\) belong to at least one member of \(Y\), the selected stations with \(y_{i}\
eq\emptyset\) represents a solution to SCP, given a polynomial transformation from SCP to FPP-D. Since all input numbers in the FPP-D instance have a size most polynomial in the size of the input, FPP is strongly NP-hard.  
SCP (as an optimization problem) was proved to be polynomially non-approximable within the ratio \(c\cdot\ln|G|\), for some constant \(c>0\)[57]. Therefore, we propose the following statement.  
**Statement 1.** There exists no polynomial \((c\cdot\ln n)\)- approximation algorithm for the FPP where \(n\) is the input size, unless \(P=NP\).