A Matheuristic for battery exchange station location planning for electric scooters

Abstract

In dieser Arbeit betrachten wir das Battery Exchange Station Location Problem (BEXSLP) welches sich mit der Platzierung von Batteriewechsel-Stationen für elektrische Roller beschäftigt. Ziel ist es, eine dreiteilige Zielfunktion unter Erfüllung eines festgelegten Mindestbedarfs zu minimieren. Nutzer können an Batteriewechsel-Stationen leere Batterien ihrer Roller unmittelbar gegen vollständig geladene Batterien tauschen. Diese entleerten Batterien werden dann bei der Station wieder aufgeladen und nach entsprechender Ladezeit anderen Nutzern wieder zur Verfügung gestellt. Hierfür betrachten wir einen Zeithorizont von einem Tag, welcher in gleich lange Zeitintervalle diskretisiert wird (typischerweise wird ein Tag auf 24 Stunden aufgeteilt). Der (Mindest)bedarf ist durch Fahrten von Nutzern mit definiertem Start- und Endziel innerhalb eines bestimmten Zeitslots, in welchem die Nutzer das Fahrzeug aufladen müssen, gegeben.Stationen können an unterschiedlichen Orten gebaut werden. Abhängig vom Ort, an dem eine Station gebaut wird, gibt es Unterschiede in Bezug auf verschiedene Eigenschaften, wie zum Beispiel die Baukosten, Anzahl der möglichen Batterieslots oder Zeiten, zu welchen Nutzer ihre Batterien tauschen können. Die Planung erfolgt unter Berücksichtigung von drei unterschiedlichen Aspekten welche linear gewichtet in einer gemeinsamen Zielfunktion minimiert werden. Diese drei Aspekte sind (a) die Baukosten für Stationen sowie Erweiterungsmodule, (b) die Kosten für das Laden von Batterien und (c) die Zeitsumme der Umwege, welche dadurch entstehen, dass Nutzer zu einer Ladestation fahren müssen. In dieser Masterarbeit entwickeln wir eine Matheuristic, welche exakte Techniken der mathematischen Programmierung mit heuristischen Methoden kombiniert, um das BEXSLP zu lösen. Wir verwenden eine Large Neighborhood Search (LNS), welche mittels einer Konstruktionsheuristik eine initiale Lösung erzeugt und dann mittels eines Zerstör-und-Reparier-Schemas versucht diese Lösung iterativ zu verbessern. Hierbei werden Teile einer bestehenden Lösung aufgelöst und anhand einer Menge vielversprechender Stationen wieder repariert. In der LNS verwenden wir gemischt-ganzzahlige lineare Programmierung (mixed integer linear programming, MILP) mit relaxierten Eigenschaften in Bezug auf die Anzahl der Stationen und Erweiterungsmodule. Anschließend wird die Lösung für das relaxierte Modell mittels heuristischer Methoden repariert, um eine gültige Lösung abzuleiten. Wir präsentieren mehrere Strategien um vielversprechende Stationen für das Zerstören beziehungsweise Reparieren von Lösungen auszuwählen, welche sich auf einzelne Aspekte unserer mehrteiligen Zielfunktion fokussieren. Wir erstellen neuartige Testinstanzen basierend auf Vorgehensweisen bestehender Literatur. Anhand dieser Testinstanzen zeigen wir, dass die entwickelte Matheuristic für größere Instanzen um zehn bis dreißig Prozent bessere Resultate erzielt als die Verwendung eines universellen MILP-Lösers.

In this thesis, we consider the Battery Exchange Station Location Problem (BEXSLP) which considers planning the setup of new stations for exchanging batteries of electric scooters with the aim of minimizing a three-part objective function while satisfying an expected amount of demand. Depleted batteries can directly be exchanged by customers at those stations for fully charged ones. Batteries returned at a station are charged and provided to customers again once they are fully charged. A time horizon of one day is considered, discretized into equally long consecutive time intervals (typically a day is split into 24 hours). Demand refers to user trips with a defined start and end point within a certain time interval at which the users need to exchange the batteries of their vehicles. Stations may be set up at given potential locations, which may differ in certain aspects, such as setup costs, number of provided battery slots or different time intervals in which exchanging batteries is possible for customers. This task is done with regard to minimizing three objectives, which are combined in a weighted linear fashion and the requirement that a certain minimal amount of demand must be fulfilled. These three objectives are (a) the setup cost for stations and extension modules, (b) the cost for charging batteries and (c) the total duration of detours for users induced by travelling to a station to exchange batteries.In this thesis, a matheuristic is developed which combines exact mathematical programming techniques with heuristic methods to solve the BEXSLP. More specifically, a Large Neighborhood Search (LNS) is implemented. The LNS uses an initial solution created by a construction heuristic and iteratively tries to improve the solution quality by applying a destroy and repair scheme, i.e., parts of an incumbent solution are destroyed and repaired with a set of promising stations. In the LNS we make use of a mixed integer linear program (MILP) with relaxed properties regarding the number of stations and modules. Afterwards, heuristic methods are applied to derive feasible solutions from the solutions of the relaxed model. Multiple strategies are presented which specifically focus on individual parts of our multi-component objective to systematically find more promising stations when destroying and repairing solutions. A set of test instances is designed based on approaches from literature. Using these instances, we show that the matheuristic approach achieves between ten to thirty percent better results for larger instances than using a general-purpose MILP solver.