OPTYMALIZACJA W
LOGISTYCE
Optymalizacja zada
ń
bazy
transportowej ( cz
ęść
2 )
Opracowano na podstawie : Stanisław Krawczyk, Metody ilo
ś
ciowe w logistyce (
przedsi
ę
biorstwa ),
Wydawnictwo C. H. Beck, Warszawa 2001
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
mo
ż
na rozwi
ą
za
ć
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
n
w
ę
złach, w
którym liczby przyporz
ą
dkowane kraw
ę
dziom s
ą
nieujemne –
c
ij
= c
ji
≥
0
5. Dla dowolnych trzech w
ę
złów
i,j,k
powinna by
ć
spełniona nierówno
ść
:
c
ik
≤
c
ij
+
c
jk
6.
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
ć
si
ę
powrotem do tego w
ę
zła.
Ka
ż
d
ą
tras
ę
spełniaj
ą
ca te warunki nazywamy tras
ą
okr
ęż
n
ą
komiwoja
ż
era,
która jest optymalna, gdy ł
ą
czna jej długo
ść
jest minimalna. Ka
ż
da z
miejscowo
ś
ci ( z wyj
ą
tkiem startowej ) musi wyst
ą
pi
ć
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.
1
1
2
3
4
5
6
Poszukiwany cykl Hamiltona oznaczymy krótko symbolem
H
. Aby móc
zapisa
ć
,
ż
e pewna kraw
ę
d
ź
nale
ż
y do tego cyklu, wprowadzimy zmienne
binarne
x
ij
, i,j= 1…, n
.
Poniewa
ż
ka
ż
da miejscowo
ść
mo
ż
e tylko raz wyst
ą
pi
ć
w trasie, wi
ę
c ka
ż
dy
w
ę
zeł
i
mo
ż
e tylko raz wyst
ą
pi
ć
jako w
ę
zeł pocz
ą
tkowy kraw
ę
dzi :
Ka
ż
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
w
0,
H
cyklu
j
i,
droga
gdy
,
1
ij
x
n.
1,...,
j
,
1
1
=
=
∑
=
n
i
ij
x
n.
1,...,
i
,
1
1
=
=
∑
=
n
j
ij
x
Minimalizacja trasy mo
ż
e by
ć
uj
ę
ta w formie funkcji kryterium:
Wprowadzamy sztuczne zało
ż
enie, na mocy którego, gdy mi
ę
dzy dwoma
w
ę
złami
p
i
r
nie istnieje poł
ą
czenie, to przyjmujemy,
ż
e s
ą
one oddalone
niesko
ń
czenie daleko, a wi
ę
c
c
pr
=
∞
, oraz równie
ż
c
ii
=
∞
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
ś
ci
ć
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
k
elementowe permutacje w
ę
złów
[ i
1
, i
2
,…, i
k
]
,
przy czym
• Gdy liczba w
ę
złów jest parzysta:
k = 2,3,…,
min
1
1
→
∗
=
∑∑
=
=
ij
n
i
n
j
ij
x
c
z
2
n
•
Gdy liczba w
ę
złów n jest nieparzysta:
k = 2,3,…,
2. Dla ka
ż
dego
k
tworzymy układ ogranicze
ń
:
Nale
ż
y teraz wzi
ąć
pod uwag
ę
,
ż
e dla ka
ż
dego
k
otrzymujemy
ogranicze
ń
. Dla n=6 otrzymamy 55 ogranicze
ń
, ale ich liczba
ro
ś
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.
2
1
−
n
1
...
1
3
2
2
1
−
≤
+
+
k
x
x
x
i
i
i
i
i
i
k
( )
!
1
−
∗
k
k
n
Algorytm droga do najbli
ż
szego s
ą
siada
Zało
ż
enia startowe
Startujemy w
ęź
le
a
. Symbolem
z
oznaczamy długo
ść
drogi okr
ęż
nej.
Przyjmujemy:
k
1
:= 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ł
k
j
, dla którego
Czyli wskazujemy w
ę
zeł, który nie jest zakwalifikowany do drogi i le
ż
y najbli
ż
ej
ostatniego z ju
ż
uwzgl
ę
dnionych w drodze.
Krok 2
Tworzymy ci
ą
g
[ k1 ,…, kj ].
{ }
1
1
,
,...,
czym
przy
,
min
,
1
1
−
≠
=
−
−
j
k
k
k
k
k
i
c
c
i
j
j
j
Krok 3
Przyjmujemy:
Po n iteracjach do ci
ą
gu
[ k
1
,…, k
n-1
, k
n
]
doł
ą
czamy w
ę
zeł startowy
k
1
, tworz
ą
c
drog
ę
okr
ęż
n
ą
H = [ k
1
,…, k
n-1
, k
n
, k
1
]
, której długo
ść
wynosi:
j
j
k
k
c
z
z
,
1
−
+
=
1
,k
c
z
z
n
k
+
=
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
ż
y
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
1
1
2
3
4
5
Wrocław
1
∞
83
78
198
131
Wałbrzych
2
83
∞
81
∞
63
Legnica
3
78
81
∞
277
66
Pozna
ń
4
198
∞
277
∞
288
Jelenia
Góra
5
131
63
66
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
5
3
2
4
1
Pozna
ń
Wrocław
Wałbrzych
Legnica
Jelenia Góra
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
ę
ta
ć
,
ż
e stosuj
ą
c
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
a
nale
ż
y ju
ż
na starcie wybra
ć
inny
w
ę
zeł
b
i
utworzy
ć
pocz
ą
tkow
ą
tras
ę
z
a
do
b
i powrotem:
[a,b,a].
W trakcie
post
ę
powania
b
ę
dziemy sukcesywnie modyfikowa
ć
t
ę
drog
ę
przez doł
ą
czanie nowych
w
ę
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.
by
ć
mo
ż
liwie najwi
ę
ksza. Przyjmujemy zatem:
•
a
– w
ę
zeł startowy,
•
b
– w
ę
zeł najbardziej oddalony od a,
•
z
– okre
ś
lona długo
ść
okr
ęż
nej drogi; w iteracja po
ś
rednich – drogi
cz
ęś
ciowej,
•
H
– cykl w
ę
złów tworz
ą
cych drog
ę
okr
ęż
n
ą
; w iteracjach po
ś
rednich jest to
droga cz
ęś
ciowa
Zało
ż
enia startowe
Przyjmujemy:
Iteracje
Numery iteracji kojarzy
ć
b
ę
dziemy z liczb
ą
odwiedzonych miejscowo
ś
ci,
dlatego.
rozpatrujemy iteracje j = 3,…,n. Przyjmijmy,
ż
e w iteracji (j-1) otrzymali
ś
my
cz
ęś
ciow
ą
.
drog
ę
okr
ęż
n
ą
:
o długo
ś
ci
z
.
Ze wzgl
ę
du na stosowane dalej wzory ostatni z w
ę
złów jest oznaczony przez
k
j
, a w
rzeczywisto
ś
ci jest nim w
ę
zeł
k
1
.
[
]
1
2
2
1
k
1
2
1
2
1
c
z
,
,
,
k
H
b,
,
k
k
k
c
k
k
k
a
k
+
=
=
=
=
[
]
j
j
k
k
k
k
H
,
,...,
,
1
2
1
−
=
W ka
ż
dej iteracji nale
ż
y wskaza
ć
, który z nie uwzgl
ę
dnionych jeszcze w
ę
złów
powinien
by
ć
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
p
≠
k
1
, k
2
,…, k
j-1
obliczamy :
Krok 2
Jako w
ę
zeł
i
, który ma by
ć
doł
ą
czony do drogi wybieramy ten, dla którego:
(
)
p
j
k
p
k
p
k
p
c
c
c
d
1
2
1
,...,
,
min
−
=
p
p
i
d
d
max
=
Krok 3
Maj
ą
c wybrany w
ę
zeł i musimy rozstrzygn
ąć
, mi
ę
dzy które w
ę
zły drogi H
wstawi
ć
ten.
w
ę
zeł. W nowej drodze pojawiaj
ą
si
ę
kraw
ę
dzie
[k
t
, i]
oraz
[i , k
t+1
]
natomiast
wypada z
niej kraw
ę
d
ź
[k
t
, k
t+1
]
k
k
1
k
t
K
t+1
k
1
i
C
i
k
t+1
Ck
t
i
Ck
t
k
t+1
Doł
ą
czenie nowych odcinków drogi powoduje zmian
ę
jej długo
ś
ci. Wielko
ść
tej
zmiany
oznaczamy symbolem
s
t
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
ą
cz
ęś
ciow
ą
tras
ę
1
1
+
+
−
+
=
t
t
t
t
k
k
ik
i
k
t
c
c
c
s
(
)
1
1
1
min
1
,...,
1
+
+
+
−
+
=
+
=
−
=
t
t
h
h
t
t
k
k
ik
i
k
j
h
ik
i
k
t
c
c
c
c
c
s
[
]
j
t
t
k
k
i
k
k
H
,...,
,
,
,...,
1
1
+
=
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
ęż
n
ą
, która jest cyklem Hamiltona
[
]
1
1
,
,...,
k
k
k
H
n
=
Przykład
Przyjmujemy jako
a
w
ę
zeł
1
, jako
b
nale
ż
y przyj
ąć
w
ę
zeł
4
, do którego czas
przejazdu . jest najdłu
ż
szy i wynosi 198 min. Otrzymujemy drog
ę
H
1
= [1,4,1]
, z=198 + 198 = 396
Iteracja 3
Wyznaczamy w
ę
zeł, który doł
ą
czymy do drogi H
1:
p=2 r
21
= min { 83 , 10000 } = 83
P=3 r
31
= min { 78 , 277 } = 78
1
1
2
3
4
5
Wrocław
1
∞
83
78
198
131
Wałbrzyc
h
2
83
∞
81
∞
63
Legnica
3
78
81
∞
277
66
Pozna
ń
4
198
∞
277
∞
288
Jelenia
Góra
5
131
63
66
288
∞
P=5 r
51
= min { 131, 288 } = 131
Do drogi H
1
doł
ą
czamy w
ę
zeł 5. Musimy teraz rozstrzygn
ąć
na które miejsce w
ty celu.
obliczmy wska
ź
niki s
t
:
s
1
= c
15
+ c
54
– c
14
= 131 + 288 – 198 = 221
s
4
= c
45
+ c
51
- c
41
= 288 + 131 – 198 = 221
Wybór jest dowolny, załó
ż
my,
ż
e wybieramy s
1
co oznacza,
ż
e tworzymy now
ą
okr
ęż
n
ą
.
tras
ę
H
2
= [1, 5, 4, 1 ]
Iteracja 4
P = 2 r
22
= min { c
21
, c
25
, c
24
} =min {83 , 63 , 10000 } = 63
P = 3 r
32
= min { c
31
, c
35
, c
34
} = min {78 , 66 , 277 } = 66
Do drogi H
2
doł
ą
czamy w
ę
zeł 3.
Musimy teraz rozstrzygn
ąć
na które miejsce w ty celu obliczmy wska
ź
niki s
t
:
s
1
= c
13
+ c
35
– c
15
= 78 + 66 – 131 = 13
s
5
= c
53
+ c
34
- c
54
= 66 + 277 – 288 = 55
S
4
= c
43
+ c
31
– c
41
= 277 + 78 – 198 = 157
wybieramy s
1
co oznacza,
ż
e w
ę
zeł 3 doł
ą
czamy do drogi H
2
po w
ęź
le 1.
Otrzymujemy
tras
ę
H
3
= [1 , 3 , 5 , 4 , 1] z = 78 + 66 + 288 + 198 = 630
Iteracja 5
P = 2 r
23
= min {83 , 273 , 81 , 63 } = 63
Musimy teraz rozstrzygn
ąć
na które miejsce wprowadzimy w
ę
zeł 2 w ty celu
obliczmy.
wska
ź
niki s
t
:
s
1
= c
12
+ c
23
– c
13
= 83 + 81 – 78 = 86
s
3
= c
32
+ c
24
- c
34
= 81 + 63 – 66 = 78
S
4
= c
42
+ c
21
– c
41
= 10000 + 83 – 198 = 9885
S
5
= c
52
+ c
24
- c
54
= 63 + 10000 - 288 = 9777
wybieramy s
1
co oznacza,
ż
e w
ę
zeł 2 doł
ą
czamy do drogi H
3
po w
ęź
le 1.
Otrzymujemy
tras
ę
H
3
= [1 , 3 , 2 , 5 , 4 , 1] z = 78 + 81 + 63 + 288 + 198 = 708
1
4
2
5
3