## 3 The Generalized Service Point Distribution Problem
to an SPR, we define values \(w_{r,v}\in[0,1]\), indicating the suitability of a service point at location \(v\in V\) to satisfy the needs of user \(u\in U\) concerning SPR \(r\in R_{u,c}\) in the use case \(c\in C_{u}\). A value of \(w_{r,v}=1\) represents perfect suitability, while a value of zero means that location \(v\) is unsuitable; values in between indicate partial suitability. With these suitability values in mind, the objective of the GSPDP is to maximize  
\[f(X)=q\cdot\sum_{u\in U}\sum_{c\in C_{u}}D_{u,c}\cdot\min_{r\in R_{u,c}}\left( \max_{v\in X}w_{r,p}\right)-\sum_{v\in X}z_{p}^{\text{var}}. \tag{2}\]  
In the first term of this objective function, the obtained prize for the expected total satisfied demand is determined by considering for each user \(u\), each use case \(c\), and each SPR \(r\) a most suitable location \(v\in V\) at which a service point is to be opened (\(v\in X\)). Over all SPRs of a use case, the minimum of the obtained suitability values is taken so that the full demand is only fulfilled when, for each SPR, an ideally suited service station is planned, and no demand is fulfilled as soon as one of the SPRs does not have an appropriate service point. The second term of the objective function represents the total maintenance costs for the service stations. By linearizing the above objective function, the GSPDP can be formulated as a mixed integer linear program (MILP) with the following variables. Binary variables \(x_{v}\) indicate whether or not a service point is deployed at location \(v\in V\), i.e., the binary vector \(x=(x_{v})_{v\in V}\) is the incidence vector of a corresponding solution \(X\subset V\). Additional variables \(h_{r,v}\) are used to indicate the actually used location \(v\in V\) for each SPR \(r\in R\). The degree to which a use case \(c\in C_{u}\) of a user \(u\in U\) can be satisfied is expressed by continuous variables \(y_{u,c}\in[0,1]\). The GSPDP is then stated as follows. \[\max q\cdot\sum_{u\in U}\sum_{c\in C_{u}}D_{u,c}\,y_{u,c}-\sum_{v\in V}z _{v}^{\rm var}\,x_{v}, \tag{3}\] \[\sum_{v\in V}z_{v}^{\rm frx}\,x_{v}\leq B,\] (4) \[\sum_{v\in V}h_{r,p}\leq 1 \forall r\in R,\] (5) \[\sum_{v\in V}w_{r,p}\cdot h_{r,p}\geq y_{u,c} \forall u\in U,\ c\in C_{u},\ r\in R_{u,c},\] (6) \[h_{r,p}\leq x_{v} \forall v\in V,\ r\in R,\] (7) \[x_{v}\in\{0,1\} \forall v\in V,\] (8) \[0\leq y_{u,c}\leq 1 \forall u\in U,\ c\in C_{u},\] (9) \[0\leq h_{r,p}\leq 1 \forall r\in R,\ v\in V. \tag{10}\]  
In correspondence to the definition of \(f\), the objective value is calculated in (3) as the sum of the prizes earned for fulfilled demand minus the costs for opening service stations. Inequality (4) ensures that the budget is not exceeded. Inequalities (5) ensure that, at most, one location is selected for each SPR. As our objective is to maximize the revenue, it is ensured that always a suitable service point location with the highest suitability value for each SPR is chosen. Inequalities (6) determine the degrees to which the use cases are satisfied, considering that the actually fulfilled demand of a use case is assumed to be proportional to the minimum suitability value of the locations selected for the SPRs of the use case. Last but not least, Inequalities (7) ensure that only locations at which service points are to be opened can be used for SPRs and, thus, to satisfy demand of use cases. The size of this model in terms of the number of variables, as well as the number of constraints, is in \(\mathcal{O}(m\,n\,|R|)\). Theorem 3.1: _The GSPDP is NP-hard._  
Proof: NP-hardness of the GSPDP is proven by providing a reduction from the well known NP-hard Maximal Covering Location Problem (MCLP) [45] in the variant stated by [PERSON] et al. [46]. Given are a set of possible facility locations \(\mathcal{J}\), a maximum number \(p\) of facilities to be opened, and a set of demand nodes \(\mathcal{D}\).