Wykład 2 - Optymalizacja w logistyce

Problem komiwoja

era

Sformułowanie problemu

Zadanie komiwoja

era jest znane od kiedy kupcy zacz

li dostarcza

produkty

klientom.

Podstawow

wersj

problemu komiwoja

era mo

na przedstawi

w dwóch

zdaniach:

1. Komiwoja

er pragnie odwiedzi

pewn

liczb

klientów w ró

nych

miejscowo

ciach i po zako

czeniu odwiedzin wróci

do domu.

2. Jak

drog

powinien wybra

( w jakiej kolejno

ci powinien odwiedza

klientów) aby przebyta przez niego droga była mo

liwie najkrótsza?

Pierwsze reguły wyznaczania trasy zostały opracowane na podstawie do

wiadcze

praktycznych ju

w połowie XIX wieku przez komiwoja

erów w USA. Jednak

dopiero formalne uj

cie matematyczne pozwoliło odkry

e to niby proste

zadanie obejmuje bardzo szerok

klas

przypadków, z których tylko niektóre

na rozwi

dokładnie.

Zało

enia:

1. Ka

dego klienta mo

na identyfikowa

przez podanie miejscowo

ci (w

zła w

grafie), w której zamieszkuje ( w jednej miejscowo

ci znajduje si

jeden klient ).

2. Mi

dzy miejscowo

ciami istniej

poł

czenia pozwalaj

ce na przemieszczanie w

obu kierunkach ( kraw

dzie grafu ).

3. Ka

dej kraw

dzi przyporz

dkowana jest liczba okre

laj

ca uogólnion

odległo

ść

4. Wyró

nione miejscowo

ci oraz potencjalne trasy przejazdu mo

na przedstawi

za pomoc

grafu

G=[ V , E , c ]

, nieskierowanego, spójnego, o

złach, w

którym liczby przyporz

dkowane kraw

dziom s

nieujemne –

= c

≥

5. Dla dowolnych trzech w

złów

i,j,k

powinna by

spełniona nierówno

ść

≤

Dla dowolnych dwóch miejscowo

ci nie mog

wyst

powa

poł

czenia przez

inne miejscowo

ci.

7. Wyró

niamy jeden w

zeł odpowiadaj

cy miejscu startu komiwoja

era i

przyjmujemy,

e jego trasa powinna ko

czy

powrotem do tego w

zła.

tras

spełniaj

ca te warunki nazywamy tras

okr

ęŜ

komiwoja

era,

która jest optymalna, gdy ł

czna jej długo

ść

jest minimalna. Ka

da z

miejscowo

ci ( z wyj

tkiem startowej ) musi wyst

na niej tylko raz. W

teorii grafów tras

tego typu nazywa si

cyklem Hamiltona. Je

eli nie

wymaga si

odwiedzenia wszystkich miejscowo

ci mówimy o cyklu

skróconym.

Poszukiwany cykl Hamiltona oznaczymy krótko symbolem

. Aby móc

zapisa

e pewna kraw

nale

y do tego cyklu, wprowadzimy zmienne

binarne

, i,j= 1…, n

Poniewa

da miejscowo

ść

e tylko raz wyst

w trasie, wi

c ka

zeł

e tylko raz wyst

jako w

zeł pocz

tkowy kraw

dzi :

dy w

zeł mo

e by

równie

tylko raz w

złem ko

cowym kraw

dzi, co

prowadzi do układu ogranicze

[ ]













∈

przypadku

przeciwnym

cyklu

droga

gdy

1,...,

∑

1,...,

∑

Minimalizacja trasy mo

e by

ta w formie funkcji kryterium:

Wprowadzamy sztuczne zało

enie, na mocy którego, gdy mi

dzy dwoma

złami

nie istnieje poł

czenie, to przyjmujemy,

e s

one oddalone

niesko

czenie daleko, a wi

∞

, oraz równie

∞

Próba tak sformułowanego zadania ko

czy si

jednak bardzo cz

sto

wskazaniem cykli skróconych, których przyj

te ograniczenia niestety nie

wykluczaj

. Aby do tego nie dopu

do zadania nale

y wprowadzi

dodatkowe ograniczenia , które czyni

zadanie trudnym do praktycznego

rozwi

zania. W literaturze mo

na spotka

ró

ne wersje ogranicze

uniemo

liwiaj

cych powstawanie cykli skróconych. Cz

sto spotykan

jest

nast

puj

ca:

1. Rozpatrujemy wszystkie

elementowe permutacje w

złów

[ i

, i

,…, i

]

przy czym

• Gdy liczba w

złów jest parzysta:

k = 2,3,…,

min

→

∗

∑∑

•

Gdy liczba w

złów n jest nieparzysta:

k = 2,3,…,

2. Dla ka

dego

tworzymy układ ogranicze

Nale

y teraz wzi

ąć

pod uwag

e dla ka

dego

otrzymujemy

ogranicze

. Dla n=6 otrzymamy 55 ogranicze

, ale ich liczba

nie bardzo szybko dla n=14 wynosi prawie 3 miliony, co czyni zadanie

niemo

liwym do rozwi

zania. Z tego wzgl

du w praktyce najcz

ęś

ciej

wykorzystywane s

algorytmy heurystyczne.

−

...

−

≤

( )

−

∗













Algorytm droga do najbli

szego s

siada

Zało

enia startowe

Startujemy w

ęź

. Symbolem

oznaczamy długo

ść

drogi okr

ęŜ

nej.

Przyjmujemy:

:= a, z := 0.

Iteracje
Numery iteracji b

dziemy kojarzy

z liczb

odwiedzanych miejscowo

ci,

dlatego.

rozpatrujemy iteracje j = 2,3,…,n.

Krok 1

Wskazujemy w

zeł

, dla którego

Czyli wskazujemy w

zeł, który nie jest zakwalifikowany do drogi i le

y najbli

ostatniego z ju

uwzgl

dnionych w drodze.

Krok 2

Tworzymy ci

[ k1 ,…, kj ].

{ }

,...,

czym

przy

min

−

≠

−

Krok 3

Przyjmujemy:

Po n iteracjach do ci

[ k

,…, k

n-1

, k

]

doł

czamy w

zeł startowy

, tworz

drog

okr

ęŜ

H = [ k

,…, k

n-1

, k

]

, której długo

ść

wynosi:

−

Przykład

Post

puj

c zgodnie z zasadami wyznaczania najbli

szego s

siada

wyznaczamy kolejno

w wierszach zaczynaj

c od wiersza 1:

•

W wierszu 1 : w

zeł 3 – czas 78

•

W wierszu 3 : w

zeł 5 – czas 66

•

W wierszu 5 : w

zeł 4 – czas 288 ,nie mo

na wybra

2 bo nie ma z niego

dojazdu do 4 , ale z 4 nie mo

liwy jest tak

e dojazd do 2. Nale

post

powanie zacz

ąć

od pocz

tku bior

c pod uwag

e najgorszy dojazd

jest do 2 i 4

•

W wierszu 1 : w

zeł 3 – czas 78

•

W wierszu 3 : w

zeł 2 – czas 81

Wrocław

∞

198

131

Wałbrzych

∞

Legnica

∞

277

Pozna

198

∞

277

∞

288

Jelenia
Góra

131

288

∞

•

W wierszu 2 : w

zeł 5 – czas 63

•

W wierszu 5 : w

zeł 4 - czas 288

•

W wierszu 4 : w

zeł 1 - czas 198

czny czas przejazdu 708

Drugi wariant drogi okr

ęŜ

nej

•

W wierszu 1 : w

zeł 3 – czas 78

•

W wierszu 3 : w

zeł 4 – czas 277

•

W wierszu 4 : w

zeł 5 - czas 288

•

W wierszu 5 : w

zeł 2 - czas 63

•

W wierszu 2 : w

zeł 1 – czas 83

czny czas przejazdu 789

Trzeci wariant drogi okr

ęŜ

nej:

•

W wierszu 1 : w

zeł 2 – czas 83

•

W wierszu 2 : w

zeł 5 – czas 63

•

W wierszu 5 : w

zeł 3 - czas 66

•

W wierszu 3: w

zeł 4 - czas 277

•

W wierszu 4 : w

zeł 1 – czas 198

czny czas przejazdu 687

Jak wida

algorytmu nie da si

zawsze zastosowa

nie

odchodz

c od wcze

niej przedstawionych reguł

post

powania. Wszystko zale

y od konfiguracji

poł

cze

. Dlatego nale

y pami

e stosuj

algorytmy heurystyczne nie zawsze otrzymujemy

rozwi

zanie optymalne ale jedynie dopuszczalne.

Algorytm sukcesywne doł

czanie w

złów.

Dla z góry zadanego w

zła startowego

nale

y ju

na starcie wybra

inny

zeł

utworzy

pocz

tkow

tras

i powrotem:

[a,b,a].

W trakcie

post

powania

dziemy sukcesywnie modyfikowa

drog

przez doł

czanie nowych

złów.

Wybór nowego w

zła nie jest jednoznacznie okre

lony, ale korzystnie jest

stosowa

nast

puj

ca reguł

Najmniejsza z odległo

ci doł

czanego w

zła do wcze

niej okre

lonej drogi

powinna.

liwie najwi

ksza. Przyjmujemy zatem:

•

– w

zeł startowy,

•

– w

zeł najbardziej oddalony od a,

•

– okre

lona długo

ść

okr

ęŜ

nej drogi; w iteracja po

rednich – drogi

ęś

ciowej,

•

– cykl w

złów tworz

cych drog

okr

ęŜ

; w iteracjach po

rednich jest to

droga cz

ęś

ciowa

Zało

enia startowe

Przyjmujemy:

Iteracje

Numery iteracji kojarzy

dziemy z liczb

odwiedzonych miejscowo

ci,

dlatego.

rozpatrujemy iteracje j = 3,…,n. Przyjmijmy,

e w iteracji (j-1) otrzymali

ęś

ciow

drog

okr

ęŜ

o długo

Ze wzgl

du na stosowane dalej wzory ostatni z w

złów jest oznaczony przez

, a w

rzeczywisto

ci jest nim w

zeł

[

]

[

]

,...,

−

W ka

dej iteracji nale

y wskaza

, który z nie uwzgl

dnionych jeszcze w

złów

powinien

doł

czony i rozstrzygn

ąć

, mi

dzy którymi w

złami istniej

cej trasy

powinien by

Doł

czony.

Krok 1

Dla ka

dego w

zła

≠

, k

,…, k

j-1

obliczamy :

Krok 2

Jako w

zeł

, który ma by

doł

czony do drogi wybieramy ten, dla którego:

(

)

,...,

min

−

max

Krok 3

Maj

c wybrany w

zeł i musimy rozstrzygn

ąć

, mi

dzy które w

zły drogi H

wstawi

ten.

zeł. W nowej drodze pojawiaj

kraw

dzie

, i]

oraz

[i , k

t+1

]

natomiast

wypada z

niej kraw

, k

t+1

]

t+1

Doł

czenie nowych odcinków drogi powoduje zmian

jej długo

ci. Wielko

ść

tej

zmiany

oznaczamy symbolem

i obliczamy nast

puj

co :

Jeste

my zainteresowani takim rozwi

zaniem, które b

dzie powodowało

najmniejszy .

przyrost długo

ci drogi, dlatego post

pujemy zgodnie z nast

puj

cym

kryterium:

Krok 4

Tworzymy now

ęś

ciow

tras

−

(

)

min

,...,

−

[

]

,...,

Krok 5

Sprawdzamy czy zostały uwzgl

dnione wszystkie w

zły. Je

eli nie to

przechodzimy

do nast

pnej iteracji. Je

eli tak wyznaczanie trasy komiwoja

era ko

czy si

Otrzymujemy drog

okr

ęŜ

, która jest cyklem Hamiltona

[

]

,...,

Przykład

Przyjmujemy jako

zeł

, jako

nale

y przyj

ąć

zeł

, do którego czas

przejazdu . jest najdłu

szy i wynosi 198 min. Otrzymujemy drog

= [1,4,1]

, z=198 + 198 = 396

Iteracja 3

Wyznaczamy w

zeł, który doł

czymy do drogi H

p=2 r

= min { 83 , 10000 } = 83

P=3 r

= min { 78 , 277 } = 78

Wrocław

∞

198

131

Wałbrzyc
h

∞

Legnica

∞

277

Pozna

198

∞

277

∞

288

Jelenia
Góra

131

288

∞

P=5 r

= min { 131, 288 } = 131

Do drogi H

doł

czamy w

zeł 5. Musimy teraz rozstrzygn

ąć

na które miejsce w

ty celu.

obliczmy wska

niki s

= c

+ c

– c

= 131 + 288 – 198 = 221

= c

+ c

- c

= 288 + 131 – 198 = 221

Wybór jest dowolny, załó

my,

e wybieramy s

co oznacza,

e tworzymy now

okr

ęŜ

tras

= [1, 5, 4, 1 ]

Iteracja 4

P = 2 r

= min { c

, c

} =min {83 , 63 , 10000 } = 63

P = 3 r

= min { c

, c

} = min {78 , 66 , 277 } = 66

Do drogi H

doł

czamy w

zeł 3.

Musimy teraz rozstrzygn

ąć

na które miejsce w ty celu obliczmy wska

niki s

= c

+ c

– c

= 78 + 66 – 131 = 13

= c

+ c

- c

= 66 + 277 – 288 = 55

= c

+ c

– c

= 277 + 78 – 198 = 157

wybieramy s

co oznacza,

e w

zeł 3 doł

czamy do drogi H

po w

ęź

le 1.

Otrzymujemy

tras

= [1 , 3 , 5 , 4 , 1] z = 78 + 66 + 288 + 198 = 630

Iteracja 5

P = 2 r

= min {83 , 273 , 81 , 63 } = 63

Musimy teraz rozstrzygn

ąć

na które miejsce wprowadzimy w

zeł 2 w ty celu

obliczmy.

wska

niki s

= c

+ c

– c

= 83 + 81 – 78 = 86

= c

+ c

- c

= 81 + 63 – 66 = 78

= c

+ c

– c

= 10000 + 83 – 198 = 9885

= c

+ c

- c

= 63 + 10000 - 288 = 9777

wybieramy s

co oznacza,

e w

zeł 2 doł

czamy do drogi H

po w

ęź

le 1.

Otrzymujemy

tras

= [1 , 3 , 2 , 5 , 4 , 1] z = 78 + 81 + 63 + 288 + 198 = 708