Die Umlaufoptimierung für ÖV-Fahrzeuge muss eine Reihe zusätzlicher Randbedingungen beachten, wenn die eingesetzten Fahrzeuge batterieelektrisch angetrieben werden. Dann reicht die Batteriekapazität oft nicht für einen kompletten Betriebstag aus. Für das Nachladen untertags existieren unterschiedliche Strategien, die sich in Kosten und Zeitbedarf unterscheiden. In diesem Paper wird eine Erweiterung der Umlaufoptimierung beschrieben, mit der Umläufe unter Reichweiten-Nebenbedingungen optimiert werden können. Ein Beispiel zeigt, wie sich damit der Fahrzeugmehrbedarf abschätzen lässt und dadurch unterschiedliche Ladestrategien planerisch bewertet werden können. Die eingesetzte Planungsmethode eignet sich verallgemeinert auch für die Behandlung anderer Erweiterungen des Optimierungs­problems.

Der Beitrag ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einführung in das Problem

Die Optimierung der Fahrzeugumläufe dient im Rahmen der Betriebsplanung für den öffentlichen Verkehr (ÖV) dazu, ein vorgegebenes Fahrplanangebot kostengünstig zu erbringen. Dazu werden die Fahrten eines Betriebstages, die der Beförderung von Fahrgästen dienen (Servicefahrten), zu Ketten (Umläufen) zusammengefasst, so dass die Fahrten jeder Kette von einem Fahrzeug erbracht werden können. Die Bildung der Umläufe erfolgt so, dass die Kosten für die Erbringung des Fahrplan-Angebots aus Sicht des ÖV-Betreibers minimiert werden.

Die Aufgabe stellt sich offensichtlich bei der Planung des konkreten Betriebs, daneben jedoch auch auf der strategischen Planungsebene. Hierbei untersucht der ÖV-Betreiber vorausschauend alternative, zukünftige Angebotskonzepte, ermittelt deren laufende Betriebskosten sowie erforderliche Investitionen in Infrastruktur und Fahrzeuge.

In den letzten Jahren rückt besonders die Frage nach der Einführung von elektrisch betriebenen Bussen (E-Bussen) in den Vordergrund. Insbesondere für batteriebetriebene Busse mit fest verbauten Batterien unterscheiden sich die betrieblichen Randbedingungen für den Einsatz sehr deutlich von denen konventionell motorisierter Busse, da aufgrund beschränkter Reichweite regelmäßig aufgeladen werden muss, oft innerhalb eines Betriebstags. Im Folgenden beschränken wir uns auf die Betrachtung solcher E-Busse.

• Unter anderem sind folgende Fragen zu beantworten:

• Wie viele (zusätzliche) Fahrzeuge sind für die Abdeckung des Fahrplanangebots nötig, wenn Ladezeiten und ggf. Leerfahrten zur Lade-Infrastruktur notwendig werden?

• Wir groß sind die Auswirkungen auf die Betriebsleistung (Betriebs-Km und -Stunden)?

• Welche der denkbaren Ladestrategien (im Depot, an Linienendpunkten, während der Fahrt, Kombinationen davon) eignet sich im konkreten Fall am besten und wo?

• Wie lässt sich der gemischte Einsatz von elektrischen und konventionellen Bussen während einer Übergangszeit optimal planen, ggf. simultan mit anderen Einsatzerfordernissen, z.B. an die Nachfrage angepasster Gefäßgröße?

Werden die spezifischen Restriktionen von E-Bussen bei der Umlaufoptimierung ignoriert, überschreiten die gebildeten Umläufe regelmäßig die Reichweite der E-Busse. Unproduktive Zeiten innerhalb eines Umlaufs reichen für ausreichendes Nachladen nicht aus oder die Lade-Infrastruktur ist dort nicht vorhanden. Die triviale Lösung, zu lange Umläufe an Reichweitengrenzen zu brechen, führt meist zu suboptimalen Lösungen. Stattdessen kann die Lösungsqualität verbessert werden, wenn die Restriktionen des elektrischen Betriebs direkt bei der Optimierung berücksichtigt werden.

Im Rest dieses Papers wird ein solches Optimierungsverfahren beschrieben. In Kap. 2 wird der Stand der Forschung dargestellt. Kap. 3 formalisiert das Optimierungsproblem und stellt zunächst die Lösung ohne die Restriktionen des elektrischen Betriebs vor. Anschließend wird das Lösungsverfahren für die E-Bus-Planung erweitert. Wie sich zeigt, eignet sich die Erweiterung auch zur Lösung eines allgemeineren Umlauf-Optimierungsproblems, das u.a. bei der Planung für gemischte Flotten wesentlich ist. Zwei Beispiele illustrieren das Lösungsverfahren und seine planerische Verwendung.

2 Stand der Forschung

Als Ergebnis intensiver Forschung in den vergangenen Jahrzehnten stehen zahlreiche leistungsfähige Lösungsverfahren für die Umlauf-Optimierung bereit. Sie unterscheiden sich einerseits durch Varianten von Zielfunktion und Restriktionen, andererseits durch das eingesetzte Optimierungsverfahren.

Bunte 2003 [1] gibt einen Überblick über die zahlreichen Aufgabenvarianten und Lösungsverfahren. In der einfachsten Formulierung (Umlaufoptimierung, englisch: Vehicle Scheduling Problem [VSP]) werden die Servicefahrten durch gleichartige Fahrzeuge abgedeckt. Die zu minimierende Zielfunktion enthält sowohl variable Betriebskosten als auch fixe Kosten pro Fahrzeug, wodurch bei geeigneter Gewichtung die Flottengröße minimiert wird. Bei der Umlaufoptimierung mit einem Depot (SD-VSP) sind alle Fahrzeuge über Nacht in einem Betriebshof stationiert. Von dort erreichen sie leer den Beginn der ersten bedienten Servicefahrt und kehren nach der letzten Leistung leer zurück. Leerfahrten können auch zum Umsetzen zwischen Servicefahrten erlaubt sein. Im Fall der Umlaufoptimierung mit mehreren Depots (MD-VSP) dürfen die Fahrzeuge im Rahmen vorgegebener Kapazitätsrestriktionen auf mehrere Betriebshöfe verteilt werden. Beide Varianten mit Depots lassen sich auf Flotten mit verschiedenen Fahrzeugtypen verallgemeinern: Bei der Umlaufoptimierung mit Fahrzeugtyp¬gruppen (MVTG-VSP) ist für jede Servicefahrt festgelegt, mit welchen Fahrzeugtypen sie gefahren werden darf. Ein Umlauf für einen bestimmten Fahrzeugtyp ist zulässig, wenn die Fahrzeugtypgruppe jeder Fahrt diesen Fahrzeugtyp enthält. Über diese Grundtypen hinaus gibt es zahlreiche Erweiterungen, die hier nicht behandelt werden.

Nur das SD-VSP ist in polynomieller Laufzeit lösbar. Bereits MD-VSP ist dagegen NP-schwer [2], alle Erweiterungen damit ebenso. Die Forschung zu spezialisierten Verfahren, die dennoch auf praxisrelevanten Instanzen vertretbare Laufzeiten aufweisen, ist nicht abgeschlossen.

Diese Verfahren verwenden verschiedene Klassen von Lösungsansätzen:

• Ausschließlich heuristische Verfahren kamen insbesondere in der Anfangszeit zum Einsatz (z.B. [3]), als die direkte Lösung großer Mixed-Integer-Probleme (MIP) aussichtlos war. Darin wird oft die manuelle Erstellung von Umlaufplänen durch Formulierung von Konstruktionsregeln imitiert.

• Das Problem wird als eines von verschiedenen möglichen Graph-Flussproblemen ([4], [5], [6], [7]) formuliert, gelegentlich auch als ein anderes kombinatorisches Optimierungsproblem (z.B. Set Covering [9]). Das Problem wird entweder als MIP formuliert und mit einem entsprechenden Solver oder durch Anwendung eines Graph-Algorithmus (ungarische Methode, min-cost-flow, o.ä.) gelöst.

• Andere Ansätze kombinieren exakte Lösungsverfahren wie oben, oft angewendet auf abgeleitete SD-VSPs, mit einer Meta-Heuristik (z.B. [10]). Dabei kommen sowohl lokale Suchverfahren als auch komplexere evolutionäre Algorithmen zum Einsatz.

Die Erweiterung um Restriktionen für Batteriekapazität, Ladestrategie und Ladeinfrastruktur führt zu weiteren Problemvarianten. Auch dafür existieren bereits spezialisierte Lösungsverfahren. In vielen dieser Varianten spielt die beschränkte Reichweite die Hauptrolle, wogegen die Ladezeit vernachlässigbar ist, so bei Ansätzen mit Schnell-Laden [11] oder mit Batteriewechsel ([12], [13], [14]).

Dagegen definieren Wang und Shen (2007) [15] das Umlaufbildungsproblem mit Fahrzeit- und Tankzeit-Restriktionen (VSPRFTC, vehicle scheduling problem with route and fueling time constraints), bei dem auch das Tanken bzw. Laden signifikant Zeit in Anspruch nimmt. Reuer et al. 2015 [16] erweitert zu dessen Lösung den Ansatz aus [7]. Dabei ergänzen spezielle Strategien für die Flussdekomposition die Formulierung als MIP, welches mit IBM ILOG CPLEX gelöst wird. Der Ansatz gestattet ebenso die Einsatzplanung für gemischte Flotten durch Berücksichtigung von Fahrzeugtypgruppen.

Auch der hier beschriebene Ansatz löst das VSPRFTC. Er stützt sich gleichfalls auf die in [7] eingeführte Repräsentation als Time-Space-Network (TSN). Im Gegensatz zu [16] wird das TSN aber auf andere Weise erweitert, und die Lösung erfolgt nicht mit einem MIP-Solver, sondern durch die Kombination eines Graph-Algorithmus mit einem Genetischen Algorithmus. Der Genetische Algorithmus ermöglicht große Flexibilität bei der Definition der Zielfunktion, wodurch neben Fahrzeugtypgruppen weitere Anforderungen an die gebildeten Umläufe abgebildet werden können.

3 Formalisierung und Lösung des Basisproblems

In diesem Abschnitt wird zunächst das Basisproblem behandelt. Dabei existiert nur ein Fahrzeugtyp, der jedoch an mehreren Depots abgestellt sein kann. In der dargestellten, offenen Form sind die Servicefahrten auf einer endlichen Zeitachse (meist ein Tag) angeordnet. Fahrzeuge rücken zu Beginn des Zeitraums aus Depots aus, bedienen Servicefahrten und rücken am Ende wieder ein. Bei entsprechender Anpassung des Time-Space-Networks kann auch der geschlossene Fall bearbeitet werden, bei dem sich die Servicefahrten zyklisch wiederholen. In diesem Fall können auch mehrtägige Umläufe gebildet werden. Der Ansatz stellt in diesem Fall jedoch nicht sicher, dass Fahrzeuge nach vorgegebener maximaler Dauer in ein Depot zurückkehren.

3.1 Formalisierung

Zur Formalisierung des Problems dient die folgende Notation:

Tabelle siehe PDF.

Die Menge aller Servicefahrten und aller Leerfahrten für Ausrücken, Einrücken oder Umsetzen wird in einem TSN repräsentiert. Knoten entsprechen jeweils einem Paar (h,t) aus einer Haltestelle h und einer Zeit t. Im TSN gibt es sechs verschiedene Typen von Kanten:

Tabelle siehe PDF.

Alle Kanten sind mit Kosten sowie einer unteren und oberen Kapazität versehen:

Tabelle siehe PDF.

In der konkreten Software-Implementierung werden die Betriebskosten der Kanten aus entfernungs- bzw. zeitbezogenen Kostensätzen und aus den Netzattributen der befahrenen Streckenfolgen vorberechnet.

Gesucht ist ein betriebskostenminimaler Umlaufplan, der die folgenden Restriktionen erfüllt:

1) Alle Servicefahrten werden durch genau ein Fahrzeug bedient.

2) Alle Depotkapazitäten werden eingehalten.

3) Alle Umläufe sind zeitlich zulässig, d.h. die enthaltenen Fahrten folgen chronologisch aufeinander und lassen dazwischen ausreichend Zeit für ggf. benötigte Einrück-, Ausrück- und Leerfahrten.

3.2 Lösungsverfahren

Das Basisproblem wird in drei Schritten gelöst:

Schritt 1: Graph-Reduktion. Das zuvor beschriebene TSN kann zunächst durch Zusammenfas¬sen von Knoten und Kanten verkleinert werden, wodurch sich die Lösung des nachfolgenden Flussproblems beschleunigt und weniger Knoten dekomponiert werden müssen. Die Methode dafür ist identisch mit der Graph-Reduktion in [7].

Schritt 2: Fluss-Problem. Das TSN ist so definiert, dass jeder optimale Umlaufplan einem kostenminimalen Fluss, der die oberen und unteren Kantenkapazitäten einhält, entspricht. Ein solcher kostenminimaler Fluss wird durch Anwendung eines Min-cost-flow-Graph-Algorithmus konstruiert. Wegen der positiven unteren Kapazitätsgrenzen an den Servicefahrt-Kanten E_f kommt es zu einem nicht-trivialen Fluss. In der konkreten Software-Implementierung wird der Algorithmus aus LEDA [8] benutzt.

Schritt 3: Fluss-Dekomposition. Zu jedem Umlaufplan gehört genau ein Fluss im TSN. Umgekehrt gilt dies nicht, vielmehr entsprechen im Allgemeinen mehrere Umlaufpläne demselben Fluss. Diese Mehrdeutigkeit entsteht durch Knoten, über die mehrere Flusseinheiten fließen – also Haltestellen, an denen sich mehrere Fahrzeuge gleichzeitig befinden. An einem Knoten gibt es mehrere eingehende (und mehrere ausgehende) Kanten, und zusätzlich können alle anderen als die Servicefahrt-Kanten jeweils einen Fluss > 1 aufweisen. Es treten deshalb Knoten auf, bei denen die Summe der Flusseinheiten über die eingehenden Kanten (und damit auch über die ausgehenden Kanten) > 1 ist. Jede Verknüpfung jeder eingehenden mit einer ausgehenden Flusseinheit am Knoten ist bezüglich der Kosten gleichwertig. Gleichzeitig haben unterschiedliche Verknüpfungen lokal an einem Knoten große Auswirkungen auf die globale Struktur der dadurch definierten Umläufe. Der sich daraus ergebende Freiheitsgrad kann genutzt werden, um sekundäre Anforderungen (z.B. Linienreinheit, gleichverteilte Wendezeitpuffer) zu erfüllen. Im einfachsten Fall werden an einer Haltestelle h ein- und ausgehende Flusseinheiten in Ankunftsreihenfolge (FIFO) oder umgekehrt (LIFO) verknüpft. Entsprechende Detailkenntnis der lokalen Verhältnisse vorausgesetzt, können an dieser Stelle aber auch Restriktionen berücksichtigt werden, die sich insbesondere im Schienenverkehr aus der Abstellungsplanung ergeben.

4 Erweiterung für elektrisch betriebene Fahrzeuge

Im erweiterten Optimierungsproblem wird zunächst weiterhin von einem einzigen Fahrzeugtyp ausgegangen. Dieser verfügt über elektrischen Antrieb, der durch eine Batterie gespeist wird. Die Batterie wird nicht getauscht, sondern im Fahrzeug aufgeladen.

4.1 Formalisierung

Gesucht ist in diesem Fall ein betriebskostenminimaler Umlaufplan, der neben den Restriktionen 1) – 3) aus Abschnitt 3.1 auch die folgenden erfüllt:

4) Batterien können nur an bestimmten Haltestellen aufgeladen werden. Dort kann nur eine begrenzte Anzahl Fahrzeuge gleichzeitig geladen werden. Auch das Laden während der Fahrt (z.B. unter abschnittsweise vorhandener Oberleitung oder induktiv) kann modelliert werden. In jedem Fall erfordert das Laden eine Zeit, und die Zunahme des Ladezustands hängt von dieser Zeit (und vom Ort des Ladens) ab.

5) Der Ladezustand jedes Fahrzeugs bleibt entlang seines gesamten Umlaufs jederzeit möglichst oberhalb eines Mindestwerts λ_min, auf jeden Fall aber positiv. Dies schließt Leerfahrten zum Erreichen des jeweiligen Ladeorts ein.

Die Batteriekapazität wird zur Vereinfachung auf den Wert 1 normiert. Zulässige Ladezustände liegen damit im Intervall [0..1]. Negative Ladezustände können in Zwischenzuständen des Lösungsverfahrens auftreten, sind jedoch für den finalen Umlaufplan unzulässig.

Grundidee der Erweiterung ist, das TSN um einen weiteren Kantentyp zu ergänzen. Dieser repräsentiert Lade-Vorgänge, wohingegen die Batterie auf den anderen Kantentypen entladen wird. Im Verfahren wird der Verlauf des Ladezustands eines Fahrzeugs durch Auswerten der Lade- und Entladefunktion für die Kanten seines Umlaufs berechnet.

Die Lade-Funktion Lf_(s,λ) repräsentiert den zeitlichen Verlauf des Ladevorgangs und wird durch zwei Parameter bestimmt (Bild 1):

• Der Ladezustand steigt linear mit der Zeit bis zum Erreichen des Schwellwerts λ. Danach nähert sich der Ladezustand der vollen Kapazität nur noch asymptotisch.

• Die Steigung des linearen Abschnitts ist s=λ/T^λ.

Es gilt genauer

Bild 1: Verlauf der Ladefunktion und charakterisierende Parameter

Dabei ist der Brechpunkt λ, also derjenige Ladezustand, bei dem die Ladekurve vom linearen in einen exponentiellen Verlauf übergeht, ein Charakteristikum des Fahrzeugs, also eine Konstante, wogegen die initiale Steigung s=λ/T^λ von der Kante (z.B. vom Ladeort und/oder von der Uhrzeit) abhängt. Weil die Zunahme des Ladezustands auf einer Kante vom Ladezustand zu Beginn der Kante und somit vom Kontext der Kante innerhalb ihrer Kette abhängt, kann nur die initiale Steigung als Funktion s(e) auf den Kanten e angesehen werden, nicht die Zunahme des Ladezustands selbst. Die Entladung (der ‚Verbrauch‘) hingegen kann jeder Kante e als feste Zahl v(e) zugeordnet werden, die sich in der konkreten Software-Implementierung aus Netzattributen (Länge, Fahrzeit, Steigung, Anzahl Fahrgäste, Stop & Go-Vorgänge auf einem Streckenabschnitt) der durchfahren Strecken berechnet.

Die Zunahme des Ladezustands eines Fahrzeugs, welches die Kante e mit Ladezustand SoC_alt erreicht, berechnet sich mithilfe der Kehrfunktion Lf^(-1) aus der Dauer d(e) der Kante wie folgt:

Formel siehe PDF.

Solange der Wert den linearen Bereich der Ladefunktion nicht verlässt, ist die Zunahme nichts anderes als s(e)d(e) und kann mithin als Produkt aus Ladedauer und Ladestrom interpretiert werden. Wird auf einer Kante gleichzeitig ge- und entladen, beispielswiese bei Fahrt unter Oberleitung, gibt es zwei sinnvolle Möglichkeiten, dies zu berücksichtigen:

• Ist die beziehbare Leistung (im relevanten Bereich) unbegrenzt, wird auf solchen Kanten der Verbrauch vollständig durch die entnommene Leistung abgedeckt, der Verbrauch entfällt also aus Sicht der Batterie, und es wird nur geladen.

• Ist die beziehbare Leistung begrenzt, wird die initiale Steigung der Ladefunktion um den mittleren Verbrauch über die Dauer der Kante reduziert.

Zur Formalisierung wird die Notation wie folgt erweitert:

Tabelle siehe PDF.

Das TSN für das erweiterte Problem enthält alle Knoten und Kanten des Basisproblems, Ausrück-Kanten E_a werden aber nicht nur für Depots, sondern zusätzlich auch von Ladeorten her eingefügt (wenn diese nicht ohnehin auch Depots sind). An Ladeorten gibt es zusätzliche Kanten analog zu den Depot-Kanten:

Tabelle sieh PDF.

Ladevorgänge können länger dauern als eine einzelne Lade-Kante, da eine Flusseinheit mehrere Lade-Kanten in Folge benutzen kann. Dies hat wegen der Nicht-Linearität der Ladefunktion zur Folge, dass die Erhöhung des Ladezustands nicht fest der Kante zugeordnet, sondern erst nach der Flussdekomposition für den resultierenden Umlauf aus allen benutzten Kanten berechnet werden kann.

Die Lade-Kanten sind mit Kosten sowie einer unteren und oberen Kapazität versehen:

Tabelle sieh PDF.

4.2 Lösungsverfahren

Zur Lösung der gegebenen Aufgabenstellung wird ein Genetischer Algorithmus verwendet. Das heißt, es gibt in jedem Schritt (‚Generation‘) eine Menge von gleichzeitig vorhandenen, alternativen Lösungen (die ‚Population‘), und von einem Iterationsschritt zum nächsten werden alle diese Lösungen variiert oder durch Kreuzung zweier Lösungen eine neue Lösung erzeugt, die Eigenschaften ihrer beiden ‚Eltern‘ kombiniert. Eine Bewertung misst die Qualität jeder einzelnen Lösung, und die beste jemals konstruierte Lösung wird als Ergebnis ausgegeben.

Die Minimierung der Gesamtkosten eines Umlaufplans einerseits und die Einhaltung der Restriktion 5) andererseits bilden konkurrierende Ziele, da das Laden selbst Kosten verursacht und eventuell sogar den Einsatz zusätzlicher Fahrzeuge erzwingt. Daher bilden die Gesamtkosten des Umlaufplans sowie die Summe aller aufgetretenen Unterschreitungen des minimalen Ladezustands λ_min zwei separate Zielfunktionskomponenten, deren relative Wichtigkeit über einen Vorfaktor gegeneinander abgewogen werden muss.

Die Daten, die eine Lösung ausmachen (das sogenannte ‚Genom‘), bestehen aus den Umläufen selbst, codiert als Abfolgen von Kanten (‚Ketten‘) im TSN.

Wegen der zusätzlichen Kosten, die durch das Laden entstehen, wird die Lösung des Min-cost-flow-Algorithmus nicht von sich aus Lösungen produzieren, welche die Bedingung 5) an den Ladezustand erfüllen. Deswegen wird der Algorithmus zur Konstruktion einer Lösung auf einem modifizierten TSN angewendet, bei dem für einzelne Ladekanten durch eine positive untere Kapazitätsschranke ein Fluss erzwungen wird. Auf diese Weise wird das Durchführen von Ladevorgängen als zusätzliche Bedingung eingeführt, ohne die guten Struktureigenschaften der Flusslösungen zu verlieren. Diese untere Grenze je Ladekante, also eine Abbildung, zählt ebenfalls zum Genom der Lösung und kann modifiziert werden, um Varianten der Lösung zu erzeugen.

Ist keiner der Start- und Endpunkte H_1,…,H_n der Servicefahrten ein Ladeort und sind Leerfahrten teuer, reicht das Erzwingen von Ladekanten allerdings nicht aus, um im Sinne von Bedingung 5) zulässige Flusslösungen zu erzielen, denn dann ist es günstiger, ein zusätzliches Fahrzeug einzusetzen, welches nur die erzwungenen Ladekanten am Ladeort L erfüllt, während sich die übrigen Fahrzeuge ausschließlich zwischen den H_i bewegen, anstatt Leerfahrten von einem der H_i nach L sowie von L nach einem H_j einzufügen. Deswegen wird eine weitere Abbildung  in das Genom aufgenommen, welche Untergrenzen für die Benutzung von Einrückkanten festlegt.

Mithilfe der erzwungenen Belegung von Einrück- und Ladekanten werden die konkreten Abfolgen von Kanten einer Lösung wie folgt berechnet:

Schritt 1‘: Graph-Modifikation. An dem zuvor einmalig aufgebauten Graph werden die Untergrenzen der Kapazität für Einrück- und Ladekanten gemäß den Daten der Lösung modifiziert.

Schritt 2: Fluss-Problem. Das Flussproblem wird exakt wie in 3.2 beschrieben gelöst, allerdings für den modifizierten Graphen.

Schritt 3: Fluss-Dekomposition. Die Dekomposition des Flusses hat naturgemäß sehr großen Einfluss auf die Einhaltung der Reichweitenbedingung 5). Außerdem sollen Ladevorgänge nicht allzu kurz ausfallen. Daher sind sowohl der Kanten-Typ als auch der Ladezustand der Fahrzeuge bei der Fluss-Dekomposition zu berücksichtigen: Eingehender Fluss auf Ladekanten wird vorzugsweise mit ausgehendem Fluss auf Ladekanten verbunden, solange die schon bekannte Abfolge von Ladekanten noch nicht hinreichend lang ist. Andere Flusseinheiten werden so miteinander verbunden, dass die Ladezustände der sich ergebenden Ketten möglichst nicht negativ werden, was auf ein Matching-Problem mit dem Ladezustands-Minimum als Bewertung für jede Kombination hinausläuft.

Im Gegensatz zum Basisproblem ist es für die erweiterte Problemstellung sinnvoll und zielführend, die Abfolgen von Kanten im Graphen, die dem Umlaufplan entsprechen, direkt zu modifizieren: Während dadurch im Basisproblem nie eine Verbesserung bezüglich der Kosten eintreten kann, da der Fluss bereits kostenoptimal ist, kann eine Verschlechterung der Kosten in der kombinierten Bewertung durch eine Verbesserung der Bewertung der Ladezustands-Bedingungen mehr als ausgeglichen werden. Dies ist z.B. dann der Fall, wenn eine Abfolge von Wartekanten in h durch eine Umsetzkante zu einem Ladeort l, einer Abfolge von Ladekanten in l und einer Ausrückkante zurück nach h ersetzt wird. Aus diesem Grund sind die geforderten Untergrenzen für Ausrück- und Ladekanten nicht hinreichend zur Charakterisierung einer Lösung, sondern nur die Ketten selbst.

Das genetische Verfahren verwaltet die verschiedenen Lösungen und deren Erstellung, Variation und Bewertung, während der Min-cost-flow-Algorithmus für die konkrete Konstruktion von Lösungen verwendet wird, kombiniert mit anderen Konstruktionsverfahren. Die eigentliche Kunst besteht in der Definition geeigneter Operationen, die eine gegebene Lösung verändern. Typische Operationen sind:

• Anheben der erzwungenen Ladung: Entlang der Abfolgen von Kanten, die den Betriebstag mit Ladezustand 1 beginnen, wird festgestellt, wann und wo der minimale Ladezustand λ_min erreicht wird. An einem von dort aus erreichbaren Ladeort, der in der gegenwärtigen Lösung noch freie Kapazität hat, wird der minimale geforderte Fluss an Kanten mit passendem Zeitpunkt angehoben, und ebenso falls notwendig der minimale Fluss auf der Einrückkante zu diesem Ladeort. Die Lösung wird nicht direkt modifiziert, sondern in dieser neuen Konstellation eine neue Flusslösung berechnet, um wiederum eine (zu den neuen Bedingungen) kostenoptimale Lösung zu erhalten. Dieser Vorgang kann mit der gleichen Lösung so lange wiederholt werden, bis dadurch keine Verbesserung der Bewertung des Ladezustands mehr eintritt.

• Absenken der erzwungenen Ladung: Ohne Kapazitätsrestriktionen zu verletzen kann die Nutzung einer Ladekante immer durch Nutzung der dazu parallelen Wartekante ersetzt werden. Für jede Ladekante im Verlauf jeder Abfolge von Ketten kann man prüfen, ob sich die Bewertung des Ladezustands durch diese Ersetzung verschlechtert. Ist dies nicht der Fall, wird die Ersetzung angenommen. Diese Operation kann wahlweise direkt auf den Kanten-Abfolgen ausgeführt werden oder durch Reduktion des Mindestflusses und anschließend erneutes Lösen des Flussproblems.

• An einem Knoten, der von zwei Kanten-Abfolgen berührt wird, werden die beiden dortigen Kanten-Übergänge in diesen beiden Abfolgen ausgetauscht, d.h. die Dekomposition an diesem Knoten wird verändert.

• Auch Zufallselemente werden für den genetischen Algorithmus benötigt, in diesem Fall das Herauf- oder Herabsetzen des Mindestflusses für Lade- und Einrückkanten.

Die ‚Kreuzung‘, also die Konstruktion neuer Lösungen auf Basis zweier ausgewählter Lösungen, kann wahlweise auf zwei Ebenen erfolgen:

• Entweder werden lediglich die Mindestanforderungen für den Fluss auf Lade- und Einrückkanten neu kombiniert, d.h. für jede Kante wird der Mindestfluss der einen oder der anderen Lösung übernommen, das dadurch definierte Min-cost-flow-Problem gelöst und der Fluss dekomponiert.

• Oder man operiert direkt auf den Kanten-Abfolgen, indem man die gegebenen Abfolgen der vorgegebenen Lösungen jeweils an den Servicefahrt-Kanten aufschneidet und die so entstandenen Teil-Kanten-Abfolgen passend neu aneinanderhängt. Da bei beiden ‚Eltern‘-Lösungen jede Servicefahrt-Kante genau einmal in den Kanten-Abfolgen vorkommt, geht diese Vertauschungsoperation stets auf. Im Gegensatz zur Rekombination auf Basis der Mindestanforderungen reproduziert diese Operation lokal die vorgegebenen Kanten-Abfolgen, so dass explizit auf diesen Abfolgen zuvor vorgenommene Veränderungen (z.B. durch Änderung der Dekom¬position an einem Knoten oder durch Einfügen von Ladevorgängen) erhalten bleiben.

Das Verfahren wird beendet, wenn sich entweder bei der fortgesetzten Modifikation und Rekombination der Lösungen der globale Bestwert aller Bewertungen über mehrere Iterationen hinweg nicht mehr verändert oder wenn eine vorgegebene maximale Anzahl Iterationen erreicht wurde. In beiden Fällen ist nicht garantiert, dass die am besten bewertete Lösung die Restriktion 5) einhält oder dass überhaupt eine Lösung gefunden wurde, welche 5) erfüllt. Man kann leicht Gegenbeispiele konstruieren, bei denen eine solche Lösung nicht existieren kann, beispielsweise wenn der Verbrauch einer einzelnen Servicefahrt bereits größer ist als die Kapazität der Batterie. Die ausgegebene Lösung wird daher explizit auf Erfüllung der Reichweiten-Bedingung 5) geprüft. In der konkreten Software-Implementierung werden auch Lösungen ausgegeben, die diese Bedingung verletzen, weil sich daraus durch den Anwender Rückschlüsse auf die Ursache und mögliche Auswege ziehen lassen.

Aufgrund der Vorgehensweise können zusätzlich zur Bestlösung weitere Lösungen mit guten Bewertungen ausgegeben werden. Das ist dann interessant, wenn sich diese strukturell voneinander unterscheiden, insbesondere weil es in der Praxis immer Randbedingungen gibt, die in der formalisierten Problemstellung keine Berücksichtigung finden, wohl aber bei der subjektiven Bewertung der Planungsvarianten durch den Anwender.

4.3 Ausblick: Erweiterung auf mehrere Fahrzeugtypen und weitere Varianten

Das beschriebene Verfahren, bei dem der Genetische Algorithmus Daten der Lösungen kontrolliert und das Flussproblem zur Konstruktion neuer Lösungen benutzt wird, lässt sich auf den Fall mehrerer Fahrzeugtypen erweitern. Dazu wird je Fahrzeugtyp ein eigenes TSN, also ein eigener Graph, gebildet. Für jede Servicefahrt ist im MVTG-VSP die Menge der Fahrzeugtypen, die diese Fahrt bedienen können, angegeben. Für jede dieser Optionen gibt es eine Servicefahrt-Kante im zum Fahrzeugtyp gehörenden TSN. Zusätzlich gibt es für jede Servicefahrt mit mehr als einer Option eine Liste der zugehörigen Kanten in den einzelnen TSN. Die Auswahl genau einer dieser Kanten je (variabler) Servicefahrt wird zum Bestandteil des Genoms einer Lösung im Sinne des Genetischen Algorithmus.

Bei gegebener Wahl der Optionen (und der Mindestflüsse auf Lade- und Einrückkanten) lässt sich wiederum eine passende Lösung mithilfe des Min-cost-flow-Algorithmus finden, indem zusätzlich zu den Modifikationen der Untergrenzen für Lade- und Einrückkanten für nicht gewählte Servicefahrt-Kanten die untere und obere Kapazitätsgrenze auf 0 modifiziert wird. Dem Algorithmus müssen natürlich Operationen hinzugefügt werden, die die Wahl der Optionen je Servicefahrt sinnvoll modifizieren.

Angemerkt sei, dass bei dieser Erweiterung alle Daten, insbesondere die Kosten für Kanten, die Fahrzeugkosten sowie die den Lade- und Entladevorgang beschreibenden Funktionen, je Graph, also je Fahrzeugtyp, unterschiedlich sein können. Durch Weglassen der Lade- und Entladefunktion in einem Graphen können so Misch-Szenarien aus batteriebetriebenen und dieselbetriebenen Bussen abgebildet werden.

Der Ansatz, das Flussproblem im TSN lediglich als eine Möglichkeit unter anderen zur Konstruktion hinreichend guter Lösungen zu benutzen, im Weiteren aber den Genetischen Algorithmus mit seinen Freiheitsgraden bei der Konstruktion, Modifikation und Bewertung zu verwenden, eröffnet die Möglichkeit, flexibel weitere Randbedingungen und Bewertungskriterien zu integrieren. Naheliegend (und in der konkreten Software-Implementierung auch umgesetzt) ist beispielsweise im Fall mehrerer Fahrzeugtypen der Abgleich der Kapazität des gewählten Fahrzeugtyps mit der erwarteten Nachfrage. Auch die Überschreitung einer vorgegebenen Anzahl Instanzen eines Fahrzeugtyps kann in diesem Setting leicht bewertet werden, obwohl diese Bewertung vollkommen nicht-linear ist.

5 Beispiele

5.1 Veranschaulichung des TSN und des Lösungsverfahrens

Das erste Beispiel dient zur Veranschaulichung des TSN und des Lösungsverfahrens. Das Angebot besteht aus einer einzigen Linie zwischen Haltestellen A und B in beiden Richtungen. Die Linienlänge beträgt 15 km. Das einzige Depot ist 10 km von A und B entfernt. Laden ist nur dort möglich (ohne Kapazitätsbeschränkung). Bei einer Linien-Fahrzeit von 30 min und einem 20 min-Takt reichen 4 konventionelle Busse für die Bedienung (Bild 2).

Bild 2: Zeit-Weg-Diagramm des Fahrplanangebots. Farben entsprechen den Umläufen mit E-Fahrzeugen

Die E-Fahrzeuge weisen jedoch nur eine Reichweite von 50 km auf, was genau für zwei Service-Fahrten und je eine Ein/Ausrück-Fahrt reicht. Das Laden der Batterie auf volle Kapazität benötigt 30 min.

Bild 3 zeigt eine Lösung, die im Verlauf der Optimierung evaluiert wurde.

Bild 3: Ausschnitt des TSN mit eingezeichnetem Fluss für eine mögliche Lösung

Grün sind die Servicefahrt-Kanten dargestellt, die erkennbar (dunkelgrün) alle von einer Flusseinheit durchflossen werden. Gelb sind Leerfahrt-Kanten zwischen den Haltestellen bzw. zum Depot. Nur die rot gezeichneten weisen einen Fluss auf. Violette Kanten repräsentieren Stand an der Haltestelle, schwarze Stand im Depot und orange Kanten Laden im Depot. Im gezeichneten Lösungskandidaten haben die Mutationsoperationen im Zuge des Genetischen Algorithmus die untere Kapazität von Ein-/Ausrück-Kanten und von Lade-Kanten von 0 auf 1 verändert und damit einen Tausch der Fahrzeug-Instanzen erzwungen, wenn die ersten vier eingesetzten Fahrzeuge das Ende ihrer Reichweite erreichen. Der Eingriff in die Fluss-Dekomposition bewirkt, dass die einrückenden Fahrzeuge auf eine Lade-Kante wechseln, wogegen die zuvor geladenen, auf Stand-Kanten im Depot wartenden Fahrzeuge ausrücken. Nach Ende des Ladevorgangs wechseln die Fahrzeuge von der Lade-Timeline auf die Depot-Timeline und warten auf erneutes Ausrücken. Der optimale Umlaufplan für dieses Beispiel bindet 8 E-Fahrzeuge.

5.2 Einsatzbeispiel in der Planung

Das zweite Beispiel zeigt, wie die Umlaufbildung planerisch der Bewertung unterschiedlicher Ladestrategien dienen kann. Drei Buslinien bedienen gemeinsam ein Stadtviertel, wobei sich ihre Linienrouten teilweise überlappen (Bild 4). Die wichtigsten Kenngrößen enthält Tabelle 1.

Bild 4: Liniennetz für Beispiel in der Planung

Tabelle 1: Verkehrsangebot für Beispiel in der Planung

Das Depot wird von keiner Linienroute direkt berührt, sondern liegt ca. 1 km von der nächsten entfernt. Ausgangspunkt ist ein Umlaufplan für konventionell angetriebene Fahrzeuge, der aus einer Optimierung des MVTG-VSP hervorgeht. Jede Servicefahrt darf von einem Standard- oder einem Gelenkbus bedient werden. Für die Servicefahrten sind aus einer Umlegung erwartete Fahrgastzahlen vorgegeben, und ein Term der Zielfunktion im Genetischen Algorithmus bestraft die Zuordnung von Fahrzeugen mit unzureichender Kapazität für die Nachfrage. Aufgrund geringerer Betriebskosten wird der Standard-Bus gewählt, wenn seine Kapazität ausreicht. Der ermittelte minimale Fahrzeugbedarf liegt bei 3 Standard- und 2 Gelenkbussen.

In der einfachsten elektrifizierten Variante werden beide Fahrzeugtypen batterieelektrisch angetrieben, wobei die Reichweite in beiden Fällen 150 km beträgt. Der Verbrauch wird vereinfacht proportional zur gefahrenen Entfernung angenommen. Laden ist nur im Depot möglich und dauert 4 Stunden für eine volle Ladung.

Die Umlaufoptimierung liefert in diesem Fall einen Umlaufplan mit 7 Bussen (3 Standard + 4 Gelenk). Die grafische Darstellung in Bild 5 zeigt den Ladezustand am Ende jedes Umlaufelements, farblich klassifiziert von grün (voll) bis rot (leer). Alle Fahrzeuge müssen zusätzlich zum Aufladen über Nacht auch tagsüber zum Nachladen (blau) ins Depot, wobei nicht alle die volle Ladezeit benötigen.

Bild 5: Umlaufplan bei Laden nur im Depot

Zur Reduktion des Fahrzeugmehrbedarfs werden zwei ergänzende Ladestrategien untersucht. In der ersten Strategie wird ein von mehreren Linien befahrener Streckenabschnitt von 2 km Länge mit Oberleitung ausgerüstet und dort während der Fahrt nachgeladen. Der resultierende Umlaufplan (Bild 6) zeigt, dass dadurch Zahl und Dauer der Ladevorgänge während des Tags reduziert und ein Gelenkbus eingespart werden kann.

Bild 6: Umlaufplan bei Laden im Depot und unter Oberleitung

Noch wirksamer ist jedoch die Ausrüstung jeweils einer Linienendstelle mit stationärer Ladeeinrichtung. Werden am gemeinsamen Endhaltepunkt der blauen und grünen Linie 2 Ladeeinheiten und am Endpunkt der roten Linie eine Ladeeinheit (mit gleicher Ladegeschwindigkeit wie im Depot) geschaffen, reichen die Wendezeiten fast zur Kompensation des Verbrauchs aus. Laden im Depot ist untertags entbehrlich. Dadurch reichen die eingangs benötigten 5 Busse (3 Standard + 2 Gelenk) zur Bedienung aus (Bild 7).

Bild 7: Umlaufplan bei Laden im Depot und an Linienendstellen

Tabelle 2 zeigt anhand weiterer betrieblicher Kenngrößen die Überlegenheit der letzten Variante. So ist in diesem Fall auch die Zahl der Leer-km minimal, weil Fahrten ins Depot zum Nachladen vermieden werden. Auffällig ist dagegen die viel höhere Anzahl von (kurzen) Lade-Vorgängen, die sich wegen des geringeren Ladehubs positiv auf die Lebensdauer der Batterie auswirken.

Tabelle 2: Betriebliche Kenngrößen aller Varianten

6 Zusammenfassung, Ausblick

Das beschriebene Verfahren für die Umlaufoptimierung für batterieelektrisch angetriebene Fahrzeuge kombiniert einen Graph-Algorithmus für das Basisproblem mit einem Genetischen Algorithmus, der den Flussgraph verändert. Zusätzlich werden die Freiheitsgrade bei der Fluss-dekomposition gezielt ausgenutzt. Das Verfahren liefert in praktikabler Rechenzeit für die bisher untersuchten Instanzen Lösungen mit nur geringem Fahrzeugmehrbedarf und guter Ausnutzung der Batteriekapazität.

Die große Freiheit bei der Zielfunktion des GA erlaubt eine Verallgemeinerung auf das MVTG-VSP und damit die Planung für heterogene Flotten. Es ist beabsichtigt, zukünftig noch allgemeiner laufleistungs- oder zeitabhängige Aktivitäten (z.B. Reinigung, Toilettenentleerung) bei der Umlaufoptimierung zu berücksichtigen.

7 Literatur

1 Bunte, S. (2009). Lösungen für Anwendungsfälle der Fahrzeugeinsatzplanung im öffentlichen Personennahverkehr. Dissertation, Universität Paderborn.

2 Bertossi, A. A., Carraresi, P., und Gallo, G. (1987). On some matching problems arising in vehicle scheduling models. Networks, 17:271-281.

3 Bodin, L. und Rosenfield, D. (1976). Estimation of the operating cost of mass transit systems. Technical report, State University of New York.

4 Bodin, L., Golden, B., Assad, A., und Ball, M. (1983). Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research, 10(2):63-211.

5 Löbel, A. (1996). Solving large-scale real-world minimum-cost flow problems by a network simplex method. Technical Report SC96-7, Konrad-Zuse Zentrum für Informationstechnik (ZIB), Berlin.

6 Mesquita, M. und Paixao, J. P. (1992). Multiple depot vehicle scheduling problem: A new heuristic based on quasi-assignment algorithms. In Desrochers, M. und Rousseau, J.-M., editors, Computer-Aided Transit Scheduling: Procs. of the Fifth International Workshop on Computer Aided Scheduling of Public Transport, volume 386 of Lecture Notes in Economics and Mathematical Systems, pages 167-180, Berlin. Springer.

7 Kliewer, N. (2005). Optimierung des Fahrzeugeinsatzes im öffentlichen Personennahverkehr - Modelle, Methoden und praktische Anwendungen. Dissertation, Universität Paderborn

8 Mehlhorn, K., Näher, S. (1999). LEDA: A platform for combinatorical and geometric computing. Cambridge University Press, Cambridge.

9 Orloff, C. S. (1976). Route constrained fleet scheduling. Transportation Science, 10(2):149-168.

10 Pepin, A.-S., Desaulniers, G., Hertz, A., und Huisman, D. (2006). Comparison of heuristic approaches for the multiple depot vehicle scheduling problem. Technical Report EI2006-34, Econometric Institute, Erasmus University Rotterdam.

11 Li, J. Q. (2014) Battery-electric transit bus developments and operations: A review. International Journal of Sustainable Transportation DOI 10.1080/15568318.2013.872737

12 Chao, Z., Chen, X. (2013). Optimizing Battery Electric Bus Transit Vehicle Scheduling with Battery Exchanging: Model and Case Study, Procedia Social and Behavioral Sciences.

13 Kang, Q., Wang, J., Zhou, M., Ammari, A.C. (2016). Centralized Charging Strategy and Scheduling Algorithm for Electric Vehicles Under a Battery Swapping Scenario. IEEE Trans. On Intelligent Transportation Systems (17) 3: 659-669.

14 Li, J. Q. (2018). Transit Bus Scheduling with Limited Energy. Transportation Science 48(4):521-539.

15 Wang H, Shen J (2007). Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints. Applied Mathematics and Computation 190(2):1237-249.

16 Reuer, J., Kliewer, N., Wolbeck, L. (2015). The Electric Vehicle Scheduling Problem – A study on time-space network based and heuristic solution approaches. In: Proc. Computers in Scheduling and Planning of Public Transport (CASPT) 2015