## 3 The Generalized Service Point Distribution Problem  
The _Generalized Service Point Distribution Problem_ (GSPDP) considered here is an extension of the _Service Point Distribution Problem_ (SPDP) introduced in Reference [16]. Given are a set of locations \(V=\{1,\ldots,n\}\), at which service points may be set up, and a set of potential users \(U=\{1,\ldots,m\}\). The fixed costs for establishing a service point at location \(v\in V\) are \(z_{v}^{\rm fix}\geq 0\), and this service point's maintenance over a defined time period is supposed to induce variable costs \(z_{v}^{\rm var}\geq 0\). The total setup costs of all stations must not exceed a maximum budget \(B>0\). Furthermore, it is assumed that opened service stations are able to satisfy an arbitrary amount of customer demand. For each unit of satisfied customer demand, a prize \(q>0\) is earned. A solution to the GSPDP is a subset \(X\subseteq V\) of all locations where service points are to be set up. A solution \(X\) is feasible if its total fixed costs do not exceed the maximum budget \(B\), i.e.,  
\[z^{\rm fix}(X)=\sum_{v\in X}z_{v}^{\rm fix}\leq B. \tag{1}\]  
Given the set of users \(U\), we assume that each user \(u\in U\) has a certain set of _use cases_\(C_{u}\), such as going to work, to a recreational facility, or shopping. Each use case \(c\in C_{u}\) is associated with a demand \(D_{u,c}>0\) expressing how often the use case is expected to be frequented by user \(u\) within some defined time period, such as a week or a month. For each unit of satisfied customer demand, a prize \(q>0\) is earned. The demand of each use case can possibly be satisfied by different service points or subsets of service points to different degrees, depending on the concrete application and the customer's preferences. Note that use cases are here just labels and are not directly associated with specific geographic locations. This separation is intentionally done in order to keep flexibility: some use cases, such as shopping or the visit of a fitness center, may possibly be realized at different places, and, as already mentioned, occasionally, a service station farther away from a specific target location may also be convenient if some other mode of transportation is used as additional leg. Depending on the actual application and characteristics of a use case, demand may be fulfilled by a single service station, e.g., when charging batteries of an electric vehicle, or a suitable combination of multiple service stations may be needed, such as when renting a vehicle at one place and returning it somewhere else. While Reference [16] just considered the first case, we pursue here the general case of possibly requiring multiple service points to fulfill demand for a single use case. To model this aspect formally, we associate each use case \(c\) of a user \(u\) with a set of _Service Point Requirements_ (SPR) \(R_{u,c}\). Similar to use cases, these SPRs are not directly associated with geographic locations but are an abstract entity, such as \"place within easy reach of home to rent a vehicle\" or \"place close to a supermarket to return a vehicle\", with which a user can express the dependency on multiple service points to fulfill the needs of one use case. Thus, the demand of such a use case can only be satisfied if a service point exists at a suitable location for each of the use case's SPRs. Note that multiple use cases of a user may also share the same SPR(s). For example, a use case referring to a trip from home to work and one from home to a supermarket may share the SPRs \"place within easy reach of home to rent a vehicle\". The set of all different SPRs over all use cases of a user \(u\) is denoted by \(R_{u}=\bigcup_{c\in C_{u}}R_{u,c}\). Moreover, let \(R=\bigcup_{u\in U}R_{u}\) be the set of all SPRs over all users. Note that, in this notation, different users never share the same SPR labels, although labels may refer to similar SPRs. For indicating how suitable a location is w.r.t.