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 "
j " n
1 # Q= i
qij
n: objektumok
# n
qij az i-edik állomásból j-edik állomásba ϑ idő alatt elszállítandó egységrakomány,
• útmátrix: 1 "
L=
j " n
1 # i # n
A ij
n: objektumok
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 "
j " n
1⎡ #⎢ ⎢ R=i⎢ ⎢ #⎢ n ⎢⎣
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦
rij
1. Feltétel:
rij = Integer! i ∈ {1, 2" n} j ∈ {1, 2" n}
Kilépő járatok száma: n
si = ∑ rij j =1
i ∈ {1, 2" n}
Beléptető járatok száma: n
f j = ∑ rij i =1
j ∈ {1, 2 " n}
2. Feltétel:
si = f j i ∈ {i, 2" 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 ⎤ ⎢#⎥ G ⎢ ⎥ r = ⎢ ri ⎥ ⎢#⎥ ⎢ ⎥ ⎢⎣ rn ⎥⎦
b)
gyűjtőjárat: →sorvektor G r T = ⎡⎣ r1 " rj " 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 ↓
T ( p) =
Lk ( p ) = Min !
„ LK ” körút hossza Célfüggvény: n
n
LK ( p ) = ∑∑ A 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: 1 2 3 4 1 ⎡0 2 ⎢2 R= ⎢ 3 ⎢2 ⎢ 4 ⎣1
1 0 1 2
2 1 0 0
2⎤ 1⎥ ⎥ 0⎥ ⎥ 0⎦
Képezhetők a sor és az oszlopok összegek:
1 ⎡ 5⎤ 2 ⎢4⎥ s= ⎢ ⎥ 3 ⎢ 3⎥ ⎢ ⎥ 4 ⎣ 3⎦
ill. f T = [5; 4; 3; 3]
Euler gráf:
4 1
3 2
Egy lehetséges üresjárat nélküli megoldás: 1→2→4→1→4→2→3→2→1→4→2→1→1→3→1→3→1
