Network design for railway infrastructure by means of linear programming

Spönemann, Jacob; Vallée, Dirk

doi:4549

Network design for railway infrastructure by means of linear programming = Entwurf von Eisenbahnnetzen unter Zuhilfenahme linearer Programmierung

Spönemann, Jacob (Author)

2013

Verantwortlichkeitsangabevorgelegt von Jacob Christian Spönemann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2013

UmfangXIV, 126 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2013

Genehmigende Fakultät
Fak03

Hauptberichter/Gutachter
Vallée, Dirk (Thesis advisor)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2013-04-29

Online
URN: urn:nbn:de:hbz:82-opus-45494
URL: https://publications.rwth-aachen.de/record/210582/files/4549.pdf

Einrichtungen

Lehrstuhl für Schienenbahnwesen und Verkehrswirtschaft und Verkehrswissenschaftliches Institut (313110)

Inhaltliche Beschreibung (Schlagwörter)
Ganzzahlige Optimierung (Genormte SW) ; Infrastruktur (Genormte SW) ; Eisenbahn (Genormte SW) ; Netzwerk (Genormte SW) ; lineare Optimierung (Genormte SW) ; Ingenieurwissenschaften (frei) ; Netzentwurf (frei) ; Netzvariante (frei) ; strategische Infrastrukturplanung (frei) ; network design (frei) ; mixed integer linear programming (frei) ; railway (frei) ; infrastructure (frei) ; optimization (frei)

Thematische Einordnung (Klassifikation)
DDC: 620
ccs: G.1.6

Kurzfassung
Das Ziel des Entwurfs von Eisenbahnnetzen (NDRI) ist die Bestimmung eines wirtschaftlichen Schienennetzes, das in der Lage ist, eine gegebene Verkehrsnachfrage aufzunehmen. Eine solche Aufgabenstellung tritt zum Beispiel in der strategischen Infrastrukturplanung auf. Eisenbahnnetze werden makroskopisch mittels Graphen modelliert. Knoten in diesen Graphen entsprechen dabei Bahnhöfen, Kanten den Strecken zwischen diesen. Das Verkehrsaufkommen wird durch Verkehrsströme bzw. -flüsse modelliert. Ein solcher Fluss wird als eine Anzahl an nach Verkehrsgattung getrennten Zügen zwischen zwei Knoten, der Quelle und der Senke, definiert. Der Kapazitätsverbrauch der Verkehrsflüsse wird mittels fahrplanunabhängiger Methoden bestimmt. Aus Gründen der Vereinfachung wird für die Knoten eine unbeschränkte Kapazität angenommen. Knoten können in einem über diese Arbeit hinausgehenden Schritt dimensioniert werden. Eine solche Abfolge der Dimensionierungsaufgaben entspricht bei Verwendung analytischer Modelle der gängigen Praxis, da für den Entwurf von Knoten die Dimensionen zugehöriger Zulaufstrecken benötigt werden. Als Dimensionierungsaufgaben im Zuge dieser Arbeit bleiben somit die Bestimmung der Kapazität der Kanten bzw. Strecken sowie die Bestimmung der Topologie des Netzes. NDRI lässt sich als nicht lineares multicommodity flow problem on a complete multi-graph modellieren. Nichtlinearität entsteht durch die capacity constraints der einzelnen Kanten. Zur Linearisierung werden, in Anlehnung an cutting pattern des bekannten cutting stock problem, für jede Kante Kombinationen von Zügen verschiedener Anzahlen und Gattungen berechnet, welche die Kapazität der aktuellen Kante völlig ausschöpfen. Es entsteht das gemischt-ganzzahlige lineare Programm NDRI-MIP. Neben diesem Modell wird noch ein weiteres Optimierungsmodell für NDRI eingeführt. Es basiert auf auf einem worst-case Kapazitätsverbrauch. Ein Netzentwurf, der mittels dieses Modells erstellt wird, stellt eine obere Schranke für die Infrastruktur dar, die benötigt wird, um die gegebenen Verkehrsnachfrage erfüllen zu können. Flüsse werden in beiden Modellen auf Pfaden anstatt auf Kanten definiert. Auf diese Weise kann die Menge der für einen Verkehrsfluss zu Verfügung stehenden Routen im Hinblick auf Praxisrelevanz einfach eingeschränkt werden. Um den Lösungsprozess zu verbessern, werden die Optimierungsmodelle um verschiedene valid inequalities ergänzt. Zur effizienteren Lösung von NDRI-MIP Instanzen wird zudem ein branch-and-price Verfahren vorgestellt.

The network design problem for railway infrastructure NDRI aims to find a network of railway infrastructure which meets given traffic demands at the lowest possible design costs. This problem, for example, comes up in long-term infrastructure planning processes. Railway infrastructure is represented by a network consisting of nodes and arcs. Nodes represent stations, arcs lines connecting the stations. Traffic demand is represented by traffic flows consisting of train counts, source and sink nodes. Stations are assumed to be equipped with unbounded capacity to reduce complexity, so design issues are the network topology and the capacity of lines. Using macroscopic models for infrastructure and operation and a timetable independent model for the capacity consumption of traffic flows, NDRI is modeled as a non-linear multicommodity flow problem on a complete multi-graph. The model is transformed to a mixed integer linear programming problem, called NDRI-MIP, using configurations similar to cutting patterns used in the widely known cutting stock problem. Besides NDRI-MIP, another optimization model based on worst-case timetables is introduced. A network designed by these means provides an upper bound on the infrastructure needed to satisfy the given traffic demand. Both models use path flows instead of arc flows. This provides the opportunity to restrict the sets of routes, which are available to traffic flows, to sets which are reasonable in relation to practice. To improve the performance of the solution process some valid inequalities are presented and a branch-and-price approach for NDRI-MIP is introduced.

Fulltext:
PDF