LOGISTICKÉ SYSTÉMY14/15

Osnova přednáškyVýrobní logistika IIMetody rozmisťování objektů

– Metoda souřadnic– Lokace depa na vrchol– Lokace absolutního depa

Metoda souřadnic

• Metoda je vhodná především pro umísťování centrálních objektů (např. skladů)

• Cílem řešení je najít “váhový střed“ resp. těžiště, tedy souřadnice x, y tohoto objektu dle vztahů:

Kde qi je objem přepravy (za jednotku času)

i i

i

i i

i

x qx

q

y qy

q

Měření vzdálenosti objektů

• Osová vzdálenost (pro pravoúhlou oblast, šachovnicové rozmístění)

• Kvadratická vzdálenost• Přímá vzdálenost (cesty „na dohled“, volné

prostranství)• Přímá korigovaná vzdálenost (zakřivené cesty

matriálu)

i i id x x y y

2 2

i i id x x y y

2 2

i i id x x y y

2 2

i i id k x x y y

Lokace depa

• Depo - místo na síti, z kterého se provádí obsluha vrcholů a hran sítě. Depem tedy nazýváme střediska obsluhy např. sklady materiálu, střediska záchranné služby, letiště atd. – Obecně lze depo umístit do libovolného místa na síti, tedy na

hranu nebo do vrcholu. V síti je možné umístit libovolný počet dep.

– Množinu dep budeme značit Dk, kde počet dep značíme k = |Dk|.– Pro k platí: 1 ≤ k ≤ n, kde n = |V|

• Dopravní práce - udává objem přepravy, kterou je nutné vykonat při obsluze vrcholu v V resp. hrany h X obsluhované z depa v Dk. Při výpočtu dopravní práce vycházíme z úvahy, ve které se obsluhovací vozidlo musí přemístit z depa do obsluhovaného místa a po obsluze se opět po téže nejkratší cestě vrátí do depa. Projetou vzdálenost násobíme váhou obsluhovaného vrcholu resp. hrany.

Příklad lokace depa

Ohodnocení hran sítě představuje délku úseku v desítkách kilometrů a ohodnocení vrcholů sítě udává množství vyrobeného materiálu. Určete, v kterém z vrcholů sítě je optimální umístění centra, aby se minimalizovaly celkový hmotový tok (resp. dopravní práce).

Příklad lokace depa

• K výpočtům hledajících optimální umístění střediska v síti při minimalizaci celkového objemu přeprav je potřeba znát údaje o vzdálenosti vrcholů u, v zadané síti.

• Je třeba sestavit – matici minimálních vzdáleností vrcholů– matici vzdáleností vrcholů k hranám sítě (v

případě obsluhy hran sítě)

Příklad lokace depa

Příklad lokace depa

Cílem této úlohy je minimalizovat celkový objem přeprav (hmotového toku). Kritériem pro určení optimálního umístění depa na vrcholově ohodnocené síti je dopravní práce, kterou vypočteme podle vztahu:

( ) 2. ( , ). ( , )kf D d u v w u v Optimálním umístěním k dep na síti jsou vrcholy v pro které je hodnota dopravní práce minimální ze všech možných kombinací umístění k dep na síti:

( ) min ( )k kf D f D

Příklad lokace depa

• Lokační problém je NP obtížná kombinatorická úloha.• Obecně se při určení optimálního umístění k dep na síti

neporovnávají hodnotící kritéria pro všechny existující kombinace řešení vzhledem k rychle rostoucí početní náročnosti s rostoucí velikostí sítě a počtu dep.

• Úlohy hledání optimálního umístění k dep se proto řeší heuristickými algoritmy

• Zadaná síť v tomto příkladu není rozsáhlá. Hodnotu dopravní práce proto určíme pro všechny varianty řešení. K určení vzdáleností d(u, v) použijeme matici vzdáleností mezi vrcholy.

Příklad lokace depa

Dopravní práce pro možnost umístění střediska do vrcholu v1 je:f(D1´) = 2×0×6 + 2×2×2 + 2×3×5 + 2×3×3 = 56

Dopravní práce pro možnost umístění střediska do vrcholu v2 je:f(D2´) = 2×2×6 + 2×0×2 + 2×1×5 + 2×4×3 = 58

Dopravní práce pro možnost umístění střediska do vrcholu v3 je:f(D3´) = 2×3×6 + 2×1×2 + 2×0×5 + 2×5×3 = 70

Dopravní práce pro možnost umístění střediska do vrcholu v4 je:f(D4´) = 2×3×6 + 2×4×2 + 2×5×5 + 2×0×3 = 102

Optimálním umístěním jednoho depa v zadané síti je vrchol, pro který:f(D1) = min {56, 58, 70, 102} = 56

Optimální umístění jednoho depa v síti je ve vrcholu v1.

Lokace absolutního depa

• K vyhledání absolutního depa slouží Hakimiho algoritmus (HA).

• HA řeší problematiku umisťování havarijních středisek. – Vrcholy v dané dopravní síti reprezentují

místa vzniku negativních událostí. Úkolem je umístit v této síti obslužné středisko, které bude tyto negativní události likvidovat.

Lokace absolutního depa

• Pojmy:– Excentricita vrcholu u (maximální obslužná vzdálenost, resp.

vzdálenost k nejvzdálenějšímu vrcholu od vrcholu u):

– Lze jí získat odečtením maximální hodnoty v matici vzdáleností na daném řádku pro daný vrchol u.

vudueVv

,max

,

Lokace absolutního depa

• Pojmy:– Vážená excentricita vrcholu u (maximální

obslužná náročnost):

– kde w(v) je váha vrcholu (počet obsluh za nějaké stanovené období).

,

vudvwuecVv

,max

Lokace absolutního depa

Vážená excentricita obecného místa y v síti:

Lokace absolutního depa

• Vzdálenostně optimálně umístěné depo je depo považujeme za vzdálenostně optimálně umístěné v případě, leží – li ve vrcholu v*, pro jehož váženou excentricitu platí:

• Absolutně vzdálenostně optimálně umístěné depo (absolutní depo) je depo považujeme za absolutní tehdy, leží-li v místě sítě, pro jehož váženou excentricitu platí:

vecvecVv

min*

.

yecyecGy

min*

.

Hakimiho algoritmus

• Algoritmus vyhledává na každé hraně grafu místo (resp. místa) s minimální váženou excentricitou a z těchto nalezených vybereme to, pro které bude vážená excentricita minimální, v tomto místě umístíme depo.

Hakimiho algoritmus

yk

Vb

VaVi

e

ibbkiakaiVv

k vvdvyevvdyvevwyeci

,,;,,minmax

ibiaabiVv

k vvdevvdeCvwyeci

,;,minmax

Je-li , potom:k be e y v

Hakimiho algoritmus

• Hakimiho algoritmus zavádí symboly Ti a Ti´, což jsou funkční zápisy vážených excentricit. – Ti je zápisem vážené excentricity při obsluze

přes vrchol vb, – Ti´ je zápisem vážené excentricity při obsluze

přes vrchol va .

,

,

i i b i

i i ab a i

T w v e d v v

T w v C e d v v

Hakimiho algoritmus

• Příklad - viz soubor – LogistickeSystemy_AdP14.doc