Dynamické okružní a rozvozní úlohy

Dynamické okružní a rozvozní úlohy

Jan FábryJan Fábry

Osnova prezentaceOsnova prezentace

_______________________________________________________________________________________Dynamické okružní a rozvozní úlohy 2

1. Úvod

2. Cíle disertační práce

3. Klasifikace úloh

4. Metodika

5. Výpočetní experimenty

6. Přínos disertační práce

7. Budoucí výzkum

1. Úvod1. Úvod


OKRUŽNÍ ÚLOHY

ROZVOZNÍ ÚLOHY

- Traveling Salesman Problem

- Vehicle Routing Problem

1. Úvod1. Úvod


STATICKÉ ÚLOHY

DYNAMICKÉ ÚLOHY

- všichni zákazníci jsou předem známí

- po výjezdu vozidel na trasu přicházejídalší požadavky

2. Cíle disertační práce2. Cíle disertační práce


• Přehled úloh

• Formulace optimalizačních modelů

• Použití heuristických algoritmů

• Vytvoření vlastního systému pro řešení úloh

(Lingo, VBA v MS Excel)

3. Klasifikace úloh3. Klasifikace úloh


• Okružní úlohy

• Rozvozní úlohy

Velikost požadavků a kapacita vozidel



• Jediné vozidlo

• Více vozidel v jednom výchozím místě

Počet a umístění vozidel

• Více vozidel v různých výchozích místech



• Minimalizace celkové ujeté vzdálenosti

• Minimalizace doby potřebné k obsloužení všech zákazníků

Cíl optimalizace

4. Metodika4. Metodika


Statická úloha

Dynamická úloha

Příchod nového požadavku

Optimalizace

Re-optimalizace

Vkládací algoritmus



Okružní úlohy

n

i

n

jijij xcz

1 1

,,...,2,1,11

nixn

jij

,,...,2,1,11

njxn

iij

,,,...,3,2,,...,2,1,1 jinjninnxuu ijji

.,...,2,1,,1,0 njixij

minimalizovat

za podmínek

Statická úloha obchodního cestujícího

11


Okružní úlohy Dynamická úloha obchodního cestujícího

Výchozí místo

Optimální trasa

Nový zákazník44

22

33

55

66

77



Okružní úlohy Statická úloha kurýrní služby

11

3322

667788

99 5544

Výchozí místo




11

3322

667788

99 5544

Optimální trasa

Výchozí místo




minimalizovat

za podmínek

12

1

12

1

n

i

n

jijij xcz

,12,...,2,1,112

1

nixn

jij

,12,...,2,1,112

1

njxn

iij

,,12,...,3,2,12,...,2,1,2)12( jinjninxnuu ijji

,,...,2,1,122 niuu ii

.12,...,2,1,,1,0 njixij



Okružní úlohy Dynamická úloha kurýrní služby

11Výchozí místo

3322

667788

99 5544

1010 Nový zákazník

1111



Okružní úlohy Statická úloha s více vozidlyv různých výchozích místech

0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70 80 90 100

5 výchozích míst

15 zákazníků


0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70 80 90 100

21

22

23

24

25



Okružní úlohy Dynamická úloha s více vozidlyv různých výchozích místech

5 nových zákazníků




Rozvozní úlohyminimalizovat

za podmínek

Statická rozvozní úloha

n

i

n

jijij xcz

1 1

,,...,3,2,11

nixn

jij

,,...,3,2,11

njxn

iij

,,,...,3,2,,...,2,1,)1( jinjniuxVqu jijji

,,...,3,2, niVuq ii

,01 u

.,...,2,1,,1,0 njixij

iqpožadavek i-tého zákazníka

kapacita vozidlaV



Rozvozní úlohy Rozvozní úloha

s dělenou dodávkou

k

ijx1, pokud (i,j) bude zařazena v k-té trase

i

K

k

k

i qq 1

k

iq počet jednotek odvezených od i-tého zákazníka vozidlem na k-té trase

0, jinak

iq požadavek i-tého zákazníka



Rozvozní úlohy Dynamická rozvozní úloha


0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70 80 90 100

30

19

26

1. vozidlo

2. vozidlo

3

5 2

44

6

5

10

2 vozidla

V=50

0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70 80 90 100

204



Rozvozní úlohy

30

19

10

1. vozidlo

2. vozidlo

3

5 2

4

56

10

26

Dynamická rozvozní úloha


2 vozidla

V=50

Re-optimalizace

5. Výpočetní experimenty5. Výpočetní experimenty


• Vlastní výpočetní systém- uživatelské rozhraní v MS Excel (VBA)- Lingo 9.0 jako řešitel - generovaná data:

• euklidovské souřadnice míst (rovnoměrné rozdělení)

• u dynamických úloh okamžik vzniku nového požadavku (exponenciální rozdělení)

• u rozvozních úloh velikost požadavku(rovnoměrné rozdělení)



• Výpočetní experimenty- re-optimalizační a vkládací algoritmy pro

vybrané úlohy- srovnání systémů Lingo 9.0

a XPRESS MP, release 2005



OPT 1 min OPT 1 min5 151,21 - 0 151,21 168 - 0 16810 319,42 - 0 343,7 348,45 - 0 357,5615 354,43 - 16 354,43 424,88 - 4 424,8820 402,87 - 18 402,87 403,35 - 1 407,9525 457,49 466,49 73 457,49 464,63 - 10 464,6330 426,1 - 48 426,1 514,69 - 1 514,86

Délka trasyDélka trasy Doba

výpočtuDélka trasy

Dynamická úloha obchodního cestujícího

Počet míst

Exp 1 Exp 2

ReoptimalizaceVkládací

algoritmusReoptimalizace


Délka trasy Doba výpočtu



Optimalizace času potřebného k obsluze všech zákazníků

200

210

220

230

240

250

260

270

280

290

300

0 5 10 15 20 25 30

Doba výpočtu (min)

Čas

potř

ebn

ý k

ob

slu

ze (

min

)

10 zákazníků, 4 vozidla v jednom výchozím místě



• Závěry- u řady dynamických úloh lze v praxi použít

vkládací algoritmus

- možnost přerušení re-optimalizačního algoritmu

- kombinace vkládacího a re-optimalizačního algoritmu

- výzkum zaměřený na heuristiky a metaheuristiky

- XPRESS MP vs. Lingo

6. Přínos disertační práce6. Přínos disertační práce


• První práce v českém jazyce

• Re-optimalizační a vkládací algoritmy

- přehled úloh

- jasné vymezení pojmů okružní a rozvozní úlohy

- z větší části původní- lze je snadno zpracovat počítačově



• Úloha obchodního cestujícího s časovými okny- čekání vozidla u právě obslouženého zákazníka- čekání vozidla u zákazníka před jeho obsluhou

• Dynamické úlohy s minimalizací času potřebného k obsloužení zákazníků

• Dynamická úloha kurýrní služby



• Dynamická rozvozní úloha s dělenou dodávkou

• Definice matematických modelů dynamických úloh s více vozidly- v jednom výchozím místě- v různých výchozích místech



• Vlastní výpočetní systém

• Výpočetní experimenty

- soubory jsou součástí disertační práce (CD)

- vhodnost použití re-optimalizace a vkládacích algoritmů pro úlohy reálného rozměru

- srovnání systémů Lingo a XPRESS MP



• Přínos pro výuku- dynamický přístup k okružním a rozvozním

úlohám

- názorné demonstrační příklady

7. Budoucí výzkum7. Budoucí výzkum


• Heuristiky a metaheuristiky

• Reálná data

• Software pro okružní a rozvozní úlohy

• Úloha kurýrní služby

Děkuji za pozornostDěkuji za pozornost

Date post:	10-Jan-2016
Category:	Documents
Upload:	keahi
View:	63 times
Download:	6 times

Dynamické okružní a rozvozní úlohy

Documents