Computational optimization approaches for distributing battery exchange stations for electric scooters

Abstract

Diese Arbeit betrachtet das Battery Exchange Station Location Problem 2 (BEXSLP2), welches zum Ziel hat, die optimale Platzierung von Batterietauschstationen für elektrische Scooter in einem dicht besiedelten Gebiet zu finden. Dazu wird eine Funktion verwendet, die mehrere Zielsetzungen gegeneinander abwägt, um so die Errichtungskosten der Batterietauschstationen, die Ladekosten und die Wegstrecken der Kunden und Kundinnen um die Batterie zu wechseln zu minimieren und gleichzeitig alle Kunden und Kundinnen mit Batterien zu versorgen. Benutzer können bei solchen Batterietauschstationen entladene Batterien gegen vollgeladene tauschen. Diese Batterien werden daraufhin wieder geladen und, sobald sie vollständig aufgeladen sind, wieder zum Tausch angeboten. Die Anzahl der Batterien, die gleichzeitig geladen werden können, hängt von der Anzahl der Module ab, die in der Batterieladestation verbaut sind. Jedoch ist die Zahl der Module, die in Batterieladestationen verbaut werden können, limitiert. Der betrachtete zyklische Planungshorizont wird in gleich große, aufeinanderfolgende Intervalle unterteilt. Des Weiteren wird der Weg, den Benutzer sich dabei bewegen müssen, durch einen Start- und Endpunkt definiert und es wird angenommen, dass sie den schnellstmöglichen Pfad wählen, wenn sie den Umweg zu einer Batterietauschstation fahren. Um die gewählten Umwege zu minimieren, ist es möglich, sowohl existierende Stationen mit zusätzlichen Modulen zu erweitern als auch neue Stationen an vordefinierten Orten zu errichten. Zur Lösung des Problems wird eine mixed integer linear programming (MILP) Formulierung entwickelt. Diese wird zusätzlich auch mit einem iterated greedy Algorithmus in einer matheuristic verschmolzen. Eine matheuristic kombiniert exakte Techniken der mathematischen Programmierung mit heuristischen Methoden. Der iterated greedy Algorithmus wird zum iterativen Zerstören und Rekonstruieren von Teilen der Lösung verwendet. Dabei wird eine Teillösung systematisch erweitert, um den Bedarf an Batterieladestationen zu erfüllen. Zum Testen der entwickelten Algorithmen werden zum einen Instanzen, die von Honda R&D zur Verfügung gestellt wurden, als auch künstlich generierte Instanzen verwendet. Das MILP-Programm ist dabei nicht in der Lage, zufriedenstellende Ergebnisse für die größten Instanzen zu liefern. Die iterated greedy Heuristik kann allerdings weiterhin bedenkenlos angewandt werden und liefert für eben jene Instanzen um 40% bessere Resultate. Beachtenswert ist hierbei weiters, dass selbst die initial gefundene Lösung der iterated greedy Heuristik für die größten Instanzen schon bessere Ergebnisse liefert als das MILP Programm.

This thesis considers the Battery Exchange Station Location Problem 2 (BEXSLP2), which aims to find the optimal configuration for battery-swapping stations for electric scooters over an urban region. In order to do so, a multi-objective target function is used to minimize the setup cost, charging cost, and the distances customers must ride to swap the battery while providing all customers with batteries. When a battery is exchanged at a battery-swapping station, it will be charged and, once charging is complete, again provided to customers. The number of batteries that can be charged simultaneously depends on the number of battery modules built into the respective station. Furthermore, the number of modules that can be built into each station is limited.We consider a cyclical time horizon of one day discretized into equal consecutive time intervals. The starting and end locations define the trips that customers must travel. Users are always assumed to take the quickest (shortest) path when traveling to a battery-swapping station. When determining the optimal placement of stations, it is feasible to construct new stations (in predefined locations) and/or extend existing stations. A mixed integer linear programming (MILP) formulation is developed to solve this problem. Moreover, we also developed an iterated greedy matheuristic that combines the exact approach of the MILP with a heuristic. This algorithm uses greedy procedures to destroy and (re)construct a solution iteratively. In each iteration, a partial solution is extended to fulfill the current demand. A slight variation of the original MILP is used for extending solutions. Both algorithms are tested on two different sets of instances, one derived from data provided by Honda R&D and the other generated artificially. The results show that the largest tested instances are too difficult to solve with our MILP approach. However, in those cases, the iterated greedy metaheuristic is still applicable and outperforms the MILP by reducing the gap up to 40%. Additionally, even the construction heuristic outperforms the MILP in those instance sets.