Transcript Making good use of railroad tracks

Making Good Use of
Railroad Tracks
Martin Grötschel
joint work with Ralf Borndörfer and Thomas Schlechte
IP@CORE
May 27-29, 2009
Martin Grötschel
 Institut für Mathematik, Technische Universität Berlin (TUB)
 DFG-Forschungszentrum “Mathematik für Schlüsseltechnologien” (MATHEON)
 Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
[email protected]
http://www.zib.de/groetschel
2
Yesterday
 Got up at 4:50 am
 Left home at 5:40 am
 Arrived at Brussels airport at 7:50 am
 Took the train
 And arrived at 10:45 am here.
Martin
Grötschel
3
The invitation
Dear Martin,
We aim to get "distinguished" speakers that give a
50-minute lecture on their current research
(I am sure you have a nice IP application area
that you can survey...).
So it will be a celebration of Laurence in disguise.
There will be a dinner and it will happen there....
Best,
Michele
Martin
Grötschel
Book Presentation on
November 11, 2008
Year of Mathematics
5
Martin
Grötschel
Railway tracks are a valuable and costly
infrastructure - not to be left empty!
6
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
7
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
8
Where do I come from?
 Technische Universität Berlin
 Konrad-Zuse-Zentrum für Informationstechnik
 DFG Research Center MATHEON
Mathematics for key technologies
 What type of problems are we aiming at?
Martin
Grötschel
9
Martin
Grötschel
10
Martin
Grötschel
11
ZIB
Martin
Grötschel
12
Martin
Grötschel
13
MATHEON Application Area B
Logistics, traffic, and telecommunication networks
Scientists in charge:
Martin Grötschel, Rolf Möhring, Martin Skutella
 Networks, such as telephone networks, the internet,
airline, railway, and bus networks are omnipresent and
play a fundamental role for communication and mobility in
our society. We almost take their permanent availability,
reliability, and quality at low cost for granted. However,
traffic jams, ill-designed train schedules, canceled flights,
break-downs of telephone and computing networks, and
slow internet access are reminders that networks are not
automatically good networks.
 In fact, designing and operating communication and
traffic networks are extremely complex tasks …
Martin
Grötschel
14
The project
Trassenbörse: Railway Slot Auctioning
 The project aims at developing new ideas to make better
(or even best) use of railway tracks.
 A basic assumption, always favoured by economists, is
that "markets" lead to an optimal allocation of goods.
 But what are the goods to be allocated in the
"railway market"?
 And if we can define such goods precisely, how can one
introduce trade mechanisms that lead to fair competition?
 In other words, is there a way to (de-)regulate the current
railway system that results in a “better utilization” of the
railway infrastructure?
Martin
Grötschel
15
The project
Trassenbörse: Railway Slot Auctioning
 The collection of question raised calls for a
multidisciplinary approach.
 The project is carried out by a group of economists,
mathematicians, and railway engineers from Berlin and
Hannover, each group bringing in its particular expertise.
Martin
Grötschel
16
Project members
 Kay Mitusch, Andreas Brenck, Andreas
Tanner, Benedikt Peter
Business consulting
Multiple EVUs
Routerequests,
Auctiondesgin
Auktio
 Mathematical optimization:
ZIB
 Ralf Borndörfer, Martin Grötschel,
Thomas Schlechte
 Railway engineering and
timetabling:
SFWGG / TU Berlin
 Jürgen Siegmann, Martin Balser, Elmar
Swarat
IVE / Univ. Hannover, RMCon
Martin
Grötschel
 Thomas Siefer, Andreas Henkel,
Marc Klemenz
Many
Bids
 Gottfried Ilgmann, Klemens Polatschek
current
winner
 Economics:
WIP / TU Berlin:
Track allocation,
Optimization
TS-Opt
Infrastructure,
Drivingdynamics
InfraGen
17
The project
Trassenbörse: Railway Slot Auctioning
 Project funding: Bundesministerium für Bildung und
Forschung, Förderungskennziffer 19M2019
 Duration in three phases:
12/2002 - 4/2010
(with some interrupts, however)
Martin
Grötschel
18
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
19
Railway network as a market place
The railway network manager is obliged by EU and
German law to offer
 as much network capacity as possible to all train
operation companies (TOCs) in a non-discriminating
way.
→ The network is a market place,
but, due to the many technical and administrative
constraints, not a simple one.
 Our goal: We want to help impove the market design!
Martin
Grötschel
20
A market must have goods
 What are the goods of the railway network market?
 The answer is clear: slots
 But what is a slot precisely?
Martin
Grötschel
21
Capacity allocation today

A slot = right to run a train with a specified schedule on
the network infrastructure
Example:
Berlin Hbf
Berlin-Spandau
Hannover Hbf
dep 10:51,
arr 11:03, dep 11:05,
arr 12:28

TOCs order specified slots.

Slot prices are fixed and regulated.

Rules to resolve conflicts:
1. Cooperatively: “Negotiations”, construction of slot alternatives
2. Non-cooperatively: Priorities, sum of regular slot prices, bidding

Martin
Grötschel
Resulting network timetable is “manually optimized”
22
Martin
Grötschel
Capacity allocation today
23
Martin
Grötschel
24
Capacity allocation tomorrow:
our vision

TOCs submit bids for specified slots.

“Base price” is the fixed and regulated price
(necessary to maintain the network infrastructure).

Bids may already include some flexibility
w.r.t. time, stops and route; also with discounts.

Conflict resolution:
1. Cooperatively: Mathematical simultaneous optimization, taking
advantage of flexibility of bids
2. Non-cooperatively: An auction process (rounds of auctions)
 Need to develop optimization tools and auction design
Martin
Grötschel
25
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
26
Difficulties to be considered
 What is a slot precisely?
 How many details can/should be taken into account?
 What about track profiles?
 What about engine characteristics?
 Routing through stations?
 Track scheduling exact with respect to switches?
 Signals?
 Buffer times and various slacks (path allowances)?
 …
 Auctioning process
 Details will be explained later
Martin
Grötschel
27
Difficulties to be considered
 If we have to take all possible technical and administrative
details in the general planning model into account, we can
immediately give up!
 Sensible complexity reduction is necessary.
 Hierarchical planning is the appropriate goal.
 Coarse plans first, then details to be specified,
iteration of the steps, if necessary.
Martin
Grötschel
28
Slot request today
Martin
Grötschel
29
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
30
Reduction of network complexity
 Train stations become
simple nodes (with capacity
data)
 Tracks between stations
become simple directed
lines (no signals, no
particular switches)
One has to verify that these simplifications are
acceptable in practice.
Martin
Grötschel
31
Standardized Train Types and
Standardized Train Dynamics
train
type
velocity
V max
[km/h]
train
length
[m]
security
ICE
250
410
LZB
IC
200
400
LZB
RE
160
225
Signal
RB
120
100
Signal
SB
140
125
Signal
ICG
100
600
Signal
Just like entry „Zugcharakteristik“
in today‘s „Trassenanmeldung“.
Martin
Grötschel
32
Discretization of time,
running and waiting times of trains
 Minimum time unit (interval): 1 minute
(but more detail sometimes necessary)
 Matrix of train types‘ running (and required waiting) times in the
network:
Martin
Grötschel
33
Further simplifications
 Wherever and whenever railway engineers have no
objections
 Data driven model precision:
do not model things precisely for which data are not
available.
Martin
Grötschel
34
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
35
Our sample network (right hand)
Martin
Grötschel
36
Time-value specifications
 Bid flexibility modelled by time-valued specifications
 Examples:
€
€
base price
t_opt
t_min
t_max
Departure time
€
time-dependent
piecewise linear
price function on
a time interval
Martin
Grötschel
t_min
t_opt
t_max
Departure time
Departure time
37
Example for a slot bid
Berlin
Ostbahnhof
depart 9.00
central
Spandau (optional)
core travel time  3:30
Discounts for
 Departure at Ostbahnhof before 9:00
 Arrival at Stuttgart after 14:30
Martin
Grötschel
Frankfurt Hbf Stuttgart
arrive  14:30
38
Martin
Grötschel
Implicit XOR-bids: Choice of path by
optimization procedure

There are many different ways to
get from Hannover to Fulda

If all of them are feasible for the
requested train (i.e., if the TOC
does not care where exactly the
train will run between Hannover
and Fulda), our optimization
procedure will pick one that is
optimal from the network
perspective.
39
Tour bids: Special support for
branching and merging of trains

A tour is a set of slots that are connected by a successor relation →

s1→s2 means that s2 can use rolling stock from s1
s1
s5
s3
s2
Martin
Grötschel
s4
s6
40
Bids
 We have developed a collection of possible bids that a
TOC can submit (more than I can describe here).
 Suppose the TOCs have submitted their bids.
 What does the network operator do?
 Actually, what is the network operator supposed to do?
Martin
Grötschel
 The network operator has to apply the
„Eisenbahninfrastruktur-Benutzungsverordnung Verordnung über den diskriminierungsfreien Zugang zur
Eisenbahninfrastruktur und über die Grundsätze zur
Erhebung von Entgelt für die Benutzung der
Eisenbahninfrastruktur - EIBV“ vom 3. Juni 2005 (BGBl. I
S. 1566), die am 1. August 2005 in Kraft getreten ist.
41
EIBV and conflict resolution
§9 Absatz 5 EIBV, „Höchste Summe der Regelentgelte“:
Let us consider an example
„(5) Bei der Entscheidung zwischen gleichrangigen Verkehren nach Absatz 4
hat der Betreiber der Schienenwege die Entgelte für die streitigen
Zugtrassen gegenüberzustellen und
1.
bei einem Konflikt zwischen zwei Zugtrassen der Zugtrasse den Vorrang
einzuräumen, bei der das höchste Regelentgelt zu erzielen ist,
2.
bei einem Konflikt zwischen mehr als zwei Zugtrassen den Zugtrassen den
Vorrang einzuräumen, bei denen in der Summe das höchste Regelentgelt zu
erzielen ist. (Note: this is a formal definition of fair access!)
…“, see http://bundesrecht.juris.de/eibv_2005/__9.html
Optimization required by law!
This seems to have been ignored by everyone involved!
Martin
Grötschel
42
Example:
Bids displayed in a Time-Way-Diagram
way
500
700
150
100
155
154
800
900
time
Martin
Grötschel
650
500
Regelentgelt
base price
43
applying the EIBV rules:
slots without any conflicts
way
500
700
150
100
155
154
800
900
Zeit
Martin
Grötschel
650
500
44
applying the EIBV rules:
two slots in conflict
Way
500
700
150
100
155
154
800
900
Zeit
Martin
Grötschel
650
500
45
applying the EIBV rules:
lots of conflicts, what now?
way
500
700
133
100
155
154
800
900
time
Martin
Grötschel
657
500
46
Lots of conflicts, what now?
„Bilateral conflict resolution“
way
in mathematical terms: greedy heuristic
500
Greedy-Sum of base prices : 1000
700
100
800
900
time
Martin
Grötschel
500
47
Martin
Grötschel
Lots of conflicts, what now?
Smart planner
48
Lots of conflicts, what now?
Smart planner
way
500
700
smart planner solution
Greedy-Sum of base prices : 1000
Smart-Sum of base prices : 1400
100
Is that optimal, i.e.,
does the planner
satisfy the law?
time
Martin
Grötschel
More traffic,
higher network revenue
800
900
500
49
Martin
Grötschel
Lots of conflicts, what now?
mathematical optimization
50
Lots of conflicts, what now?
mathematical optimization
way
500
700
Greedy-Sum of base prices : 1000
Smart-Sum of base prices : 1400
the provable optimum: 1700
100
800
900
time
Martin
Grötschel
500
51
Lots of conflicts, what now?
mathematical optimization
way
the provable total optimum: 2655
500
700
150
100
155
154
800
900
time
Martin
Grötschel
650
500
52
Example:
track bids with flexibilities
way
500
700
150
100
155
154
800
900
time
Martin
Grötschel
650
500
53
Looking at the major conflicts:
Optimumwith flexibilities
way
sum of base prices: 2200 > 1700
500
even more traffic, more network revenue
700
100
800
900
time
Martin
Grötschel
500
54
Looking at the major conflicts:
Optimum with flexibilities
way
sum of base prices: 2200 > 1700
500
even more traffic, more network revenue
700
100
155
154
800
900
time
Martin
Grötschel
500
obvious case
for further bidding
55
Track Allocation
• Route/Track
Problem
 Route/Track
Martin
Grötschel
56
Track Allocation
Problem
 Route/Track
 Route Bundle/Bid
Martin
Grötschel
57
Track Allocation
Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
Martin
Grötschel
58
Track Allocation
Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
Martin
Grötschel
59
Track Allocation
Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Headway Times
 Station Capacities
Martin
Grötschel
60
Track Allocation
Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Track Allocation
(Timetable)
Martin
Grötschel
61
Track Allocation
Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Track Allocation
(Timetable)
 Track Allocation
Problem (OPTRA)
Martin
Grötschel
…
…
62
Track allocation problem
…
Martin
Grötschel
63
Solution approach:
What methods?
 The current standard is the use of heuristics.
 This is infeasible in our situation!
Namely, suppose the system finds a “good” solution that
rules out one bid that some TOC eagerly wants to run.
And now the TOC finds a solution, including its special
bid, that is overall better than the “good” solution.
The TOC would declare the work of the network operator
cheating.
 A proof of optimality is required!
Martin
Grötschel
64
Mathematical solution approach:
Integer Programming Models
 APP
 Arc-based
 Routes: Multiflow
 Conflicts: Packing
(max. cliques)
 Proposition: The
LP-relaxation of
OPTRA2 can be solved
in polynomial time.
Variables

Arc occupancy
Constraints

Flow conservation

Arc conflicts (maximal cliques)
Objective
Martin
Grötschel

Maximize proceedings
65
IP Models
 PCP
 Path-based routes
 Path-based configs
Variables

Path und config usage
Constraints

Path and config choice

Path-config-coupling (track capacity)
Objective Function
Martin
Grötschel

Maximize proceedings
66
two IP Models solving the track
allocation problem – in priniple
 PCP
 Path-based
 Proposition:
v (PLP(APP))
 = v (PLP(PCP))
Thomas Schlechte
Martin
Grötschel
67
Results
 Test Network
 45
Tracks
 32
Stations
6
Traintypes
 10
Trainsets
 122 Nodes
 659 Arcs
 3-12 Hours
 96
Station Capacities
 612 Headway Times
Martin
Grötschel
68
Results
Szenario
• 324 trains
• max. # trains
Martin
Grötschel
flex/min.
#var.
#constr.
#trains
time/sec.
5
29.112
34.330
164
4,5
6
39.641
54.978
200
26,3
7
52.334
86.238
251
45,7
8
67.000
133.689
278
613,1
9
83.227
206.432
279
779,1
10
101.649
315.011
311
970,0
69
Model Comparison
Scenario:
Status Quo Schedule
285 Trains
APP
Flex.
Martin
Grötschel
*- Runtime maximal 1h
PCP
LP1
IP1*
LP3
IP3*
0
2351692
2080255
2234211
2125213
2
2453476
2092045
2351977
2173288
4
2453476
2092045
2426999
2234398
6
2453476
2174897
2453476
2304735
8
2453476
2282305
2453476
2304735
10
2453476
2390921
2453476
2339652
70
Line Plan Problem „China20“
Thomas
Schlechte
71
Example „China20“
Which track upgrading
project is more
important ?
upgrading tracks
fixed tracks
Thomas
Schlechte
72
Origin Destination Matrix
Estimated Passenger
Demand for all pairs
Thomas
Schlechte
73
Optimize Cost, case (A)
Cost function:
1.000.000 € per line,
100,- € per km
Thomas
Schlechte
74
Optimize Traveltime, case (B)
Thomas
Schlechte
75
Line Plan Decision ?
(A cost)
Thomas
Schlechte
(A)
(B)
number of lines
9
18
cost in Mio. €
238
264
traveltime in Mio. min.
383
349
(B time)
76
Timetabling
periodic Passenger
versus
individual Cargo
TS-OPT
Optimization Model
Train
Requests
Tracks
Stations
Thomas
Schlechte
maximize
track utilization
timetable attractiveness
subject to
safety requirements
time windows
Timetable
77
Timetable for Lineplan (A)
Thomas
Schlechte
78
Timetable for Lineplan (B)
Thomas
Schlechte
79
Saturation with Cargo Trains/Slots
add cargo trains
Beijing/Shanghai
Thomas
Schlechte
80
Timetable Decision ?
(A)
number of train slots
passenger ICE‘s
cargo trains
Thomas
Schlechte
(A)
(B)
452
462
36
18
426
444
(B)
81
Switzerland
 A real case with real data.
 Micro » Macro » Micro test
 Data problems, problems with the definitions,
inconsistencies of simulation software systems, etc.
 But we have very interesting results.
 Unfortunately,…
Martin
Grötschel
82
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
83
Goal
Development of an auction mechanism for track usage (slots):
economic and technical analysis of the various track
allocation rules
development of a mathematical program for optimal time
tabeling
Martin
Grötschel
84
Basic idea of a slot auction
 train operation companies (TOCs) deliver bids for slots
(possibly including various degrees of freedom concerning
willingness to pay, timing, stops, train routes)
 minimum bid = base price
 Auctioneer computes conflict free slot assignment (combination of bids)
that maximizes the network revenue and temporarily allocates them to
the bidders.
 Iteration (rounds of the auction): Bids that have not won can be
repeated or modified and resubmitted.
 Criterion for termination of auction (# of rounds, # of changed bids,..)
 The result of the process is a timetable (possibly combining slots
allocated to various bidders) which then has to be refined for use in
practice.
Martin
Grötschel
85
Goal of the slot allocation auction:
practical rules for an auction mechanism
Components:
Martin
Grötschel

„from coarse to fine“: …

Exact mathematical optimization: …

Consideration of alternatives: …

Economic and technical analysis: …
86
Remarks on the current EIBV
 All relevant rules can be implemented, e.g.:
 Priorities
 „maximale Summe der Regelentgelte“
 Höchstpreisverfahren
 Rechte aus Rahmenverträgen
 The sog. „Koordinierungsprozess“ in EIBV, i.e., the bilateral negotiation
(considering also alternative options) is automatically included in the
approach: no discrimination, optimality,…
Martin
Grötschel
87
Auction design
 Iterative, combinatorial auction similar to Parkes’ ibundle
auction
 Next slide shows procedure
Martin
Grötschel
88
Rail Track Auction
TOCs decide on bids for slots
BEGIN
Bid is
unchanged
Bid is increased by a
minimum increment
yes
All bids
Unchanged?
no
OPTRA
model is solved with
maximum earnings
no
yes
Wish to increase
bid?
yes
no
END
Martin
Grötschel
Bid assigned?
89
There are still lots of economic issues
 Auction rounds
 Sequences of auctions
 Informal coordination between TOCs
 Use-it-or-lose-it rules
 Network proceeds is operational goal
 The „density“ of potential goods
 Bidding strategies
 How to analyse auction design?
Martin
Grötschel
90
Contents
1. Introduction and project outline
2. What is the goal?
3. What are the problems?
4. The model: networks, tracks, trains, time, slots,…
5. Bids
6. The auction process
7. Summary
Martin
Grötschel
91
slot allocation problem:
other literature
Charnes Miller (1956), Szpigel (1973), Jovanovic and Harker (1991),
Cai and Goh (1994), Schrijver and Steenbeck (1994), Carey and Lockwood (1995)
Nachtigall and Voget (1996), Odijk (1996) Higgings, Kozan and Ferreira (1997)
Brannlund, Lindberg, Nou, Nilsson (1998) Lindner (2000), Oliveira & Smith (2000)
Caprara, Fischetti and T. (2002), Peeters (2003)
Kroon and Peeters (2003), Mistry and Kwan (2004)
Barber, Salido, Ingolotti, Abril, Lova, Tormas (2004)
Semet and Schoenauer (2005),
Caprara, Monaci, T. and Guida (2005)
Kroon, Dekker and Vromans (2005),
Vansteenwegen and Van Oudheusden (2006),
Cacchiani, Caprara, T. (2006)
Caprara, Kroon, Monaci, Peeters, T. (2006)
Martin
Grötschel
92
Failed railroad infrastructure planning
Martin
Grötschel
Making Good Use of
Railroad Tracks
Martin Grötschel
Thank you for
your attention
joint work with Ralf Borndörfer and Thomas Schlechte
IP@CORE
May 27-29, 2009
Martin Grötschel
 Institut für Mathematik, Technische Universität Berlin (TUB)
 DFG-Forschungszentrum “Mathematik für Schlüsseltechnologien” (MATHEON)
 Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
[email protected]
http://www.zib.de/groetschel