Eötvös Lóránd Tudomány Egyetem Bsc szakdolgozat Egészérték¶ programozási feladatok a közlekedés-tervezésben
Czifra Domonkos
Témvezet®:
Jüttner Alpár Operációkutatás Tanszék
Budapest,2016
Köszönetnyilvánítás Köszönöm témavezet®m, Jüttner Alpár segítségét, aki hasznos tanácsaival jó irányba terelte e dolgozatot, és akihez mindig fordulhattam kérdéseimmel. Valamint köszönöm szüleimnek, testvéreimnek, barátaimnak a támogatást, biztatást.
1
Tartalomjegyzék
1. Egy közlekedési hálózat tervezése
4
1.1.
A tervezés folyamata . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.
Folyammodell . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3.
Útpakolási modell
. . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.4.
Hálózattervezés . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.5.
Járattervezés
1.6.
4
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.5.1.
1.modell . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.5.2.
2.modell . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Menetrendtervezés
. . . . . . . . . . . . . . . . . . . . . . . . . .
8 9
1.6.1.
Periodikus Menetrendtervezés(Periodic Event Sheduling . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.6.2.
Pesp által fedett menetrendtervezési lépések . . . . . . . .
11
Problem) 1.7.
A járm¶vek elosztása . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.8.
Személyzetelosztás
. . . . . . . . . . . . . . . . . . . . . . . . . .
15
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.8.1.
Rotáció
2. Nagy IP feladatok megoldása 2.1.
2.2.
16
Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.1.1.
Branch and Cut
. . . . . . . . . . . . . . . . . . . . . . .
17
2.1.2.
Branch and Price . . . . . . . . . . . . . . . . . . . . . . .
17
2.1.3.
Diving heurisztikák . . . . . . . . . . . . . . . . . . . . . .
18
2.1.4.
Simple Feasibility Pump . . . . . . . . . . . . . . . . . . .
19
2.1.5.
Objective Feasibility Pump
21
Rapid Branching
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1.
Perturbation Branching
2.2.2.
Binary Search Branching
3. Kitekintés
23
. . . . . . . . . . . . . . . . . . .
24
. . . . . . . . . . . . . . . . . .
25
27
2
Bevezetés Az emberiség történelme során mindig is törekedett a meglév® eszközök fejlesztésére, és a meglév®kb®l a legjobbak kihozására, OPTIMALIZÁSÁRA. Azonban a közlekedésben talán csak a 20.században jelent meg akkora forgalom a közlekedési útvonalakon, hogy legyen értelme érdemben optimalizálásról beszélni. Az egyik legnagyobb igény a közlekedés optimalizálásra a légitársaságoktól érkezett: hiszen az er®s verseny, és az er®források relatív magas költsége miatt egy ügyes optimalizáláson akár a pro tabilitásuk múlhat. A légitársaságok két legfontosabb feladata az er®forrás elosztás: repül®gépek (Vehicle-), és a személyzet elosztása (Crew-sheduling). Jóllehet ekkor már létezett az a matematikai apparátus, melyekkel modellezni, és megoldani lehetett a problémákat, de látszólag kis problémák megoldásának kiszámítása az ismert eszközökkel "végtelen" sok id®be telt volna, így új módszereket kellett kidolgozni, hogy reális id®ben megoldják a problémákat. A 21.században az angolszász területeken a közösségi közlekedés egyes részeit privatizálták, így pro torientált vasúttársaságok, busztársaságok is optimalizálni szerették volna járataikat, már a kezdeti tervezést®l (Network planing) a legkisebb részletekig (Crew-sheduling). A dolgozat els® része a f®bb tervezési lépésekkel foglalkozik, mint a hálózattervezés, járattervezés, menetrendtervezés, er®forrás-, illetve személyzetelosztás. A második rész pedig ezek általános megoldását tárgyalja, kezdve a legegyszer¶bb algoritmusoktól (Branch and Bound) az egyszer¶ heurisztkákon át az összetettebb heurisztikákig, amit már a gyakorlatban is alkalmaznak (lásd [1]).
3
1. Egy közlekedési hálózat tervezése 1.1. A tervezés folyamata A közlekedési rendszer (pl busz- illletve vasúthálózat) megtervezésénél alapvet®en két fázisról beszélhetünk:
•
stratégiai (strategic)
•
illetve m¶ködtetési (operational) tervezésr®l.
A stratégiai tervezés általában több id®t vesz igénybe, a döntések hosszú id®re szólnak. Ebb®l adódóan nehezebb is modellezni, mert akár politikai döntésekt®l is függhet. Célja meghatározni a szolgáltatás színvonalát, a kivitelezés módját. Itt kap helyet többek között az er®források beszerzése, a hálózattervezés (network planning), a járattervezés (line planning), és a menetrendtervezés (timetable planning). A menetrendtervezés operációkutatással azonban már egy széles körben alkalmazott terület, sok vasúti menetrend már nem kézzel készül, úgymint a német, svájci, vagy éppen a holland vasúti menetrend: [2]. A m¶ködtetés megszervezése a tényleges folyamat el®tt nem sokkal/közben történik, itt már a meglév® er®forrásokat osztjuk be a megfelel® feladatokhoz, például a járm¶veket (vehicle sheduling), vagy a személyzetet (crew sheduling). Számos légitársaság, és egyéb közlekedési társaság automatizálja ezt a tervezési lépést, mert a rendelkezésre álló algoritmusok olcsóbban, és sokkal hatékonyabban osztják be a személyzetet, mint az ember.
1.2. Folyammodell Talán ez a legkézenfekv®bb modell egy hálózat tervezéséhez.
(V, A) irányított gráf, V a csúcsok halmaza, A az (irányított) élek {s,t} forrás illetve nyel®. min max max Legyen ka , ka , a ∈ A alsó illetve fels® kapacitások, hogy ka ≥ kamin . Valamint legyen ca , a ∈ A egy adott folyamegységre jutó költség. A feladat egy minimális költség¶ folyam megtalálása s és t között, az adott Legyen
halmaza,
kapacitás megszorítások mellett. (Természetesen egyéb megszorításokat is lehet tenni.) Ez formálisan felírva:
min cT y in
y(δ (v)) − y(δ
out
kamax
(1)
(v)) = 0, ≤y≤
∀v ∈ V \ {s, t},
(2)
∀a ∈ A,
(3)
kamin
By = b
(4)
ya ≥ 0,
∀a ∈ A
A
y∈Z Itt
ya
megmondja adott
(5) (6)
a ∈ A élre a folyam értékét.
(2) biztosítja a folyam-
feltételt (amennyi folyam egy csúcsba befolyt, annyi kell kifolynia is; a forrás és a nyel® kivételével).
(3) biztosítja az élekre, hogy a folyam egy adott élen
4
1. ábra. Tervezési lépések
5
ne lépje túl a korlátait. (4) feltételek megadásával a folyamnak speciális tulajdonságokat írhatunk el®. (5)-(6) pedig a nemnegativitásti, és az egészérték¶ségi feltételek, hiszen általában egész dolgokat kell szétosztani:
pl.:
személyzetet
vagy járm¶veket. Érdemes (4) nevezetes eseteire kitérni
•
Ha ugyanis (4) üres, akkor egy minimális költség¶ folyamot kell megoldanunk, így ez polinomiális id®ben megy.
•
Azonban (4) helyébe többtermékes folyamfeltételeket is tehetünk, így egy többtermékes folyamfeladatot kapunk.
•
Jól alkalmazható
P
a∈p
≤ |p| − 1
feltétel egy
p∈P
út tiltására.
A többtermékes folyam jól modellezi például több járm¶parkból való járm¶ütemezést, vagy a telekommunikációs hálózatok m¶ködését is, hiszen minden kapcsolat egy külön termék folyamának tekinthet®. A harmadik speciális feltétel kényelmes lehet bizonyos utak kizárására, azonban ez a feltétel elronthatja a feladatunk szerkezetét, ami az így módosult feladat megoldásánál komoly hátrányokat okozhat. Mint látszik a célfüggvényen is, ez egy
él-központú
modell. Ha bizonyos
utakat gyakran kell kitiltani az algoritmus során, akkor jobban használható a következ® modell, mely
út-központú,
mert a korlátozó feltételeket bizonyos
utakra szabjuk meg.
1.3. Útpakolási modell Ha az el®z® modellben (3)-ban többtermékes korlátozó feltétel van, sok termékkel a többtermékes folyam megoldása id®igényes lehet. Ennek elkerülése végett a folyamfeladatot utak és körök uniójára bontjuk föl (lásd Datzig-Wolfe [3]). Az általános útpakolási modell: (General Path Based Model)
min dT x kamax ≤
X
(7)
xp ≤ kamin ,∀a ∈ A,
(p ∈ S)
(8)
a változók nemnegatívak
(9)
és a változók egészek.
(10)
az alsó fels® korlát
a∈p
xp ≥ 0,∀p ∈ S, S
x∈Z , Ahol például:
S Pbizonyos a hálózatban haladó utak halmaza. a∈p ca .
Itt
dp a költségfüggvény,
GPBM-nek három nevezetes speciális esete van:
S
•
Path Packing Problem: (8a)
1≤
•
Path Partitioning Problem: (8b)
•
Path Packing Problem: (8c)
1≥
P
xp P
a∈p
1= P
a∈p
a∈p
xp
xp
mérete így nagyon nagy lehet, ezért ezt a problémát érdemes valamilyen
oszlopgenerálós algoritmussal megoldani.
6
1.4. Hálózattervezés A hálózat és járattervezés még nem olyan jól kidolgozott, és ritkán alkalmazott tervezési lépések, és ha használják is, inkább csak a városi tömegközlekedésben.
Ugyanis még a városi tömegközlekedésben is ritka az az alapszituáció,
hogy alapjaitól kell, illetve lehet egy város közlekedését megszervezni, hiszen az infrastruktúra (buszmegállók, táblák, járatinformációk) már adottak, ezek lecserélése és az utasok tájékoztatása nagy marketingköltséggel járhat. Sokkal inkább jellemz®, hogy egy meglév® hálózatot b®vítenek, optimalizálnak az új igényeknek megfelel®en. A hálózattervezési feladatban adottak végállomások, és transzfer pontok, ahol a járatok indulnak, pályát módosíthatnak. A célunk adott forgalmú közlekedés megszervezése minimális költséggel.
N = (V, A) egy hálózat, A azon útszakaszok/utcák, ahol a járm¶vek közlekedhetnek. Legyen egy p útra O(p) illetve D(p) az út két p végpontja, b közlekedési forgalom O(p), D(p) között. F legyen a járm¶fajták Az alábbi modellt [4] szerz®i írták fel el®ször. Legyen
ahol
V
a végállomások, és transzfer pontok halmaza,
halmaza (mint például: csuklósbusz, alacsonypadlós busz, trollibusz, villamos stb). Ennek segítségével minden járm¶típusra különböz® kapacitásokat, illetve
ufa mondja meg egy f típusú járm¶fajtából a f p élen hány ember fér fel. Legyen ca és da (f ∈ F ; a ∈ A) az a költség, amely a közlekedési társaságnak a élen keletkezik p úton, illetve f járm¶vön. f Jelölje ya (f ∈ F ; a ∈ A) azon közleked® egységek/emberek számát, akik a p élen f típusú járm¶vel utaznak, és xa azon folyamérték, mely a élen folyik át. költségeket tudunk felírni. Tehát
(Network Design Problem)
min
X
bp (cp T xp ) +
X
T
df y f
f ∈F
p∈P
X
bp xpa
X
uf yaf ≤ 0,
∀a ∈ A
(11)
x(δpin (u)) − x(δpout (u)) = 0,
∀p ∈ P, u ∈ V, \(O(p) ∪ D(p))
(12)
= 1,
∀p ∈ P
(13)
≥0
∀p ∈ P, a ∈ A
(14)
∈ N0 ,
∀a ∈ A, f ∈ F
(15)
−
f ∈F
p∈P
x(δpin (u))
=
x(δpout (u)) xpa yaf
Ahol a szumma els® tagja minden egyes útra a közleked®kre jutó költség, a második tag a járm¶veken es® költség.
(11) biztosítja, hogy minden élen tel-
jesüljön a kapacitáskorlát, (12) a folyamfeltétel, (13) biztosítja, hogy az el®írt közlekedési forgalom teljesüljön. (14) és (15) a nemnegativitás, és egészérték¶ségi feltételek. Azonban ez a modell nem mindig szolgáltat megfelel® eredményt. Ugyanis a kapott hálózatot a következ® fázisban (járattervezés) nem biztosan fogjuk tudni gazdaságosan felbontani, mert egyes útvonalak akár túl hosszú/rövidre sikerülhetnek.
Valamint még az is megoldandó feladat,hogy az utasok hány
átszállással fognak eljutni a célállomásukra.
7
1.5. Járattervezés Az el®z® feladatban kaptunk egy hálózatot lehetséges útvonalakkal, ezeket kell most járatokra felbontani, és meghatározni azok a gyakoriságát.
Tehát adott
egy hálózat végállomásokkal, transzfer pontokkal, és lehetséges összeköt® útvonalakkal (lehetséges azonban, hogy egyes utakat csak bizonyos járm¶típusok használhatnak), valamint az egyes utakra az el®írt forgalommal. A cél a költségek és az utazók élégedetlenségének minimalizálása (elégedettségi feltétel például: a belvárosban bárhonnan bárhova adott id® alatt avagy átszállással el lehessen jutni). Mint már az el®z® részben is megemlítettem, nem jellemz® egy hálózatot alapjaitól tervezni, sokkal inkább itt a járattervezésbe kalkulálják bele egy esetleges útvonal-módosítás költségét.
1.5.1. 1.modell Szétválasztjuk a feladatot: els® körben meghatározzuk az utasok útvonalát, és mértékét közlekedési szokásaik szerint.
Majd meghatározzuk a járatokat, és
azok gyakoriságát az ismert forgalom mellett, egy útalapú algoritmussal. Tehát legyen
l ∈ L,
az
l
L
lehetséges járat-útvonalak halmaza.
él-járat incidenciamátrix:
Legyen továbbá
Fl az l járat gyakorisága (0 ∈ Fl ). A legyen A ∈ {0, 1}AxL . És b ∈ RA a forgalom az éleken.
járatra jutó költség,
cl , az
(Line Planning Problem)
mincT x
(16)
Ax ≥ b
(17)
xl ∈ Fl És a feladat megoldása:
x
∀l ∈ L
(18)
az el®re megadott járatok gyakoriságát adja meg.
1.5.2. 2.modell A második megoldás (lásd [1]) az el®z® két fázist próbálja meg együtt megoldani egy útalapú algoritmussal, ahol az utasokat és járatokat próbáljuk összeegyeztetni.
p ∈ P potenciális járatútvonal. Egy l ∈ L járatra, mely megmondja, fogjuk-e használni az adott járatot. Az fl egész változó mondja meg az l járat p gyakoriságát (a maximum kapacitást Fl jelöli). Jelölje b azt a változót, amely p megadja p útra O(p), D(p) közötti forgalmat, P pedig tartalmazza O(p), D(p) közötti összes utat. P legyen ezek uniója, P(a) pedig azon q ∈ P melyek a ∈ A L élen átmennek. L(a) azon járatok, amelyek átmennek a élen.κ ∈ R+ adja meg a járatkapacitást. Végül da az utasonkénti költség a ∈ A élen , cl pedig a járatköltség l ∈ L járatra. Jelölje
új
xl
yp ∈ R+
a forgalmat, ahol
bináris változót vezetünk be minden
A hosszas jelölések után végre felírhatjuk a feladatot:
8
min cT x + dT y + cT f
(19)
y(P p ) = bp , X
∀OD
κl fl − y(P(a)) ≥ 0,
párra,
(20)
∀a ∈ A
(21)
l∈L(a)
f ≤ Fx
(22)
L
x ∈ {0, 1} ,
0 ≤ f ≤ F, y ≥ 0.
(23) (24)
(20) biztosítja, hogy az adott forgalmat elvezettük. (21) miatt nem lépjük át a kapacitáskorlátokat. (22) feltétel kényszeríti ki
x
változótól, hogy 1 legyen,
amikor az adott járatot betettük a megoldáshalmazba. Megjegyzés: az els® modellt inkább vasúti modellekre alkalmazható, hiszen itt az utasoknak nincs sok választása ha
A
városból
B
városba akar menni, így
itt az utasok útjainak el®re meghatározása nem nagy korlátozás. A második modell mivel nem határozza meg ezt el®re, a városi közlekedéstervezésben jobban alkalmazható. Azonban egyik modell sem veszi gyelembe, hogy az utasoknak hányszor káll átszállniuk céljuk eléréséhez. S®t, mivel csak végállomásokat és transzfer pontokat vettünk be a modellbe, így a köztes megállókat nem is határoztuk meg, amik jelent®sen befolyásolják egy járat menetidejét.
1.6. Menetrendtervezés
1.6.1. Periodikus Menetrendtervezés(Periodic Event Sheduling Problem) A periodikus menetrendek egy gyakran használt menetrend forma/tulajdonság, amikor egy menetrend során periódusonként ismétl®dnek az események. a periódus tipikusan egy óra.
Ez
Ennek az utazók számára legkézzelfoghatóbb
el®nye, hogy csak egyetlen óra menetrendjét kell az adott állomásra megjegyezni: például a Budapest-Bécs railjet mindig 'óra negyvenkor' indul Budapestr®l (és minden köztes állomáson miden óra azonos percén halad át). Az alábbi modellt Sera ni és Ukovitch [5] vezette be 1989-ben. Tehát egy periódikus modellben adott egy
T
periódusid® (ami gyakran egy óra), egy
V
események halmaza, ami általában vonatok adott állomáson való érkezési/indulási idejeinek halmaza. Meg van adva természetesen egy
A
feltételhalmaz: ami
egy eseménypárból áll, valamint minden élhez adott egy alsó-fels® korlát (ua , la :
∀a ∈ A). A célunk egy menetrend; egy olyan függvény, ami megmondja egy eseményre, mikor következzen be. Formálisan keressük
π(j) − π(i) − la (modT ) ≤ ua − la Másképpen röviden:
π
:
V → [0, T )
∀a = (i, j) ∈ A; i, j ∈ V.
π(j) − π(i) ∈ [la , ua ]modT .
9
függvényt, hogy
(25)
π(i)
la
π(j) ua
2. ábra. Illusztráció korlátokra
Def : • •
Egy ilyen
Speciálisan:
π
függvényt menetrendnek nevezünk.
la = ua
:
π(j) − π(i) = la
a = (i, j); la = 10, ua = 15
Például ha
mod és
T.
π(j) = 5.
Ekkor
π(i)
'óra 50 és
'óra 55 között következhet be.
1. Megjegyzés. ua − la
Alkalmazhatunk egy másik felírást is, ha
0 ≤ la < T
és
δa =
változókat használjuk, ekkor
π(j) − π(i) − la (modT ) ≤ δa
∀a ∈ A.
(26)
Ezen a felíráson látszik, hogy két eseményre megmondhatjuk, hogy mennyi id®
l
teljen el közöttük egy menetrendben ( a ), valamint hogy mennyire engedünk a
δ
pontosságból ( ).
2. Megjegyzés.
Ha egy adott eseményt rögzíteni szeretnénk, akkor ezt bátran
megtehetjük, ugyanis
(∀i0 ∈ V )(∀t0 ∈ [0, T ))(∀π
menetrendhez
)(∃π 0 : π(i0 ) =
t0 ). Biz:
t0
Ugyanis el tudjuk forgatni a menetrendünket: legyen
π(i0 ) = t10 . Ekkor π 0 := π + (t0 − t10 ). 0 π (i0 ) := π(i0 ) + (t0 − t10 ) = t10 + t0 − t10 = t0 .
adott, ahol
lesz, és
3. Megjegyzés.
egy menetrend,
i0 ,
Ha nem egy, hanem több eseményt szeretnénk rögzíteni, azt
is megtehetjük egy egyszer¶ trükkel. kívánt eseményt,
π
Ez ugyanúgy menetrend
t0
Válasszunk ki egy tetsz®leges
rögzíteni kívánt id®ponttal. Ekkor
i1 . . . in
i0
rögzíteni
legyen a maradék
t1 . . . tn rögzíteni kívánt id®pontokkal. Ekkor A- hoz ai := (i0 , ii ) ∀i = 1 . . . n, la = ua = ti − t0 alsó-fels® Ha van megoldás, akkor már csak az el®z® megjegyzés szerint i0 esekell forgatni t0 id®pontba, és akkor minden rögzíteni kívánt esemény
rögzíteni kívánt esemény, adjunk hozzá korláttal. ményt be
ti
n
élet:
id®pontban fog megtörténni.
Egy menetrend hasznosságát/pontosságát egy
c
költségfüggvény méri. Azaz
egy menetrend annál jobb, minél kisebb
X
ca (π(j) − π(i) − la ).
a=(i,j)∈A
10
(27)
Itt
la
helyébe
ua
is írható lenne, s®t bármely köztes szám (mod
T ),
attól
függ®en, hogy az esemény pontosságát mihez viszonyítjuk Az IP feladat felírásához egy fogalom:
1. De níció (tenzió). nak
Adott egy (
nevezünk, ha minden
C
G, A)
gráf. Egy
A→R
függvényt
tenzió-
körre az éleket irányítás szerinti el®jellel összeadva
0-t kapunk.
Mivel az eddigi képletekben
π
csak mint potenciálkülönbség jelent meg, így
érdemes bevezetni:
x ˆ0 = π(j) − π(i)
(28)
függvényt. Ez tenzió triviálisan, hiszen egy potenciálból származtattuk. Tehát az MIP (Mixed Integer Program: kevert egészérték¶ programozási feladat) probléma: minc(ˆ x
+ pT )
Γˆ x=0 la ≤ x ˆ + pT ≤ ua p ∈ ZA
1. Lemma (Sera ni és Ukovich). Q
Ha nem
menetrendet keresünk, akkor bármeny
létezik olyan is, amire
p=0
H
π : V → [0, T ),
feszít®fára bármeny
hanem
π
π:V →
menetrendhez
minden élre.
1.6.2. Pesp által fedett menetrendtervezési lépések Mivel az el®z® szekciókban meghatároztuk az utasok forgalmát, a vonatok útvonalát, és gyakoriságát, ezért ezek adottak. A három legelemibb dolog, amit modelleznünk kell, az az
•
utazás/mozgás:
•
megállás:
azaz mikor áll meg a vonat, és mennyi ideig várakozik
•
átszállás:
mennyi ideig kell várakozni ha egyik vonatról egy másikra aka-
runk átszállni.
az adott vonalon mennyi ideig megy a vonat
Adott egy minimális átszállási id®, hiszen ha a vonatok
nem ugyanazon a vágányon állnak meg, akkor az utasoknak át kell sétálniuk egyik peronról a másikra.
[1:22,1:22]
[2,6]
Budapest
[1:16,1:16] Gy®r
Bécs
3. ábra. Példa járatok modellezésére: a halvány vonal a megállási él, a vastagabb nyilak a vonat közlekedését írják le. A megállási éleknek általában pici a fesztávja: azaz a minimum és maximum várakozási id® közötti különbség, hiszen egy sok helyen megálló vonatnál ezen
11
fesztávok összeadódnak, tehát a modell felírása után az indulási id® ismeretében még csak körülbelül sem tudnánk, mikor érkezik meg a vonat. Ezért érdemes ezt a fesztávot nagy állomásoknál picire venni, kis állomásoknál nullára venni (azaz megmondjuk el®re, mennyi ideig várakozik a vonat). További el®nye a
0
fesztávnak, hogy ilyenkor a modellünket tovább tudjuk
egyszer¶síteni. Hiszen legyen élt
j
a = (i, j) 0 fesztávú él. j minden élét ua = la
csúccsal, éspedig úgy, hogy
intervallumot eltolunk).
Ekkor összehúzhatjuk az értékkel eltoljuk (minden
Továbbá párhuzamos él elhagyható, ha intervalluma
a1 = (i, j), a2 = (i, j)
tartalmazza a másik intervallumot (azaz
[la2 , ua2 ] ekkor a2 elhagyható). Ha k vonat közlekedik egy
és
[la1 , ua1 ] ⊆
adott vonalon, és egy egyenletes/kiegyensúlyo-
zott menetrendet szeretnénk, könnyen megtehetjük ezt: vegyünk egy új élet az indulási csúcstól
[la , ua ] = [T /k, T − T /k]
korlátokkal. Ez az él "kényszeríti" a
vonatokat egyenl® id®közönként indulni. Az egyszer¶ség kedvéért tegyük fel, hogy minden vonat mozgási tulajdonságra ugyan olyan típusú: azaz ugyanolyan a gyorsulása, végsebessége stb.
Követési távolság:
A biztonságos közlekedés céljából bizonyos esetekben
szükség van követési távolság beállítására. él felvételével tudjuk megtenni
[l, T − l]
Ezt természetes módon egy plusz
intervallummal, azon vágány elejéhez,
vagy végéhez toldva, amit több vonat használ. Így biztosan nem lesz ütközés, hiszen a vonatok ugyan olyan sebességgel közlekednek, azaz nem tudják megel®zni egymást, és a követési távolságot is betartják a biztonsági él bevezetése miatt. Szembemen® forgalom esetén a legegyszer¶bb példa: Tegyük fel, hogy a hármas metró felújítása során az egyik alagutat teljes egészében lezárják a Deák Ferenc tér t®l Újpest-Központ ig.
Ezért ezen a szakaszon csak az egyik alag-
útban közlekedik a metró (oda-vissza).
Itt a menetid® 16 perc a megfordu-
lási id® 4 perc, és egy 2 perces biztonsági távolságot szeretnénk minden szerelvény között.
Ekkor egy új élet veszünk fel Újpest-Központ-nál az alábbi
[la , ua ] = [2, T − (16 + 16)] = [2, T − 32]
korlátokkal.
Amennyiben egy vonat,f egységgel gyorsabb egy másik vonatnál, úgy
f, T − d]
[d +
korlátokat kell közéjük tenni, hogy betartsuk a biztonsági rést.
Biztosan tapasztaltuk már, hogy ha egy kétsávos útból lezárnak egy sávot, és egy sávon engedik a forgalmat, akkor nem a felére, hanem annál nagyobb mértékben visszaesik az út kapacitása. S®t és nem is mindegy, a váltakozó forgalmat hogyan szabályozzuk. Ha ugyanis a forgalmat "csomókban" engedjük (azaz egy irányból egyszerre többet is), adott id® alatt nagyobb forgalmat tudunk átengedni, mintha egyesével engednénk az autókat/vonatokat. De nem csak egyirányú útszakaszokra, hanem többsebességes útszakaszokon (ahol ICE/IC és személyvonat is egy vágányon közlekedik) is célszer¶ "csomósítani" a vonatokat. Tehát nem mindegy, milyen sorrendben indítjuk a vonatainkat, mert ett®l függ®en a menetrend optimalitása is változhat. Szerencsére a
P ESP
modellbe ezt is könnyen belevehetjük. Vegyünk ugyan-
is fel egy plusz csúcsot, és
i1 , ..., in ∈ V
a "csomósítani kívánt vonatok" azon
idejét jelzi, amikor a közös vágányra lépnek. A plusz csúcsból vegyünk minden
12
Bp
Északi
Déli
Északi
Bp
[5,10] [2,58]
[5,10]
Déli
4. ábra. Példa járatok szétkapcsolására
i1 , ..., in
csúcsba egy élet
[0, T /2 − t]
korlátokkal, ahol
t
a vágányon az adott
vonatok menetideje (csak azonos tulajdonságú vonatokat szoktunk "csomósítani"). És így nem is kell meghatároznunk a "csomósított" vonatok sorrendjét, amit esetleg már egy fels®bb tervezési szinten hoztunk. Egy vasúthálózatban el®fordulhatnak olyan megoldások is, hogy egy vonatszerelvényt egy állomáson
szétvágnak két szerelvénnyé, és más útvonalon folyösszecsatlakoztatják ®ket Gon-
tatják útjukat, vagy fordítva, két külön útról
doljunk csak Budapest-Balaton útvonalakra:
Északi-Déli part szerint szét is
bonthatnák a szerelvényeket, és így az utasoknak nem kellene átszállniuk. Ez üzemeltetési költségek szempontjából is meggondolandó, de sokkal inkább túlterhelt útvonalakon lehet hasznát venni, hiszen két külön vonat között akár több perc biztonsági rés is lehet, míg ha összekapcsoljuk ®ket; 0. Az ábra mutatja, egy ilyen összekapcsoló csúcsot csak szét kell szedni 3 csúcsba, két átszállási él id®korlátja természetesen adódik, míg a harmadik él behúzásával biztosítjuk, hogy például 2 perc biztonsági réssel induljanak el az állomásról.
S®t ezzel a megoldással még csak a szétkapcsolt vonatok indulási
sorrendjét sem kellett meghatároznunk.
13
1.7. A járm¶vek elosztása Ez a negyedik tervezési lépés, amely már az operációs tervezési fázisba esik. Általában egy x menetrenddel dolgozunk, azaz az egyes járatokra meg van határozva a kezdeti- és végállomás, valamint az induló, és érkez® buszok id®pontja is.
A járm¶veink kezdetben, és a munka befejeztével (ugyan abba) a
garázsba térnek vissza. A célunk az, hogy költséghatékonyan határozzuk meg az egyes buszok feladatait/útvonalait, hogy minden menetrend szerinti járaton egy (és csak egy) járm¶ haladjon végig, miközben ez a közlekedési társaságnak a legkevesebb költségbe kerüljön (például: minimális járm¶ üzembe helyezése, minimális üzemanyag fogyasztása stb.). Tehát a feladataink, amelyeket el kell végezni, két helykoordináta (kiindulási és végcél) valamint két id®koordináta (kiindulási és végcél id®pont) jellemzi. Ezeket
menetrend szerinti járatoknak (timetable trip) nevezzük. Hogy üres járatok adják meg a kapcso-
ezeket el lehet-e végezni egymás után, az latot.
Tipikusan ilyen járat a garázs, és az els®/utolsó járat közötti út, ezt
pull-in/pull-out trip -nek nevezi a szakirodalom.
De természetesen az is üres
járat nak min®sül, ha a végállomáson megfordul a járm¶.
Nem minden járm¶ közlekedhet minden útvonalon (a csuklós busz nem közlekedhet kis utcákon, hanem a nagyforgalmú járatokat kell szolgálnia).
S®t
minden garázsra meg van határozva, milyen típusú járm¶vek parkolhatnak itt, és típusonként vagy összesen adva van egy kapacitáskorlát. Egy járm¶ végállomások közötti üres járat ok és menetrend szerinti járat ok egymásutáni f¶zését blokkoknak hívjuk. Egy közlekedési társaságnak az alábbi költségei keletkezhetnek: x költség a járm¶venként (fenntartási, tárolási, lízing költség), valamint a garázson kívül töltött id® és távolság függvényében további költségek (emberi er®forrás, üzemanyag stb.). Összefoglalva célunk tehát egy blokkokból álló olyan halmaz meghatározása, mely elvégzi az összes feladatot, miközben az említett költségeket minimalizálja.
Modell:
Legyen
G = (V, A), ahol a csúcsok menetrend-szerinti útvonal aknak, da költséggel (minden da ∈ A
az élek pedig az üres útvonal aknak felelnek meg,
élre). Természetesen a menetrend-szerinti útvonal aknak is meghatározhatnánk költséget, de mivel úgyis mindegyiket teljesíteni kell, ezért nincs értelme ebbe a modellbe bevenni. Legyen
Ag
azon élek halmaza, melyeken a
járm¶vek haladhatnak. Azon éleket, amelyek és
g
v
g
depóból induló
csúcsból be- illetve kiindulnak,
depóból induló járm¶vek haladhatnak rajta,
in/out
δg
-nak jelöljük.
Tehát formálisan a feladatunk: (Járm¶elosztás) min
dT y
y(δgin (v)) − y(δgout (v)) = 0 y(δgin (v)) y(δgout (v))
∀v ∈ V \ {s, t}, g ∈ G ∀v ∈ V
=1 ≤ kg
∀v ∈ V, ∀g ∈ G A
y ∈ {0, 1}
Lényegében egy többtermékes folyamot írtunk le, itt az els® három feltétel ezt fejezi ki. A negyedik feltétel pedig a depó tárolási kapacitása.
14
4. Megjegyzés.
Lehetséges a járm¶vek elosztását összevonni/beleépíteni a me-
netrendtervezésbe, hogy még optimálisabb/költséghatékonyabb közlekedési rendszert kapjunk.
Például megengedhetünk a menetrendben kisebb módosításokat
(shiftelés).
1.8. Személyzetelosztás Az eddigiekben sikeresen megalkottunk egy közlekedési hálózatot, meghatároztuk a járatok útvonalát, menetrendjét, és végül pedig a rendelkezésre álló járm¶veket beosztottuk menetrend szerint. Már csak az emberi er®forrás elosztása maradt. Ez nagyon hasonló az el®bb tárgyalt problémához, azonban mivel nem gépekr®l beszélünk, más korlátozásokat kell gyelembe vennünk. Mint például megfelel® pihen®id® közbeiktatása, az esetleges x munkaid® betartása, vagy esetleg túlórák minimalizálása, és egyéb munkaügyi el®írások betartása. Továbbá a járm¶vezet®knek egyéb feladatokat is el kell látniuk, mint a járm¶ átnézése (sign in/o time), üzembe helyezése, különböz® naplók vezetése, az utazásra való felkészülés (lásd például légitársaságok pilótái).
1.8.1. Rotáció Az el®bbi rész után azt gondolhatnánk, hogy most már nincs mit szervezni a személyzeten, azonban ez nem így van.
Ugyanis beosztottuk a személyzetün-
ket feladatokra, az igényeiknek, és a jogszabályoknak megfelel®en. Azonban a feladatokat névtelen sof®röknek osztottuk be. Ez azért probléma, mert el®fordulhat, hogy egy sof®r egyik nap sokáig dolgozik,akkor másnap nem kezdhet túl korán, hiszen pihen®id®re van szüksége. Ezért egyes közlekedési társaságok úgynevezett rotációs rendszerben osztják be járm¶vezet®iket (lásd 1.8.1 ábra).
1
Hétf®
Kedd
Szerda
Csütürtök
Péntek
Szombat
éjszakás
éjszakás
nappali
nappali
délel®tti
délel®tti
éjszakás
éjszakás
nappali
nappali
délel®tti
délel®tti
éjszakás
éjszakás
nappali
nappali
délel®tti
éjszakás
éjszakás
nappali
nappali
éjszakás
éjszakás
nappali
éjszakás
éjszakás
2 3 4
délel®tti
5
délel®tti
délel®tti
6
nappali
délel®tti
délel®tti
7
nappali
nappali
délel®tti
délel®tti
8
éjszakás
nappali
nappali
délel®tti
Vasárnap
éjszakás délel®tti
1. táblázat. Példa rotációra (A m¶szakokat rotációs rendszerben cserélik)
15
2. Nagy IP feladatok megoldása Az el®z® részben sok egészérték¶ programozási feladatot írtunk fel, ebben a részben ezek megoldásával foglalkozunk. A következ®kben, ha nem mondjuk a következ® általános egészérték¶ programozási feladattal foglalkozunk:
min
cx
Ax ≤ b
(29)
l≤x≤u xj ∈ Z;∀j ∈ S ⊆ N;
2. De níció (LP fízibilis megoldás). csak az optimalitást nem teljesít®
x
3. De níció (IP fízibilis megoldás). feladat, amely esetleg
Adott egy egészérték¶ feladat.
Ennek
megoldását fízibilis megoldásnak nevezzük.
x ∈ ZS × Rn−S ,
Adva van egy egészérték¶ programozási
azaz csak
S
indexhalmaz egészérték¶ségét
követeli meg. Ennek egy IP fízibilis (és nem feltétlen LP fízibilis) megoldása egy olyan
x
vektor, melynek
S
koordinátái egészek.
Az LP és IP fízibilis megoldást egyszer¶en fízibilis megoldásnak nevezzük.
4. De níció (lock).
Egy (29)-cel megadott IP feladat
x
megoldás
dinátához tartozó 'lock' száma azon feltételek száma, mely
xj
j -edik
koor-
kerekítése során
megsérülhetnek.
2.1. Branch and Bound Talán a legáltalánosabb ismert, egészérték¶ programozási feladatokra használt algoritmus, vagy inkább megoldási séma. A branch and bound lényege, hogy a diszkrét megoldási halmazt alproblémákra osztja/szétdarabolja ("branch"), majd elvet néhányat ("bound").
Ezt
rekurzív ismételve addig folyatjuk, amíg meg nem találjuk az optimális megoldást. Egy lehetséges séma pszeudókódja:
Data: Adatszerkezet, Az IP feladat LP relaxáltja Result: Az IP megoldása Adatszerkezet.push({LP}) while Adatszerkezet 6= ∅ do Problem=Adatszerkezet.pop() ;
if
Problem.egész() AND Problem.vizsgáld()
then
optimális megoldás frissítése;
else
xi =Problem.törtVáltozó(); P roblemi ={P roblem} ∪ { branch1 } i=1 . . . Adatszerkezet.push(P roblemi ) i=1 . . . k;
end end
k;
Algorithm 1: Branch and Bound 16
Itt persze sok múlik az adatszerkezetünkön, hogy melyik problémát fogja kiadni, amikor kérünk egyet t®le (.pop()). Példa ilyen stratégiára (verem/sor): mindig az utolsó/els® betett problémát adja vissza (ilyen típusú kereséssel mélységi/szélességi bejárást kapunk). A Problem.vizsgáld() függvény logikai érték¶ függvény, ezzel olyan ágakat vethetünk el az algoritmus során, amelyr®l már tudjuk, hogy nem fog optimális megoldást adni.
5. De níció (branch and bound fa).
Egy olyan gyökeres fa, melynek csú-
csai olyan Lp problémák, mely az eredeti Lp problémánkból kaphatunk néhány korlátozó feltétel hozzáadásával, és egy probléma leszármazottja egy másik problémának, ha származtatható néhány feltétel hozzáadásával.
Ha van jó becslésünk az adott problémára, bizonyos alproblémákat "levághatunk".
Hiszen például egy ágat levághatjuk, ha Lp relaxáltja nagyobb az
eddigi legjobb megoldás költségénél (minimalizációs problémáknál).
Ugyan-
is ezen az ágon hiába keresnénk egész megoldásokat, az LP relaxáltnál csak nagyobb-egyenl® költség¶t találhatunk, ami nagyob-egyenl® az eddigi optimális megoldásnál, így biztosan nem lesz optimális. Esetleg ha tudjuk, hogy a gyökér csúcsban az Lp relaxált jól közelíti az Ip megoldást, az olyan alproblémákat is levághatjuk, amelyek el®re megadott (mondjuk 5) százalékkal rosszabb Lp relaxálttal rendelkeznek a gyökér LP optimumnál. Ha tehát van egy közel optimális Ip megoldásunk, általában sok alproblémát "levághatunk", így gyorsítjuk algoritmusunkat. Egy ilyen megoldás megtalálására érdekében többféle stratégiánk lehet.
Például a branch and bound
fá ban szélességi bejárást végzünk. Azonban ez nagyon sok memóriát igényelhet.
Szigorúbb memóriakorlátok mellett a mélységi bejárás alkalmazása gyakoribb, valamilyen alámerülési heurisztikával.
Vagy ezeket kombinálhatjuk is:
amíg
van elég memóriánk szélességi bejárást végzünk, mikor már nem sok maradt, a kigenerált csúcsokból mélységi bejárást indítunk egymás után (a sorrendet okosan/heurisztikusan megválasztva).
2.1.1. Branch and Cut Ezt olyan feladatok megoldásánál használhatjuk, ahol nagyon sok(például exponenciálisan sok) korlátozó feltétel van.
Ennek az algoritmusnak az alapja
a branch and bound, azonban a sok korlátozó feltétel miatt az Lp megoldása hosszadalmas lehet. Ezért kezdetben sorok csak egy alkalmasan választott részhalmazával foglalkozunk.
Ha a branch and bound fá ban a részprobléma egy
megoldáshoz jutunk, akkor megnézzük, teljesíti-e az részprobléma megoldása az összes feltétel. Ha nem, akkor a részproblémához hozzáadunk néhány sért® sort,és folytatjuk az eljárást.
2.1.2. Branch and Price Tipikusan olyan feladatokra alkalmazható, melyekre nagyon sok változónk van. Ez a branch and bound egy oszlopgenerálós változata. A Branch and Cut algoritmushoz hasonlóan m¶ködik, csak a kiindulási részprobléma itt oszlopok egy
17
alkalmasan megválasztott részhalmazából áll. Az algoritmus során a rész LPhez az olyan oszlopokat vesszük hozzá, amelyeknek a redukált költsége negatív. A Branch and Price és Branch and Cut nyilván akkor m¶ködnek jól, ha az alkalmas oszlopok/sorok generálását gyorsan (polinomiális id®ben) meg tudjuk tenni, valamint a kezd®problémát jól meg tudjuk választani, amely nem túl sok oszlopot/sort tartalmaz, és viszonylag nem is kell túl sok oszlop/sorgenerálást végezni.
2.1.3. Diving heurisztikák Az el®z®ekben leírtam, miért is fontos egy fízibilis megoldást találni, minél gyorsabban, hogy a Branch and Bound minél hatékonyabb legyen. Tehát ebben a részben olyan heurisztikákat mutatok be, amely egy ilyen fízibilis megoldást talál, lehet®leg minél optimálisabbat. A heurisztikák mélységi bejárással egy fízibilis, és minél optimálisabb megoldás felé törekednek, úgy, hogy a branch and bound fában ígéretes változókat kerekítenek a megfelel® irányba. De el®tte vezessünk be néhány fogalmat az egyszer¶bb tárgyalás kedvéért:
6. De níció (legközelebbi egész). számot az
xj -hez
Legyen
xj
törtváltozó.Az
bxj + 0.5c
egész
tartozó legközelebbi egésznek hívjuk.
7. De níció (töredékrész). tévesztend® a törtrésszel) legközelebbi egészt®l való
Egy xj tört koordináta töredékrészén (nem össze|xj − bxj + 0.5c| számot értjük. Azaz a töredékrész a távolság. A továbbiakban f (xj )-ként jelöljük.
8. De níció (triviálisan le/felkerekítés). tozója triviálisan lefelé kerekíthet®, ha Hasonlóan egy
•
xj
Egy ( 29)-el adott IP egy
változó triviálisan felfelé kerekíthet®, ha
Töredékrészes módszer:
xj
vál-
A.j ≥ 0. A.j ≤ 0.
Addig branchel a minimális töredékrész vál-
tozó mentén a legközelebbi változó felé, amíg van egész változó, vagy amíg infízibilissé nem válik a megoldás.
•
Együttható módszer:
Azon koordinátát kerekítjük a megfelel® irányba,
melynek a 'lock' száma a legkisebb. Ha több ilyen is van, akkor a legkisebb töredékrész¶t választjuk.
•
Lineáris keresés:
x ˆ az branch and bound fa gyökerében lev® LP x ˜ az aktuális csúcsban lev® megoldás xj = k szerint s= x ˆx ˜ szakasz el®ször metszi az xj = k hipersíkot.
Legyen
relaxált megoldása, és kerekítünk, melyre a
•
Vectorlength módszer:
Ez a módszer Set Packing problémákra alkal-
mazható, ami a valóságban gyakran el®forduló problématípus. A Set packing probléma:
(SP P ) min
cx
Ax = 1 x ∈ {0, 1}n ahol
A ∈ {0, 1}m×n
18
Ennél a feladatnál ha egy tört változót 1-re xálunk, akkor az új Lp megoldásban legalább egy másik változó egészre (0-ra) állítódik, hiszen
A {0, 1}
mátrix, és a sorösszeg 1. Azt a
j.
koordinátát állítjuk 1-re, amire
min
([¯ xj ]∗ − x ¯j ) ∗ cj |{aij 6= 0}|
(30)
felveszi minimumát.Ahol
( [¯ xj ]∗ =
b¯ xj c d¯ xj e
if if
cj ≥ 0 cj ≤ 0
(31)
Vagyis afelé próbálunk kerekíteni, amerre a célfüggvény kevésbé romlik, és a nullára állítható változók száma egyre nagyobb (Hiszen
∀i : aij = 1 =⇒ xj = 0, mert
Pm
i=1
xj = 1 esetén
aij = 1).
Továbbá bármely eddigi heurisztikára igaz, hogy érdemes (ha lehet) bináris változók mentén kerekíteni, hiszen ez xálást jelent, így elkerülhetjük egy nem bináris változó többszöri korlátozását. Valamint bináris változók a modellekben, és az eredmény szempontjából is általában fontos szerepet játszanak. Például a járattervezés 2. modelljében (1.5.2) el®ször
x
bináris változóval eldöntöttük, az
adott járatot bevesszük-e a megoldásba, és egy másik változóval döntöttük csak el, milyen gyakorisággal közlekedik.
Így ha el®ször a bináris változók mentén
branch elünk, akkor megmondjuk, melyik járatot választjuk is be a megoldásba,
így a megmaradt jóval kevesebb járat gyakoriságait kell csak úgy megválasztani, hogy az adott forgalmat elvezessék.
5. Megjegyzés.
Az el®bbi heurisztikák akár bejárási technikák is lehetnek, hi-
szen csak azt mondták meg, egy adott csúcsában a branch and bound fának melyik ágán haladjunk egy fízibilis, vagy közel optimális megoldás megtalálása érdekében.
2.1.4. Simple Feasibility Pump A Feasibility Pump [6] fejlesztették ki el®ször bináris problémákra, majd [7] fejlesztették tovább általános egészérték¶ problémákra.
Ennek a primál heu-
risztikának a lényege, hogy két sorozatot de niál;
•
egy Lp fízibilis pontokból állót, amely általában nem IP fízibilis
•
és egy IP fízibilis pontokból állót, amely nem feltétlen LP fízibilis.
A heurisztika szerint ezek a sorozatok konvergálnak, és a határérték ezek szerint már IP, és LP fízibilis is lesz.
9. De níció ( S halmazra vett egészrész). ( S
[x] :=
[xj + 0.5] xj
19
ha ha
Legyen
j∈S j∈ /S
S ⊆ N. (32)
10. De níció ( S halmazra vett L1 távolság). δ S (x, y) :=
X
Legyen
S ⊆ N.
|xj − yj |
(33)
j∈S Valamint hasonlóan
f S (x) :=
P
j∈S
f (xj )
ahol már
f (xj )
töredékrészt már de-
niáltuk. Az eljárás menete a következ®: jük ezt
x ¯-al.
S = {
bináris változók} vagy
megoldjuk a feladat LP relaxáltját, jelöl-
Ehhez megtaláljuk a legközelebbi egész megoldást:
S = {
egész változók}.
Ha
x ˜
x ¯1
pontot.
ahol
fízibilis, megál-
lunk. Különben egy újabb LP feladat megoldásával keressük az távolság szerinti legközelebbi
x ˜ = [x]S
x ˜-hoz δ S (x, x ˜)
Majd elölr®l addig ismételjük ezt az
eljárást, amíg fízibilis megoldást nem kapunk, vagy egy bizonyos id®korlátot el nem érünk. Az algoritmus pszeudókódja:
Data: x ¯:
LP fízibilis megoldás
maxIter: maximális iterációszám
Result:
Az IP egy fízibilis megoldása, vagy hogy sikertelen volt az algoritmus
while i<maxIter do x ˜ := [¯ x]S ; if x˜ LP fízibilis
break; end
then
x ¯ = {x|δ S (x, x ˜)minimális
end
és x LP fízibilis};
Algorithm 2: Feasibility Pump
Ahhoz hogy meghatározzuk
x ¯ = {x|δ S (x, x ˜)
minimális, és
x
LP fízibilis
}
(34)
pontot, meg kell oldanunk a következ® LP feladatot: min
X
X
(xj − lj ) +
j∈S:˜ xj =uj
j∈S:˜ xj =lj
X
(uj − xj ) +
dj
(35)
j∈S:lj <˜ xj
Ax ≤ b
(36)
d≥x−x ˜
(37)
d≥x ˜−x
(38)
l ≤ x ≤ u.
(39)
Ez látszik hogy jó, hiszen a egy optimális megoldás esetén az egyiket egyenl®séggel teljesíti, így
x
valóban
x ˜-hoz
dj
(37),(38) közül
legközelebbi LP fízibilis
d-re nincs j ∈ S : lj < x ˜j < uj -
megoldás lesz. Természetesen ha az egész változóink binárisak, akkor szükségünk, ugyanis a célfüggvényben a harmadik szumma re megy, ami üres halmaz, hiszen lj , x ˜j , uj
20
∈ {0, 1},
így mindkét egyenl®tlenség
nem teljesülhet. [6] szerz®i azt javasolják, osszuk három fázisra az eljárást. Az els® fázisban csak a nem bináris egész változókat relaxáljuk így
{
bináris változók
}.
S = B :=
Az eljárás
•
vagy egy fízibilis megoldás megtalálása után áll meg,
•
vagy egy bizonyos abszolút számú iterációszám elérése után,
•
vagy egy bizonyos számú olyan iteráció után, amikor a törekékrészek összege (f
s
(x))
nem csökken mondjuk
p%
-nál nagyobb mértékben. Ezzel el-
kerülhetjük olyan megoldások keresését, amelyek csak kevéssé mozdítanak minket a kit¶zött cél irányába. A második fázisban az egész változókat akarjuk kerekíteni, azaz változók
}.
S = I := { egész
Azért választottuk szét az els® két fázist, mert abban reménykedünk,
hogy az els® fázisban sok nem bináris egész változót sikerült egészre állítani, így csak kevés új
dj
változót kell bevezetnünk.
Addig futtatjuk az eljárásunkat,
amíg egy IP, és LP fízibilis megoldást nem találunk, vagy egy bizonyos iterációs határt el nem értünk a fentiekhez hasonlóan. Az utolsó fázisban azt reméljük, hogy a második fázisban kapott
x ˜
már
majdnem fízibilis, így a környezetében találunk egy jó fízibilis megoldást.
A
környezetben lev® megoldások átvizsgálásához, az alábbi MIP problémát oldjuk meg:
min
δ I (x, x ˜) Ax ≤ b d≥x−x ˜ d≥x ˜−x l≤x≤u xj ∈ Z;
∀j ∈ I.
2.1.5. Objective Feasibility Pump A Simple Feasibility Pump a gyakorlatban elég hatékonynak bizonyult egy fízibilis megoldás megtalálásában, azonban gyenge primál megoldást nyújt. Jóllehet mert a fenti algoritmus csak kiindulása során veszi gyelembe a célfüggvényt: csak a kezdeti
x ¯
LP optimum megtalálásakor. Ezen úgy lehet segíteni, hogy a
távolságfüggvénybe beépítjük
c-t,
ezáltal remélve hogy a heurisztika jobban az
optimalitás felé mozdul. Tehát
δ S (., x ˜)-t
lecseréljük;
δ S (., x ˜)
és
c
konvex kombinációjára:
p δαS (x, x ˜)
S
:= (1 − α)δ (x, x ˜) + α
|S| T c x kck
(40)
Tehát az algoritmus ugyan az, csak más távolságfüggvényt alkalmazunk. Sajnos az optimalitás növelése a fízibilitás terhére tehet® meg. Így az algoritmus el®rehaladtával érdemes
c
α csökkentésével αi := β i valamilyen
hatását csökkenteni, ezt pedig
tehetjük meg, ennek egyik módja, ha minden
21
i
iterációban
β ∈ [0, 1)
valós számra.
δαS (x, x ˜)
c ≡ 0 vagy β ≡ 0 a Simple Feasibic ≡ 0-t azért is érdemes külön venni, mert
Természetesen
lity Pump algoritmust adja vissza (
de níciójában 0-val osztanánk ...) .
Bár a leírt algoritmus csak egy heurisztika, ezért nem is várunk t®le
mindig
megoldást, még inkább nem optimális megoldást. De van egy olyan eshet®ség, amit érdemes orvosolni, éspedig a ciklizálás.
Azaz az algoritmus visszatérése
ugyan abba a pontba. Különösen fontos ez a Simple Feasibility Pump esetében, ugyanis ha ugyanabba a
x ˜
egész változóba értünk vissza, akkor ugyanabba a
x ¯
törtváltozó lesz ehhez a legközelebb, mint az els® alkalommal. Így az algoritmus ciklizál, és nem lesz esélye egy fízibilis megoldás megtalálására.
A hibát
kétféleképpen próbáljuk orvosolni:
• x ¯ •
néhány változóját random fel-lefelé toljuk el
ha a kerekítés ismét
x ˜ lesz, akkor pedig néhány nagy töredékrész¶ változót
a távolabbi egész felé kerekítünk. Majd ezután folytatjuk az algoritmust. Az Objective Feasibility Pump is visszatérhet ugyan abba az els® és a második látogatás
it1 , it2
x ˜
csúcsba (az
iterációban történjen). Azonban a távolság-
S
δαSit2 (x, x ˜)), így a legközelebbi fízibilis csúcs x ¯ sem lesz feltétlen ugyanaz. Így tehát csak δαSit1 (x, x ˜), S (x, x ˜ ) nagymérték¶ egyezése (azaz αit1 − αit2 ≤ δ0 ; δ0 ∈ (0, 1)) során kell és δα it2
függvény nem ugyan az a két lépés során (δα (x, x ˜), és it1
a fenti javítási módszert alkalmazni.
22
2.2. Rapid Branching A Rapid Branching egy hatékony branch and bound heurisztika, amit f®leg nagyméret¶ tömegközlekedési problémák megoldására használnak. Eredetileg Weider [8] használta ezt az algoritmust összehangolt személyzet és járm¶elosztásra. De sikeresen alkalmazta Borndörfer [9] track allocation és egyéb [10] problémák megoldására is. A továbbiakban az alapproblémánk egy hálózatban éleknek valamilyen részhalmazát kell megtalálnunk (általában utak és körök unióját), valamilyen
c költ-
ségfüggvény mellett. A probléma méretét a hálózat csúcsszámában mérjük. A Rapid Branching egyik ötlete, hogy a célfüggvény ügyes módosításával a feladatott az egészérték¶ megoldások felé tereli (Perturbation Branching ). Másrészt megpróbál minél több koordinátát 1-re rögzíteni. Ezt persze nem mindig jó ötlet, ezt felügyeljük egy bináris féle kereséssel: binary search barnching. És természetesen LP approximációs technikákat is felhasználhatunk, hogy gyorsítsuk az algoritmust. A
T
min{c
x|Ax = b, x ∈ {0, 1}n }
típusú problémákkal foglalkozunk (A dekkel nagyobb, mint ciális függvénye).
m
(például
n
(41)
∈ Rm×m , b ∈ Rm ),
ahol
n
a hálózat csúcsainak lineáris,
nagyságren-
m
exponen-
Emiatt, hogy kezelni tudjuk a problémát, oszlopgenerálást
is alkalmaznunk kell az algoritmus során (a generált sorok indexeinek halmaza:
N ⊆ N).
Mivel nagy problémákkal foglalkozunk, nem nagy megszorítás, ha fel-
tesszük, hogy az LP approximáció jól közelíti az IP optimumot.
{cT x : Ax = b, x ∈ {0, 1}n }
•
(IP)(l, u) minl≤x≤u
•
(RIP)(l, u) legyen (IP)(l, u) megszorítása
•
(MLP)(c, l, u) az (IP)(l, u) probléma LP relaxáltja.
•
(RMLP)(c, l, u) (MLP)(c, l, u) megszorítása
N
koordinátákra.
N
koordinátákra.
Mint már ezel®tt megemlítettem, a célfüggvényt perturbálni fogjuk az algoritmus során (azt remélve, a perturbált célfüggvénnyel
f I (x)
csökken), ezért
kell MLP, RMLP-hez paraméterként hozzáadni egy célfüggvényt. Célunk egy minél jobb IP megoldás megtalálása, ezt egy IP(0, 1) gyöker¶ fából fogjuk indítani, melynek csúcsai IP(l, u). A fa bejárása mélységi jelleg¶, a megfelel® irányt a perturbation branch fogja megadni az adott csúcsban, azaz néhány változót xálunk
l
és
u
segítségével. Ahogyan a branch and bound
algoritmus pszeudókódjában is jeleztük, minden csúcsot analizálunk, érdemes-e ebbe az irányba tovább keresnünk egy jó IP megoldás érdekében. A perturbation branching tipikusan sok változót ad vissza (k darabot), amiket xálásra javasol. Ha kés®bb kiderül, valamiért mégsem érdemes az összes (k ) javasolt változót xálni, akkor megpróbáljuk a xálni. Ha ez is soknak bizonyul,
k/4
k/2
legígéretesebb változót
változót xálunk, és így tovább... Azaz
23
"bináris módon" próbáljuk megkeresni melyik az az
l
egész szám, amennyi vál-
tozót érdemes lerögzíteni. A Rapid Branching pszeudókódja:
Data: IP feladat, és egy δ tolerancia küszöb Result: Sikeres futás esetén x∗ megoldás, és az optimalitást bizonyító lb alsó korlát, amire fenn kell hogy álljon
S0 :=IP feladat; ub∗ := ∞; lb∗ := −∞; i := 0; while S 6= ∅ do set Ni ∈ Si /*binary search alapján*/ compute lbi ≤ minx∈Ni cT xi ; if xi ∈ Ni megoldást találtunk then ubi := cT xi ; ub∗ = min1≤k≤i ubk ; x∗ := argmin1≤k≤i cT xk ;
lb + δ ≥ cT x
;
else
ubi := ∞;
end if lbi ≥ ub∗ then Ezt az ágat nem érdemes vizsgálni:
Si+1 := Si \ Ni ;
i := i + 1;
continue; end
lb∗ := min{lbk : Nk ∈ Si }; if lb∗ + δ ≥ ub∗ then
Egy elég jó megoldást találtunk, így megállhatunk.
break; end
A perturbáció branching:
compute ∪kj=1 Qji , 1 ≤ j ≤ ki i
;
i
Si+1 = (Si \ {Ni }) ∪kj=1 Qji ; i := i + 1;
end
Algorithm 3: Rapid Branching, [10] nyomán
Mivel mi csak egy közel optimális megoldást keresünk,
Ni
szétbontásából
nem fogjuk az összeset végigvizsgálni, arra fogjuk használni a perturbation branching eljárást, hogy pár igéreteset kiválasszunk ezek közül.
2.2.1. Perturbation Branching A perturbation branching egy sor MLP-t old meg, miközben a célfüggvényt úgy változtatja (ci , i=0,1,2
. . .), hogy a megoldás egészérték¶ség felé mozduljon (pélf I (x), ami ezek szerint
dául mérjük ezt a koordináták töredékrész összegével:
csökken). Az algoritmus során azoknak a koordinátáknak a költségét csökkent-
24
jük, amelyek közel vannak egyhez. A célfüggvény perturbációja:
c0j := cj ;j ∈ N cij + 1 := cij + cj αx2j ;j ∈ N
j = 0, 1, 2, . . .
Azaz így elérjük, hogy az 1-hez közel lev® változók 1 felé mozduljanak el. A folyamat sikerességét a
v(xi ) := cT x − δ|B(xi )| méri, ahol
δ,
B(xi ) := {majdnem
1 változók}
(42)
= {j ∈ N : xij > 1 − }. Ahol δ = 1, = 0.1).
segítségével az egészérték¶séget hangolhatjuk (például
Ezt addig folytatjuk, amíg ez a tesztfüggvény csökken, ha már egy bizonyos iteráció után sem csökken, a legnagyobb olyan indexet xáljuk 1-re, és a célfüggvényét 0-ra állítjuk. Ha ez sem segít leállítjuk az algoritmust.
2.2.2. Binary Search Branching B ∗ koordináták egy halmazát jelöli ki, amit arra i ∈ B ∗ -ra xj alsó korlátját 1-re xáljuk. De mint ezt már
A preturbation branching egy javasol, hogy minden
írtam, nem mindig célszer¶ az összes változót xálni, mert így gyorsan infízibilis megoldásokhoz juthatunk, és messze kerülünk az optimális megoldástól. Ezért is építünk be egy olyan mechanizmust, ami az ilyen eltévedések után a 'megfelel®' csúcshoz vezet minket vissza.
B∗
Tehát az algoritmus során egy
K := |B ∗ |. FeltehetB ∗ a redukált költség szerint növekv®en van rendezve. Azaz i, j ∈ B ∗ T T esetén i < j =⇒ (c − A y)i ≤ (c − A y)j ha RMLP(c, l, u) (29) alakban van megadva (y a duális vektor). Ekkor
RMLP(c, l, u) csúcsban adva van egy
indexhalmaz,
jük hogy
Bk∗ := i1 ...ik
k = 1...K;
(43)
Vizsgáljuk az alábbi alproblémákat:
Pk := min {cT x : Ax ≤ b, x ∈ [0, 1]n |xj = 1, j ∈ Bk∗ } l≤x≤u
Így
PK
komplementere, ha az utolsó feltételben egy változóra is
(44)
j ∈ Bk∗ : xj = 0
áll fenn. Ezt egy egyszer¶ feltétellel is megfogalmazhatjuk:
X
∗ xi ≤ |BK |−1
i∈Bk∗ Ez azonban elronthatja a feladat szerkezetét: sokszor az oszlopgenerálás ezt a speciális szerkezetet tuja kihasználni, hogy gyorsan tudjon új oszlopot negatív redukált költséggel generálni. Ezért is inkább
|K|
részhalmazra fogjuk RMLP(c, l, u)-t szétbontani:
∗ Qk := RM LP (c, l, u) ∩ {x ∈ [0, 1]n |xj = 1, j ∈ Bk−1
25
és
∗ xi = 0, i ∈ Bk∗ \ Bk−1 }
B∗
Q1
P1
Q2
P2
Q3
P3
Q4
P4
Q5
P5
5. ábra. (Binary Search) csak a pirossal jelölt csúcsokat vizsgálja csak meg a Rapid Branching
Így tehát
∪K k=1 (Qk ∪ Pk ) =RMLP(c, l, u).
Az algoritmus során az alábbi csúcsokat fogjuk végigvizsgálni (lásd az ábra):
xj = lj = 1,j ∈ Bk∗ ;
k = K, dK/2e, dK/2e, ..., 2, 1.
Tehát a Rapid Branching algoritmusában:
∗ ∗ Si+1 = (Si \ {Ni }) ∪ {BdK/2e } ∪ {BdK/4e } ∪ ... ∪ {B2∗ } ∪ {B1∗ } szerint bontjuk szét
2K
Si + 1-et.
Így tehát ahelyett hogy sorra végigvizsgálnánk
csúcsot, csak ennek a logaritmusának megfelel® csúcsot vizsgálunk át.
26
3. Kitekintés Ezen szakdolgozat els® része csak közösségi közlekedési problémákat írt fel. Azonban a nem közösségi közlekedés is érdekes témákat rejt: mint például az autós közlekedési lámpákat hogyan állítsuk be. Hogyan állítsuk be a közlekedési lámpákat, hogy az adott menetrend szerinti busz illetve villamos járatok mindig zöld lámpát kapjanak? Ha nem lehetséges, lehet-e a menetrendet úgy módosítani, hogy ez lehetséges legyen? Meg lehet-e oldani egy adott csomópontban egy adott forgalommal, hogy semelyik autónak se kelljen lassítania amelyik ott áthalad?
Ha nem, átlagosan
mennyit kell várakoznia? A GPS-ek térnyerése kapcsán egyre fontosabb kérdés, ha mindegyik autós a legkevesebb id® alatt akar elérni kezd® és végcélja között, egy id® után mindig ugyan azon az útvonalon érdemes autóznia (szigorú Nash-egyensúly) ? Lehetséges-e bizonyos utcák kiszélesítésével, esetleg lezárásával Nash-egyensúlyt létrehozni? (lásd [11]). Az önvezet® autók szintén érdekes kérdéseket vethetnek fel. Tegyük fel, hogy az egyes résztvev®k nem törekednek saját veszteségüket/menetidejüket minimalizálni (nem 'racionálisak'), vagy esetleg hajlandóak
p% pluszveszteséget vállalni,
hogy az összforgalom gyorsuljon. Ekkor mennyire lehet felgyorsítani a forgalmat? Tehát van még mit tenni egy optimális közlekedés eléréséig...
27
Hivatkozások [1] R. Borndörfer, M. Grötschel, and M. E. Pfetsch, Computer-aided Systems in Public Transport, ch. Models for Line Planning in Public Transport,
pp. 363378. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. [2] D. Huisman, The new dutch timetable:
The or revolution, Interfaces,
vol. 39, pp. 617, 2009. [3] P. W. George B. Dantzig, Decomposition principle for linear programs, in ATMOS, 1960. [4] D. Kim and C. Barnhart, Computer-Aided Transit Scheduling: Proceedings, Cambridge, MA, USA, August 1997, ch. Transportation Service Network
Design: Models and Algorithms, pp. 259283. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. [5] P. Sera ni and Ukovich, A mathematical for periodic scheduling problems, SIAM J. Discret. Math., vol. 2, pp. 550581, Nov. 1989. [6] F. G. M. Fischetti and A. Lodi, The feasibility pump, Mathematical Programming, p. 91104, 2005.
[7] L. Bertacco, M. Fischetti, and A. Lodi, A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization, vol. 4, no. 1, pp. 63 76, 2007. Mixed Integer ProgrammingIMA Special Workshop on MixedInteger Programming. [8] S. Weider, Integration of Vehicle and Duty Scheduling in Public Transport. PhD thesis, 2007. [9] R. Borndörfer, T. Schlechte, and S. Weider, Railway Track Allocation by Rapid Branching, in 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (T. Erle-
bach and M. Lübbecke, eds.), vol. 14 of OpenAccess Series in Informatics (OASIcs), pp. 1323, Schloss DagstuhlLeibniz-Zentrum fuer Informatik,
2010. [10] R. Borndörfer, A. Löbel, M. Reuther, T. Schlechte, and S. Weider, Rapid branching, Public Transport, vol. 5, no. 1, pp. 323, 2013. [11] E. Tardos, Network games, in Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC '04, (New York, NY,
USA), pp. 341342, ACM, 2004. [12] C. Liebchen and R. H. Möhring, Algorithmic Methods for Railway Optimization: International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, Norway, September 16-17, 2004, Revised Selected Papers, ch. The Modeling Power
of the Periodic Event Scheduling Problem:
Railway Timetables and
Beyond, pp. 340. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. [13] T. Berthold, Primal heuristics for mixed integer programs, Master's thesis, Technischen Universität Berlin, 2006.
28
[14] C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance, Branch-and-price: Column generation for solving huge integer programs, Oper. Res., vol. 46, pp. 316329, Mar. 1998.
29
