Embed Size (px)
Citation preview
Routing Cars in Rail Freight Service
Armin Fügenschuh - Zuse Institute Berlin, Germany
Henning Homfeld - Technische Universität Darmstadt, GermanyAlexander Martin - Technische Universität Darmstadt, GermanyHanno Schülldorf - Technische Universität Darmstadt, Germany & Deutsche Bahn AG, Frankfurt am Main, Germany
January 7, 2010
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Deutsche Bahn (G. Pfau, J. Wolfner)• Department for Company Development (GSU1)• Interested in long-term traffic & demand forecast
& simulaton• Code testing & result benchmarking
• Schenker (A. Below, C. Liebchen, T. Klingler)• DB subsidary for freight service• Solving the operational routing problem manually• Providing real-life data
• Federal Ministry for Science and Education (BMBF)• Funding applied math projects (period 2007-2010)• OVERSYS:
• U. Zimmermann, R. Hansmann (TU Braunschweig)• U. Clausen, A. Chmielewski, J. Baudach (Fraunhofer IML)• C. Helmberg, F. Fischer (TU Chemnitz)• R. Schultz (U Duisburg), G. Reinelt (U Heidelberg)
Project Partners
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Introduction
• Railway freight transport has a market share of 20%.• 100,000 Mil. ton km, of which:
• 45% inland traffic,• 45% cross-border traffic,• 10% transit traffic.
• Deutsche Bahn offers whole trains (~30 cars) and individual cars.
• Several individual cars with different destinationsare grouped to trains at classification yards.
• At the next classification yard, the cars are re-grouped, until they reached their destinations.
• Main question: what is the „best“ path for each car?
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Facts and Figures
• Railway network length: 38,200 km• 5000 trains per day, 150,000 cars• Terminal stations: 2,200• Classification yards:
• Large („Rangierbahnhöfe“): 11• Medium („Knotenbahnhöfe“): 30• Small („Satellitenbahnhöfe“): 200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Classification Yards
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Disintegration of trains• Sorting the cars (with the help of gravity)• Assembling of new trains
Classification Yards
entry tracks hump sorting tracks exit tracks
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Survey of the Literature
• First models for the blocking problem emerged in the 1960s. Since then...
• Bodin, Schuster & Golden (1980)
• Assad (1983)
• Crainic, Ferland & Rousseau (1984)Crainic & Rousseau (1986)
• Keaton (1989, 1992)
• Newton (1997)Newton, Barnhart & Vance (1998)Barnhart, Hong & Vance (2000)
• Ahuja (2007)
• Main differences to our problem:
• Special constraints due to DB operational rules („Leitwege“).
• Costs are induced by trains (and not so much by cars).
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by cars
100
100
60
10
30
30
40
0
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by cars
100
100
60
10
30
30
40
0
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by cars
100
100
60
10
30
30
40
200
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by cars
100
100
60
10
30
30
40
200
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
0
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
0
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
70
70
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
70
70
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
130
190
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
130
190
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
170
230
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Bundling Effect
• Cost induced by trains
100
100
60
10
30
30
40
170
230
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Modes of Operation
• Three ways of sending cars from origin to destination:• Individual car routing
• Assign a sequence of yards to each car
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
500
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
500
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
500
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
700
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
700
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
700
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
900
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
900
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
900
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
1100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
1100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
1100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
1300
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Individual Car Routing
1300
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Modes of Operation
• Three ways of sending cars from origin to destination:• Individual car routing
• Assign a sequence of yards to each car• Blocking of cars
• Assign a sequence of yards to each order• All cars in an order follow the same path
through the network
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
400
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
600
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
600
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
600
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
800
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
800
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
800
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1000
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1000
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1000
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1400
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: Blocking of Cars
1400
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Modes of Operation
• Three ways of sending cars from origin to destination:• Individual car routing
• Assign a sequence of yards to each car• Blocking of cars
• Assign a sequence of yards to each order• All cars in an order follow the same path
through the network• „Leitwege“ - DB car routing
• For all orders with the same destination and each yard assign a successor
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
0
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
100
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
500
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
500
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
500
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
800
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
800
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
800
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1000
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1000
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1000
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1200
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1400
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1400
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1400
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1600
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
300
200 200
200200
100
Example: DB „Leitwege“ System
1600
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Modes of Operation
• Three ways of sending cars from origin to destination:• Individual car routing
• Assign a sequence of yards to each car• Blocking of cars
• Assign a sequence of yards to each order• All cars in an order follow the same path
through the network• „Leitwege“ - DB car routing
• For all orders with the same destination and each yard assign a successor
• If „Leitwege“ are so expensive, then why do they do it?• Historical reasons• More robust / errors can easily be corrected
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .V A := V × V K
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:• Delivery:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀i ∈ V, k ∈ K :�
j:(i,j)∈A
xki,j −
�
j:(j,i)∈A
xkj,i =
1, i = o(k),−1, i = d(k),
0, else.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:• Delivery:
• Time limit:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀i ∈ V, k ∈ K :�
j:(i,j)∈A
xki,j −
�
j:(j,i)∈A
xkj,i =
1, i = o(k),−1, i = d(k),
0, else.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:• Delivery:
• Time limit:
• Yards:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀i ∈ V, k ∈ K :�
j:(i,j)∈A
xki,j −
�
j:(j,i)∈A
xkj,i =
1, i = o(k),−1, i = d(k),
0, else.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:• Delivery:
• Time limit:
• Yards:• Number of sorting tracks:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀i ∈ V :�
j:(i,j)∈A
yi,j ≤ Yi
∀i ∈ V, k ∈ K :�
j:(i,j)∈A
xki,j −
�
j:(j,i)∈A
xkj,i =
1, i = o(k),−1, i = d(k),
0, else.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:• Delivery:
• Time limit:
• Yards:• Number of sorting tracks:
• Number of trains per track:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀i ∈ V :�
j:(i,j)∈A
yi,j ≤ Yi
∀(i, j) ∈ A : ni,j ≤ 6yi,j
∀i ∈ V, k ∈ K :�
j:(i,j)∈A
xki,j −
�
j:(j,i)∈A
xkj,i =
1, i = o(k),−1, i = d(k),
0, else.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
• Orders:• Delivery:
• Time limit:
• Yards:• Number of sorting tracks:
• Number of trains per track:
• Hump capacity:
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀i ∈ V :�
j:(i,j)∈A
yi,j ≤ Yi
∀(i, j) ∈ A : ni,j ≤ 6yi,j
∀i ∈ V :�
k∈K,j:(i,j)∈A
vk · xki,j ≤ Hi
∀i ∈ V, k ∈ K :�
j:(i,j)∈A
xki,j −
�
j:(j,i)∈A
xkj,i =
1, i = o(k),−1, i = d(k),
0, else.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:• Max. length:
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀(i, j) ∈ A :�
k∈K
lk · xki,j ≤ 700 · ni,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:• Max. length:
• Max. weight:
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀(i, j) ∈ A :�
k∈K
lk · xki,j ≤ 700 · ni,j
∀(i, j) ∈ A :�
k∈K
wk · xki,j ≤ 1600 · ni,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:• Max. length:
• Max. weight:
• „Leitweg“ (unique successor) constraint („plain“):
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀(i, j) ∈ A :�
k∈K
lk · xki,j ≤ 700 · ni,j
∀(i, j) ∈ A :�
k∈K
wk · xki,j ≤ 1600 · ni,j
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:• Max. length:
• Max. weight:
• „Leitweg“ (unique successor) constraint („plain“):
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀(i, j) ∈ A :�
k∈K
lk · xki,j ≤ 700 · ni,j
∀(i, j) ∈ A :�
k∈K
wk · xki,j ≤ 1600 · ni,j
i
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:• Max. length:
• Max. weight:
• „Leitweg“ (unique successor) constraint („plain“):
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀(i, j) ∈ A :�
k∈K
lk · xki,j ≤ 700 · ni,j
∀(i, j) ∈ A :�
k∈K
wk · xki,j ≤ 1600 · ni,j
i
k
l
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Trains:• Max. length:
• Max. weight:
• „Leitweg“ (unique successor) constraint („plain“):
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
∀(i, j) ∈ A :�
k∈K
lk · xki,j ≤ 700 · ni,j
∀(i, j) ∈ A :�
k∈K
wk · xki,j ≤ 1600 · ni,j
i
k
l
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
k
l
j1
j2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
• Objective:
The Arc-Flow Model
• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .
V A := V × V K
xki,j ∈ B yi,j ∈ N ni,j ∈ N
C1 ·�
(i,j)∈A
ni,j + C2 ·�
(i,j)∈A
yi,j + C3 ·�
k∈K,(i,j)∈A
xki,j → min
C1 � C2 � C3
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints• Model formulation:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints• Model formulation:
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints• Model formulation:
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
j1
j2
ik
l
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints• Model formulation:
• Improved formulation („lifted“):
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
j1
j2
ik
l
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints• Model formulation:
• Improved formulation („lifted“):
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
j1
j2
ik
lj1
j2
j2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (1)
• Strengthening of „Leitweg“-constraints• Model formulation:
• Improved formulation („lifted“):
∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1
+ xli,j2
≤ 1
∀k, l ∈ K, d(k) = d(l), i ∈ V, V1∪̇V2 = V :�
j1∈V1
xki,j1
+�
j2∈V2
xli,j2
≤ 1
j1
j2
ik
lj1
j2
j2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .• Unique successor:
(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
∀i ∈ V, κ ∈ K :�
j:(i,j)∈A
zκi,j ≤ 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .• Unique successor:
• Cars follow trees:
(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
∀i ∈ V, κ ∈ K :�
j:(i,j)∈A
zκi,j ≤ 1
∀(i, j) ∈ A, k ∈ K : xki,j ≤ zd(k)
i,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .• Unique successor:
• Cars follow trees:• Cons: more variables
(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
∀i ∈ V, κ ∈ K :�
j:(i,j)∈A
zκi,j ≤ 1
∀(i, j) ∈ A, k ∈ K : xki,j ≤ zd(k)
i,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .• Unique successor:
• Cars follow trees:• Cons: more variables• Pros:
(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
∀i ∈ V, κ ∈ K :�
j:(i,j)∈A
zκi,j ≤ 1
∀(i, j) ∈ A, k ∈ K : xki,j ≤ zd(k)
i,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .• Unique successor:
• Cars follow trees:• Cons: more variables• Pros:
• Do not need „Leitweg“-constraint in -variables.
(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
∀i ∈ V, κ ∈ K :�
j:(i,j)∈A
zκi,j ≤ 1
∀(i, j) ∈ A, k ∈ K : xki,j ≤ zd(k)
i,j
x
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Improving the Arc-Flow Model (2)(communicated by A. Bley, 2008)
• Consider the structure of a feasible solution:
• The „Leitweg“-constraint (uniqueness of successor) leads to trees.• Formulate trees directly and merge them with the model:
• Variable for all and .• Unique successor:
• Cars follow trees:• Cons: more variables• Pros:
• Do not need „Leitweg“-constraint in -variables.• Better LP-relaxation.
(i, j) ∈ Azκi,j ∈ B κ ∈ K := {d(k) : k ∈ K}
∀i ∈ V, κ ∈ K :�
j:(i,j)∈A
zκi,j ≤ 1
∀(i, j) ∈ A, k ∈ K : xki,j ≤ zd(k)
i,j
x
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Hence a „typical“ path has the following structure:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Hence a „typical“ path has the following structure:
4 4
3
2
1 1 1
2
3
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Hence a „typical“ path has the following structure:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Hence a „typical“ path has the following structure:
4 4
2
1
3
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Hence a „typical“ path has the following structure:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Hence a „typical“ path has the following structure:
4 4
3
2
3
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• The following path is considered as „untypical“:
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• The following path is considered as „untypical“:
4 4
3
2
1 1
2
33
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Analysis of historical data shows: 98% of all car paths are „monotone“.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Heuristic Cuts: Hierarchy Constraints
• Observation: Large yards „attract“ cars, because• They are at central locations in the network,• They can handle more cars (capacity & speed),• They can be connected to more yards.
• Analysis of historical data shows: 98% of all car paths are „monotone“.• Separate „monotone“ paths from „zig-zag“ paths by new constraints:
∀j ∈ V, l ∈ K :�
i:(i,j)∈A,hi≤hj
xli,j +
�
k:(j,k)∈A,hj≥hk
xlj,k ≤ 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
• Consider again the time-limit constraint:∀k ∈ K :
�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
• Consider again the time-limit constraint:
• Note: The turnover time is a constant here.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
ui
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
• Consider again the time-limit constraint:
• Note: The turnover time is a constant here.• In reality, the turnover time depends on the number of trains that are
assembled on the resp. sorting track:
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
ui
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
• Consider again the time-limit constraint:
• Note: The turnover time is a constant here.• In reality, the turnover time depends on the number of trains that are
assembled on the resp. sorting track:
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
0
6
12
18
24
30
1 2 3 4 5 6
ui
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
• Consider again the time-limit constraint:
• Note: The turnover time is a constant here.• In reality, the turnover time depends on the number of trains that are
assembled on the resp. sorting track:
• In a more realistic model, is a variable, and .
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
0
6
12
18
24
30
1 2 3 4 5 6
ui
uki,j ∈ R+ uk
i,j =24ni,j
· xki,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Refining the Model: Turnover Times
• Consider again the time-limit constraint:
• Note: The turnover time is a constant here.• In reality, the turnover time depends on the number of trains that are
assembled on the resp. sorting track:
• In a more realistic model, is a variable, and .
• Problem: We now have an MINLP.
∀k ∈ K :�
(i,j)∈A
(ui + ti,j) · xki,j ≤ Tk
0
6
12
18
24
30
1 2 3 4 5 6
ui
uki,j ∈ R+ uk
i,j =24ni,j
· xki,j
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:u · n = 24 · x
(u, n, x)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:u · n = 24 · x
(u, n, x)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .u · n = 24 · x
(u, n, x)
x ∈ {0, 1} n ∈ Z+
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
w ≤ 24x
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
w ≤ 24x
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
w ≤ 24x
Nu ≤ 24N + 24x − 24n
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
w ≤ 24x
x ≤ 1Nu ≤ 24N + 24x − 24n
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
w ≤ 24x
x ≤ 1Nu ≤ 24N + 24x − 24n
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 1
• The set of feasible points with is:
• Remeber that and .• Thus the convex hull is
• Note that all lower-bound-cuts contain the origin, like „projective cuts“, c.f.• Frangioni, Gentile (2006, 2009)• Frangioni, Gentile, Grande, Pacifici (2009)• Günlük, Linderoth (2009)
u · n = 24 · x(u, n, x)
x ∈ {0, 1} n ∈ Z+
w ≤ 24x
x ≤ 1Nu ≤ 24N + 24x − 24n
24x ≤ Nu
24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
January 7, 2010
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,
January 7, 2010
u · n = 24 · x
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,and make it even „more“ nonlinear: .
January 7, 2010
u · n = 24 · x
u · n = 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,and make it even „more“ nonlinear: .
January 7, 2010
u · n = 24 · x
u · n = 24 · x2
u · n = 24 · x
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,and make it even „more“ nonlinear: .
January 7, 2010
u · n = 24 · x
u · n = 24 · x2
u · n = 24 · x u · n = 24 · x1
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,and make it even „more“ nonlinear: .
January 7, 2010
u · n = 24 · x
u · n = 24 · x2
u · n = 24 · x u · n = 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,and make it even „more“ nonlinear: .
January 7, 2010
u · n = 24 · x
u · n = 24 · x2
u · n = 24 · x u · n = 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2
• Consider the nonlinear relation ,and make it even „more“ nonlinear: .In the sequel we are interested in a lower bound on the waiting time:
January 7, 2010
u · n = 24 · x
u · n = 24 · x2
u · n = 24 · x u · n = 24 · x2
u · n ≥ 24 · x2.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
• On we apply the following variable substitutionu = τ + α,
n = τ − α,
24 · x2 = β2.
u · n ≥ 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
• On we apply the following variable substitutionu = τ + α,
n = τ − α,
24 · x2 = β2.
u · n ≥ 24 · x2
u · n ≥ 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
• On we apply the following variable substitutionu = τ + α,
n = τ − α,
24 · x2 = β2.
u · n ≥ 24 · x2
u · n ≥ 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
• On we apply the following variable substitutionu = τ + α,
n = τ − α,
24 · x2 = β2.
u · n ≥ 24 · x2
u · n ≥ 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
• On we apply the following variable substitutionu = τ + α,
n = τ − α,
24 · x2 = β2.
u · n ≥ 24 · x2
u · n ≥ 24 · x2
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linearization 2 (cont.)
• On we apply the following variable substitution
• We obtain the Lorentz (second order) cone
u = τ + α,
n = τ − α,
24 · x2 = β2.
u · n ≥ 24 · x2
u · n ≥ 24 · x2
�α2 + β2 ≤ τ.
�α2 + β2 ≤ τ.
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linear Approximation of the SOC
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linear Approximation of the SOC
• The SOC can be approximated by linear inequalities (Ben-Tal, Nemirovski 1998, Glineur 2000):
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linear Approximation of the SOC
• The SOC can be approximated by linear inequalities (Ben-Tal, Nemirovski 1998, Glineur 2000):
ξ0 ≥ |α|η0 ≥ |β|
ξi = cos(π
2i+1)ξi−1 + sin(
π
2i+1)ηi−1
ηi ≥ | − sin(π
2i+1)ξi−1 + cos(
π
2i+1)ηi−1|
ξn ≤ τ
ηn ≤ tan(π
2n+1)ξn
i = 2, 3, . . . , M
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linear Approximation of the SOC
• The SOC can be approximated by linear inequalities (Ben-Tal, Nemirovski 1998, Glineur 2000):
with accuracy
ξ0 ≥ |α|η0 ≥ |β|
ξi = cos(π
2i+1)ξi−1 + sin(
π
2i+1)ηi−1
ηi ≥ | − sin(π
2i+1)ξi−1 + cos(
π
2i+1)ηi−1|
ξn ≤ τ
ηn ≤ tan(π
2n+1)ξn
i = 2, 3, . . . , M
ε(M) =1
cos( π2M+1 )
− 1 = O(1
4M)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Linear Approximation of the SOC
• The SOC can be approximated by linear inequalities (Ben-Tal, Nemirovski 1998, Glineur 2000):
with accuracy
• Good news: We are back in the MILP world!
ξ0 ≥ |α|η0 ≥ |β|
ξi = cos(π
2i+1)ξi−1 + sin(
π
2i+1)ηi−1
ηi ≥ | − sin(π
2i+1)ξi−1 + cos(
π
2i+1)ηi−1|
ξn ≤ τ
ηn ≤ tan(π
2n+1)ξn
i = 2, 3, . . . , M
ε(M) =1
cos( π2M+1 )
− 1 = O(1
4M)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Computational Results (1)
• Comparison of formulations on random instances • CPlex 11.2, default settings
• CPU times:
• B&B nodes:
instance plain lifted tree
1 338 47 31
2 956 136 80
3 7208 3019 6095
4 3422 796 190
5 83 43 34
instance plain lifted tree
1 557 572 628
2 1347 1811 1428
3 63893 37806 52388
4 19555 21740 5454
5 8376 3832 1884
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Computational Results (2)
• National traffic in Germany• 43 yards (medium and large)• 1,600 orders• CPlex10• 6 hours CPU time• 8% gap• Visible bundling effects -
most traffic on main axes
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Computational Results (3)
• Cross-border traffic to France(real-world instance)
• 26 yards, ~250 orders• CPlex 11.1• 8 processors, 32 GByte RAM• 1 hours CPU time• Best feasible solution: 89,100• With only small gap (2.58%)
Armin Fügenschuh January 7, 2010Zuse Institute BerlinDep. Optimization
Thank you for your attention!
