Algorithmic railway capacity allocation in a competitive European railway market [Elektronische Ressource] / von Sebastian Georg Klabes

Klabes

Sujets

• Handel

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2010
• Nombre de lectures: 15
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Algorithmic Railway Capacity Allocation in a
Competitive European Railway Market
Von der Fakult¨at fu¨r Bauingenieurwesen
der Rheinisch-Westf¨alischen Technischen Hochschule Aachen
zur Erlangung des akademischen Grades eines Doktors
der Ingenieurwissenschaften genehmigte Dissertation
vorgelegt von
Sebastian Georg Klabes
Berichter: Universit¨atsprofessor Dr.-Ing. Ekkehard Wendler
Universit¨atsprofessor Dr.rer.nat. Berthold Vo¨cking
Tag der mu¨ndlichen Pru¨fung: 14. Januar 2010
Diese Dissertation ist auf den Internetseiten
der Hochschulbibliothek online verfu¨gbar.Abstract
The induced liberalisation process within the European railway system severely affects
the railway infrastructure capacity allocation procedure. In the past a single and often
governmental owned integrated railway company planned, built and operated a national
railway system. The liberalisation process led to a segregation of the integrated rail-
way companies into railway infrastructure manager and railway undertaking in many
European Countries.
The open access paradigm for railway infrastructure capacity that grants any licensed
railway undertaking access to the railway infrastructure capacity induces competition
between different railway undertakings trying to acquire railway infrastructure capacity.
Recent figures indicate that more railway undertakings emerge and do request railway
infrastructure capacity. Their increasing share of uncoordinated request for railway in-
frastructure capacity increases the complexity of the coordination phase of the railway
infrastructure capacity allocation process. In this phase the railway infrastructure man-
ager needs to adjust train path requests in a way to resolve conflicting requests for
railway infrastructure capacity.
This work introduces an algorithmic framework that shall provide efficient measures
to support the railway capacity allocation process and to analyse different allocation
procedures. Inordertomakealgorithmicapproachesapplicableinthisdomainofrailway
engineering a sophisticated modelling approach for railway infrastructure capacity is
extended in order to account for the objectives of the railway undertakings participating
on the secondary railway market for railway infrastructure capacity.
The objectives for railway capacity allocation are formulated from the point of view of
the railway undertakings submitting train path requests. These objectives account for
the negative effects due to adjustments applied to their train path requests during the
coordination phase of the railway capacity allocation process.
The formalised railway capacity allocation process can be optimised globally, by taking
into account standardised objectives with help of algorithmic approaches introduced in
this work.
However, due to the required confidentiality of information provided by the railway
undertakings to the railway infrastructure manager, a global optimisation, taking into
accounttherealobjectivesofallrailwayundertakingsisnotapplicable. Inordertoallow
for incorporating the real objectives of the railway undertakings a game theoretical
3Abstract
setting is formulated: the railway undertakings are players acting on the secondary
railway market for railway infrastructure capacity. Assuming that these players act
rationally, such a game theoretical setting always leads to a result, where no player can
further improve his situation. Such a solution of the game is a Nash Equilibrium.
Comparing the obtained Nash Equilibria of the game theoretical setting to the optimal
solution obtained by global optimisation techniques gives an indication of the negative
effect of non-cooperative behaviour in such a competitive market for railway capacity
allocation.
Moreover,itwillbeshownhowthealgorithmicframeworkforrailwaycapacityallocation
can be used to determine the degree of congestion of a railway system, based on the
submitted train path requests and standardised objectives.
4Kurzfassung
Die Liberalisierung des Schienenverkehrs in der Europ¨aischen Union hat großen Ein-
fluss auf das Trassenmanagement. Wahrend in der Vergangenheit haufig ein integriertes¨ ¨
Schienenverkehrsunternehmen unter staatlicher Beteiligung das Schienenverkehrssystem
geplant, konstruiert und betrieben hat, fuhrte der Liberalisierungsprozess in vielen eu-¨
rop¨aischen L¨andern zu einer strikten Trennung von Eisenbahninfrastrukturbetreibern
und Eisenbahnverkehrsunternehmen.
Der garantierte, diskriminierungsfreie Zugang zur Fahrwegskapazitat fur jedes berech-¨ ¨
tigte Eisenbahnverkehrsunternehmen fu¨hrt zu einem erho¨hten Wettbewerb zwischen un-
abhangigenEisenbahnverkehrsunternehmen.AktuelleStatistikenzeigen,dassdieAnzahl¨
derEisenbahnverkehrsunternehmenw¨achst.DashatzurFolge,dassimmermehrunkoor-
dinierteTrassenwunschebeidenEisenbahninfrastrukturbetreiberneingehen.Dieserhoht¨ ¨
die Komplexita¨t des Trassenkoordinierungsverfahrens erheblich. Im Rahmen des Koor-
dinierungsverfahrensdesTrassenmanagementsmussendiesichausschließendenTrassen-¨
wu¨nsche koordiniert, d.h. aneinander angepasst werden. Dazu werden die Trassenwu¨n-
sche im Rahmen festgelegter Freiheitsgrade verandert.¨
In dieser Arbeit sollen algorithmische Ans¨atze im Rahmen des Trassenmanagements be-
nutzt werden, um zum einen die Konfliktl¨osung zu optimieren und zum anderen das Ko-
ordinierungsverfahren analysieren zu konnen. Ein etabliertes Modell zur Bemessung des¨
Fahrwegskapazita¨tsverbrauchseinerZugfahrtwirderweitert,umalgorithmischeAns¨atze
zu diesem Zweck zu nutzen und das Koordinierungsverfahren zu formalisieren.
Die Bewertungsfunktionen fu¨r das Trassenmanagement sind spezifisch fu¨r jedes Schie-
nenverkehrsunternehmen formuliert, das Trassenwunsche aufgibt. Diese Bewertungs-¨
funktionenbewertendennegativenEffektvonno¨tigenAnpassungenderTrassenwu¨nsche
im Rahmen des Koordinierungsverfahrens des Trassenmanagements.
DasTrassenmanagementkannaufBasisvonstandardisiertenBewertungsfunktionenmit
Hilfe von algorithmischen Verfahren global optimiert werden. Die dafu¨r notwendigen
Verfahren werden im Rahmen dieser Arbeit vorgestellt.
Aufgrund der Tatsache, dass die Informationen des Eisenbahninfrastrukturbetreibers
uber die Eisenbahnverkehrsunternehmen als vertraulich zu behandeln sind, kann das¨
Trassenmanagementnichtglobaloptimiertwerden,dadieEisenbahnverkehrsunternehm-
en ihre Informationen nicht mit allen anderen Wettbewerbern austauschen. Um es zu
ermo¨glichen, dass die wahren Bewertungsfunktionen Einzug in das Trassenmanagement
5Kurzfassung
erhalten, wird ein spieltheoretischer Ansatz fur das Trassenmanagement formuliert: Die¨
EisenbahnverkehrsunternehmensindSpieleraufdemsekunda¨renSchienenverkehrsmarkt
fur Fahrwegskapazitat. Unter der Annahme, dass sich diese Spieler rational verhalten,¨ ¨
stellt sich ein Gleichgewichtszustand ein. Dieser Gleichgewichtszustand entspricht einer
Losung des Trassenmanagements, bei dem sich kein Spieler im Rahmen seiner Aktionen¨
verbessern kann. Eine solche L¨osung wird als Nash–Gleichgewicht bezeichnet.
Der Vergleich der sich einstellenden Nash–Gleichgewichte des spieltheoretischen Ansat-
zes mit den global optimierten Losungen lasst quantitative Ruckschlusse auf den ne-¨ ¨ ¨ ¨
gativen Effekt eines nicht kooperativen Verhaltens im Vergleich zu einem kooperativen
Trassenmanagements zu.
Daru¨ber hinaus wird gezeigt, wie das algorithmische Trassenmanagement benutzt wer-
den kann, um die Auslastung der Eisenbahninfrastruktur trassenwunschabhangig auf¨
Basis von standardisierten Bewertungsfunktionen zu bestimmen.
6Contents
Table of Contents 7
Glossary and Variables 10
1 Introduction 21
1.1 Operational Planning of Railway Systems. . . . . . . . . . . . . . . . . . 21
1.2 Motivation for Algorithmic Capacity Allocation . . . . . . . . . . . . . . 22
1.3 Structure of this Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2 Railway Capacity Allocation in Europe 28
2.1 Legal Framework for Capacity Allocation . . . . . . . . . . . . . . . . . . 28
2.1.1 European Directives for Railway Capacity Allocation . . . . . . . 28
2.1.2 Implementation of the European Directives . . . . . . . . . . . . . 31
2.2 Railway Capacity Allocation Procedure . . . . . . . . . . . . . . . . . . . 32
2.2.1 Train Path Request Types . . . . . . . . . . . . . . . . . . . . . . 32
2.2.2 Work-flow of the Annual Railway Capacity Allocation Process . . 33
2.2.3 Objectives for Railway Capacity Allocation . . . . . . . . . . . . . 35
2.2.4 Coordination of Railway Capacity Allocation . . . . . . . . . . . . 36
2.2.5 Planning Time Horizon . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3 Analysis of Railway Capacity Allocation . . . . . . . . . . . . . . . . . . 42
2.3.1 Coordination as Optimisation . . . . . . . . . . . . . . . . . . . . 43
2.3.2 Identifying Congestion . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3.3 Train Timetable Stability . . . . . . . . . . . . . . . . . . . . . . 47
2.3.4 Rescheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.3.5 Congestion Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.4 Related Work . . . . . . . . . . .