JÁRATTERVEZÉS
Járattípusok Kapcsolatok szerint: Sugaras, ingajárat:
Vonaljárat:
Körjárat:
Targoncás járattervezés egyszerű modellje Feltételek:
• az anyagáram determinisztikus, • a beszállítási és kiszállítási időpont nem kötött a ϑ időszak alatt bármikor megtörténhet, • járatkapacitás állandó: C0, • útvonal választható, • várakozási felrakásnál ill. lerakásnál nincs tv=0, • járműpark homogén, • rakodási idő állandó: tR=állandó.
Kiindulási adatok a járatkezeléshez: • anyagáram mátrix 1 L
j L n
1 M Q= i M n
qij
n: objektumok
qij az i-edik állomásból j-edik állomásba ϑ idő alatt elszállítandó egységrakomány,
• útmátrix: 1 L L=
j L n
1 M i
l ij
n: objektumok
M n
lij az i-edik állomásból j-edik objektumba a legrövidebb úthossz. • Járatkapacitás: C0 egy járat által elszállítandó mennyiség.
Járattervezés célfüggvénye:
T( p) = th ( p) + tü ( p) + tw( p) + tR ( p) = Min! T ( p) ahol: a ϑ feladatok összes komponensei:
idő alatt elvégzendő szállítási időszükséglete, amelynek
th ( p ) a hasznos járatidők összege, tü ( p ) az üresjárati idők összege,
tw ( p ) a rakodóhelyeken fellépő rakodási idők összege,
tR ( p ) a rakodóhelyen a rakodási idők összege, p
a rakodóhelyek felkeresésének sorrendjére képzett változat jele.
A hasznos és üresjárati idők:
Lh th = v Lü tü = v Modell változatok az R mátrix alakulásától függnek.
a) Üresjáratok nélkül megvalósítható járatok 1 L
j L n
1⎡ M⎢ ⎢ R=i⎢ ⎢ M⎢ n ⎢⎣
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦
rij
1. Feltétel:
rij = Integer! i ∈ {1, 2L n}
j ∈ {1, 2L n}
Kilépő járatok száma: n
si = ∑ rij j =1
i ∈ {1, 2L n}
Beléptető járatok száma: n
f j = ∑ rij i =1
j ∈ {1, 2 L n}
2. Feltétel:
si = f j i ∈ {i, 2L n}
Ha a feltételek teljesülnek, akkor a járatok Euler gráfot alkotnak
Járatokból képzett Euler gráf tulajdonságai: – csúcsok a rakodóhelyek, i rij=2
j
rij=3
– élek a járatok vagyis ha i-ből j-be pl.: 3 járat, a j-ből az i-be 2 járat fut, akkor a gráfban i csúcsból a j csúcsba 3 él, a j csúcsból az i csúcsba 2 él fut, – ha élek mentén képezzük a járatokat vagyis minden élen egyszer és csakis egyszer haladunk át a gráfon maradhatna minden állomásba az előírtak szerint járhatunk el. A célfüggvény általános alakja:
T( p) = th ( p) + tü ( p) + tw( p) + tR ( p) = Min! A fentiek alapján tehát az üres járat elkerülhető.
Lü( p) = 0 Mivel Lh(p)=állandó vagy nem függ a sorrendtől, továbbá tR(p)=állandó, tw=0, így
T ( p) = állandó Vagyis a T(p) összidő nem függvénye a járatváltozatnak. Több féle járatváltozat vezet üresjárat nélküli megoldáshoz. (Lásd 1. példa)
b. Üresjárat úthossz minimalizálással megoldandó targoncás járatok rij = Integer !
si ≠ f j j ∈Θ ≠ 0 ahol Θ azon rakodóhelyek halmaza, ahol a befutó és kifutó járatok száma eltérő.
si>fj-nél si=fj-nél si
befutó üresjárat hj = si-fj hj = 0 hj = 0
kifutó üresjárat di = 0 di = 0 di = fj-si
Az üresjáratok száma: n
n
i =1
j =1
m = ∑ d i = ∑ h j = állandó
Célfüggvény általános alakja:
T( p) = th ( p) + tü ( p) + tw( p) + tR ( p) = Min! mivel Th ( p) = állandó, Tr ( p) = állandó, Tw = 0 T ( p ) → Tü ( p ) = Min!
amely visszavezethető: Tü ( p ) =
Lü ( p ) → Lü ( p ) = Min! v
vagyis az üresjárati úthossz minimalizálását kell elvégezni.
Minimális üresjárati úthossz: k m
Lü ( p ) = ∑ ∑ lij' xij = Min! i =1 j =1
lij'
a redukált útmátrix, törölni kell az eredeti lij'
útmátrix azon sorát, ahová nincs befutó üresjárat, ill. azon oszlopot, ahonnan nincs kifutó üresjárat. Keressük: xij mátrixot, ahol xij az i-edik állomásból a j-edik rakodóhelyre menő üresjáratok száma.
Feltételek: xij =Integer! k
∑x i =1
ij
m
∑x j =1
ij
= hj
( j = 1...m)
= di
(i = 1...k )
A redukált útmátrix képzése: lij' = 0 ha h j = 0 vagy d j = 0 ellenkező esetben
lij' = lij ha h j > 0 vagy d j > 0 Az optimalizálás a lineáris programozás egy speciális feladatára a „szállítási feladatra” vezethető visza, amely az un. „magyar módszerrel” megoldható. (Lásd 2. példa)
c. Körjáratok tervezése (gyűjtő- és elosztójárat) R mátrix degenerálódik: a)
elosztójárat:→oszlopvektor ⎡ r1 ⎤ ⎢M⎥ r ⎢ ⎥ r = ⎢ ri ⎥ ⎢M⎥ ⎢ ⎥ ⎢⎣ rn ⎥⎦
b)
gyűjtőjárat: →sorvektor r r T = ⎡⎣ r1 L rj L rn ⎤⎦
Egy járattal megoldható: n
n
i =1
j =1
r0 = ∑ ri ≤ 1; r0 = ∑ rj ≤ 1
„p” járattal oldható meg: n
n
i =1
j =1
r0 = ∑ ri > 1; r0 = ∑ rj > 1
Szükséges járatszám: p ≥ Entier ⋅ r0 + 1
T ( p ) = th ( p ) + tü ( p ) + tw ( p ) + tR ( p ) tw ( p ) = 0 tü ( p ) = 0 tR ( p ) = állandó T ( p ) = th ( p ) = Min ! LK ( p ) = Min ! v ↓ Lk ( p ) = Min !
T ( p) =
„ LK ” körút hossza Célfüggvény: n
n
LK ( p ) = ∑∑ l ij xij = Min ! j =1 i =1
xij
1 0
Feltétel: n
∑ xij = 1 i =1 n
∑ xij = 1 j =1
Egy járattal megoldható gyűjtő vagy elosztó járatok: START
Képezzük az útmátrix oszlopösszegeit Vesszük a legnagyobb oszlopösszegeket adó 3 rakodóhelyet Az oszlopösszegek csökkenése sorrendjében körutat képezünk és meghatározzuk a körút hosszát B igen
A
Van-e még bevonandó rakodóhely?
nem
Kiíratás
STOP
(Lásd 3. példa)
1. Példa: Bemenő adatok: ⎡ 0 20 40 40 ⎤ ⎢ 40 0 20 20 ⎥ ⎥ Q=⎢ ⎢ 40 20 0 0 ⎥ ⎢ ⎥ ⎣ 20 40 0 0 ⎦
⎡ 0 30 40 80 ⎤ ⎢30 0 30 60 ⎥ ⎥ L=⎢ ⎢ 40 30 0 40 ⎥ ⎢ ⎥ ⎣80 60 40 0 ⎦
C0 = 20 t,
v = 80 km/óra, tr = 0, 25 óra, ϑ = 16 óra, ϕ = 0, 9
Üresjárat nélküli megoldhatóság ellenőrzése: ⎡0 ⎢2 R=⎢ ⎢2 ⎢ ⎣1
1 0 1 2
2 1 0 0
2⎤ ⎡5⎤ ⎥ ⎢4⎥ 1⎥ T ; sor- és oszlopösszegek vektorai: s = ⎢ ⎥ , f = [5 4 3 3] , ⎢3⎥ 0⎥ ⎥ ⎢ ⎥ 0⎦ ⎣3⎦
Mivel teljesül mindkét feltétel, így a feladat megoldható üresjárat-nélküli járattervvel. Képezzünk a járatokból Euler-gráfot:
Célfüggvény értékének kiszámítása: n
tH ( p) =
n
∑∑ r l i =1 j =1
v tÜ ( p ) = 0 óra, tW ( p ) = 0 óra, n
ij ij
=
730 = 9,125 óra, 80
n
t R ( p ) = ∑∑ rij tr = 3, 75 óra, i =1 j =1
T ( p) = t H ( p ) + tÜ ( p ) + tW ( p ) + t R ( p ) = 12,875 óra ⎡ T ( p) ⎤ ⎡12,875 ⎤ K 0 = k0 ( ⎢ + 1) = k0 ( ⎢ + 1) = k0 ⎥ ⎥ ⎣ 14, 4 ⎦ Entier ⎣ ϑϕ ⎦ Entier
Feladat megoldásának generálása (egy lehetséges járatterv, minimális járműszám): Egy lehetséges üresjárat nélküli megoldás: 1→ 2 → 4 →1→ 4 → 2 → 3 → 2 →1→ 4 → 2 →1→ 3 →1→ 3 →1
A járatterv végrehajtásához szükséges minimális szállítójármű-szám: ⎡ T ( p) ⎤ ⎡ 12,875 ⎤ Z =⎢ +1 = ⎢ +1 = 1 ⎥ ⎥ ⎣16*0,9 ⎦ Entier ⎣ ϑϕ ⎦ Entier
2. Példa: Bemenő adatok: ⎡0 ⎢0 ⎢ Q=⎢0 ⎢ ⎢ 40 ⎢⎣ 0
40 0 80 40 20
60 20 0 ⎤ 40 60 80 ⎥⎥ 0 20 40 ⎥ ⎥ 40 0 20 ⎥ 40 100 0 ⎥⎦
C0 = 20 t,
⎡ 0 15 12 7 25⎤ ⎢14 0 6 8 13 ⎥ ⎢ ⎥ L = ⎢10 5 0 12 8 ⎥ ⎢ ⎥ ⎢ 5 6 15 0 6 ⎥ ⎢⎣12 8 10 5 0 ⎥⎦
v = 80 km/óra, tr = 0, 25 óra, ϑ = 16 óra, ϕ = 0, 9
Az üresjáratok számának meghatározása Képezzük az R mátrixot és sor- és oszlopvektorait. ⎡0 ⎢0 ⎢ R = ⎢0 ⎢ ⎢2 ⎢⎣ 0
2 0 4 2 1
3 2 0 2 2
1 3 1 0 5
0⎤ 4 ⎥⎥ 2⎥ ; ⎥ 1⎥ 0 ⎥⎦
⎡6⎤ ⎢9 ⎥ ⎢ ⎥ s = ⎢7 ⎥ , ⎢ ⎥ ⎢7 ⎥ ⎢⎣8 ⎥⎦
f = [ 2,9,9,10] , T
Meghatározzuk a be- és a kifutó üresjáratok vektorát: ⎡0⎤ ⎢0⎥ ⎢ ⎥ d = ⎢ 2 ⎥ és h jT = [ 4, 0, 0, 0,1] ⎢ ⎥ ⎢ 3⎥ ⎢⎣ 0 ⎥⎦
Képezhető a szükséges üresjáratok száma: n
n
i =1
j =1
m = ∑ di = 2 + 3 = ∑ h j = 4 + 1 = 5
Minimális üresjárati össz úthosszat biztosító relációkénti üresjárati számok optimalizálása A d ill. h jT vektorok nullát tartalmazó sorainak ill. oszlopainak megfelelő sorokat és oszlopokat töröljük az L mátrixból és így megkapjuk a redukált útmátrixot: P1
P5
P3 ⎡10 8 ⎤ P4 ⎢⎣ 5 6 ⎥⎦ Az üresjáratok relációnkénti értékelése a d és h T vektorok kielégítésére a következő L' =
egyenletek adódnak:
x31 + x35 = 2 x41 + x45 = 3 x31 + x41 = 4 x35 + x45 = 1
A fenti egyenletrendszerek nem függetlenek egymástól ezért két megoldás adódik:
1. változat
2. változat
1 5
1
3 ⎡2 0⎤ x' = ⎢ 4 ⎣ 2 1 ⎥⎦
5
3 ⎡1 1 ⎤ x '' = ⎢ 4 ⎣3 0 ⎥⎦
Az 1. változatnál az üresjárati úthossz a (6) szerint: L 'ü = 2 ⋅10 + 0 ⋅ 8 + 2 ⋅ 5 + 1⋅ 0 = 36km
A 2. változatnál az üresjárat úthossz: L "ü = 1⋅10 + 1⋅ 8 + 5 ⋅ 5 + 0 ⋅ 6 = 33km
Mivel L"ü < L'ü , ezért a 2. változat adja az optimális megoldást. Az optimális járatterv egy változatainak meghatározása A 2. változat szerinti optimális üresjárati elosztást figyelembe véve előállítjuk a korrigált járatszám mátrixot, amelyre fenn áll, hogy r31' = r31 + x31 = 0 + 1 = 1 r35* = r35 + x35 = 2 + 1 = 3 r41* = r41 + x41 = 2 + 3 = 5 r45* = r45 + x45 = 1 + 0 = 1
A mátrix további elemei változatlanok. Vagyis rij* = rij kivéve az r31* , r35* , r41* és r45* elemeket. Így előállítható a korrigált járatszám mátrix: ⎡0 ⎢0 ⎢ R = ⎢1 ⎢ ⎢5 ⎢⎣0
2 0 4 2 1
3 2 0 2 2
1 3 1 0 5
0⎤ 4 ⎥⎥ 3⎥ ⎥ 1⎥ 0 ⎥⎦
⎡6⎤ ⎢9⎥ ⎢ ⎥ s* = ⎢ 9 ⎥ ⎢ ⎥ ⎢10 ⎥ ⎢⎣ 8 ⎥⎦ i, j ∈ {1; 2;...;5}
f
Látható, hogy si* = f T * ha i = j vagyis a járattervezés visszavezethető egy Euler-gráfra:
A kapcsolódó Euler gráf
T*
= [ 6,9,9,10,8]
A járatterv egy lehetséges változata
1→ 4 →1→ 4 → 5 → 4 → 5 → 2 → 5 → 2 →1→ 4 → 5 → 2 →1→ 4 → 5 → 2 → 4 → 5 → → 3 → 5 → 3 → 5 → 3 → 4 → 3 → 4 → 2 → 3 → 2 → 3 → 2 → 3 →1→ 3 →1→ 4 → 2 → → 4 → 2 → 3 →1
A járatterv végrehajtásához szükséges minimális szállító járműszám: ⎡ t ( p ) + tÜ ( p ) + tr ( p ) ⎤ Z =⎢ H ⎥ ϑ ⋅ϕ ⎣ ⎦ Entier
⎡ 353km ⎤ ⎢ 80 km + 0 + 2 ⋅ 42 ⋅ 0, 25h ⎥ h ⎥ +1 = ⎢ = [1, 765]Entier + 1 = 2 db 16h ⋅ 0,9 ⎢ ⎥ ⎢⎣ ⎥⎦ Entier
3. Példa Bemenő adatok Anyagáram vektor ⎡ 1 2 3 4 5 6⎤ t qT = ⎢ ⎥ ⎣0, 4, 1, 7, 4, 3 ⎦ 16óra 1 ⎡0 ⎤ 2 ⎢⎢ 4 ⎥⎥ 3 ⎢ 1⎥ t q= ⎢ ⎥ 4 ⎢ 7 ⎥ 16óra 5 ⎢4⎥ ⎢ ⎥ 6 ⎢⎣ 1⎥⎦
A minimális úthosszak mátrixa P1 P1 ⎡ 0 P2 ⎢⎢10 P ⎢14 L= 3⎢ P4 ⎢ 26 P5 ⎢15 ⎢ P6 ⎣⎢ 8
P2
P3 P4 P5
P6
8⎤ 0 10 18 23 16 ⎥⎥ 10 0 12 13 6 ⎥ ⎥ 18 12 0 17 18 ⎥ 23 13 17 0 7 ⎥ ⎥ 16 6 18 7 0 ⎦⎥ 10 14 26 15
10 km
Cv = 20t
További adatok:
v = 80km / ó tri = 0,05 + 0,25γ i
ϑ = 16óra
Ellenőrizzük, hogy a kitűzött feladatot 1 körjárattal megoldható-e ezért képezzük a járatszám vektorokat.
⎡1
2
3
4
5
6 ⎤
γ =⎢ ⎥ ⎣0, 0,2, 0,05, 0,35, 0,2, 0,15 ⎦ ⎡ 0 ⎤ ⎢ 0,2 ⎥ ⎢ ⎥ ⎢ ⎥ 0,05 γT = ⎢ ⎥ ⎢0,35 ⎥ ⎢ 0,2 ⎥ ⎢ ⎥ ⎢⎣ 0,15 ⎥⎦
és kiszámítjuk n
γ 0 = ∑ γ i = 0,95 < 1 i =1
A feladat 1 körjárattal megoldható. Képezzük az útmátrix oszlopösszegét: P1
P2
P3
P4
P5
P6
s = [73, 77, 55, 91, 75, 55 ]
Az oszlopösszegek • csökkenő sorrendjében az állomások: SR1 = ( P4 ; P2 ; P5 ; P1; P3 ; P6 ) • növekvő sorrendjében az állomások: SR 2 = ( P6 ; P3 ; P1; P5 ; P2 ; P4 ) Keressük meg az optimális körjáratot először az útmátrix oszlopösszegének csökkenő, majd másodszor növekvő sorrendnek. A. Útmátrix csökkenő meghatározása
oszlopösszegének
sorrendjéből
kiinduló
körjárat
Válasszuk ki a legnagyobb három útmátrix oszlopösszegű állomást és határozzuk meg a köztük lévő utakat az I. mátrixból: (Az úthosszak 10-zel szorozva km-ben értjük) P4 → P2 → P5 → P4 LK 1 = 18 + 23 + 17 = 58
Válasszuk meg, hogy a sorrendbe következő állomás az előzőekben megállapított járatba a legkisebb útkövetelmény mellett hová illeszthető be. P1
a1
P4
P2
∆L = / 26 + 10 − 18 = 18
P5
∆L = /10 + 15 / − 23 = 2
P4
∆L = /15 + 26 / − 17 = 24
P1
b1
P2 P1
c1
P5
Mivel a b. változat útnövekménye a legkisebb, így a P1 üzem a P2 és P5 üzemek közé illeszthető be legkedvezőbben. Vagyis a bővített járat: P4 → P2 → P1 → P5 → P4 LK 2 = 18 + 10 + 15 + 17+ = 60
A fenti elvek szerint vonjuk be a sorrendben következő üzemet a P3 -t és vizsgáljuk meg a lehetséges variációkat: P3
a2
b2
c2
P4
P2
∆L = /12 + 10 / − 18 = 4
P1
∆L = /12 + 10 / − 18 = 4
P5
∆L = /14 + 13 / − 15 = 12
P3 P2 P3 P1 P3 P
4 ∆L = /13 + 12 / − 17 = 8 d2 A legkisebb útnövekmény a P4 és P2 üzemek közé illeszthető be a P3. A bővítet járat:
P4 → P3 → P2 → P1 → P5 → P4
LK 3 = 12 + 10 + 10 + 15 + 17+ = 64
Végül nézzük meg a P6 üzem járatba kapcsolását. A járatba való kapcsolás lehetséges változatai: P6
a3
b3
c3
d3
P4
P3
∆L = /18 + 6 / − 12 = 12
P2
∆L = / 6 + 16 / − 10 = 12
P1
∆L = /16 + 8 / − 10 = 14
P5
∆L = / 8 + 7 / − 15 = 0
P6 P3 P6 P2 P6 P1
További variáció /P4-P5 közé kapcsolás/ vizsgálat fölösleges, mert d, variációtól nem lehet kedvezőbb. Az optimális körjárat: P4 → P3 → P2 → P1 → P6 → P5 → P4
Az optimális körjárat hossza:
LK = (12 + 10 + 10 + 8 + 7 + 17 )10 = 640km
A körjárat az induló pont felírva: P1 → P6 → P5 → P4 → P3 → P2 → P1
B. Útmátrix növekvő oszlopösszegének sorrendjéből kiinduló körjárat meghatározása Válasszuk ki a legkisebb három útmátrix oszlopösszegű állomást és határozzuk meg a köztük lévő utakat az L mátrixból. P6 → P3 → P1 → P6
Határozzuk meg a körút hosszát az útmátrix felhasználásából: LK 1 = ( 6 + 14 + 8 ) 10 = 280km
Keressük meg a soron következő P5 állomás helyet: P5
a1
P6
P3
∆L = / 7 + 13 / − 6 = 14
P1
∆L = /13 + 15 / − 14 = 14
P6
∆L = /15 + 7 / − 8 = 14
P5
b1
P6 P5
c1
P1
Mivel mind 3 változat azonos az első változatot választjuk: P6 → P5 → P3 → P1 → P6 LK 2 = K K 1 + 140 = 420km
Keressük a soron következő P2 állomás helyét P2
a2
P6
P5
∆L = /16 + 23 / − 7 = 32
P3
∆L = / 23 + 10 / − 13 = 20
P2
b2
P5
P2
c2
P3
P1
∆L = /10 + 10 / − 14 = 6
P6
∆L = /10 + 16 / − 8 = 18
P2
d2
P1
A P2-t a P3-P1 közé helyezzük, mert ez esetben legkisebb a körúthossz növekmény. A bővített körút felépítése: P6 → P5 → P3 → P2 → P1 → P6
amely úthossza
LK 3 = ( LK 2 + 160 ) = 420 + 60 = 680km
Az utolsó P4 állomás helyét keressük: P4
a3
P6
P5
∆L = /18 + 17 / − 7 = 28
P3
∆L = /17 + 12 / − 13 = 16
P2
∆L = /12 + 18 / − 10 = 20
P1
∆L = /18 + 26 / − 10 = 34
P6
∆L = / 26 + 18 / − 8 = 36
P4
b3
P5 P4
c3
P3 P4
d4
P2 P4
e4
P1
A legkisebb útnövekményt P5-P3 között P4 elhelyezés adja. A teljes körút felépítése P1 → P6 → P5 → P4 → P3 → P2 → P1
A teljes körút úthossza:
LK 4 = ( LK 3 + 160 ) = 640km
