Für die operative Planung von Erhaltungsmaßnahmen im Straßenbau beschreiben wir eine mathematische Formulierung der Kompromissfindung zwischen wirtschaftlicher Optimalität und praktischer Durchführbarkeit. Entsprechend der konkreten Anforderungen des Landesbetriebs Straßenbau NRW (Straßen.NRW) wird mithilfe unterschiedlicher Ziel- bzw. Bonusfunktionen die Bewertung der Qualität von Sanierungsplänen durchgeführt. Auf Grundlage dessen verwenden wir Methoden der ganzzahligen linearen Programmierung, um optimierte Sanierungspläne zu generieren.

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

1 Einleitung

Durch die stetig wachsende Anzahl an Fahrzeugen, sowohl im Personen- als auch im Güterverkehr und das daraus resultierende erhöhte Verkehrsaufkommen, sind die Straßen auf deutschen Autobahnen einer großen Belastung ausgesetzt. Der mit der Belastung einhergehenden Abnutzung muss mit Sanierungsarbeiten entgegengewirkt werden, um für die Qualität und damit für die Sicherheit der Straßen garantieren zu können. In NRW ist der Landesbetrieb Straßenbau NRW (Straßen.NRW) für die Unterhaltung und Instandsetzung der Autobahnen zuständig. Im Zuge dessen wird in regelmäßigen Abständen der Zustand aller Autobahnen erhoben. Straßen.NRW sieht sich dann mit der Herausforderung konfrontiert, aus den Zustandsdaten einen Sanierungsplan für die kommenden Jahre zu entwickeln, in dem festgelegt wird, welche Maßnahme auf welchem Teil der Autobahn in welchem Jahr durchgeführt wird. Dabei gilt es beispielsweise zu berücksichtigen, dass sich der Aufwand für die Durchführung der Sanierungsarbeiten gleichmäßig über NRW verteilt, dass sich störende Einflüsse von Baustellen auf den Verkehrsfluss der einzelnen Autobahnen in Grenzen halten und dass der Jahresetat nicht überschritten wird. Zur Entscheidungsunterstützung wird dafür aktuell das Pavement Management System dTIMS verwendet. Der Fokus von dTIMS liegt auf der Planung der Maßnahme auf einem Straßenabschnitt zum wirtschaftlich optimalen Zeitpunkt.

In der operativen Planung der Sanierungsmaßnahmen muss ein Kompromiss aus wirtschaftlicher Optimalität und praktischer Durchführbarkeit gefunden werden. Im Folgenden werden wir darstellen, wie diese Kompromissfindung mathematisch modelliert und mithilfe ganzzahliger linearer Optimierung durchgeführt werden kann.
Zunächst werden wir beschreiben, wie man das Autobahnnetz von NRW auf eine geeignete Graphenstruktur übertragen kann. Anschließend werden die praktischen Anforderungen eines Sanierungsplans mathematisch modelliert. Dazu gehören Fragen der Durchführbarkeit und der Quantifizierung der Qualität des Plans mittels verschiedener Ziel- bzw. Bonusfunktionen. Nachdem eine auf die konkreten Anforderungen von Straßen.NRW zugeschnittene Form dieses Problems als ganzzahliges lineares Programm beschrieben worden ist, stellt Abschnitt 3 dar, wie das Modell automatisiert gelöst werden kann und wie sich unterschiedliche Zielfunktionen auf die Qualität der Lösung bzw. der generierten Pläne auswirken: Sie verbessern die Qualität der dTIMS-Lösung je nach Bonussystem deutlich.

2 Problembeschreibung und -modellierung

In diesem Abschnitt werden wir die Erstellung eines durchführbaren Sanierungsplans mathematisch modellieren.

2.1 Modellierung des Straßennetzes

Je nach Anwendungsbereich werden Straßennetze unterschiedlich beschrieben. Die in dieser Arbeit verwendete Beschreibung ist im Wesentlichen aus den von Straßen.NRW übergebenen Daten entstanden, lässt sich aber auch als Spezialfall der in [5] beschriebenen Netzstruktur interpretieren. Als Einstieg betrachte man Bilder 1 bis 4, die mithilfe der Online - Auskunft der Straßeninformationsdatenbank Nordrhein-Westfalen [1] entstanden sind.

Bild 1:Straßen im Bereich Duisburg

Bild 2: Autobahnen im Bereich Duisburg

Bild 3: Netzknoten

Bild 4: Autobahnnetz als Graph

Bild 1 zeigt einen Ausschnitt des von Straßen.NRW betreuten Straßennetzes im Raum Duisburg. Dazu gehören neben Autobahnen (in rot dargestellt) auch Bundesstraßen (nicht im Ausschnitt zu sehen), Landstraßen (grün) und Kreisstraßen (braun). Da in dieser Arbeit der Fokus ausschließlich auf Autobahnen liegt, werden zunächst alle anderen Straßentypen aus der Darstellung entfernt (Bild 2). Ebenso bleiben Autobahnauf- und -abfahrten, sowie Straßen, die dem Wechsel zwischen zwei verschiedenen Autobahnen dienen, unberücksichtigt. Dies macht es möglich, das Bild weiter zu vereinfachen, indem alle Anschlussstellen und Autobahnkreuze durch einen Punkt ersetzt und die zugehörigen Straßen entfernt werden. Bild 3 zeigt die entsprechende Darstellung. Die eingefügten Punkte repräsentieren Stellen, an denen ein Auf- bzw. Abfahren oder ein Wechsel der Autobahn möglich ist. Sie heißen Netzknoten. Die Straßenabschnitte zwischen zwei Netzknoten werden als Autobahnabschnitt bezeichnet. Interpretiert man nun Netzknoten als Knoten eines Graphen und Autobahnabschnitte als Kanten, ergibt sich bereits eine erste einfache Darstellung des Autobahnnetzes als Graph (siehe Bild 4). Weil diese simple Darstellung nicht ausreicht, um auf ihr die Planung von Baustellen be- schreiben zu können, müssen die Autobahnabschnitte weiter unterteilt werden.

Die kleinste in dieser Arbeit relevante Straßeneinheit stellt der so genannte Messabschnitt dar. Wir verweisen dazu auf Bild 5. Bei einem Messabschnitt handelt es sich um einen Teil einer Fahrspur, der in der Regel 100 m lang ist. Die Stellen, an denen ein Messabschnitt beginnt bzw. endet, heißen Stationspunkte. Sollte eine Fahrspur nicht komplett von Netzknoten zu Netzknoten verlaufen, z.B. weil eine Fahrspur zwischen zwei Netzknoten beginnt, so ergänzen wir den Graphen mit Hilfsmessabschnitten.

Bild 5: Autobahnabschnitt als gerichteter Graph

Da die Einteilung in Messabschnitte für die Planung von Baustellen zu fein ist, werden Messabschnitte, die aufgrund eines ähnlichen Zustandes der gleichen Sanierungsmaßnahme unterzogen werden können, zu homogenen Abschnitten zusammengefasst (siehe Bild 6). Für den in Bild 1 bis 4 betrachteten Ausschnitt ist in Bild 7 das Autobahnnetz als gerichteter Graph mit homogenen Abschnitten als Kanten zu sehen.

2.2 Formulierung des Problems als ganzzahliges lineares Programm

Als Ansatz zur Lösung des Baustellenproblems wird eine Formulierung als ganzzahliges lineares Programm vorgestellt. Da für jeden homogenen Abschnitt entschieden werden muss, in welchem Jahr die vorgesehene Maßnahme durchgeführt wird, werden Binärvariablen eingeführt. Diese modellieren, ob der homogene Abschnitt h im Zeitabschnitt t bearbeitet wird oder nicht. Mithilfe dieser und einiger weiterer Variablen lassen sich die Nebenbedingungen des Problems durch eine Reihe von linearen Ungleichungen formulieren, die wir im Folgenden darstellen.

Bild 6: Beispielhafter Übergang von Messabschnitten zu homogenen Abschnitten; die Farbe repräsentiert den Zustand der Abschnitte (Abbildung nach [4])

Bild 7: Autobahnnetz als gerichteter Graph im Bereich Duisburg (Hilfsmessabschnitte und inzidierende Netzknotenkanten sind nicht dargestellt)

2.2.1 Nebenbedingungen

Zunächst muss jeder homogene Abschnitt, auf dem eine Maßnahme geplant ist, in einem der zu planenden Jahre bearbeitet werden. Das kann durch eine Nebenbedingung für jeden solcher homogenen Abschnitt gewährleistet werden. Diese hat die folgende Form:

Formel siehe PDF.

Um sicherzustellen, dass in jedem Zeitabschnitt pro Autobahn eine Spur in jeder Fahrtrichtung befahrbar bleibt, muss für jede Menge B von benachbarten homogenen Abschnitten, die bei gleichzeitiger Bearbeitung die Autobahn komplett blockieren würde (siehe zum Beispiel Bild 8) und für jedes Jahr t eine Ungleichungen der Form gelten.

Formel (1) siehe PDF.

Es reicht es aus, diese Ungleichungen nur für Mengen B aufzustellen, für die das Entfernen eines beliebigen homogenen Abschnittes dazu führen würde, dass die Autobahn nicht mehr blockiert wird. Alle übrigen Ungleichungen der Form sind dann implizit erfüllt. Beispielsweise könnte bei den blau eingefärbten homogenen Abschnitten in Bild 8 der homogene Abschnitt auf dem mittleren Fahrstreifen des linken Abschnittes entfernt werden, ohne dass die Autobahn bei gleichzeitiger Bearbeitung der anderen blauen Abschnitte befahrbar wäre.

Bild 8: Homogene Abschnitte in einer Fahrtrichtung; die Menge B der blauen Abschnitte blockiert eine Fahrtrichtung

Falls der Gegenverkehr über den in die Gegenrichtung verlaufenden Fahrbahnabschnitt des entsprechenden Autobahnabschnittes umgeleitet werden kann, ist es in der operativen Planung möglich, komplette Fahbahnabschnitte zu sperren. Dies kann durch ähnliche Ungleichungen wie in (1) umgesetzt werden. Gemäß der Vorgaben von Straßen.NRW wurde in dieser Arbeit auf die Erweiterung verzichtet.

Sehr ähnliche Ungleichungen ergeben sich, wenn Baustellen eine maximale Länge nicht überschreiten dürfen. Jede Menge von homogenen Abschnitten L, die bei gleichzeitiger Bearbeitung eine Baustelle ergeben würden, welche die Längenschranke überschreitet, definiert für jedes Jahr t eine Nebenbedingung der Form

Formel siehe PDF.

Auch hier sind wieder alle Mengen von Abschnitten L redundant, die so verkleinert werden können, dass die resultierende Menge die Längenschranke immer noch verletzt.

Weiterhin soll verhindert werden, dass sehr kurze Abschnitte eines Fahrstreifens getrennt von vorhergehenden oder nachfolgenden homogenen Abschnitten bearbeitet werden. Dazu führen wir für jeden homogenen Abschnitt h, der kürzer als eine Mindestlänge ist, Nebenbedingungen ein, die sicherstellen, dass ein ausreichend langes, h umfassendes Stück des Fahrstreifens geplant wird. Je nach Wahl von können dazu mehrere homogene Abschnitte notwendig sein. Es ergeben sich also verschiedene Mengen homogener Abschnitte, deren Gesamtlänge überschreitet und die h enthalten. Es sei die Menge solcher Mengen.

Es muss nun sichergestellt werden, dass alle homogenen Abschnitte aus mindestens einer der Mengen in im selben Zeitabschnitt bearbeitet werden. Dazu wird zu jeder Menge I aus und jedem Jahr t eine zusätzliche binäre Variable eingeführt, die angibt, ob alle homogenen Abschnitte in I im Jahr t stattfinden oder nicht. Damit ergibt sich für jeden homogenen Abschnitt, der nicht schon für sich genommen länger ist als, folgender Block von Ungleichungen:

Formel siehe PDF.

Da für die Erweiterung von h nur homogene Abschnitte des gleichen Fahrstreifens betrachtet werden, bleibt die Anzahl der Mengen in und damit die Anzahl der zusätzlich eingeführten Variablen klein.

Die bis hierhin formulierten Bedingungen beschreiben die Zulässigkeit einer Baustellenplanung innerhalb einer Autobahn, d.h. insbesondere beziehen sich die in einer Ungleichung auftretende Variablen immer auf dieselbe Autobahn. Für die nun folgenden Ungleichungen ist dies nicht mehr der Fall.

Zunächst sollen die jährlichen Kosten für Maßnahmen in NRW insgesamt beschränkt werden. Erzeugt die Durchführung der vorgesehenen Maßnahme auf einem homogenen Abschnitt h Kosten von und steht pro Jahr ein Budget von zur Verfügung, ergeben sich für die Limitierung der Kosten pro Jahr folgende Nebenbedingungen.

Formel siehe PDF.

Weiterhin ist die Durchführbarkeit eines Sanierungsplans davon abhängig, dass die von den Sanierungsmaßnahmen ausgehende Belastung die Maximalbelastung einzelner Autobahnmeistereien nicht überschreitet. Beschreibt a(h) die Belastung, die die Durchführung der vorgesehenen Maßnahme auf einem homogenen Abschnitt h auslöst und ist die Maximalbelastung der Autobahnmeisterei, die für die homogenen Abschnitte in zuständig ist, so lässt sich die obige Anforderung durch je eine Nebenbedingung für jede Meisterei und jedes Jahr t der Form umsetzen.

Formel siehe PDF.

Die betrachteten Nebenbedingungen stellen sicher, dass ein generierter Sanierungsplan die Vorgaben von Straßen.NRW erfüllt.

2.2.2 Quantifizierung der Lösungsqualität

Eine geeignete Zielfunktion erlaubt uns, die Qualität des Sanierungsplans zu beeinflussen und so z.B. die Homogenität von Baustellen zu verbessern: Die Idee ist, homogene Abschnitte zu zusammenhängenden Baustellen zusammenzufassen, für die eine gemeinsame Bearbeitung wünschenswert ist. In diesem Fall soll die Zielfunktion unseres linearen Programms einen Bonus vergeben. Zusätzlich kann die Verteilung von Boni daran geknüpft sein, dass weitere homogene Abschnitte nicht im gleichen Jahr bearbeitet werden wie der Rest, z. B. können Baustellen, die an Netzknoten beginnen und enden, erstrebenswert sein. Soll die Zusammenfassung ähnlicher Maßnahmen zu gemeinsamen Baustellen präferiert werden, kann die durchzuführende Maßnahmenart die Größe des Bonus beeinflussen. Da dTIMS den wirtschaftlich optimalen Eingriffszeitpunkt für die Durchführung einer Maßnahme berechnet, kann es sinnvoll sein, das Zusammenfassen zweier homogener Abschnitte zu einer Baustelle niedriger zu bewerten, je stärker sich die optimalen Eingriffszeitpunkte unterscheiden.

Um diese Konzepte zu formalisieren, führen wir die Begriffe Bonusmenge, Bonusfunktion und Bonussystem ein. Eine Bonusmenge ist ein Paar von disjunkten Mengen homogener Abschnitte auf denen Maßnahmen geplant sind. Dabei wird als Positivmenge und als Negativmenge bezeichnet. Ist eine Menge von Bonusmengen, so bezeichnen wir als Bonusfunktion und als Bonussystem. Der durch vorgegebene Bonus wird genau dann erteilt, wenn alle homogenen Abschnitte aus im Jahr t bearbeitet werden und alle homogenen Abschnitte aus nicht im Jahr t bearbeitet werden.

Für die Umsetzung dieser Art von Bonus in der Zielfunktion des ganzzahligen linearen Programms wird für jede Bonusmenge und jedes Jahr t eine zusätzliche Binärvariable eingeführt, die angibt, ob die Belegung der x-Variablen die Vergabe des für Z im Jahr t vorgesehenen Bonus auslöst. Die Kopplung der a- und x -Variablen für alle homogenen Abschnitte in wird dann durch die Ungleichungen formuliert. Analog ergeben sich für alle homogenen Abschnitte in die Ungleichungen

Formel siehe PDF.

Für ein Bonussystem stellt sich die Zielfunktion des ganzzahligen linearen Programms wie folgt dar

Formel siehe PDF.

Vor allem die fehlende Spezifizierung des Bonussystems macht die Zielfunktion in dieser allgemeinen Form schwer greifbar. Im folgenden Abschnitt werden deshalb mehrere konkrete Bonussysteme eingeführt, welche die speziellen Anforderungen von Straßen.NRW realisieren.

2.2.3 Konkretisierung von Bonussystemen

Maximierung der Übereinstimmung mit dTIMS

Als erster Schritt zu einer sinnvollen Baustellenplanung wird die Maximierung der Übereinstimmung mit der von dTIMS vorgeschlagenen Lösung betrachtet. Dazu soll ein Bonus von 1 für jeden homogenen Abschnitt gewährt werden, auf dem eine Maßnahme im gleichen Jahr wie in der dTIMS-Lösung vorgesehen ist. Auf diese Weise wird mit einer minimalen Anzahl an Änderungen ein Sanierungsplan erzeugt, der den formulierten Nebenbedingungen genügt. Ein Bonussystem, welches diese Zielfunktion repräsentiert, ergibt sich, indem man für jeden homogenen Abschnitt, auf dem eine Maßnahme geplant ist, eine Bonusmenge der Form als Bonusfunktion verwendet. Hierbei entspricht th dem Jahr, in dem der homogene Abschnitt h in der dTIMS-Lösung durchgeführt wird. Klar ist, dass der insgesamt erzielte Bonus einer optimierten Lösung mit diesem Bonussystem nicht besser sein kann, als der erzielte Bonus der dTIMS-Lösung. Dabei kann Gleichheit nur dann erreicht werden, falls die dTIMS-Lösung bereits alle Restriktionen erfüllt. Ansonsten ist der Bonuswert der optimierten Lösung geringer als der Bonuswert der dTIMS-Lösung.

Formel siehe PDF.

Zwar führt die Verwendung dieses Bonussystems zu einer zulässigen Baustellenverteilung, eine verbesserte Zusammenfassung der homogenen Abschnitte zu Baustellen wird dadurch aber nicht erreicht. Zu diesem Zweck werden im Folgenden Paare von homogenen Abschnitten betrachtet.

Zusammenfassung von Paaren homogener Abschnitte

Bei der Zusammenfassung homogener Abschnitte wird bewertet, wie groß die „Motivation“ von Paaren benachbarter homogener Abschnitte ist, als eine gemeinsame Baustelle aufgefasst zu werden. Dabei werden homogene Abschnitte als benachbart bezeichnet, falls ein Fahrzeug von einem der beiden homogenen Abschnitte auf den anderen wechseln kann, ohne dabei einen weiteren homogenen Abschnitt überqueren zu müssen. In Bild 9 sind für die beiden Autobahnabschnitte aus Bild 8 benachbarte Paare homogener Abschnitte jeweils durch eine Kante verbunden. Hier wird also genau dann ein Bonus vergeben, falls ein Paar von homogenen Abschnitten durch eine Kante verbunden ist und im selben Jahr bearbeitet wird, also mit der gleichen Farbe hinterlegt wurde. Die Bonusmengen, die solche Paare homogener Abschnitte belohnen, werden durch definiert.

Formel siehe PDF.

Alle weiteren Bonussysteme dieses Abschnitts verwenden die Bonusmengen aus.

Als erstes einfaches Modell dieser Art soll der Bonus unabhängig von weiteren Einflussfaktoren für jedes benachbarte Paar von homogenen Abschnitten, auf denen eine Maßnahme geplant ist, 1 betragen, d.h. b ≡ 1. Das zugehörige Bonussystem bezeichnen wir als.

Die erste Verbesserung, die nun vorgenommen wird, besteht darin, dass der Bonus auch von den Maßnahmen abhängig ist, die auf den jeweiligen homogenen Abschnitten durchgeführt werden sollen. Dabei ist der Bonus umso größer, je ähnlicher sich die durchzuführenden Maßnahmen auf den beiden Abschnitten sind. Straßen.NRW hat dazu auf einer Skala von 0 bis 1 für jedes Paar von verschiedenen Maßnahmen bewertet, wie ähnlich sich die jeweiligen Maßnahmen sind und wie zielführend eine Zusammenlegung der entsprechenden homogenen Abschnitte ist. Diese Bewertung wird durch die Funktion motivation repräsentiert. Als entsprechendes Bonussystem erhält man.

Formel siehe PDF.

Eine letzte betrachtete Verfeinerung dieser Art von Bonussystemen ist eine Variante, die zusätzlich zur Maßnahme den Abstand zwischen dem Jahr der Durchführung t und den Jahren der Durchführung der beiden homogenen Abschnitte in der dTIMS-Planung und miteinbezieht. Dieser Abstand wird in einen Dämpfungsfaktor umgerechnet. Der hier betrachtete Dämpfungsfaktor ist durch definiert (vgl. Bild 10). Diese Idee wird durch mit und umgesetzt.

Formel siehe PDF.

Bild 10: Plot des Dämpfungsfaktors für th1 = 4,th1 = 7und einen Planungshorizont von10 Jahren

Maximierung von Netzknoten-zu-Netzknoten Baustellen

In den bisherigen Bonussystemen war die Vergabe des Bonus nur an die gleichzeitige Bearbeitung bestimmter homogener Abschnitte geknüpft, nicht aber daran, dass bestimmte andere Abschnitte nicht im gleichen Jahr bearbeitet werden. Es sollen nun solche Baustellen belohnt werden, die jeweils genau an einem Netzknoten beginnen und enden, sowie zusätzlich einen kompletten Fahrstreifen zwischen diesen beiden Netzknoten beinhalten.

Wir definieren deshalb Bonusmengen für jede zusammenhängende Menge von homogenen Abschnitten eines Fahrstreifens, die an einem Netzknoten beginnt und endet.
Für die Positivmenge gilt dann jeweils. Die Negativmengen müssen jetzt so definiert werden, dass H auch tatsächlich an den betrachteten Netzknoten beginnt bzw. endet, also nicht über einen der Netzknoten hinaus erweitert werden kann. Als Negativmenge muss deshalb die Menge aller homogenen Abschnitte gewählt werden, die an ein Element von H angrenzen, so dass sie die Baustelle auf einen weiteren Autobahnabschnitt verlängern würden. Wir bezeichnen diese Menge als Nachbarschaft von H und notieren sie mit N (H). Zur Veranschaulichung ist in Bild 11 eine solche Baustelle abgebildet. Dabei ist die Menge H blau und die Nachbarschaft N (H) rot hinterlegt.

Wir definieren als die Menge aller solcher Bonusmengen. Dann erhalten wir ein Bonussystem, das Baustellen, die auf einem Fahrstreifen von Netzknoten zu Netzknoten führen, mit einem Bonus von 1 belohnt, indem wir wählen.

Da dieses Bonussystem für sich genommen keine zufriedenstellenden Ergebnisse liefert, haben wir als letztes Bonussystem eine Kombination aus und gewählt, in der wir Paare von homogenen Abschnitten gemäß und zusätzlich Netzknoten-zu-Netzknoten Baustellen mit einem Bonus von 1,5 belohnen. Das kombinierte Bonussystem bezeichnen wir mit.
Auf diese Weise lassen sich auch andere Bonussysteme mit verschiedenen Gewichtungen kombinieren.

3 Studie

Für die Durchführung einer Fallstudie stand ein Datensatz von Straßen.NRW aus dem Jahr 2015 zur Verfügung, der die Ergebnisse der dTIMS-Planung mit einem Planungshorizont von 10 Jahren für das gesamte Autobahnnetz in NRW enthielt. Insgesamt werden 8364 homogene Abschnitte betrachtet, von denen auf 5754 eine Maßnahme durchgeführt werden soll.

Die Erstellung der ganzzahligen linearen Programme aus den gegebenen Daten erfolgt durch ein C + + Programm. Dieses liest in einem ersten Schritt die Daten ein und konstruiert daraus einen Graphen wie in Abschnitt 2 beschrieben. Auf Grundlage dessen wird automatisiert mithilfe der „ILOG Concert Technology“[2] das ganzzahlige lineare Programm erstellt. Abhängig vom konkreten Bonussystem werden auf diese Weise zwischen 419.000 und 510.000 Ungleichungen und 173.000 bis 189.000 Variablen erzeugt. Dabei werden zwei Ansätze zur Lösung verfolgt:

1. Die exakte Lösung der entstehenden ganzzahligen linearen Programme.

2. Die folgende Heuristik: Auf Teilautobahnen werden zunächst Zusammenfassungen von Sanierungsmaßnahmen vorgenommen, die anschließend auf die Jahre des Planungshorizontes verteilt werden.

Für beide Ansätze werden die „IBM ILOG CPLEX Optimizers 12.4“ [2] verwendet. Alle Rechnungen in diesem Kapitel wurden mit einem Zeitlimit von 24 Stunden (= 86.400 Sekunden) und einem Speicherplatzlimit von 100 GB auf einem Rechner mit Intel Core i7-3770 Prozessor (vier Kerne und acht Threads) mit 3,40 GHz und einem Arbeitsspeicher von 32 GB durchgeführt.

Wir untersuchen, wie sich die fünf unterschiedlichen Bonussysteme auf die Lösbarkeit der linearen Programme und die Qualität der gefundenen Lösungen auswirken. In Bild 12 werden die Zielfunktionswerte der dTIMS-Lösung bei Verwendung der verschiedenen Bonussysteme mit den besten gefundenen Lösungen der Heuristik und des ganzzahligen linearen Programms (ILP) verglichen. Außerdem werden die Laufzeit, das Abbruchkriterium, der Gap zur LP Schranke beim Abbruch des Verfahrens und die prozentuale Verbesserung dargestellt. Obwohl das ganzzahlige lineare Programm, in der Formulierung aus Abschnitt 2, nicht innerhalb unseres Zeit- bzw. Speicherlimits gelöst werden kann, übertreffen die gefundenen Lösungen die Qualität des dTIMS-Vorschlags deutlich, gemessen am Zielfunktionswert je nach Bonussystem um 32 − 66%. Die einzige Ausnahme bildet das Bonussystem bei dem aufgrund seiner Definition bereits klar ist, dass der Wert der dTIMS-Lösung nicht übertroffen werden kann.

Bild 12: Ergebnisse der Rechenstudie

Die prozentuale Verbesserung im Vergleich zur dTIMS-Lösung fällt bei der Heuristik immer etwa 5% schlechter aus als die der exakten Lösung. Es sei zusätzlich erwähnt, dass neben einem deutlich gesteigerten Zielfunktionswert, die in dieser Arbeit gefundenen Lösungen alle Restriktionen aus Kapitel 2 erfüllen. Das ist bei der dTIMS-Lösung nicht der Fall.

Exemplarisch stellen wir im Folgenden die Ergebnisse des Bonussystems genauer dar. Der Lösungs- bzw. Bonuswert des dTIMS-Vorschlags liegt bei 5.436 Punkten. Das heuristische Verfahren terminiert nach 321 Sekunden. Die gefundene Lösung hat einen Wert von 7.185, 94 Punkten. Hier ergibt sich eine Verbesserung der dTIMS-Lösung um 32, 19%. Erst nach 6.552 Sekunden findet das exakte Verfahren eine bessere Lösung und nach ca. 74.000 Sekunden überschreitet es das Speicherlimit von 100 Gigabyte. Die beste gefundene Lösung liegt am Ende der Berechnung bei etwa 7.441, 14 Punkten (Die Lücke zur LP-Schranke beträgt in diesem Fall nur gut 5, 06%). Der Lösungswert der dTIMS-Lösung wird um 36, 89% übertroffen. Um auch visuell den homogenisierenden Effekt der Optimierung zu beobachten und die erwarteten Auswirkungen der verschiedenen Bonussysteme zu bestätigen, werden im Folgenden drei Plots verschiedener Lösungen miteinander verglichen. Lösungen werden dabei so dargestellt, dass homogene Abschnitte mit einer Farbe hinterlegt werden, die das Bearbeitungsjahr wiedergibt. Um auch die Verschiebung der Bearbeitungsjahre erkennbar zu machen, richtet sich die Farbgebung dabei nach Bild 13, so dass Bearbeitungszeiträume, die nahe beieinander liegen, durch eine ähnliche Farbe repräsentiert werden. Homogene Abschnitte, auf denen keine Maßnahme vorgesehen ist, werden grau hinterlegt. In Bild 14 werden nun die dTIMS-Lösung, die gefundene Lösung des exakten Verfahrens mit dem Bonussystem und die Lösung des exakten Verfahrens mit dem Bonussystem verglichen.

Bild 13: Farbgebung der Kanten

Bild 14: Ausschnitte aus der dTIMS-Lösung (oben), der gefundenen Lösung des exakten Verfahrens mit dem Bonussystem (Ze, be) (mittig) und der Lösung des exakten Verfahrens mit dem Bonussystem (ZdTIMS, bdTIMS) (unten)

Vergleicht man zunächst die dTIMS-Lösung mit der Lösung unter Verwendung des Bonussystems ist eine stark gesteigerte Homogenität zu beobachten. Viele der benachbarten homogenen Abschnitte sind zu gemeinsamen Baustellen zusammengefasst worden. Allerdings fällt auf, dass die Bearbeitungszeitpunkte teilweise deutlich von der ursprünglichen Planung abweichen. So werden beispielsweise in der dTIMS-Lösung viele homogene Abschnitte zwischen „DU-Homberg“ und „Kreuz Duisburg“ eher spät bearbeitet (rote Farbgebung). Nach der Optimierung werden alle diese Abschnitte in einem der ersten beiden Jahre bearbeitet (blaue Farbgebung).

Auch in der Darstellung der Lösung unter Verwendung des Bonussystems fällt eine gesteigerte Homogenität auf. Während einige Teile komplett im gleichen Jahr behandelt werden können, wie die in 2015 (dunkelblau) geplanten homogenen Abschnitte zwischen „Kreuz DU-Nord“ und „Kreuz Oberhausen-West“, werden Mengen von homogenen Abschnitten, die in der dTIMS-Lösung zwar nicht im gleichen Jahr aber in nahe beieinander liegenden Jahren bearbeitet werden, ebenfalls zusammengefasst. Dies ist etwa bei den homogenen Abschnitten zwischen „Kreuz DU-Nord“ und „DU-Beek (134)“ zu beobachten.

Abschließend vergleichen wir in Bild 15 nun die dTIMS-Lösung und die Lösung des exakten Verfahrens mit den Bonussystemen, um den Einfluss der Belohnung von Netzknoten-zu-Netzknoten Baustellen aufzeigen zu können.

Bild 15: Ausschnitt aus der dTIMS-Lösung (links), der exakten Lösung mit Bonussystem (ZdTIMS, bdTIMS) (mittig) und der exakten Lösung mit Bonussystem (ZdTIMS, bdTIMS)
+1, 5 (Zn,bn) (rechts)

Beide nachbearbeiteten Lösungen zeigen eine Homogenisierung gegenüber der dTIMS-Lösung. Im Vergleich dieser Lösungen untereinander ist in der rechten Abbildung der Einfluss der Belohnung von Baustellen, die an Netzknoten anfangen und enden, deutlich zu erkennen. Während in der mittleren Lösung noch keiner dieser Boni verteilt wird, da alle Baustellen entweder zu kurz sind oder auf anschließenden Fahrbahnabschnitten fortgesetzt werden, sind es im gezeigten Ausschnitt in der rechten Lösung vier (zwischen „Moers-Kapellen“ und „Krefeld-Gartenstadt“ (dunkelblau), zwischen „Krefeld-Gartenstadt“ und „Krefeld-Zentrum“ (hellgrün und mittelgrün) und zwischen „Krefeld-Zentrum“ und „Krefeld-Oppum“ (orange)).

Andererseits fällt auf, dass diese zusätzlichen Bonuspunkte teilweise auf Kosten der Berücksichtigung der Bearbeitungszeitpunkte in der dTIMS-Lösung erzielt werden. Beispielsweise ist die oben genannte Baustelle zwischen „Moers-Kapellen“ und „Krefeld-Gartenstadt“ in der Lösung rechts im Jahr 2015 vorgesehen, was eine deutliche Abweichung von der dTIMS-Lösung darstellt. In der mittig dargestellten Lösung gelingt dies besser.

4 Fazit

Mithilfe von Straßendaten, die Strassen.NRW bereitgestellt hat, und Geoinformationen aus der OpenStreetMap-Datenbank [3] ist das Autobahnnetz in NRW in ein Standard-Graph-Format übertragen worden. Sowohl die Baumaßnahmen, die dTIMS generiert hat, als auch selbst generierte Lösungen können mithilfe der entwickelten Software visualisiert werden. Als Nächstes haben wir die Durchführbarkeit und die Quantifizierung der Qualität eines Sanierungsplan mathematisch modelliert, um die Nachbearbeitung der Ergebnisse von dTIMS zu automatisieren. Der Fokus liegt dabei auf einer möglichst geschickten Zusammenfassung der von dTIMS vorgeschlagenen Erhaltungsmaßnahmen unter verschiedenen Aspekten:

- Belohnung von Zusammenfassungen ähnlicher und benachbarter Sanierungsmaßnahmen,

- Minimierung der Abweichung zur dTIMS Lösung,

- Belohnung von zusammengefassten Baustellen von Netzknoten zu Netzknoten.

Diese Aspekte wurden als mögliche Zielfunktionen eines ganzzahligen linearen Optimierungsproblems verwendet, welches Nebenbedingungen berücksichtigt, die dTIMS nicht oder nur teilweise beachtet:

- Kapazitätsgrenzen für einzelne Gebiete in NRW,

- homogene Verteilung der Baumaßnahmen pro Jahr in NRW,

- Mindest- und Maximallängen von Baustellen einhalten und realistische Baustellenlängen vorschlagen,

- mindestens eine freie Spur pro Fahrtrichtung.

Es sind weitere Zielfunktionen denkbar, die beispielsweise nur dann einen Bonus vergeben, wenn das Planungsjahr sich um nicht mehr als drei Jahre von dem Planungsjahr der dTIMS-Lösung unterscheidet. Aufgrund der allgemeinen Verwendbarkeit und Flexibilität des Bonussystemkonzepts ist eine solche Anpassung problemlos möglich.
Ebenso ist auch die Ergänzung weiterer Nebenbedingungen denkbar. Etwa könnte eine Begrenzung des Baustellenaufkommens in besonders verkehrsstarken Regionen durch Nebenbedingungen, ähnlich zu denen zur Beschränkung des Aufwandes für Autobahnmeistereien, realisiert werden.

Das entstehende lineare Programm muss, aufgrund der Problemgröße für NRW (ca. 450.000 Ungleichungen und 180.000 Variablen), automatisiert generiert werden. Die CPLEX Rechnerstudie mit den Originaldaten von Strassen.NRW zeigt, dass die Qualität des dTIMS Vorschlages, sowohl mit einem exakten als auch einem heuristischen Optimierungsverfahren, deutlich verbessert werden kann. Auch Straßen.NRW war mit den Ergebnissen sehr zufrieden und bestätigte unsere positive Beurteilung der homogenisierenden Einflüsse der untersuchten Methoden. Sie haben das Potential als weiterer Baustein für die Entscheidungsfindung in der Planung von Erhaltungsmaßnahmen eingesetzt zu werden. Die vorgeschlagenen Szenarien können dabei die Entscheidungsgrundlagen verbessern.

5 Literatur

[1]    Online-Auskunft der Straßeninformationsbank Nordrhein-Westfalen. (Aufgerufen am 09.05.2016). http://www.nwsib-online.nrw.de/.

[2]    CPLEX Optimization Studio Interfaces. (Aufgerufen am 09.05.2016). http://www-01.ibm.com/software/commerce/optimization/interfaces/.

[3]    OpenStreetMap-Datenbank. (Aufgerufen am 09.05.2016). http://www.openstreetmap.org/.

[4]    KRAUSE, G. (2001). TU Dresden. SEP Maerschalk. Vortrag.

[5]    ROSE, M. (2003). Modellbildung und Simulation von Autobahnverkehr. Institut für Bauinformatik der Universität Hannover. Dissertation.