A learning multilevel optimization approach for a large location allocation problem

Abstract

A problem in the wide-scale adoption of electric vehicles is the long charging time. To avoid the waiting time for the customer, vehicles with exchangeable batteries and a network of battery swapping stations are a promising solution for smaller-scale vehicles like electric scooters. A customer can drive to a station and exchange their depleted batteries with an already charged battery and thus avoid the waiting that would be necessary otherwise. A good infrastructure is needed to make the implementation of such a system viable.We, therefore, consider the Demand Maximizing Battery Swapping Station Location Problem (DMBSSLP). The DMBSSLP models the challenge of finding optimal locations and configurations for battery swapping stations in an urban environment. In this thesis, we develop a novel machine learning supported metaheuristic which aims to solve this problem for a large number of potential areas and customers. We call this algorithm the Learning Multi Level Optimization (LMLO) approach. It uses elements of the conventional Multi Level Optimization (MLO) metaheuristic. Coarsening a problem instance until it is small, solving the small instance accurately, and projecting the solution of the small problem instance back to the original problem instance.A challenging part of this algorithm is to determine how elements of the problem instance should be coarsened. To solve this problem we consider a machine learning approach using two Neural Network (NN) models to guide the coarsening process.The algorithm is tested on problem instances with up to 10.000 areas and customers and is compared to conventional MLO approaches which use the Jaccard similarity measures.Our LMLO approach can to significantly improve the number of satisfied customers on instances of sizes up to 10000 areas and customers.

Ein Problem für die breite Akzeptanz von Elektrofahrzeugen sind die langen Ladezeiten der Batterien. Um den Kunden die Wartezeit zu ersparen, sind Fahrzeuge mit austauschbaren Batterien und ein Netz von Batterietauschstationen eine vielversprechende Lösung für kleinere Fahrzeuge wie Elektroroller. Der Kunde kann zu einer Station fahren und seine leere Batterie gegen eine bereits geladene austauschen und so die Wartezeit vermeiden. Um die Einführung eines solchen Systems zu ermöglichen, ist eine gute Infrastruktur erforderlich.Wir betrachten daher das Demand Maximizing Battery Swapping Station Location Problem (DMBSSLP). Das DMBSSLP modelliert die Herausforderung, optimale Standorte und Konfigurationen für Batterietauschstationen in einer städtischen Umgebung zu finden. In dieser Arbeit entwickeln wir eine neuartige, durch maschinelles Lernen unterstützte Metaheuristik, die darauf abzielt, dieses Problem für eine große Anzahl von potenziellen Gebieten und Kunden zu lösen. Wir nennen diesen Algorithmus den Learning Multi Level Optimization (LMLO) Ansatz. Dieser verwendet Elemente der konventionellen Multi Level Optimization (MLO) Metaheuristik. Vergröberung einer Probleminstanz, bis sie klein ist, genaue Lösung der kleinen Instanz und Projektion der Lösung der kleinen Probleminstanz zurück auf die ursprüngliche Probleminstanz. Ein wichtiger Teil dieses Ansatzes ist zu bestimmen, wie die Elemente der Probleminstanz vergröbert werden sollen. Um dieses Problem zu lösen, benutzen wir zwei neuronale Netzwerke, die den Vergröberungsprozess steuern. Der Algorithmus wird an Probleminstanzen mit bis zu 10.000 Gebieten und Kunden getestet und mit konventionellen MLO-Ansätzen verglichen, die das Jaccard-Ähnlichkeitsmaß verwenden. Unser LMLO Ansatz ist in der Lage, die Anzahl der Kunden, die erfolgreich ihre Batterien tauschen können, auf Instanzen dieser Größenordnung signifikant zu verbessern.