Transcript lecture slides - Departamento de Matemática

Optimal Rail Track Allocation
Ralf Borndörfer
joint work with
Martin Grötschel
LBW
Thomas Schlechte
X Encuentro de Matemática, Quito, 25. Juli 2006
Ralf Borndörfer
[email protected]
 DFG Research Center MATHEON Mathematics for Key Technologies
 Zuse-Institute Berlin (ZIB)
 Löbel, Borndörfer & Weider GbR (LBW)
http://www.zib.de/borndoerfer
2
Overview
 Rail Track Auctions
 The Optimal Track Allocation Problem (OPTRA)
 Mathematical Models
 Computational Results
LBW
Ralf
Borndörfer
3
Background
 Problems
 Network utilization
 Deficit
 European Union
 Establish a rail traffic market
 Open the market to competition
LBW
 Improve cost recovery of infrastructure provider,
reduce subsidies
 Deregulate/regulate this market
 Project
Ralf
Borndörfer
 WiP (TUB), SFWBB (TUB), I&M, Z, ZIB
4
Auctioning Approach
 Goals
 More traffic at lower cost
 Better service
 How do you measure?
 Possible answer: in terms of willingness to pay
 What is the „commodity“ of this market?
LBW
 Possible answer: timetabled track
= dedicated, timetabled track section
= use of railway infrastructure in time and space
 How does the market work?
 Possible answer: by auctioning timetabled tracks
Ralf
Borndörfer
5
Arguments for Auctions
 Auctions can …
 resolve user conflicts in such a way that the bidder with the
highest willigness to pay receives the commodity (efficient
allocation, wellfare maximization)
 maximize the auctioneer’s earnings
 reveal the bidders’ willigness to pay
 reveal bottlenecks and the added value if they are removed
LBW
 Economists argue …
 that a “working auctioning system” is usually superior to
alternative methods such as bargaining, fixed prices, etc.
Ralf
Borndörfer
6
Examples
 In ancient times …
 Auctions are known since 500 b.c.
 March 28, 193 a.d.: The pretorians auction the Roman Emperor‘s
throne to Marcus Didius Severus Iulianus, who ruled as Iulianus
I. for 66 days
LBW
Ralf
Borndörfer
7
The Story of Didius Iulianus
(http://www.roman-emperors.org/didjul.htm)
LBW
Ralf
Borndörfer
[193 A.D., March 28] When the emperor Pertinax was
killed trying to quell a mutiny, no accepted successor
was at hand. Pertinax's father-in-law and urban
prefect, Flavius Sulpicianus, entered the praetorian camp
and tried to get the troops to proclaim him emperor, but
he met with little enthusiasm. Other soldiers scoured the
city seeking an alternative, but most senators shut
themselves in their homes to wait out the crisis. Didius
Julianus, however, allowed himself to be taken to the
camp, where one of the most notorious events in Roman
history was about to take place. Didius Julianus was
prevented from entering the camp, but he began to
make promises to the soldiers from outside the wall.
Soon the scene became that of an auction, with Flavius
Sulpicianus and Didius Julianus outbidding each other
in the size of their donatives to the troops. The Roman
empire was for sale to the highest bidder. When Flavius
Sulpicianus reached the figure of 20,000 sesterces per
soldier, Didius Julianus upped the bid by a whopping
5,000 sesterces, displaying his outstretched hand to
indicate the amount. The empire was sold, Didius
Julianus was allowed into the camp and proclaimed
emperor.
8
Examples
 In ancient times …
 Auctions are known since 500 b.c.
 March 28, 193 a.d.: The pretorians auction the Roman Emperor‘s
throne to Marcus Didius Severus Iulianus, who ruled as Iulianus
I. for 66 days
 In modern times …
LBW
Ralf
Borndörfer








Traditional auctions (antiques, flowers, stamps, etc.)
Stock market
eBay etc.
Oil drilling rights, energy spot market, etc.
Procurement
Sears, Roebuck & Co.
Frequency auctions in mobile telecommunication
Regional monopolies (franchising) at British Rail
9
Sears, Roebuck & Co.
 3-year contracts for transports on dedicated routes
 First auction in 1994 with 854 contracts
 Combinatorial auction
 „And-“ and „or-“ bids allowed
 2854 (≈10257) theoretically possible combinations
 Sequential auction (5 rounds, 1 month between rounds)
LBW
 Results
 13% cost reduction
 Extension to 1.400 contracts (14% cost reduction)
Ralf
Borndörfer
10
Frequency Auctions
(Cramton 2001, Spectrum Auctions, Handbook of Telecommunications Economics)
LBW
Ralf
Borndörfer

Prices for mobile telecommunication frequencies (2x10 MHz+5MHz)

Low earnings are not per se inefficient

Only min. prices => insufficient cost recovery
11
LBW
Ralf
Borndörfer
12
Track Request Form
LBW
Ralf
Borndörfer
13
Track Construction
LBW
Ralf
Borndörfer
14
Rail Track Auctioning
LBW
Ralf
Borndörfer
15
Rail Track Auction
BEGIN
Minimum Bid = Basic Price
EVUs decide on bids for
bundles of timetabled tracks
Bids is
unchanged
Bids are increased by a
minimum increment
LBW
Bid is assigned
All bids assigned:
END
Ralf
Borndörfer
OPTRA finds
allocation with
maximum earnings
Bid is not assigned
16
Overview
 Rail Track Auctions
 The Optimal Track Allocation Problem (OPTRA)
 Mathematical Models
 Computational Results
LBW
Ralf
Borndörfer
17
Optimal Track Allocation Problem
(OPTRA)
Input
 Set of bids for timetabled tracks
incl. willingness to pay
 Available infrastructure (space and time)
Output
LBW
Ralf
Borndörfer
 Assignment of bids that maximizes the total
willigness to pay
 Conflict free track assignments for the chosen
bids
18
Bids for Timetabled Tracks
 Train number(s) and type(s)
 Starting station, earliest starting time
 Final station, latest arrival time
 Basic bid (in Euro)
LBW
 Intermediate stops
(Station, min. stopping time, arrival interval)
 Connections
 Combinatorial bids
Ralf
Borndörfer
19
Blocks and Standardized Dynamics
State (i,T,t,v)
 Directed block i
 Train type T
 Starting time t, velocity v
LBW
v
i
Ralf
Borndörfer
j
k
s
20
Standard Train Types
train
type
LBW
Ralf
Borndörfer
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
…
21
Infrastructure
LBW
Ralf
Borndörfer
22
Block Conflicts
conflict
t
LBW
conflict
s
Ralf
Borndörfer
23
Variable Bids
Bid =
€
Basic Bid
+ Departure/Arrival Time Bonus
+ Travel Time Bonus
€
90
4 €/min
LBW
80
12:00 12:08 12:20 Dep. time
Ralf
Borndörfer
40
60
Travel
time
[min]
24
Effects
difficult!
3x
A
B
C
+1x
D
I. variant
= ???
II.
III.
LBW
time
Ralf
Borndörfer
ICE goes
ICE slower
ICE drops out
25
Track Allocation Problem
 Route/Track
LBW
Ralf
Borndörfer
26
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
LBW
Ralf
Borndörfer
27
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
LBW
Ralf
Borndörfer
28
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
LBW
Ralf
Borndörfer
29
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Headway Times
 Station Capacities
LBW
Ralf
Borndörfer
30
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Headway Times
 Station Capacities
LBW
Ralf
Borndörfer
 This Talk: Only Block
Occupancy Conflicts
31
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Track Allocation
(Timetable)
LBW
Ralf
Borndörfer
32
Track Allocation Problem
 Route/Track
 Route Bundle/Bid
 Scheduling Graph
 Conflict
 Track Allocation
(Timetable)
LBW
Ralf
Borndörfer
 Optimal Track Allocation
Problem (OPTRA)
…
…
33
Track Allocation Problem
 Route/Track
Proposition [Caprara, Fischetti, Toth (02)]:
 Route Bundle/Bid
OPTRA is NP-hard.
 Scheduling Graph
LBW
 Conflict
Proof:
 Track Allocation
(Timetable)
Reduction from Independent-Set.
 Optimal Track Allocation
Problem (OPTRA)
 Complexity
Ralf
Borndörfer
34
Overview
 Rail Track Auctions
 The Optimal Track Allocation Problem (OPTRA)
 Mathematical Models
 Computational Results
LBW
Ralf
Borndörfer
35
IP Model OPTRA1
 Arc-based
 Routes: Multiflow
 Conflicts: Packing
(pairwise)
LBW
 This talk: Block
occupancy conflicts
only
Variables

Arc occupancy
Constraints

Flow conservation

Arc conflicts (pairwise)
Objective
Ralf
Borndörfer

Maximize proceedings
36
Selected Literature
Brännlund et al. (1998)
 Standardized Driving Dynamics
 States (i,T,t,v)
 Path formulation
v {0, vs t d (i)}
 Computational experiments with 17 stations at the route
Uppsala-Borlänge, 26 trains, 40,000 states
LBW
Caprara, Fischetti & Toth (2002)
 Multi commodity flow model
 Lagrangian relaxation approach
 Computational experiments on low traffic and congested
scenarios
Ralf
Borndörfer
37
IP Model OPTRA1
 Arc-based
 Routes: Multiflow
 Conflicts: Packing
(pairwise)
 Conflict Graph
(Interval Graph)
LBW
 Cliques
 Perfectness
Ralf
Borndörfer
38
IP Model OPTRA2
 Arc-based
 Routes: Multiflow
 Conflicts: Packing
(Max. Cliques)
LBW
 Proposition: The
LP-relaxation of
OPTRA2 can be
solved in
polynomial time.
Variables

Arc occupancy
Constraints

Flow conservation

Arc conflicts (cliques)
Objective
Ralf
Borndörfer

Maximize proceedings
39
IP Model OPTRA2
 Arc-based
 Routes: Multiflow
 Conflicts: Packing
(Max. Cliques)
LBW
 Proposition: The
LP-relaxation of
OPTRA2 can be
solved in
polynomial time.
 In practice …
Ralf
Borndörfer
40
IP Model OPTRA3
 Track Occupancy
Configurations
LBW
Ralf
Borndörfer
41
IP Model OPTRA3
 Track Occupancy
Configurations
LBW
Ralf
Borndörfer
42
IP Model OPTRA3
 Path-based Routes
 Path-based
Configs
Variables
LBW

Path and config usage
Constraints

Config choice

Path-config coupling (capacities)
Objective

Ralf
Borndörfer
Maximize proceedings
43
IP Model OPTRA3
 Path-based Routes
 Path-based
Configs
 Shadow prices
(useful in auction)
 Arc prices a
LBW
Ralf
Borndörfer
 Track prices r
44
IP Model OPTRA3
 Path-based Routes
 Path-based
Configs
LBW
Ralf
Borndörfer
 Proposition:
 PLP(OPTRA1)
 PLP(OPTRA2)
= PLP(OPTRA3).
45
IP Model OPTRA3
 Path-based Routes
 Path-based Configs
 Proposition:
PLP(OPTRA2)= PLP(OPTRA3).
LBW
Ralf
Borndörfer
 Proposition:
Route pricing =
acyclic shortest path
46
IP Model OPTRA3
 Path-based Routes
 Path-based Configs
 Proposition:
PLP(OPTRA2)= PLP(OPTRA3).
LBW
 Proposition:
Route pricing =
acyclic shortest path
 Proposition:
Config pricing =
acyclic shortest path
Ralf
Borndörfer
47
IP Model OPTRA3
 Path-based Routes
Begin
Compute
Prices
Add
Solve Variables
Yes
Relaxation
All fixed?
No
(LP)
 Path-based Configs
 Proposition:
PLP(OPTRA2)= PLP(OPTRA3).
LBW
Ralf
Borndörfer
 Proposition:
Route and config
pricing = acyclic
shortest path
 Proposition: The
LP-relaxation of
OPTRA3 can be
solved in polynomial
time.
No
Stop?
Yes
Unfix/Fix
Variables
OPTRA (IP)
Column Generation
End
48
Overview
 Rail Track Auctions
 The Optimal Track Allocation Problem (OPTRA)
 Mathematical Models
 Computational Results
LBW
Ralf
Borndörfer
49
Computational Results
 Test Network
 45
Tracks
 32
Stations
 6
Traintypes
 10
Trainsets
 122 Nodes
LBW
 659 Arcs
 3-12 Hours
 96
Station Capacities
 612 Headway Times
Ralf
Borndörfer
50
Computational Results
 Test Network
 Preprocessing
LBW
1486 Nodes
1881 Arcs
Ralf
Borndörfer
293 Nodes
441 Arcs
51
Computational Results
 Test Network
 Preprocessing
LBW
1486 Nodes
1881 Arcs
Ralf
Borndörfer
293 Nodes
441 Arcs
52
Computational Results
 Test Network
Delay in
min.
#Var.
#Con.
#Trains
Time in
sec..
5
29112
34330
164
4.5
6
39641
54978
200
26.3
7
52334
86238
251
45.7
8
67000
133689
278
613.1
9
83227
206432
279
779.1
10
101649
315011
311
970.0
 Preprocessing
 Degrees of Freedom
 324 Trains, Profit 1
LBW
Ralf
Borndörfer
53
Computational Results
 Test Network
 Preprocessing
 Degrees of Freedom
 Timetables
LBW
Ralf
Borndörfer
255 Trains
285 Trains
54
Computational Results
 Test Network
 Preprocessing
 Degrees of Freedom
 Timetables
 Harmonization
LBW
Ralf
Borndörfer
55
Tripling Experiment
variation
LBW
cpu time
(CPLEX)
earnings
(% Status Quo)
trains
(% Status Quo)
0 mins
6 secs
52.066 (+ 84%)
420 (+ 47%)
1 mins
8 secs
60.612 (+114%)
496 (+ 74%)
4 mins
1 days
67.069 (+137%)
617 (+117%)
5 mins
3+ days
67.975 (+140%)
737 (+159%)
 Status quo
 284 tracks through 6 hours in the Hannover—Braunschweig—
Fulda network, (hypothetical) total income of 28,255 €
 Scenario
Ralf
Borndörfer
 triple requests to 946 bids
(~15 minutes alteration, identical willingness to pay)
56
Outlook
 Column Generation
 Microsimulation
LBW
Ralf
Borndörfer
Thank you
for your attention !
LBW
Ralf Borndörfer
[email protected]
 DFG Research Center MATHEON Mathematics for Key Technologies
 Zuse-Institute Berlin (ZIB)
 Löbel, Borndörfer & Weider GbR (LBW)
http://www.zib.de/borndoerfer