Varga, J. (2021). Computational Methods for fleet scheduling in E-mobility [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2021.87627
In dieser Arbeit untersuchen wir das Fleet Scheduling Problem (FSP), das bei E-Carsharing auftritt. Dabei sind eine Flotte von Fahrzeugen und eine Menge von Reservierungen gegeben. Jede Reservierung besteht aus dem Zeitraum in dem ein Fahrzeug gebraucht wird und der Menge an Energie, die voraussichtlich verwendet wird. Aufgabe ist es Reservierungen Fahrzeugen zuzuweisen und für jedes Fahrzeug einen Ladeplan zu erstellen. Dabei soll eine Kostenfunktion minimiert werden. Es kann gezeigt werden, dass das Problem NP-hart ist. Wir streben eine exakte Lösung des Problems an. Dafür verwenden wir Software zum Lösen von Mixed Integer Linear Programs (MILPs). Die Lösung des Problems wird auf zwei verschiedene Arten angegangen. Zuerst formulieren wir das Problem als MILP und entwerfen eine Klasse von stärkenden Ungleichungen, die die Zuweisung einer Teilmenge von Reservierungen an ein Fahrzeug verhindert, falls das nicht mit dem Ladeplan vereinbar ist. Für den zweiten Ansatz führen wir eine Benders decomposition durch. Dabei wird das MILP in ein Master Problem (MP) und eine Subproblem (SP) unterteilt, welche in mehreren Iterationen abwechselnd gelöst werden. Die Benders decomposition wird auf zwei verschiedene Arten durchgeführt. Einmal auf eine klassischere Art, das andere Mal mit mehr Variablen im MP und weniger Variablen im SP. Wie sich herausstellt wird, verglichen mit dem SP, deutlich mehr Zeit für das Lösen des MPs aufgebracht. Wir untersuchen daher verschiedene Möglichkeiten, den Lösungsprozess für Instanzen des MPs zu beschleunigen. Zuerst implementieren wir Branch-and-Check, das die Benders decomposition in einen Branch-and-Bound Baum einbettet. Dadurch muss das MP nicht in jeder Iteration vollständig gelöst werden. Der zweite und dritte Ansatz versuchen das Lösen des MP zu beschleunigen, indem es nicht bis zur Optimalität gelöst wird. Einerseits wird das erreicht indem bei der Lösungssoftware für MILPs eine Gap erlaubt wird. Andererseits entwerfen wir eine auf General Variable Neighborhood Search basierende Heuristik für das MP, die mittels Delta-Evaluation die Nachbarschaften durchsucht. Wir haben außerdem eine Network Flow Formulierung entworfen, um das SP zu lösen. Wie sich allerdings herausstellt ist der Network Simplex Algorithmus mit der Network Flow Formulierung nicht schneller als eine Lösungssoftware für Linear Programs mit dem entsprechenden Linear Program. Daher untersuchen wir diesen Ansatz nicht im Detail. Es stellt sich heraus, dass das direkte Lösen des MILPs für kleine und mittelgroße Instanzen besser funktioniert als der Ansatz mit der Benders decomposition. Bei großen Instanzen kann die Lösungssoftware für MILPs allerdings keine vernünftigen Lösungen finden. Hier kann die Benders decomposition mit guten Lösungen punkten. Insbesondere der Ansatz mit der Heuristik findet gute Lösungen für große Instanzen, allerdings findet diese Variante bei vielen dieser Instanzen keine duale Schranke.
de
In this work we investigate the Fleet Scheduling Problem, which arises in the context of E-carsharing. Given are a fleet of electric vehicles and a set of reservations. A reservation consists of the timespan in which a vehicle is needed and the amount of energy that is expected to be used. The task is to find a feasible assignment from reservations to vehicles as well as a charging plan for each vehicle that minimize a cost function. The problem can be shown to be NP-hard. We aim to solve the problem in an exact manner. For that purpose we make use of solvers for Mixed Integer Linear Programs (MILPs). We consider two different solution approaches. First we formulate the problem directly as one MILP, which is strengthened in several ways. In particular we also propose a class of strengthening constraints that prohibit the assignment of subsets of reservations to a vehicle, if that assignment is not possible due to charging constraints. In our second approach we perform a Benders decomposition which decomposes the problem into a master problem (MP) and a subproblem and solves them iteratively in an alternating manner. We perform the decomposition in two different ways. First we do it in a more classical way, then we choose different subsets of variables making the MP stronger and more complex and the subproblem smaller. It turns out that the MP is the bottleneck of the Benders decomposition. We therefore investigate different measures that aim to improve the performance of solving the MP instances. The first measure implements Branch-and-Check which embeds the Benders decomposition in a single Branch-and-Bound tree. That way the MP does not need to be solved from scratch in each iteration. For the second and third measure we speed up the solving process of the MP by solving it in an inexact manner, either allowing a gap for the MILP solver or applying a heuristic. The heuristic is based on General Variable Neighborhood Search and we are able to make use of delta evaluation in order to speed up the search of the neighborhoods. We also propose a network flow formulation that can be used to solve the subproblem. However,we found that the network flow formulation solved with a network simplex algorithm does not perform better than the linear program solved with a general purpose linear program solver. Therefore we do not investigate further here. As it turns out directly solving the single MILP usually performs better than the Benders decomposition approach for small to medium sized problem instances. For large instances however the MILP solvers are not able to find any reasonable primal solutions while the Benders decomposition was able to do so and therefore achieved smaller gaps. Especially the variant that uses a heuristic for the MP is able to find good feasible solutions for large instances, altough at the cost of not finding reasonable dual bounds for many of these instances.