Szállításszervezési módszerek A „megtakarítási” eljárás kiterjesztése
1
Néhány alapvető szempontot a járatkapcsolás előtt figyelembe kell venni. 1. Akkor célszerű a járatokat összekapcsolni, ha ezzel költséget (távolságot, időt, járművet stb.) takarítunk meg. 2. Akkor lehet a járatokat összekapcsolni, ha
•az alkalmazott jármű alkalmas mindkét küldemény továbbításához, •a járatok időben egymás után végrehajthatók (a kapcsolást árufogadási vagy árufeladási „időablak” problémák nem gátolják), •a járatok összekapcsolása belefér a napi foglalkoztatási időbe, •a jármű időben érkezik meg a telephelyre (pihenőidő!),
•az összekapcsolást nem akadályozzák előírások, szabályok (pl. járműtisztítás)
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
2
A „Megtakarítási” eljárást (Savings módszer) a körjáratok szerkesztésére Clarke-Wrigt dolgozta ki (1962-ben).
A megtakarítási elv - általánosított megfogalmazásban - kiválóan alkalmazható a járatkapcsolási feladatok gyors, jó eredményességű megoldásához. A megtakarítás (út, idő, költség stb.) általánosított felírása a következő: Tegyük fel, hogy XS pontból XD pontba, továbbá YS pontból YD pontba kell
Xs
XD
egy-egy rakományt szállítanunk, amint azt
YS
az ábra mutatja. Ha a két járatot összekapcsoljuk, üres járműfutás takarítható meg. Ez a következő: Mxy = L (XDG) + L (GYS) - L (XDYS)
G
YD
Ha az „S” és „D” indexű pontok egybeesnek, akkor az eredeti, körjáratokra felírt megtakarítás formulát kapjuk!
A már ismert eljárásnak megfelelően a megtakarításokat minden lehetséges járatpárosításra el kell készíteni. A programozás , mint a körjáratszerkesztés esetében, szintén a legnagyobb megtakarítási helyen kezdődik.
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
3
Az eljárás megismeréséhez vegyünk fel egy mintapéldát. Legyenek az ellátandó egyszerű járatok a következők! Összesen 6 egyszerű járatot kell tehát elvégezni, a G telephelyen lévő járművekkel. AS BD BS
Feltételezzük, hogy a járatok összekapcsolhatók.
FS
AD
A távolságokat az alábbi mátrix tartalmazza.
CD ES DS
FD
G CS DD
ED
G AD BD CD DD ED FD
G A S B S CS 0 60 55 25 45 70 55 60 0 80 60 65 5 25 105 55 45 80 135 95 90 50 85 105 110
DS 70 100 110 50
ES 40 70 85 35 30
45 120 90
FS 35 45 45 25 65 90
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
4
Tegyük fel, hogy a „G” telephelyen 2 tehergépjármű áll rendelkezésre. Mindegyik jármű legfeljebb 3 rakott menetet teljesíthet, utána vissza kell térnie a garázsba. A távolságmátrixban piros színnel G AS BS CS DS ES FS tüntettük fel a járatok hosszát. G 0 60 55 25 70 40 35 A megtakarítás mátrix elemeit a AD 45 80 70 55 100 70 45 következőképpen számítjuk:
BD CD DD ED FD
60 0 80 80 60 65 5 90 25 105 55 45 80 135 95 90 50 85 105 110
AS AD BD 120 CD DD ED FD
BS
CS 5
15
DS
110 50 100 45 120
ES
85 45 35 25 30 65 90 90 90 110
FS
Ha a B és C járatokat akarjuk ebben a sorrendben összekapcsolni, akkor a BD -ből való visszatérés (60), a CS -be való kimenetel (25) megtakarításaiból kivonjuk
a BD -ből CS -be való átállás távolságát (80) Az eredmény 5, amit a megfelelő helyre beírunk. Gyakorlásképpen figyelje meg a BA és az EC összekapcsolásakor elérhető megtakarítások számítását! 80 +25 - 90 = 15 60 +60 - 0 = 120
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
AS
BS 30
CS 15 5
DS 15 20 80
AD BD 120 CD 55 110 DD -20 25 5 ED 5 40 15 105 FD 25 0 -35 0
ES 15 15 65 35 0
FS 35 50 70 -5 25
5
Folytatva a számítást a balra lévő megtakarítás-mátrixot kapjuk. Egyes járatok összekapcsolása kifejezetten nem tanácsos, hiszen ekkor az úthossz növekedni fog. Ezeket piros színnel jelöltük. Az összekapcsolás algoritmusa a következő:
Megkeressük a legnagyobb megtakarítást (ez 120 egység, az BA kapcsolat esetén). Töröljük a kapcsolt járatok adatait (BD sorát, mert innen már nem mehetünk máshova) és a AS oszlopát, mert ide már nem érkezhetünk meg máshonnan. Töröljük a „rövidzár” elemét, ADBS -t, hogy BA után ne kapcsoljuk esetleg AB-t! Megvizsgáljuk, hogy korlátok nem akadályozzák-e a kapcsolatot, illetve, hogy a program még folytatható-e. Ha a program folytatható, akkor megvizsgáljuk, hogy a létrehozott BA járatpár elé, vagy mögé célszerű-e további járatot kapcsolni. Az AD sorát és az BS oszlopát kell megvizsgálni, s a legnagyobb elemet kiválasztani. Látható, a legnagyobb elem a CDBS helyen van, ezért a jármű programja a következő: G … CSCD … BSBD … ASAD … G
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
AS
BS 30
CS 15 5
DS 15 20 80
AD BD 120 CD 55 110 DD -20 25 5 ED 5 40 15 105 FD 25 0 -35 0
ES 15 15 65 35
FS 35 50 70 -5 25
6
Folytatva a még lehetséges elemekre, a következő legnagyobb érték 105, mégpedig az ED járatok összekapcsolásakor.
Töröljük a megfelelő sort és oszlopot és kizárjuk a a DE kapcsolat létrehozásának lehetőségét.
0
Megvizsgáljuk, hogy az E elé vagy a D mögé indokolt-e a megmaradt F járat beiktatása. Mivel az DF negatív eredménnyel jár, ezért nyilván az FE kapcsolatot fogadjuk el. Ez egyébként nem jár megtakarítással. A második gépkocsi programja tehát a következő lesz: G … FSFD … ESED … DSDD … G
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
7
Nézzük most meg a „térképen”, hogy milyen programokat állítottunk össze!
Az első gépkocsi a következő feladatot látja el: G … CSCD … BSBD … ASAD … G A második jármű programja pedig az alábbi. G … FSFD … ESED … DSDD … G AS BD Megfigyelhető, hogy az első jármű programjában alig van üres futás. BS
FS AD
Ha minden járatot külön-külön láttunk volna el, az üres futások összege 605 km-t tett volna ki. (Ellenőrizd!) Az elkészített 2 kapcsolt járatban az üres futás jelentősen 285 km-re csökkent. (Számold ki!)
CD ES DS
FD
G CS DD
ED
Az eredmény a korlátozó feltételektől is függ. Ha például egyetlen, 6 rakott menetet tartalmazó kört engedtünk volna meg, még jobb eredményt kaptunk volna.
Ha megnézzük, hogy a jármű egy ilyen kapcsolt járatban milyen útvonalon haladt végig, akkor láthatóan egy sokszögű alakzatot látunk. Ezeket a kapcsolt járatokat ezért SOKSZÖGJÁRATOKNAK is hívják.
Szállításszervezési módszerek - Járatkapcsolás A „megtakarítási” eljárás kiterjesztése
8
A bemutatott feladat természetesen megoldható optimumra is (Krekó-Szántó).
G G AD BD CD DD ED FD Ig
AS
BS
CS 1
DS
ES 1
1 1 1 1 1 21
1
1
1
1
1
FS Kap 21 1 1 1 1 1 1 1 1
Kezdjen az első gépkocsi a CS pontban. A C rakott menet teljesítése után megérkezik a járat végpontjába, CD-be, ahonnan a táblázatunk szerint BS -be kell üresen átállnia.
Az optimális programot a mellékelt táblázat mutatja.
Az üres járat kibocsátási „kapacitások”, kivéve a telephelyet, ahonnan 2 kocsit indítunk - minden járatvégponton egységnyiek, mert mindenhova csak egy járat ment rakottan. Az üres járat „igények” is egységnyiek, mert mindenhonnan csak egy járat indul.
Innen A következik, de innen nem tudunk G-be menni, F-be kell mennünk. A másik járat ( G - E - D - G) meghatározását már nem mutatjuk be. (Készítsd el!)
Hasonlítsd össze a két eljárás előnyét, hátrányát!
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
9
Jordan és Burns publikált (1984-ben) egy olyan „megtakarítási” elven alapuló eljárást, amely oda-vissza irányú járműkiterhelések (járatkapcsolatok) létrehozásához különösen jól alkalmazható.
A javasolt heurisztika szerint azokat a járatokat kell "párosítani", amelyek a legnagyobb várható üres futás megtakarításához vezetnek. Tegyük fel, hogy az R1 és R2 árukibocsátó helyekről az X és Y vevőkhöz kell árut szállítani. Ha nincs járatkapcsolás - vagyis pl. a két cég egymástól függetlenül oldja meg a feladatot - a járművek a szállítások befejezése után üresen térnek vissza a kiindulóhelyre. Az üres futás:Fü=L(XR2) + L(YR1) X Y Az üres futás megtakarítás, ha a járatokat összekapcsoljuk, azaz Y-ból nem az R1-be, hanem R2-be megyünk, a következő: R1
R2
S(X,Y)=L(XR2) + L(YR1) - L(YR2) - L(XR1)
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
10
A legjobb járatkapcsolásokhoz először kiszámítjuk az összes lehetséges útmegtakarítást, majd azok közül a legnagyobb megtakarítást ígérő párokat kapcsoljuk össze. A járatvégpontok távolságait az 3-1
1-3
1-1
1-4
2-2
3-2 R1 2-3
R2 1-2
3-3 2-4
Az R2,3-1 reláció távolsága (5) azt mutatja, hogy 3-1-től milyen messze van R2.
R3
2-1 R1-ből indulók
egyes raktáraktól (járatkibocsátó helyektől) az alábbi táblázat tartalmazza. A távolságok szimmetrikusak. R1,1-3 távolsága (6) ezért megegyezik 1-3,R1 távolságával. Ez tulajdonképpen a rakott menet hossza. R2-ből indulók
R3-ból indulók
1-1 1-2 1-3 1-4 2-1 2-2 2-3 2-4 3-1 3-2 3-3 R1 2 6 6 8 10 12 3 7 9 3 6 R2 8 6 5 2 4 3 6 8 5 5 9 R3 10 2 9 8 3 7 5 3 11 7 5
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere R1-ből indulók
11 R2-ből indulók
R3-ból indulók
1-1 1-2 1-3 1-4 2-1 2-2 2-3 2-4 3-1 3-2 3-3 R1 2 6 6 8 10 12 3 7 9 3 6 R2 8 6 5 2 4 3 6 8 5 5 9 R3 10 2 9 8 3 7 5 3 11 7 5
Így például az R3,3-1 és R2,2-4 járatok összekapcsolása esetén a következő lenne az üres futás megtakarítás: S(3-1,2-4)=11 + 8 - 5 - 3 = 11
2-1 2-2 2-3 2-4 3-1 3-2 3-3
1-1
3 1 6 8 3 1-2
4 2 1 1-3
0 9 7 2 0 1-4
7 3 2-1
2 2-2
7 3 2-3
11 7 1 2-4
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
12
A legnagyobb megtakarítást az előzőek szerint a 3-1 és a 2-4 járatok összekapcsolásakor kapjuk.
2-1 2-2 2-3 2-4 3-1 3-2 3-3
1-1
3 1 6 8 3 1-2
4 2 1 1-3
0 9 7 2 0 1-4
7 3 2-1
2 2-2
7 3 2-3
11 7 1 2-4
Kihúzzuk a 3-1 sorát és a 2-4 sorát, oszlopát. A megmaradt pozitív megtakarítások közül most a legnagyobb (9) a 2-3 és az 1-4 járatok összekapcsolásával adódik. A megfelelő sor és oszlop törlése után a 3-2 és az 1-2 járatok kapcsolása következik. Miután több pozitív megtakarítás nincs, a programozás befejeződött, a többi járat összekapcsolása nem célszerű.
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
13
Ábrázoljuk a „térképen” a készített programokat!
3-1 1-3
1-1
1-4 2-2
3-2 R1 2-3 3-3 2-4
R3
A másodikat R2-ből indítjuk (sárga vonal). A harmadik szintén R3-ban kezd (barna vonal).
R2 1-2
Az első kapcsolt járat R3-ból indul (fekete vonal).
2-1
Figyelje meg, hogy a járatok a másik - kapcsolt - raktárból is indulhatnának, az eredmény nem változna.
Ez lehetőséget ad a programozónak arra, hogy a gépkocsit a legmegfelelőbb pontról indítsa.
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
14
Ez a feladat is megoldható optimumra a Krekó-Szántó féle módszerrel. Tekintve, hogy az üres járat „kibocsátó” helyek a rakott menetek végpontjai, ezért a távolságmátrixot 90°-kal elforgatva írjuk fel. R1 1-1 2 1 1-2 6 1-3 6 1-4 8 2-1 10 2-2 12 2-3 3 1 2-4 7 3-1 9 3-2 3 1 3-3 6 1 Igény 4 3
R2 8 6 5 1 2 1 4 3 1 6 8 5 1 5 9 4
R3 Kap 10 1 2 1 1 9 1 8 1 3 1 1 7 1 5 1 3 1 1 11 1 7 1 5 1 3 2 11
A szállítási probléma megoldása után az optimális szétosztási programot piros számokkal jelöltük. Ebből a táblázatból a járatokat azonban másként kell „kiolvasni”, mint amint azt eddig megismertük.
A járatkapcsolásokat most ugyanis ott hozhatjuk létre, ahol a programozott érték nem a járatot kibocsátó raktár oszlopában van. Így például az 1-1 járat végpontjából a program szerint R1-be kell menni, ami azt jelent, hogy a járat üresen visszatér a kiindulási helyére, másként: nem történik járatkapcsolás.
Az 1-2 járat végpontjából viszont R3-ba mentünk, s innen akár a 3-2, akár a 3-3 járattal visszatérhet R1-be.
Mi a 3-2 járatott választottuk.
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
15
Az első járatpár tehát R1,1-2 …R3,3-2…R1 A következő program: R1,1-3 …R2,2-3…R1
R1 R2 1-1 2 1 8 1-2 6 6 1-3 6 5 1 1-4 8 2 1 2-1 10 4 2-2 12 3 1 2-3 3 1 6 2-4 7 8 3-1 9 5 1 3-2 3 1 5 3-3 6 1 9 Igény 3 2 1 43 2
R3 Kap 10 1 2 1 1 9 1 8 1 3 1 1 7 1 5 1 3 1 1 11 1 7 1 5 1 2 1 11
Ezután az 1-4 ből a kijelölt program szerint átállunk R2-be. Innen azonban már nincs visszaút az optimális megoldás szerint R1-be, mert ezt az előbb „elhasználtuk”. Emiatt tovább kell mennünk R3-ba (például az R2-ből induló 2-1 járat végpontjából, mert innen a 3-3járat befejezése után, már R1 következhet. A harmadik jármű programja tehát: R1,1-4 …R2,2-1…R3,3-3 … R1
Még egy járatpárt tudunk létrehozni: R2,2-4 …R3,3-1 … R2
A Jordan-Burns algoritmussal elkészített járatok 38 egység üres futással oldotta meg a feladatot, az optimális eredmény 37. (Ellenőrizze!)
Szállításszervezési módszerek - Járatkapcsolás Jordan-Burns módszere
16
Ábrázoljuk a „térképen” a készített programokat!
3-1 1-3
1-1
1-4 2-2
3-2 R1 2-3 3-3 2-4
R2 1-2
R3
Az első kapcsolt járat R1-ből indul (barna vonal). A másodikat is R1-ből indítjuk (fekete vonal).
A harmadik szintén R1-ben kezd, s három rakott menetet tartalmaz (sárga vonal). Most van egy negyedik kapcsolás is, ez a jármű az R3-ból indul (kék vonal).
2-1
Figyelje meg, hogy a járatok a másik - kapcsolt - raktárból is indulhatnának, az eredmény nem változna. Ez lehetőséget ad a programozónak arra, hogy a gépkocsit a legmegfelelőbb pontról indítsa.
Kedves hallgatóm! Jó tanulást kívánok.
Ha a bemutatóban bármilyen hibát talál, vagy az anyaggal kapcsolatban észrevétele van, kérem, küldjön e-mailt! Segítségét előre is köszönöm. Hirkó Bálint
[email protected]
2012.03.06.
17