@inproceedings {pub4283,
	title = {A Large Neighborhood Search for Distributing Service Points in Mobility Applications with Capacities and Limited Resources},
	author = {Thomas Jatschka AND Tobias Rodemann AND Guenther Raidl},
	year = {2020},
	month = {September},
	abstract = {In a previous work we presented a cooperative optimization algorithm for distributing service points with special focus on mobility applications. The problem formulation considered there, called the Service Point Distribution Problem (SPDP), more or less corresponds to a rather generic facility location problem, and the focus was on an interactive optimization approach in which a broader
base of potential users provides iteratively feedback on solution scenarios in order to guide a heuristic search for a solution that maximizes the expected fulfilled demand.
While being quite general, the SPDP lacks important aspects that need to be considered in order to model certain mobility applications like the charging of electric vehicles in more realistic ways. Hence, we now aim to investigate a problem formulation more suitable for such applications by extending the SPDP. One major weakness of the SPDP is that it does not consider capacities
of stations, i.e., a single station may in principle satisfy an infinite amount of customer demand. Hence, our first extension is to limit the demand a station can serve by introducing capacities in dependence of possible configurations of the stations. In order to achieve a good utilization of the stations in the system, customers will be automatically assigned by the system to appropriate stations that are able to serve their demand. In this automated assignment, it is also considered that users do not want to make larger detours in order to reach their service stations. Following previous work we assume an exponential dropout of users in dependence of the detour length. Another extension of the SPDP we consider is that each station can only serve a limited number of users at the same time. For this purpose we introduce resources, which are occupied when a station serves a customer. To this end, we consider a day in a discretized fashion as a sequence of time intervals. We make the simplifying assumption that serving a single customer always takes the same amount of time.
In general, our new problem formulation can be seen as a variant of the multiple allocation Fixed Charge Facility Location Problem (FLP). The FLP is a classical location-allocation problem in which customers need to be assigned to facilities in order to satisfy the customers{\textquoteright} demands while minimizing costs for setting up the facilities with appropriate capacities. In the multiple allocation
case considered here, customer demand can be split between multiple facilities. Our problem also features similarities with contributions in the domain of distributing refueling stations for alternative-fuel vehicles. The basis of such problems is the Flow Refueling Location Model (FRLM) by Kuby and Lim. Kim and Kuby present an extension of the FRLM, the deviation flow refueling location model (DFRLM), in which customers are allowed to deviate from their shortest paths in order to go to a refueling station. A capacitated version of the DFRLM is presented by Hosseini et al..
After motivating and formalizing the problem, we present solution approaches based on a mixed integer linear programming (MILP) formulation as well as on a large neighborhood search heuristic. we essentially decompose the problem into a location and an allocation subproblem. The goal of the location subproblem is to identify a set of stations to open, whereas the allocation problem corresponds to the subproblem of allocating customers to the opened stations.
We compare the performance of our algorithms on synthetic test instances partly adopted from previous work as well as instances derived from NYC yellow taxi data. While the MILP approach is able to handle benchmark instances with up to 200 locations and 1000 origin-destination pairs exactly in reasonable time, the large neighborhood search turns out to scale significantly better and is able
to deal reasonably with instances up to 2000 locations. Although we do not explicitly consider the user interaction aspects from [3] here, the suggested solution approaches are designed in a way to fit nicely into the cooperative optimization framework.},
	publisher = {TU Wien},
	booktitle = {CPAIOR 2020, Vienna}
}