## 2 Related Work  
The considered problem in general falls into the broad category of facility location problems, i.e., optimization problems where facilities should be set up on a subset of given potential locations as economically as possible in order to fulfill a certain level of customer demand. Similar to a p-median or maximal covering location model, as in Reference [18], we limit the facilities to be opened. However, instead of imposing a direct limit on the number of facilities, in our formulation, a maximum budget for setting up facilities is specified, and each facility is associated with setup costs. In general, our problem can be classified as an uncapacitated fixed charge Facility Location Problem (FLP), as in Reference [19], however, without explicitly given demands (see below). Moreover, our problem also has similarities to stochastic or robust FLPs [20] in which problem inputs, such as the demand, may be uncertain. For such problems, uncertain inputs are usually modeled via random variables [21] or scenario-based approaches [22]. For a survey on FLPs, see Reference [23]. In our problem formulation, we have mobility applications in mind, such as the distribution of charging stations for electric vehicles or setting up rental stations for car/bike sharing. While there already exists a vast amount of literature for setting up such systems, to the best of our knowledge, all existing work essentially assumes customer demand to be estimated upfront. For example, Refs. [8; 24] use parking information to identify promising locations for electric vehicle charging stations. Ref. [25] locates charging stations for an on-demand bus system using taxi probe data of Tokyo. Moreover, census data are commonly used for estimating demand for car sharing systems [26], like sharing systems [27], or for setting up electric vehicle charging stations [28]. Data mining and other related techniques are also often employed to detect traffic patterns for bike sharing systems [29; 30], as well as car sharing systems [31]. [PERSON] et al. [32] recognize the difficulties in making demand predictions for new transport options based on estimated data and, therefore, propose to use an activity-based microsimulation technique for the modeling of car sharing demand. The simulation is completed with help of the travel demand simulator MATSim [33]. There also exist some works that take user preferences into account, e.g., in Reference [34], a car sharing system is designed based on different assumptions on the behavior of users. The authors come to the conclusion that providing real-time information to customers can greatly improve the service level of a system if users are willing to visit a different station if their preferred one does not have a vehicle available. In our approach, we substantially deviate from this traditional way of acquiring existing demand upfront and instead resort to an interactive approach. Potential future customers are directly incorporated in the optimization process as an integral part by iteratively providing feedback on meaningfully constructed location scenarios. In this way, we learn user demands on-the-fly and may avoid errors due to unreliable a priori estimations. For a survey on interactive optimization algorithms, in general, see Reference [14]. The performance of interactive algorithms is strongly influenced by the quality of the feedback given by the interactors. Too many interactions with a user will eventually result in user exhaustion [35], negatively influencing the reliability of the obtained feedback. Additionally, interacting with users can be quite time consuming, even when dealing with a single user. Hence, in order to keep the interactions with users low, one can resort to surrogate-based optimization approaches [36; 37]. Surrogate models are typically machine learning models serving as proxy of functions that are difficult to evaluate [38]. In Reference [16], as well as in this contribution, we make use of a matrix factorization [39]-based surrogate model.