MILP
Ansatz
Die Abkürzung MILP bedeutet Mixed Integer Linear Programming, auf Deutsch: gemischt-ganzzahlige lineare Optimierung. Jedes Optimierungsproblem besteht aus den folgenden drei Teilen:
- Entscheidungsvariablen: Das sind jene Größen, die in einem bestimmten durch die Nebenbedingungen definierten Bereich verändert werden können. Sie entsprechen auch jenen Entscheidungen, die optimal getroffen werden sollen. Die Entscheidungsvariablen können ganzzahlige oder reelle Zahlen sein
- Nebenbedingungen: Das sind Bedingungen, die die möglichen Werte der Entscheidungsvariablen einschränken. Durch die Nebenbedingungen wird der Spielraum des Optimierungsproblems definiert.
- Zielfunktion: Die Zielgröße ist jene Größe, die minimiert oder maximiert werden soll. Durch die Zielfunktion wird die Abhängigkeit der Zielgröße von den Entscheidungsvariablen beschrieben.
Linear ist das Optimierungsproblem dann, wenn die Zielfunktion und alle Nebenbedingungen linear in den Entscheidungsvariablen sind.
Übersetzt in das Problem eines optimalen Lademanagements bedeutet das:
- Spitzenlast minimieren: Maximum alle 15-Minuten-Mittel
- Betriebskosten minimieren: Energie- und Leistungskosten
- robuster Betrieb: SOC-Buffer, Unsicherheiten abfangen
- Synergien: PV, stationärer Speicher, THG-Quote, Förderungen, Flexibilität verkaufen
- Investitionskosten minimieren: Anschlussleistung, Ladeninfrastruktur, Auslastung, Ausbaufähigkeit, Flexibilität
Die kursiven Punkte werden im Free-E-Bus Projekt nicht oder nur teilweise bearbeitet.
- Ladeleistungen der Busse über einen definierten Zeitraum
- Ladepunktzuweisung, Tourenplanung und -zuweisung
- Auslegung der Flotte und der Ladeinfrastruktur
Die kursiven Punkte werden im Free-E-Bus Projekt nicht oder nur teilweise bearbeitet.
- Batterien der Fahrzeuge: Kapazität und max. Ladeleistung, Ladekurve, Wirkungsgrad
- Umlaufplan: Ladefenster und Verbräuche
- Ladeinfrastruktur: Kapazität und max. Ladeleistung, diskrete Ladeleistungen, Wirkungsgrad
Die kursiven Punkte werden im Free-E-Bus Projekt nicht oder nur teilweise bearbeitet.
Modellumfang und Datenanforderung werden durch die Auswahl der Entscheidungsvariablen, Nebenbedingungen und Zielfunktion bestimmt. Die zur Bestimmung einer optimalen Lösung notwendige Rechenzeit hängt zudem noch von der Rechenkapazität des Computers und der verwendeten Software ab.
Minibeispiel: Lade einen Bus (300 kWh, 150 kW) in 2 Stunden kostenoptimal von 0 auf 200 kWh. Preise: 0.15 €/kWh in der ersten Stunde, 0.1 €/kWh in der zweiten Stunde.
Entscheidungsvariablen: Ladeleistungen \(p_1, p_2\) (kW) für die erste und zweite Stunde.
\[\begin{align*} \textit{minimiere die Zielfunktion} & \quad 0.15 p_1 + 0.1 p_2 \\ \textit{unter den Nebenbedingungen:} & \quad p_1 + p_2 = 200 \\ & \quad 0 \leq p_1, p_2 \leq 150 \end{align*}\]
Vorteile vom MILP: flexible Modellierung, optimal
Nachteile von MILP: Rechenzeit kann bei vielen ganzzahligen Entscheidungsvariablen oder großem Modellumfang sehr lang sein
Funktionsweise
Datenstruktur
Die Ladeinfrastruktur liefert eine Reihe von teils gekoppelten Leistungseinschränkungen, die aber problemlos als lineare Nebenbedingungen formuliert werden können. Die hierarchische Struktur ist in Abbildung 1 dargestellt.
Die Batterien der Fahrzeuge werden im einfachsten Fall durch ihre Kapazität (kWh) und ihre maximale Ladeleistung (kW) parametrisiert.
Es wird eine ereignisbasierte Zeitdiskretisierung verwendet, siehe Abbildung 2.
Einheiten:
| Größe | Einheit |
|---|---|
| Dauer | h |
| Energie | kWh |
| Leistung | kW |
Konfiguration:
- Die Zuweisungen Bus \(\rightarrow\) Touren sind vorgegeben.
- Die Zuweisungen Bus \(\rightarrow\) Ladepunkt sind vorgegeben oder frei, aber in jedem Fall während eines Ladefensters konstant.
- Es werden aktuell keine Mindestladeleistungen und keine Ladeleistungsstufen berücksichtigt.
MinimizePeak Power at One Charging Location
TODO: übersetzen, kürzen und ausformulieren
objective: minimize aggregate charging power at a charging location
variables:
- maximum aggregate power \(m\): continuous
- charging power (interval, bus) \(p_{i, b}\): continuous
- battery energy (time, bus) \(E_{t,b}\): continuous
- assignment bus \(\rightarrow\) charging point (interval, bus, charging point) \(a_{i,b,c}\): binary
constraints:
- maximum aggregate charging power
- charging powers during intervals: bounds, charging availability
- battery energies at time points:
- capacity bounds
- initially fully charged
- minimum final energy
- updates from one time point to the next including consumption of trip at end of trip
- charging infrastructure constraints:
- maximum location power
- maximum stations’ powers
- maximum charging points’ powers
- assignment bus \(\rightarrow\) charging point:
- charging availability during charging windows
- maximum one charging point per bus
- maximum one bus per charging point
- constant charging point assignment during charging window
MILP Formulation:
Mathematical formulation of the optimization problem as a Mixed Integer Linear Program (MILP):
Indices:
- \(b\): index of busses
- \(c\): index of charging points
- \(i\): index of time intervals
- \(t\): index of time points
- \(T\): final time point
Selection of parameters and data:
- \(p_{\text{max}, b}\): maximum charging power of bus \(b\)
- \(E_{\text{max}, b}\): maximum battery energy of bus \(b\)
- \(E_{\text{final}, b}\): minimum final battery energy of bus \(b\)
- \(\text{consumption}_{t, b}\): total trip energy consumption of bus \(b\) at time point \(t\)
- \(\text{dt}_t\): duration of time interval with end time point \(t\)
- \(p_{\text{max}, c}\): maximum charging power of charging point \(c\)
- \(p_{\text{max}, s}\): maximum charging power of charging station \(s\)
- \(p_{\text{max}, l}\): maximum charging power of charging location \(l\)
Decision variables:
- \(m\): maximum aggregate charging power, non-negative
- \(p_{i,b}\): charging power of bus \(b\) during time interval \(i\), bounds: \(0 \leq p_{i,b} \leq p_{\text{max}, b} \quad \forall \text{ time intervals } i\)
- \(E_{t,b}\): battery energy of bus \(b\) at time point \(t\), bounds: \(0 \leq E_{t,b} \leq E_{\text{max}, b} \quad \forall \text{ time points }t\)
- \(a_{i,b,c}\): binary variable, 1 if bus \(b\) is assigned to charging point \(c\) during time interval \(i\), 0 otherwise
Model:
\[\begin{align} \min \; & m \\ \text{s. t.} \; & 0 \leq m \\ & \sum_b p_{i,b} \leq m \quad \forall \text{ time intervals } i \\ & p_{i,b} = 0 \text{ if not chargeable } \quad \forall \text{ time intervals } i \text{, and busses } b \\ & a_{i,b,c} = 0 \text{ if not chargeable or not assignable} \quad \forall \text{ time intervals } i \text{, busses } b \text{, and charging points } c \\ & E_{1,b} = E_{\text{max}, b} \quad \forall \text{ busses } b \\ & E_{T,b} \geq E_{\text{final}, b} \quad \forall \text{ busses } b \\ & E_{t+1,b} = E_{t,b} + p_{t,b}\,\text{dt}_t - \text{consumption}_{t+1, b} \quad \forall \text{busses } b \text{, and time points} t = 1, \ldots, T-1 \\ & \sum_c a_{i,b,c} \leq 1 \quad \forall \text{ time intervals } i \text{, and busses } b \\ & \sum_b a_{i,b,c} \leq 1 \quad \forall \text{ time intervals } i \text{, and charging points } c \\ & p_{i,b} \leq \sum_c a_{i,b,c} \; p_{\text{max}, c} \quad \forall \text{ time intervals } i \text{, and busses } b \\ & \sum_b p_{i,b} \leq p_{\text{max}, s} \text{ summed over all busses at station } s \quad \forall \text{ time intervals } i \text{, and charging stations } s \\ & \sum_b p_{i,b} \leq p_{\text{max}, l} \text{ summed over all busses at location } l \quad \forall \text{ time intervals } i \text{, and charging locations } l \\ & a_{i+1,b,c} = a_{i,b,c} \quad \forall \text{ time intervals } i \text{during a charging window, busses } b \text{, and charging points } c \\ \end{align}\]
Die Summe in der Nebenbedingung \(\sum_b p_{i,b} \leq p_{\text{max}, s}\) geht über alle Busse an der Station \(s\). Welche Busse an der Station \(s\) sind, wird aber erst durch die Zuordnungsvariablen \(a_{i,b,c}\) festgelegt. Dadurch wird die Summe allerdings quadratisch in den Entscheidungsvariablen: \[ \sum_{b \text{ at} s} p_{i,b} = \sum_{b, c \text{ of } s} p_{i,b} \cdot a_{i,b,c}. \] Um das Optimierungsproblem weiterhin als MILP formulieren zu können, schreiben wir die Produkte \(p_{i,b} \cdot a_{i,b,c}\) mittels zusätzlicher Variablen und zu neuen, linearen Nebenbedingungen um. Siehe dazu [1], pp. 149-150.
Zusätzliche Variablen:
- \(q_{i,b,c} \in \mathbb{R} \quad \forall \text{ time intervals } i \text{, busses } b \text{, and charging points } c\). Diese Variablen modellieren die Produkte \(p_{i,b} \cdot a_{i,b,c}\).
- \(z_{i,b,c} \in \mathbb{R} \quad \forall \text{ time intervals } i \text{, busses } b \text{, and charging points } c\).
Zusätzliche Nebenbedingungen:
- \(q_{i,b,c} = p_{i,b} - z_{i,b,c} \quad \forall \text{ time intervals } i \text{, busses } b \text{, and charging points } c\).
- \(0 \leq q_{i,b,c} \leq p_{\text{max}, b} \cdot a_{i,b,c} \quad \forall \text{ time intervals } i \text{, busses } b \text{, and charging points } c\).
- \(0 \leq z_{i,b,c} \leq p_{\text{max}, b} \cdot (1 - a_{i,b,c}) \quad \forall \text{ time intervals } i \text{, busses } b \text{, and charging points } c\).
Die ursprünglichen Nebenbedingungen \(\sum_{b, c \text{ of } s} p_{i,b} \cdot a_{i,b,c} \leq p_{\text{max}, s}\) werden dann ersetzt mit \[ \sum_{b, c \text{ of } s} q_{i,b,c} \leq p_{\text{max}, s} \quad \forall \text{ time intervals } i \text{, and charging stations } s. \]
TODO: 15-Minuten-Mittelung der Spitzenlast
Kostenoptimierung
TODO: Formulieren der Kostenfunktion mit Energie- und Leistungspreisanteilen
SOC-Optimierung
TODO: Formulieren möglicher Zielfunktionen
Integration von Baseloads
TODO: Erweiterung der Zielfunktionen und Nebenbedingungen
Integration von stationären Speichern
TODO: Erweiterung der Zielfunktionen und Nebenbedingungen