Vasúti menetrendek optimalizálása

Vasúti menetrendek optimalizálása Jüttner Alpár ELTE TTK Operációkutatási Tsz.

Jüttner Alpár (ELTE TTK)

Vasúti menetrendek optimalizálása

1 / 10

Vasúti menetrendek tervezése Bemenet A vasúthálózat leírása ˝ ... állomások, összeköttetések, min/max menetidok

Járatok leírása honnan hova, milyen állomások érintésével

A járatok menetrendjével kapcsolatos elvárások ˝ min/max állásido˝ az egyes állomásokon, min/max átszállási ido, ˝ ... teljes menetido,

Biztonsági feltételek és kapacitáskorlátok ˝ min. követési idok

Feladat: a menetrend megtervezése ˝ minden Pontos útvonaltervek megadása (érkezési/indulási idok állomáson) ˝ és átszállási idok ˝ minimalizálása Célfüggvény: teljes menetidok Jüttner Alpár (ELTE TTK)


2 / 10

A modellezés szintjei Makró modell Nagy területet (pl. egész ország) modellezünk Mikró modell Részletesebb modell, de csak kisebb terület Kontroll feladat Valós ideju˝ döntéshozatal



3 / 10

A modellezés szintjei Makró modell Nagy területet (pl. egész ország) modellezünk Nem teljes részletességgel Állomások: A kapacitásokat nézzük csak Vágányok: Az állomások közötti összeköttetéseket osztatlan szakaszoknak tekintjük (plusz adott a párhuzamos vágányok száma)

Mikró modell Részletesebb modell, de csak kisebb terület Kontroll feladat



3 / 10

A modellezés szintjei Makró modell Nagy területet (pl. egész ország) modellezünk Mikró modell Részletesebb modell, de csak kisebb terület Váltók, vonalszakaszok, biztonsági zónák modellezése Állomások részletes leírása Vonatok fizikai paramétereinek (gyorsulás, fékezés, hossz) modellezése Kontroll feladat



3 / 10

A modellezés szintjei Makró modell Nagy területet (pl. egész ország) modellezünk Mikró modell Részletesebb modell, de csak kisebb terület Kontroll feladat Valós ideju˝ döntéshozatal Ismerjük a szerelvények aktuális pozícióját és sebességét Döntések: ˝ ˝ Keresztezodéseknél melyik szerelvényt engedjük elore Az állomásokról mikor indítsuk a vonatokat



3 / 10

A modellezés szintjei Makró modell Nagy területet (pl. egész ország) modellezünk Mikró modell Részletesebb modell, de csak kisebb terület Kontroll feladat Valós ideju˝ döntéshozatal A magasabb szinten kapott megoldás az alacsonyabb szinten realizálató legyen



3 / 10

Példa: Rio Tinto Rails

14 bányát szolgál ki kb. 1,400 kilométernyi vágánnyal Kb. 228 millió tonna vasércet szállítanak A szerelvények Egy ember vezeti Max 234 vagon, mindegyik kb. 112 tonna kapacitású. Teljes kapacitás 31 000 tonna Kb. 2.4 kilométer hosszú szerelvények Kb. 35 óra menetido˝ Átlagosan 25 percenként jár egy szerelvény minden vonalon.



4 / 10

Periodikus (ütemes) menetrendek

Az emberek/vállalatok szeretik, ha a járatok minden órában ugyanakkor indulnak ˝ Ez megoldható a járatok közötti szigorú követési idok ˝ definiálásával, ami viszont jelentosen megnöveli a probléma méretét. Lehetnek egyszerre periodikus és nem periodikus járatok



5 / 10

Megoldási módszerek: Egészértéku˝ programozási feladat

Az egyes eseményekhez egy ti változót rendelünk, ami az esemény idejét jelöli. Menetido˝ egy vágányon: Várakozás egy állomáson: Átszállás:

i i Wmin ≤ tleave − tarrival ≤ Wmax

Cmin ≤ tj − ti ≤ Cmax

˝ Követési ido:


i+1 i ∆min ≤ tarrival − tleave ≤ ∆max

H ≤ |tj − ti |


6 / 10


Az egyes eseményekhez egy ti változót rendelünk, ami az esemény idejét jelöli. Menetido˝ egy vágányon: Várakozás egy állomáson:

i+1 i ∆min ≤ tarrival − tleave ≤ ∆max i i Wmin ≤ tleave − tarrival ≤ Wmax

Átszállás: Cmin ≤ tj − ti ≤ Cmax ˝ Követési ido: H ≤ |tj − ti | pij ∈ {0, 1},


H ≤ tj − ti + Mpij ,

H ≤ ti − tj + M(1 − pij )


6 / 10


Az egyes eseményekhez egy ti változót rendelünk, ami az esemény idejét jelöli. Menetido˝ egy vágányon: Várakozás egy állomáson:

i+1 i ∆min ≤ tarrival − tleave ≤ ∆max i i Wmin ≤ tleave − tarrival ≤ Wmax

Átszállás: Cmin ≤ tj − ti ≤ Cmax ˝ Követési ido: H ≤ |tj − ti | pij ∈ {0, 1}, H ≤ tj − ti + Mpij , H ≤ ti − tj + M(1 − pij ) „Jump constraint”: Egy vonat nem ugorhat át egy másikat egy vágányon



6 / 10

Megoldási módszerek: PESP modell Periodic Event Scheduling Problem ˝ minden feltételt „mod P” nézünk Adott egy P periódusido, A feltételek általános alakja: lij ≤ tj − ti ≤ uij (mod P) Ez felírható egészértéku˝ programozási feladatként: lij ≤ tj − ti + Ppij ≤ uij , pij ∈ {0, 1} Tenzió alapú felírás (gyakorlatban hatékonyabb) ˝ A változók az idokülönbségek lesznek: πij := tj − ti lij ≤πij ≤ uij , pij ∈ {0, 1} X πij = Ppij ∀C ∈ C

(1) (2)

(ij)∈C

Hogyan válasszuk a C körbázist? Jüttner Alpár (ELTE TTK)


7 / 10

Megoldási módszerek: PESP modell Periodic Event Scheduling Problem ˝ minden feltételt „mod P” nézünk Adott egy P periódusido, A feltételek általános alakja: lij ≤ tj − ti ≤ uij (mod P) Ez felírható egészértéku˝ programozási feladatként: lij ≤ tj − ti + Ppij ≤ uij , pij ∈ {0, 1} Tenzió alapú felírás (gyakorlatban hatékonyabb) ˝ A változók az idokülönbségek lesznek: πij := tj − ti lij ≤πij ≤ uij , pij ∈ {0, 1} X πij = Ppij ∀C ∈ C

(1) (2)

(ij)∈C

Hogyan válasszuk a C körbázist? Jüttner Alpár (ELTE TTK)


7 / 10

˝ Térido-gráf modell ˝ Térido(sebesség)-gráf ˝ Diszkrét idopontok: t1 , t2 , . . . tk ˝ Csúcsok: (t, l) ido-pozíció párok ˝ Élek: (t1 , l1 ) −→ (t2 , l2 ), ha t1 idoben l1 -ben tartózkodunk, akkor ˝ l2 -ben lehetünk a t2 -idoben. Egy járat menetrendje: Egy út (sáv) ebben a gráfban. Feladat: Constrained Integer Multi-Commodity Flow Problem Minden járatra keresünk egy 1 értéku˝ egész folyamot (utat) Az utak „diszjunktak” kell legyenek . . . (egyéb feltételek) Oszlopgeneráción alapuló megoldási módszerek Alkalmas az extra feltételek kezelésére Egész megoldás keresése: Branch&Cut&Price eljárás Jüttner Alpár (ELTE TTK)


8 / 10

Kihívások

Makró – mikró felbontás: Feladat aggregálás Klaszterezés Extra flexibilitás biztosítása a makró szinten

PEST modell: alkalmas körbázisok keresése Részletek és hatékony mikró szintu˝ modellezés Oszlopgenerálás hatékony megvalósítása Branching módszerek ˝ Idoskála adaptív finomítása (vágósíkos módszer)

Heurisztkus megközelítések



9 / 10

Köszönöm a figyelmet!



10 / 10

Vasúti menetrendek optimalizálása

Recommend Documents