@inproceedings {pub4284,
	title = {Distributing Battery Swapping Stations for Electric Scooters in an Urban Area
},
	author = {Thomas Jatschka AND Fabio F. Oberweger AND Tobias Rodemann AND Guenther Raidl},
	year = {2020},
	month = {September},
	abstract = {Charging the battery of an electric vehicle is usually a time-consuming process that hinders the large-scale adoption of such vehicles. A more time efficient approach is to build electric vehicles in which depleted batteries can be replaced with charged ones. While this battery swapping approach at least today is not a common option for electric cars due to standardization difficulties and the lack
of the required expensive replacement infrastructure, it seems to be promising for electric scooters. Batteries for electric scooters are compact enough to be replaced directly by any customer in a few simple steps. Replacement batteries are provided in exchange for the used ones at swapping stations. Returned batteries are charged at these stations and, once full, are again provided for exchange.
In order to achieve the best utilization of the stations in the system, customers will be automatically assigned by the system to an appropriate station for the exchange. Moreover, in this way, the availability of a battery is guaranteed upon arrival for each customer. However, such an automated assignment also needs to consider a certain customer dropout as not every customer is willing to travel to a predestined station if the detour is too long. Generally, we assume that the dropout scales exponentially with the length of the detour induced by travelingto the assigned station.
We aim to develop algorithms for planning such a battery swapping system in an urban area. The system should be designed in such a way that the costs for building stations and corresponding battery slots are minimal while ensuring that a specified minimum amount of customer charging demand is satisfied. Batteries for electric scooters are usually quite expensive and constitute a sig-
nificant portion of the total costs of the system. Hence, a crucial aspect of our optimization problem is that available batteries are utilized as best as possible.
For this purpose, we consider a day in a discretized fashion as a sequence of consecutive time intervals. We make the simplifying assumption that charging any battery always takes the same time and only completely recharged batteries are provided to customers again.

In general, our problem can be described as a variant of the well-known multiple allocation Fixed Charge Facility Location Problem (FLP) [16]. The FLP is a classical location-allocation problem [8] in which customers need to be assigned to facilities in order to satisfy their demand while minimizing costs for setting up the facilities in appropriate configurations. In the multiple allocation case, 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 [15]. Kim and Kuby [14] 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. [13].
In this contribution we first give of a formal definition of the problem, which we call the Multi-Period Battery Swapping Station Location Problem (MBSSLP). We essentially model it as a resource-constrained, capacitated, multiple allocation FLP, i.e., in contrast to a classical FLP, the MBSSLP also considers that resources, i.e., battery slots, are renewable and are available again after some
time. Afterwards we present solution approaches based on mixed integer linear programming (MILP) and large neighborhood search. Similar to [25], we decompose our problem into a location and an allocation problem. The goal of the location problem is to identify a set of stations to open, whereas the allocation problem is a subroutine of the location problem and is responsible for allocating
customers to the opened stations and consequentially for calculating the number of battery slots at each station. We compare the performance of our algorithms on synthetic test instances as well as instances derived from NYC yellow taxi data and present corresponding results. Essentially we see that small to moderately large instances can be solved exactly or a small remaining optimality gap
with the MILP approach, while larger instances can still be handled reasonably by the large neighborhood search.},
	publisher = {Springer, LNCS, LNAI, LNBI},
	booktitle = {Optima (XI International Conference Optimization and Applications)},
	editor = {Olenev, Nicholas and Evtushenko, Yuri and Khachay, Michael and Malkova, Vlasta},
	city = {Cham},
	pages = {150--165},
	series = {LNCS 12422}
}