Routing Cars in Rail Freight Service€¦ · in Rail Freight Service Armin Fügenschuh - Zuse...

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

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?

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

Classification Yards

• Disintegration of trains• Sorting the cars (with the help of gravity)• Assembling of new trains

Classification Yards

entry tracks hump sorting tracks exit tracks

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).

The Bundling Effect

• Cost induced by cars

The Bundling Effect

• Cost induced by trains

The Bundling Effect

Modes of Operation

• Three ways of sending cars from origin to destination:• Individual car routing

• Assign a sequence of yards to each car

200 200

200200

Example: Individual Car Routing

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

Modes of Operation

• 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

200 200

200200

Example: Blocking of Cars

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

Modes of Operation

through the network• „Leitwege“ - DB car routing

• For all orders with the same destination and each yard assign a successor

200 200

200200

Example: DB „Leitwege“ System

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

200 200

200200

Modes of Operation

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

The Arc-Flow Model

• Sets: stations , precedence relations , orders .V A := V × V K

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

The Arc-Flow Model

• Sets: stations , precedence relations , orders .• Variables: car routes , sorting tracks , trains .• Constraints

V A := V × V K

The Arc-Flow Model

• Orders:

V A := V × V K

The Arc-Flow Model

• Orders:• Delivery:

V A := V × V K

∀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.

The Arc-Flow Model

• Time limit:

V A := V × V K

∀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

The Arc-Flow Model

• Time limit:

• Yards:

V A := V × V K

∀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

The Arc-Flow Model

• Time limit:

• Yards:• Number of sorting tracks:

V A := V × V K

∀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

The Arc-Flow Model

• Time limit:

• Number of trains per track:

V A := V × V K

∀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

The Arc-Flow Model

• Time limit:

• Number of trains per track:

• Hump capacity:

V A := V × V K

∀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

The Arc-Flow Model

V A := V × V K

• Trains:

The Arc-Flow Model

V A := V × V K

• Trains:• Max. length:

The Arc-Flow Model

V A := V × V K

∀(i, j) ∈ A :�

lk · xki,j ≤ 700 · ni,j

• Max. weight:

The Arc-Flow Model

V A := V × V K

∀(i, j) ∈ A :�

lk · xki,j ≤ 700 · ni,j

∀(i, j) ∈ A :�

wk · xki,j ≤ 1600 · ni,j

• Max. weight:

• „Leitweg“ (unique successor) constraint („plain“):

The Arc-Flow Model

V A := V × V K

∀(i, j) ∈ A :�

lk · xki,j ≤ 700 · ni,j

∀(i, j) ∈ A :�

wk · xki,j ≤ 1600 · ni,j

∀k, l ∈ K, d(k) = d(l), i ∈ V, (i, j1) �= (i, j2) ∈ A : xki,j1

+ xli,j2

• Max. weight:

The Arc-Flow Model

V A := V × V K

∀(i, j) ∈ A :�

lk · xki,j ≤ 700 · ni,j

∀(i, j) ∈ A :�

wk · xki,j ≤ 1600 · ni,j

+ xli,j2

• Max. weight:

The Arc-Flow Model

V A := V × V K

∀(i, j) ∈ A :�

lk · xki,j ≤ 700 · ni,j

∀(i, j) ∈ A :�

wk · xki,j ≤ 1600 · ni,j

+ xli,j2

• Max. weight:

The Arc-Flow Model

V A := V × V K

∀(i, j) ∈ A :�

lk · xki,j ≤ 700 · ni,j

∀(i, j) ∈ A :�

wk · xki,j ≤ 1600 · ni,j

+ xli,j2

The Arc-Flow Model

V A := V × V K

• Objective:

The Arc-Flow Model

V A := V × V K

C1 ·�

(i,j)∈A

ni,j + C2 ·�

(i,j)∈A

yi,j + C3 ·�

k∈K,(i,j)∈A

xki,j → min

C1 � C2 � C3

Improving the Arc-Flow Model (1)

• Strengthening of „Leitweg“-constraints

• Strengthening of „Leitweg“-constraints• Model formulation:

+ xli,j2

• Improved formulation („lifted“):

+ xli,j2

∀k, l ∈ K, d(k) = d(l), i ∈ V, V1∪̇V2 = V :�

j1∈V1

xki,j1

j2∈V2

xli,j2

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.

• 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}

• 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

• 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)

• 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)

• 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)

• 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)

• 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)

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:

• The following path is considered as „untypical“:

• Analysis of historical data shows: 98% of all car paths are „monotone“.

• 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

Refining the Model: Turnover Times

• Consider again the time-limit constraint:∀k ∈ K :

(i,j)∈A

• Consider again the time-limit constraint:

• Note: The turnover time is a constant here.

∀k ∈ K :�

(i,j)∈A

• 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

∀k ∈ K :�

(i,j)∈A

1 2 3 4 5 6

• In a more realistic model, is a variable, and .

∀k ∈ K :�

(i,j)∈A

1 2 3 4 5 6

uki,j ∈ R+ uk

i,j =24ni,j

· xki,j

• In a more realistic model, is a variable, and .

• Problem: We now have an MINLP.

∀k ∈ K :�

(i,j)∈A

1 2 3 4 5 6

uki,j ∈ R+ uk

i,j =24ni,j

· xki,j

Linearization 1

• The set of feasible points with is:u · n = 24 · x

(u, n, x)

Linearization 1

• The set of feasible points with is:u · n = 24 · x

(u, n, x)

Linearization 1

• The set of feasible points with is:

• Remeber that and .u · n = 24 · x

(u, n, x)

x ∈ {0, 1} n ∈ Z+

Linearization 1

• Remeber that and .• Thus the convex hull is

u · n = 24 · x(u, n, x)

x ∈ {0, 1} n ∈ Z+

Linearization 1

u · n = 24 · x(u, n, x)

x ∈ {0, 1} n ∈ Z+

24(2i + 1)x − 24n ≤ i(i + 1)u, i = 1, . . . , N

Linearization 1

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

Linearization 1

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

Linearization 1

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

Linearization 1

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

Linearization 1

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

Linearization 1

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

Linearization 1

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

Linearization 1

• 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

Linearization 2

January 7, 2010

Linearization 2

• Consider the nonlinear relation ,

January 7, 2010

u · n = 24 · x

Linearization 2

• Consider the nonlinear relation ,and make it even „more“ nonlinear: .

January 7, 2010

u · n = 24 · x

u · n = 24 · x2

Linearization 2

January 7, 2010

u · n = 24 · x

u · n = 24 · x2

u · n = 24 · x

Linearization 2

January 7, 2010

u · n = 24 · x

u · n = 24 · x2

u · n = 24 · x u · n = 24 · x1

Linearization 2

January 7, 2010

u · n = 24 · x

u · n = 24 · x2

u · n = 24 · x u · n = 24 · x2

Linearization 2

January 7, 2010

u · n = 24 · x

u · n = 24 · x2

u · n = 24 · x u · n = 24 · x2

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.

Linearization 2 (cont.)

• On we apply the following variable substitutionu = τ + α,

n = τ − α,

24 · x2 = β2.

u · n ≥ 24 · x2

n = τ − α,

24 · x2 = β2.

u · n ≥ 24 · x2

n = τ − α,

24 · x2 = β2.

u · n ≥ 24 · x2

n = τ − α,

24 · x2 = β2.

u · n ≥ 24 · x2

n = τ − α,

24 · x2 = β2.

u · n ≥ 24 · x2

• On we apply the following variable substitution

• We obtain the Lorentz (second order) cone

u = τ + α,

n = τ − α,

24 · x2 = β2.

u · n ≥ 24 · x2

�α2 + β2 ≤ τ.

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

with accuracy

ξ0 ≥ |α|η0 ≥ |β|

ξi = cos(π

2i+1)ξi−1 + sin(

2i+1)ηi−1

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

with accuracy

• Good news: We are back in the MILP world!

ξ0 ≥ |α|η0 ≥ |β|

ξi = cos(π

2i+1)ξi−1 + sin(

2i+1)ηi−1

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

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

• 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

• 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%)

Thank you for your attention!

Routing Cars in Rail Freight Service€¦ · in Rail Freight Service Armin Fügenschuh - Zuse...

Documents

Frauscher ULTIMATE RAIL

Minister's declaration · In presence of theE U Coordinator for ERTMS, Mr. Karel Vinck on the conference of Ministers regarding 'Rail infrastructure for freight services: from . corridors

Handbuch DHL Freight Intraship - spedition-leupold.de · Handbuch DHL Freight Intraship ZL/PI/IT Handbuch DHL Freight Intraship

CNAM SIA 18.3Système Common Rail de première génération avec pompe CP1 Engine speed (crank) Engine speed (cam) Accelerator pedal Other sensors Rail pressure sensor Common Rail

Common-Rail-Systeme - Krafthand · Common-Rail-Systeme Leseprobe Peugeot bietet als erster Hersteller ein Diesel-Hybridfahrzeug an. Bild: Peugeot Die 5. Auflage ,Common-Rail-Systeme

IVECO „Common Rail“ EURO6

High-speed rail Holland Germany

RAIL SOLUTIONS...RAIL SOLUTIONS 2 Edelstahlpfosten made in Germany Wir ermöglichen Ihnen mit unse-rem eigenen Produktionscenter eine auftragsbezogene Herstel-lung von maßgefertigten

Hellmann Rail Eurasia · International anerkannte Frachtpapier: CIM / SMGS Hauptrouten Transit China und Europa Transportroute Rail Eurasia . Vostochny ... Prozessablauf Rail Eurasia

Motortechnologie Common-Rail-Einspritzung ... Schlüsseltechnologie für eine saubere und sparsame Verbrennung Pionier beim Common-Rail-Einspritzsystem Die Emissionsvorschriften für

für Güterverkehr - Rail Cargo Group · for internatonal Freight traffic: List of railway statons List of handover/unloading points used ... A complete and above all legally binding

Freight News - DB Cargo · FreightNews Ausgabe 5/06 Titelthema / Kurzmeldungen 3 Stinnes AG Freight Logistics Marktbereich Montan Jürgen Albersmann Tel.: +49 (0)203 3017-2533 Fax:

ÖBB kompakt 2017/18 bringen. Österreich zusammen495758fd-738a-48d8-8d77-b0fa03629f6f/... · Rail Cargo Hungaria Zrt. ÖBB-Personenverkehr AG Rail Cargo Austria AG Rail Cargo Logistics

Telescopic Rail...TR-2 Produkterläuterung 1 Produkterläuterung Telescopic Rail: Voll- und Teilauszüge in sieben Baureihen Bevorzugte Einsatzgebiete der Telescopic Rail-Produktfamilie:

Amberg Rail - Release Notes

Pre%Readforthe! MITFuture!Freight!FlowsSymposium! 11 ...€¦ · Pre%Readforthe! MITFuture!Freight!FlowsSymposium! 11–12March2010!!!!! Authors:! Dr.!ChrisCaplice,MITCTL!(caplice@mit.edu)!

Crosinox rail solution

Kurzpräsentation DHL Freight GmbH, Menden / Hagen

Konzepte zur Gebäudeinstandhaltung, Sanierung & Modernisierung von Kongress- und Veranstaltungsstätten - Matthias Ehrentraut, Eco Rail Innovation/DB Eco Rail

Gateway Rail Freight Limitedgatewayrail.in/data/GatewayRailFreightLimited30102015...Page- 1/19 1 Gateway Rail Freight Limited Inland Container Depot – Garhi Harsaru Opp Railway Station