Hlavní práce4628_xdemj03.pdf, 879.3 kB Stáhnout

V PRAZE

FAKULTA INFORMATIKY A STATISTIKY KATEDRA EKONOMETRIE

Název bakalářské práce:

Rozvozní úloha s dělenou dodávkou (Split delivery vehicle routing problem)

Vedoucí bakalářské práce: prof. RNDr. Jan Pelikán, CSc.

Prohlášení:

Prohlašuji, že jsem bakalářskou práci vypracoval samostatně, s využitím odborné literatury uvedené v seznamu použité literatury.

V Praze dne 18. 12. 2006

_________________________

Jiří Demeš

Poděkování:

Děkuji prof. RNDr. Janu Pelikánovi, CSc. za odborné vedení práce a mnoho cenných rad a podnětů.

OBSAH

1. CHARAKTERISTIKA ROZVOZNÍ ÚLOHY --- 4

1.1. Vymezení úlohy s nedělenou dodávkou --- 4

1.2. Vymezení úlohy s dělenou dodávkou --- 4

1.3. Faktory ovlivňující rozvozní úlohu v praxi --- 5

1.4. Cíl bakalářské práce --- 6

2. FORMULACE PROBLÉMU A UVEDENÍ PODMÍNEK --- 7

2.1. Obecná symbolika a formulace VRP --- 7

2.2. Obecná symbolika a formulace SDVRP --- 8

2.3. Dělení dodávky k-tého řádu --- 9

2.4. Potenciální úspory z dělení dodávky --- 9

3. DEMONSTRACE PŘÍKLADÚ A JEJICH MOŽNÁ ŘEŠENÍ ---11

3.1. Optimální řešení SDVRP s jedním dělením dodávky ---11

3.2. Úloha s optimálním řešením bez dělení dodávky ---12

3.3. Úloha s optimálním řešením s větším počtem zákazníků obsloužených dělenou dodávkou ---14

4. EXPERIMENTÁLNÍ POROVNÁNÍ VRP A SDVRP UKAZUJÍCÍ NA URČITÉ ZÁKONITOSTI ---16

4.1. Ukázka empirických studií rozvozní úlohy a z toho vyplývajících poznatků ---16

4.2. Rozvozní trasy a jejich specifika ---17

4.3. Vliv odchylky požadavků ---19

4.4. Vliv velikosti průměrného požadavku ---20

5. ZÁVĚR ---22

SEZNAM POUŽITÉ LITERATURY ---23

1. CHARAKTERISTIKA ROZVOZNÍ ÚLOHY

Rozvozní úloha je v dnešní době často řešeným problémem. Obzvláště se pak zvedl zájem o rozvozní úlohu s dělenou dodávkou. Je to vyzývavá varianta dopravního systému s velikým potenciálem pro praktické využití. Tento problém je teoreticky zajímavý a řešení často nebývá snadné. Redukce rozvozních nákladů je jedním z nejdůležitějších faktorů pro společnosti uvažujících vstoupit do tohoto oboru podnikání. Zde je třeba doplnit, že se může jednat i o svozní úlohu, která pracuje na stejném principu. Rozdíl je v tom, že se zákazníkům nedováží zboží, ale odebírá se od nich, například odpad. Snížení nákladů lze v určitých případech dosáhnout pomocí dělené dodávky. Je zde však patrné, že se tím zvyšují nároky na administrativu a účetnictví, popřípadě na časové rozložení rozvozu. Společnosti tak musí zhodnotit obě strany pohledu na tento problém.

1.1. Vymezení úlohy s nedělenou dodávkou

Rozvozní úloha je všeobecný název pro úlohy, kde je zapotřebí uspokojit požadavky určitého počtu zákazníků pomocí vozidel s danou kapacitou, přičemž jednotlivé požadavky zákazníků jsou předem dány. U úloh s nedělenou dodávkou je podmínka, že každý ze zákazníků může být obsloužen právě jedním vozidlem.

Hlavní úkol je pak minimalizovat celkovou trasu najetou jednotlivými vozidly. Jedná se o standardní problém operačního výzkumu, který má v dnešní době velké využití a je předmětem mnoha studií.

1.2. Vymezení úlohy s dělenou dodávkou

U rozvozní úlohy s dělenou dodávkou je odstraněna podmínka, že každý zákazník smí být obsloužen právě jedním vozidlem. Je tedy možné, v případech kdy požadavek převýší kapacitu vozidla dokonce nutné, aby některý ze zákazníků byl obsloužen více vozidly. Tato změna umožňuje v určitých případech dosáhnout značných úspor, a to jak v najeté vzdálenosti, tak i v počtu použitých vozidel. Záleží samozřejmě také na tom, u jakého zákazníka dojde k dělení dodávky. Je logické, že dělení na rozlišných místech bude mít za následek i různé celkové rozvozní náklady.

Je tedy důležité, aby vše bylo řádně naplánováno a rozvoz byl tak co nejefektivnější.

Rozvozní úloha bez dělené dodávky bude dále v práci označována zkratkou VRP, z anglické terminologie Vehicle Routing Problem. Rozvozní úloha s dělenou dodávkou, tedy Split Delivery Vehicle Routing Problem, bude označována SDVRP.

1.3. Faktory ovlivňující rozvozní úlohu v praxi

Poznatky z praxe ukazují, že rozvozní úloha obsahuje mnoho omezení, se kterými se společnost musí vyrovnat. Například délka pracovní doby řidičů nebo časový interval, po který je zákazník ochoten převzít dodávku. Tato omezení můžeme klasifikovat podle toho, zda se jedná o omezení na straně zákazníků nebo na straně vozidel. Je důležité si uvědomit, že jednotlivé případy nemusí nastat, ale obecně je užitečné vzít v úvahu i ty případy, které mohou potenciálně nastat.

Vozidla

¾ Každé vozidlo má určitou kapacitu, obvykle počítáno v hmotnosti nebo objemu, pro náklad, který má vézt. Tankery vezoucí benzín jsou omezeny co do objemu, autobusy jsou zase omezeny v počtu cestujících.

¾ Každé vozidlo má určitý časový limit na cestu z depa k zákazníkovi a zpět, obvykle vyhovující pracovní době řidiče.

¾ Každé vozidlo má časový interval, v kterém musí opustit depo, obvykle z důvodu uvolnění místa pro přijíždějící vozidla pro doplnění zboží.

¾ Každé vozidlo má stanovený počet časových intervalů, během kterých musí mít volno.

¾ Každé vozidlo se opotřebovává z důvodu doručování dodávek.

Zákazníci

¾ Každý zákazník má nějaký požadavek, který musí být splněn. Obvykle se jedná o čistě rozvozní operace, například doplnění zboží do obchodů. Existují však i operace spojené pouze se sběrem, zde se tedy jedná o svoz. Například sběr odpadu nebo výběr poštovních schránek. Někdy je objem dopředu přesně určen, zde se jedná o deterministický případ. V situaci, kdy objem dodávky není předem určen, se jedná o stochastický případ.

¾ Každý zákazník má počet časových intervalů, během kterých se dodávka, popřípadě sběr, může vyskytnout. Zákazník může například převzít zboží v době od 12.00 hod. do 13.00 hod. nebo od 15.30 hod. do 17.00 hod. Tyto dva časové intervaly se nazývají časová okna zákazníka. Tato časová okna si zákazník obvykle upravuje podle své pracovní doby, podle toho jak jsou pro něj výhodná. Z hlediska rozvozní společnosti to snižuje flexibilitu rozvozu a zvyšuje nároky na plánování rozvozu.

¾ Zákazník může, ale i nemusí být ochoten převzít zboží dopravované dělenou dodávkou. V těchto případech se většinou nejedná o stejné časové intervaly.

1.4. Cíl bakalářské práce

Cílem této bakalářské práce je popsat VRP a SDVRP. Uvést možné postupy řešení a poukázat na situace, kdy je výhodné využít dělení dodávky a kdy nikoliv.

Zároveň to bude dokumentováno ukázkovými příklady, numerickými výpočty a grafy.

2. FORMULACE PROBLÉMU A UVEDENÍ PODMÍNEK 2.1. Obecná symbolika a formulace VRP

V této podkapitole je vymezen matematický model úlohy. Každý zákazník smí být obsloužen pouze jedním vozidlem, dodávku nelze dělit. Model úlohy lze vyjádřit takto:

^ij (1)

n i

n j

ij

x

∑ ∑ c

=1 =1

min

1 , 2 , 3 ,..., ,

(2)

1

n j

x

n i

ij

= =

∑

=

1 , 2 , 3 ,..., ,

(3)

1

n i

x

n j

ij

= =

∑

=

u

_i

+ q

_j

− V ( 1 − x

_ij

) ≤ u

_j

, i = 1 , 2 ,..., n , j = 2 , 3 ,..., n , i ≠ j ,

₍₄₎

u

₁

= 0 , u

_i

≤ V , i = 1 , 2 ,..., n ,

(5)

q

_i

≤ V , i = 1 , 2 ,..., n ,

(6) Binární proměnná xij znamená rozhodnutí, zda pojedu z uzlu i do uzlu j či nikoliv a nabývá hodnot 1 nebo 0. Matice se značí C a platí, že C = {cij} udává vzdálenost v kilometrech. Podmínka (1) je účelová funkce, která minimalizuje skutečný počet najetých kilometrů. Podmínky (2) a (3) zajišťují, že se do každého uzlu pojede a zároveň z každého uzlu vyjede. Podmínka (4) zabraňuje parciálním cyklům. Podmínka (5) zajišťuje, že obsah nákladu musí být menší nebo roven, než je kapacita vozidla. Podmínka (6) zajišťuje, aby i-tý požadavek nepřesahoval kapacitu vozidla.

2.2. Obecná symbolika a formulace SDVRP

V tomto modelu je odstraněna podmínka qi ≤ V. Za situace kdy qi > V je třeba některé zákazníky obsloužit prostřednictvím několika tras. V situaci, kdy platí vztah qi < V není nutné dělit dodávku, ale přinese-li to snížení nákladů, je to výhodné. Je-li qi = V, vybereme takové řešení, které přinese nižší náklady. Model lze vyjádřit takto:

∑ ∑ ∑

(1)

= = =

K k

n i

k ij n

j

ij

x c

1 1 1

min

∑ ∑

(2)

=

=

=

=

=

ⁿ

i

k ji n

i

k

ij

x j n k K

x

1 1

, ,...

2 , 1 ,

,..., 3 , 2 ,

∑

(3)

=

=

n

≤

j

k

j

k K

x

2

1

1 , 1 , 2 ,..., ,

(4)

, ,..., 2 , 1 , , ,..., 3 , 2 , ,..., 2 , 1 , )

1

( x u i n j n i j k K

V q

u

_i^k

+

_j

−

_k

−

_ij^k

≤

_j^k

= = ≠ =

∑

(5)

=

=

K

=

k

i k

i

q i n

q

1

, ,..., 3 , 2 ,

∑

(6)

=

=

=

≤

ⁿ

j k ij i

k

i

q x i n k K

q

1

, ,..., 2 , 1 , ,..., 3 , 2 ,

u

₁^k

= 0 , u

_i^k

≤ V

_k

, i = 2 , 3 ,..., n , k = 1 , 2 ,..., K .

(7) Opět se zde minimalizuje skutečný počet najetých kilometrů za výše

uvedených podmínek. Binární proměnná xij uvedená v předchozím modelu má v tomto případě o jeden index více, konkrétně o hodnotu k. Proměnná xijk znamená, zda pojedeme z uzlu i do uzlu j na k-té trase či nikoliv. V tomto modelu lze obsloužit jednoho zákazníka více vozidly; je tedy možno dělit dodávku a po konkrétní trase do uzlu jet vícekrát. Dělení je však možné jen za určitých předpokladů, které jsou vymezeny v následující podkapitole.

2.3. Dělení dodávky k-tého řádu

Dělení dodávky k-tého řádu znamená, že i-tý zákazník je obsloužen pomocí k tras. Ukázka dělené dodávky druhého řádu je znázorněna na obrázku 1. Pro jednoduchost mějme tři zákazníky A, B a C. Vozidlo 1 jede z depa k zákazníkovi A, vozidlo 2 k zákazníkovi B a u zákazníka C je dělená dodávka výhodná. Jestliže qc je požadavek v C, a sv je úspora v-tého vozidla, pak musí platit s1 + s2 ≥ qc . Obecně lze toto napsat ve tvaru

s

1

+ s

2

+ ... + s

_k

≥ q

_k+1 (1)

Požadavky: (2, 2, 2), V = 3 (1) + (2) 0

B A

C

A

C

0

C

0

B

Obr. 1 - Ukázka dělení dodávky druhého řádu 2.4. Potenciální úspory z dělení dodávky

Tato podkapitola se zaměřuje na úsporu, vzniklou při použití SDVRP.

Označíme-li i1 , j1 jako dva po sobě jdoucí body na trase 1, a i2 , j2 jako dva po sobě jdoucí body na trase 2, bp a ap jako body jdoucí těsně před a těsně po bodu p na trase 3, pak úspora vzniklá dělením dodávky mezi trasami 1 a 2 je vyjádřena vzorcem (1).

Takto popsaná situace je zároveň znázorněna na obrázku 2.

SAV p = C

i j

+ C

i j

+ C

b_pp

+ C

pa_p

2 2 1

)

1

3

(

(1)

− C

i₁p

− C

pj₁

− C

i₂p

− C

pj₂

− C

b_pa_p

Tento vzorec je však definován pro případ, že dělení v bodě p nastává mezi trasami 1 a 2. V tomto případě tedy k = 2. Pro k ≥ 3 lze použít zobecněný vzorec v následujícím tvaru

(2)

p p p

p t

t t

tj ip pj b p pa b a

i k t

k

p C C C C C C

SAV = ∑ − − + + −

=

) (

) (

1

Výše uvedené dva vzorce tedy umožňují vypočítat úsporu při dělení dodávky pro k = 2 a pro k ≥ 3. Na obrázku 2 je graficky demonstrována situace pro k = 2.

Pomocí vzorce (1) lze pak vypočítat potenciální úsporu.

B^Bp

Ap

P

I1 I2

J2

J1

Trasa 3

Trasa 2 Trasa 1

Obr. 2 - Ukázka dělení dodávky pro k = 2 v bodě p

Z tohoto obrázku je patrné, že dělení dodávky mezi trasami 1 a 2 je výhodné pouze když SAV3 (p) ≥ 0. Pro záporné hodnoty je výhodnější obsloužit zákazníka v bodě p pomocí trasy číslo 3 a nedělit tak dodávku mezi trasy 1 a 2, tak jak je to naznačeno pomocí šipek.

3. DEMONSTRACE PŘÍKLADŮ A JEJICH MOŽNÁ ŘEŠENÍ 3.1. Optimální řešení SDVRP s jedním dělením dodávky

V této kapitole jsou uvedeny příklady s různými variantami řešení, přičemž je zde snaha dosáhnout optimálního řešení pomocí dělení dodávky. Příklady jsou řešeny heuristickou metodou, nejde tedy o matematicky optimalizační řešení. Na prvním příkladě je názorně vidět, že dělení dodávky u čtvrtého zákazníka přinese snížení celkové najeté trasy a tedy i nákladů.

Příklad 1

1 2

3

4 5

6

0 7

8 8

6

7 8

4

2 3

3 5

sklad

Požadavky: (2, 4, 2, 3, 4, 4) V=10

Obr. 3 - Grafické znázornění prvního příkladu včetně optimálního řešení V tomto příkladě máme jeden sklad a šest zákazníků. U jednotlivých tras jsou udány vzdálenosti a dále jsou zde požadavky prvního až šestého zákazníka. Kapacita je pro všechna vozidla stejná a je deset. Žádný požadavek nepřevyšuje kapacitu, tudíž dělení dodávky není nutné. Je-li to však výhodné, bude dělení zahrnuto do optimálního řešení. Níže jsou uvedena možná řešení s tím, že poslední je optimální.

To je také znázorněno na obrázku 3 pomocí směrových šipek ukazující obě trasy.

Řešení 1: ( C01 + C12 + C23 + C30 ), ( C04 + C40 ) a ( C06 + C65 + C50 ). V tomto řešení je rozvozní plán rozložen na tři trasy a neuvažuje se dělení dodávky. Jedná se o klasický VRP. Vzdálenost najetá třemi vozidly je v tomto případě 52. Toto řešení však není nejefektivnější. Použijeme-li pouze dvě vozidla a zákazníka číslo 4 obsloužíme pomocí dělené dodávky, dostaneme trasy dvě a celková najetá vzdálenost bude nižší. Tento postup je obsažen v druhém řešení.

Řešení 2: Protože platí s1 + s2 ≥ q4, můžeme zákazníka pod číslem čtyři obsloužit pomocí dělené dodávky. Zde se jedná o SDVRP. Vzniknou tak dvě trasy a to ( C01 + C12 + C23 + C34 + C40 ) a ( C06 + C65 + C54 + C40 ). V tomto případě použijeme pouze dvě vozidla a celková najetá vzdálenost je 44, což je o 8 méně, než v předchozím postupu. Toto řešení je tedy optimální.

3.2. Úloha s optimálním řešením bez dělení dodávky

V některých případech, kdy přidání trasy odstraní dělení dodávky, může dojít ke snížení najeté vzdálenosti. Toto je znázorněno na příkladě 2. Obecně vzato, je následující příklad opačným případem, než je dělení dodávky druhého řádu, které je zmíněno v předchozí kapitole na obrázku 1.

Příklad 2

0

1 3

A 5

6 6

8 8

2 2

0

1 3

6

6 Požadavky: (2, 2, 2,)

Obr. 4 - Grafické znázornění druhého příkladu (obě varianty) V=3

5 B

Porovnáním situace A a situace B zjistíme, že v druhém případě, kdy nedochází k dělené dodávce u zákazníka pod číslem dva je trasa najetá vozidly menší.

Řešení 1: C01 + C12 + C03 + C32 + 2C20 = 38. Tento postup počítá s dvěma vozidly a celková najetá trasa je 38.

Řešení 2: C01 + C10 + C02 + C20 + C03 + C30 = 12 + 10 + 12 = 34. V tomto případě tedy použijeme tři vozidla a celková najetá trasa je 34.

Z toho vyplývá, že trasa najetá podle plánu B je kratší, ale je zde použito o jedno vozidlo více než v plánu A. V praxi by nejspíše nastala otázka, jaký je nákladový rozdíl mezi použitím dvou nebo tří vozidel, respektive, kdyby přidání jednoho placeného řidiče vozidla znamenalo vyšší náklady, než je ona úspora v nákladech z hlediska najeté délky, pak by se plán B nevyplatil. V tomto modelu rozvozní úlohy se ale tento faktor neuvažuje. Minimalizujeme délku najeté trasy a proto je plán B optimální řešení.

3.3. Úloha s optimálním řešením s větším počtem zákazníků obsloužených dělenou dodávkou

Příklad 3

0

3 2

1

7 9

4

6 8,5

6

6

3

3 3

4

5 4

4,5 4,5 9

2

2 2

4 4

3,5

4 3

3 2,5

3 2,5

6

5

8

Požadavky: (5, 7, 4, 6, 5, 4, 5, 5, 6) V=8 Obr. 5 - Grafické znázornění třetího příkladu včetně optimálního řešení

Tento příklad je poněkud složitější, než předchozí příklady. Je zde více možností sestavení rozvozního plánu. Jsou zde uvedena tři možná řešení, z nichž třetí je optimální. Třetí řešení obsahuje dělenou dodávku u zákazníků 2, 5 a 7.

Řešení 1: C01 + C10 + C02 + C20 + ( C03 + C36 + C60 ) + C04 + C40 + C05 + C50 + + C07 + C70 + C08 + C80 + C09 + C90. V tomto případě se jedná o rozvozní úlohu bez dělené dodávky. Jedná se tedy o klasický VRP. Výraz v závorce je trasa, kde můžeme obsloužit zákazníky 3 a 6 jedním vozidlem, protože součet jejich požadavků

nepřevyšuje kapacitu vozidla. V ostatních situacích připadá na jednoho zákazníka jedna trasa. Najetá vzdálenost je 66.

Řešení 2: (C01 + C12 + C20 ) + (C03 + C32 + C20 ) + (C06 + C64 + C40 ) + ( C05 + C54 + C40 ) +( C07 + C78 + C80 ) + ( C09 + C98 + C80 ), kde jedna závorka popisuje jednu trasu. Najetá vzdálenost je 66,5. K dělení dodávky dochází u zákazníků 2, 4 a 8.

Řešení 3: ( C01 + C12 + C20 ) + ( C03 + C32 + C20) + (C04 + C45 + C50 ) + ( C06 + C65 + C50 ) +( C09 + C97 + C70 ) + ( C08 + C87 + C70 ). V tomto případě jsou dělenou dodávkou obslouženi zákazníci 2, 5 a 7. Najetá vzdálenost je 60,5 a toto řešení je tedy optimální.

4. EXPERIMENTÁLNÍ POROVNÁNÍ VRP A SDVRP UKAZUJÍCÍ NA URČITÉ ZÁKONITOSTI.

4.1. Ukázka empirických studií rozvozní úlohy a z toho vyplývajících poznatků V této kapitole budou uvedeny některé poznatky, kterých bylo v poslední době dosáhnuto. Jednu z největších zásluh na tom má Italka Claudia Archetti, která se zabývá kvantitativními metodami v ekonomii a značně tak přispěla k prohloubení znalostí k tématu SDVRP.

Archetti ukázala, že redukce v rozvozních nákladech, tedy najeté délce, u úloh kde je povolena dělená dodávka nikdy nepřesáhne 50%. To znamená, že v optimálním řešení SDVRP jsou rozvozní náklady vždy větší než polovina rozvozních nákladů u optimálního řešení VRP. Z teoretického hlediska to však neposkytuje jakési zásadní porozumění vzájemného vztahu mezi charakteristikami specifického distribučního prostředí spojeného se zákazníky, jejich požadavky a možností redukce nákladů pomocí dělení dodávky. Výzkum se zaměřuje především na odhadování užitků vyplývajících z dělené dodávky. Níže jsou uvedeny tři poznatky, které upřesňují tento problém v obecném měřítku.

¾ V případě, že požadavky jsou relativně velké vzhledem ke kapacitě vozidla, pak snížení nákladů pomocí dělení dodávky není příliš velké.

¾ V případě, že požadavky jsou relativně malé vzhledem ke kapacitě vozidla, pak snížení nákladů pomocí dělení dodávky není příliš velké.

¾ V případě, že požadavky jsou o něco málo větší než je polovina kapacity vozidla, je možno dosáhnout značného snížení nákladů pomocí dělení dodávky.

K upřesnění těchto pozorování je možno dojít podle [2], pomocí empirické studie níže uvedeného poměru.

) (

) (

SDVRP z

VRP

z

(1)

Čitatel tohoto poměru udává náklady optimálního řešení VRP a jmenovatel

Počítačová studie a následné analýzy potvrdily, že dělení dodávky může mít za následek výrazné prospěchy. Zároveň se však ukázalo, že tyto prospěchy nastanou pro zákazníky s dosti specifickými charakteristikami. Konkrétně, když průměrný požadavek je větší než polovina kapacity vozidla, ale menší než tři čtvrtiny a jeho odchylka je relativně malá. Také lze poukázat na to, že existuje velmi silný vzájemný vztah mezi redukcí rozvozních nákladů a redukcí v počtu rozvozních tras, vyplývajících z dělení dodávek.

4.2. Rozvozní trasy a jejich specifika

Nyní je už jasné, že jedním z největších přínosů dělení dodávky je v možnosti snížit počet tras, potřebných k uspokojení všech zákazníků. Pro podrobnější zkoumání slouží níže uvedený poměr.

(1) )

(

) (

SDVRP r

VRP r

Čitatel v tomto případě udává minimální počet rozvozních tras, potřebných k uspokojení všech zákazníků u VRP. Jmenovatel udává minimální počet rozvozních tras potřebných k uspokojení všech zákazníků u SDVRP. V následujících úvahách se vychází z předpokladu, že platí trojúhelníková nerovnost. Zkoumání tohoto poměru se dá definovat jako pokus o dokázání tvrzení, které je dáno nerovností (2), viz [2].

Následující text se tedy věnuje důkazu této nerovnosti.

) (

) (

SDVRP r

VRP

r ≤

2

Tvrzení:

(2)

Dokázání tvrzení: U SDVRP je možné pozorovat, že minimální počet tras potřebných k uspokojení požadavků všech zákazníků je ∑qi /V. Z toho plyne (3).

Dosadíme-li výraz ∑qi /V do (2) dostaneme (4).

V q SDVRP

r ⁱ

∑

i

≥ =¹

) (

n

(3)

V q VRP

r ⁱ

∑

i

≤ 2 =¹

) (

n

(4) Uvažujeme-li případ, kde všichni zákazníci mají stejný požadavek, označený jako q, a zároveň q = (V + 1)/2, je možno pozorovat, že za určitých podmínek se poměr

) (SDVRP r

) (VRP

r blíží hodnotě 2. Nikdy však tuto hodnotu nepřesáhne. To znamená, že nemůže nastat situace, aby minimální počet rozvozních tras u VRP byl například třikrát větší než minimální počet rozvozních tras u SDVRP. Následující odstavec se zaměřuje na různé hodnoty tohoto poměru a na to, v jakých situacích nastávají.

Výsledky jsou zpracovány do grafu 1, kde je znázorněn poměr (1) jako funkce požadavku q a platí, že n = V = 149 a všichni zákazníci sdílí stejnou lokaci a mají stejný požadavek q. Z grafu je dobře vidět, že poměr nabývá své maximální hodnoty 1,987 pro q = V/2 = 75. Pro q = 75, je tedy v optimálním řešení VRP potřeba 149 tras. Jedno vozidlo vždy obslouží jednoho zákazníka. V optimálním řešení SDVRP je potřeba pouze 75 tras. Potřebný počet tras v optimálním řešení VRP je vždy n, pokud jedno vozidlo obslouží vždy jen jednoho zákazníka. Naproti tomu se u optimálního řešení SDVRP potřebný počet tras zvyšuje z n/2 + 1 na n, což znamená, že poměr (1) pomalu klesá z hodnoty 2 na hodnotu 1. Dále je možno pozorovat, že pro q = 74 mohou být v optimálním řešení VRP dva zákazníci obslouženi pomocí jedné trasy, tudíž je potřeba 75 tras. U optimálního řešení SDVRP je potřeba o jednu trasu méně, tedy 74. Jeden zákazník bude obsloužen pomocí dělené dodávky. V tomto případě je poměr (1) roven hodnotě 1,014. Dále je možno z grafu vidět, že další vrchol je pro q = 50. V optimálním řešení VRP je možno obsloužit pomocí jedné trasy nanejvýše dva zákazníky. Je tedy potřeba 75 tras. Zatímco u optimálního řešení SDVRP mohou být kombinovány požadavky hned tří zákazníků do jedné trasy. Zde je potřeba 50 tras. Poměr tak nabývá hodnoty 1,5. Je patrné, že to směřuje k určitému předpisu, respektive vrcholy se nacházejí při požadavcích V/k pro k = 2,….

Pro malé q, například q = 2, v řešení VRP je možno obsloužit 74 zákazníků pomocí jediné trasy, takže celkem jsou potřeba tři trasy. Pro řešení SDVRP stačí 2 trasy. Hodnota poměru je pak 1,5. Obdobně pro q = 2 je hodnota poměru 1,333.

(q + 1)/q pro q = 2,…,14. Pro q > 14 je minimální počet tras optimálního řešení VRP evidentně větší než (q + 1).

Je tedy patrné, že relativně největší úspory je dosáhnuto pro q = 75, kdy poměr (1) je roven 1,987. Je třeba si však uvědomit, že zde je podmínka rovnosti požadavků. V opačném případě by se stal tento problém mnohem komplikovanějším.

2,000

0,900 1,000 1,100 1,200 1,300 1,400 1,900 1,800

1,600 1,700

1,500

1 6 11 16 21 26 31 36 41 46 51 56 61 66 71 76 81 86 91 96 101 106 111 116 121 126 131 136 141 146

Zdroj: C. Archetti, M.W.P. Savelsbergh, M.G. Speranza. „To Split or Not To Split: That is the Question.“

Graf 1 - Poměr

) (

) ( SDVRP r

VRP

r jako funkce q

4.3. Vliv odchylky požadavků

V následující podkapitole je zkoumán poměr

) (SDVRP z

) (VRP

z , uvedený

v podkapitole 4.1. Pro vysvětlení určitých poznatků jsou zavedeny předpoklady se kterými studie [2] pracuje. Počet zákazníků n = 100, kapacita V = 200 a zákazníci tvoří shromážděnou skupinu. Vliv odchylky požadavků na tento poměr je znázorněn na grafu 2. V grafu jsou znázorněny dvě varianty poměru, a to pro hodnoty průměrného požadavku velikosti 95 a 105. Tyto poměry jsou uvedeny pro jednotlivé hodnoty odchylky požadavků.

Zdroj: C. Archetti, M.W.P. Savelsbergh, M.G. Speranza. „To Split or Not To Split: That is the Question.“

Graf 2 - Vliv odchylky požadavků

Protože kapacita vozidla je 200, vybrané hodnoty průměrného požadavku reprezentují průměrný požadavek těsně pod polovinou kapacity vozidla a těsně nad kapacitou poloviny vozidla. V případě, že průměrný požadavek je těsně pod kapacitou vozidla, zvýšení odchylky požadavků má za následek zvýšení počtu zákazníků s požadavkem vyšším než je kapacita vozidla. Tito zákazníci musí být u VRP obslouženi takzvanou “tam a zpět“ cestou, což vede ke zvýšení z(VRP).

Protože z(SDVRP) zůstává neměnné, celkový efekt vede ke zvýšení poměru

) (SDVRP z

) (VRP

z . Naopak, je-li průměrný požadavek těsně vyšší než polovina kapacity vozidla, nastává opak. Zvýšení odchylky požadavků má za následek snížení počtu zákazníků s požadavkem vyšším než je polovina kapacity vozidla, tedy snížení z(VRP) a celkové snížení poměru

) (SDVRP z

) (VRP

z .

4.4. Vliv velikosti průměrného požadavku

K demonstraci vlivu velikosti průměrného požadavku na poměr

) (SDVRP z

) (VRP z

slouží graf 3, kde jsou znázorněny tři varianty poměru, přesněji pro hodnoty

průměrné hodnoty požadavku. U křivky s nulovou odchylkou je vidět jasná podobnost v chování jako u křivky na grafu 1. Nejvyšší vrchol nastává těsně nad polovinou kapacity vozidla. Poměr potom klesá společně s rostoucím průměrným požadavkem. Další menší vrchol je možno pozorovat těsně nad jednou třetinou kapacity vozidla. Pohledem na křivku s odchylkou požadavků 196 se dá vyčíst, že zvýšená odchylka zplošťuje křivku, především mezi hodnotami průměrného požadavku 105 a 130. Díky zvýšené odchylce klesá totiž počet zákazníků s požadavkem vyšším než je polovina kapacity vozidla. Klesá tedy i poměr

) (SDVRP z

) (VRP

z . U poslední křivky s odchylkou 900 je možno sledovat, že toto chování je ještě výraznější a křivka mezi hodnotami průměrného požadavku 105 a 130 je ploší, než u křivky s odchylkou požadavků 196.

Graf 3 - Vliv průměrného požadavku

Zdroj: C. Archetti, M.W.P. Savelsbergh, M.G. Speranza. „To Split or Not To Split: That is the Question.“

5. ZÁVĚR

Cílem bakalářské práce bylo popsat SDVRP a zároveň srovnat tuto metodu s VRP. Tyto úlohy byly zformulovány a na dílčích příkladech byly ukázány heuristické postupy, pomocí kterých lze nalézt optimální řešení dané úlohy. Zároveň bylo ukázáno, že ne vždy musí dělení dodávky směřovat k optimálnímu řešení.

Na experimentální studii bylo ukázáno, že dělení dodávky může mít značný prospěch ve smyslu redukce snížení rozvozních nákladů, především pak počtu najetých tras. Na výše uvedených grafech lze dobře vyčíst situace, kdy je úspora z dělení dodávky veliká. To však ale jen za určitých předpokladů:

¾ Největších úspor je dosáhnuto, když průměrný požadavek je větší než polovina kapacity vozidla, ale menší než tři čtvrtiny.

¾ V případě, že požadavky jsou relativně velké nebo malé vzhledem ke kapacitě vozidla, můžeme dosáhnout prospěchu pomocí dělené dodávky, avšak nikoliv tak značného.

¾ Úspory z dělení dodávky převážně záleží i na odchylce požadavků.

Největších úspor lze dosáhnout v případě relativně malé odchylky.

Smyslem bakalářské práce bylo porozumět tomuto problému, poukázat na možné varianty řešení a objasnit situace, kdy je výhodné dělit dodávku a kdy nikoliv.

Doufám, že tato práce k tomu přispěla.

SEZNAM POUŽITÉ LITERATURY

[1] C. Archetti, A. Hertz, M.G. Speranza, „A tabu search algorithm for the split delivery vehicle routing problem.“ Transportation Science 40, 64-73, 2006.

[2] C. Archetti, M.W.P. Savelsbergh, M.G. Speranza. „To Split or Not To Split:

That is the Question.“ To appear inTransportation Research E, 2005.

[3] C. Archetti, M.W.P. Savelsbergh, M.G. Speranza, „Worst-case analysis for split delivery vehicle routing problem.“ To appear in Transoprtation Science

[4] P. Toth, D. Vigo, „The granular tabu search and its application to the vehicle- routing problem,“ INFORMS Journal on Computing, 15:333-346, 2003.

[5] M. Dror, P. Trudeau, „Savings by split delivery routing,“ Transportation Science, 23: 141-145, 1989.

[6] M. Dror, P. Trudeau, „Split delivery routing,“ Naval Research Logistics, 37:

383-402, 1990.

[7] M. Dror and L. Levy, „A vehicle routing Improvement Algorithm:Comparison of „Greedy“ and a „Matching“ Implementation for Inventory Routing,“ Comput.

Opns. Res. 13(1), 33-45 (1986).

[8] M. Solomon, „Algorithms for vehicle routing and scheduling problems with time windows,“ Operations Research, 35: 254-265, 1987.

[9] J. Fábry, „Rozvozní úloha s dělenou dodávkou.“ Progrsivní metody a nástroje managementu a ekonomiky podniků, Brno 2005.