OPTYMALIZACJA W
LOGISTYCE
Optymalizacja zadań bazy
transportowej ( część 1 )
Opracowano na podstawie : Stanisław Krawczyk, Metody ilościowe w logistyce (
przedsiębiorstwa ),
Wydawnictwo C. H. Beck, Warszawa 2001
Planowanie tras dostaw wielu pojazdów
Zasady tworzenia tras. Zało\
enia:
1. Produkty są względnie jednorodne ( wspólna miara ładowności ) i mo\
na je
transportować pewnym jednolitym środkiem transportu.
2. Produkty mają być pobrane z jednego magazynu (Lo) i dostarczane do n
odbiorców ( B1,& ,Bn ).
3. Znamy zamówienia odbiorców, które są wyra\
one w tych samych
jednostkach ładowności ( Bi, i=1,& ,n wynosi bi ).
4. Produkty będą rozwo\
one identycznymi środkami transportu o ładowności
Q ( Q > bi, i=1,& ,n ).
5. Czas przebywania na trasie, ka\
dego pojazdu, nie mo\
e przekroczyć T
jednostek czasu.
6. Dla uproszczenia zakładamy, \
e czas wyładunku jest równy zero.
Sformułowanie problemu:
Nale\
y wyznaczyć ilość środków transportowych oraz trasy ich przejazdów
pozwalające obsłu\
yć wszystkie zamówienia klientów przy zachowaniu
warunków przewozów tak, aby łączny czas obsługi wszystkich klientów był
minimalny.
Sformułowane zadanie składa się z dwóch zadań częściowych:
1. Przydziału
2. Wyznaczania tras
Stosowane oznaczenia:
" H  dowolna trasa rozpoczynajÄ…ca siÄ™ w punkcie Lo i przebiegajÄ…ca przez
punkty i1,i2,& ir i kończąca się w punkcie Lo
" tij - czas przejazdu z punktu i do punktu j , przy zało\
eniu, \
e toi + tio d" T
" t(H) = toi1 + ti1i2 +& + tiro , t(H) d" T - czas przejazdu dowolnej trasy
" b(H) = bi1 + & + bir , b(H) d" Q - łączna wielkość zamówień dowolnej trasy
Wariant wyjściowy:
Ka\
dy klient jest obsługiwany indywidualnie. Wtedy łączny czas dostawy dla n
klientów wynosi :
n
z =
"(t + toi )
io
i=1
Czy zasadne jest połączenie tras kilku odbiorców w celu skrócenia czasu
dostawy i zmniejszenia ilości wykorzystywanych pojazdów, dla dwóch
pojazdów wygląda to następująco:
t0 = (toi + tio ) + (toj + t )
" Indywidualna obsługa:
jo
i t0j j
t0i
ti0 0 tj0
" Wspólna obsługa:
t = toi + tij + t
jo
tij
ii j
ti0 tj0
j0
Obliczając ró\
nicę czasów otrzymujemy:
sij = t0 - t1 = t0i + t - tij
j0
Wartość sij określa wielkość zaoszczędzonego czasu.
Algorytm oszczędnościowego łączenia tras.
Zało\
enia startowe:
1. Znamy czasy przejazdów tij, i,j=0,1,& n. Na podstawie tych czasów
obliczamy potencjalne oszczędności czasów przejazdu sij. Wartości sij
porządkujemy malejąco, odrzucając wcześniej wszystkie sij d" 0;
2. Zakładamy, \
e ka\
dy odbiorca jest obsługiwany indywidualnie co oznacza,
\
e liczba pojazdów jest równa liczbie odbiorców.
Iteracje
Krok 1
Bierzemy największą wartość sij i odczytujemy wskazania numerów
odbiorców. Je\
eli zbiór jest pusty postępowanie się kończy. Otrzymaliśmy
rozwiÄ…zanie .
Krok 2
Sprawdzamy, jakÄ… pozycjÄ™ zajmujÄ… wskazani odbiorcy i oraz j w swych trasach
i w zale\
ności od ich umiejscowienia albo dokonujemy łączenia tras albo
pozostawiamy bez zmian.
Przypadek I
Gdy ani i, ani j nie nale\
Ä… do \
adnej grupy odbiorców obsługiwanych wspólnie,
tworzymy grupę { i,j} i sprawdzamy, czy trasa {0,i,j,0} spełnia warunki
dopuszczalności. Gdy są spełnione  tworzymy trasę {0,i,j,0}
Przypadek II
Gdy i nale\
y do pewnej grupy, natomiast j jest obsługiwany indywidualnie,
musimy uwzględnić, jakie miejsce w trasie zajmuje i:
1. Je\
eli i jest odbiorcą pośrednim w swej grupie  nie rozpatrujemy
dołączenia j do grupy.
2. Je\
eli i jest odbiorcą krańcowym, sprawdzamy, czy dołączenie j do trasy nie
naruszy warunków dopuszczalności przewozu. Je\
eli warunki przewozu sÄ…
spełnione, odbiorcę j dołączmy do trasy zawierającej i, przy czym j będzie
obsługiwany:
 Przed i, gdy i występował w trasie jako pierwszy, czyli tworzymy trasę
{0,j,i,& ,0}
 Po i, gdy i występował jako ostatni, czyli tworzymy trasę {0,& ,i,j,0}
Przypadek III
Je\
eli i nale\
y do trasy H1, a j do np.: H2. To połączenie tras ma sens, gdy
zarówno i jak i j są odbiorcami krańcowymi swych tras oraz gdy po
połączeniu tras są spełnione warunki przewozu. Nową trasę tworzymy
zgodnie z zasadami omówionymi w przypadku II.
Krok 3
Po wyznaczeniu nowej trasy skreślamy z listy te, które połączyliśmy, a do
zbioru dołączamy nową. Skreślamy rozpatrzoną sij ze zbioru i przechodzimy
do następnej iteracji.
Przykład
Producent ma swój magazyn we Wrocławiu. Odbiorcy mają swe lokalizacje w
ró\
nych miastach rejonu dystrybucji. PodstawowÄ… jednostka transportowÄ…
jest samochód mogący przewiez
ć Q=30 palet produktów, a czas
przebywania kierowcy na trasie nie mo\
e przekroczyć T=16 godzin.(960
min.)
Poznań
1
Legnica
3
Wrocław
Jelenia Góra
0
4
2
Wałbrzyc
h
Czasy przejazdów między miejscowościami rejonu dystrybucji i
zapotrzebowanie odbiorców.
000 11 2 3 4 bi
Wrocław 0 0 83 78 198 131 0
Wałbrzyc 1 83 0 81 273 63 8
h
Legnica 2 78 81 0 277 66 7
Poznań 3 198 273 277 0 288 14
Jelenia 4 131 63 66 288 0 9
Góra
Macierz S dla przewozów w rejonie dystrybucji
0 1 2 3 4
0 0 0 0 0 0
1 0 0 80 8 151
2 0 80 0 -1 143
3 0 8 -1 0 41
4 0 151 143 41 0
Tworzymy ciąg malejących wartości z dodatnich elementów macierzy S. Jest on
następujący:
S14 = 151 > S24 = 143 > S12= 80 > S34= 41 > S13= 8
Iteracja I
S14 = 151. Zarówno 1 jak 4 są obsługiwani indywidualnie, mo\
emy więc
rozpatrywać trasę H={0,1,4,0}. Otrzymujemy: T= 83 + 228 + 156 = 467 <
960 ;
b = 8 + 9 = 17 < 30. Trasa spełnia warunki dopuszczalności, przyjmujemy
H1={0,1,4,0}
Iteracja II
S24 = 143. 4 nale\
y do trasy H1 i jest odbiorcą krańcowym (ostatnim), a 2 jest
obsługiwany indywidualnie. Rozpatrujemy trasę {0,1,4,2,0}. Otrzymujemy:
T= 83 + 63 + 66 + 78 = 290 < 960
b = 8 + 9 + 7 = 24 < 30
Trasa spełnia warunki dopuszczalności . 2 dołączamy do trasy H1 , otrzymując
:
H1={0,1,4,2,0}
Iteracja III
S12= 80. Zarówno 1 jak i 2 nale\
Ä… do trasy H1. Nie rozpatrujemy tworzenia
nowej trasy.
Iteracja IV
S34= 41. 4 nale\
y do trasy H1 i jest odbiorcą pośrednim. Nie rozpatrujemy
tworzenia nowej trasy.
Iteracja V
S13= 8. 1 nale\
y do trasy H1 i jest odbiorcą krańcowym (pierwszym), a 3 jest
obsługiwany indywidualnie. Rozpatrujemy trasę {0,3,1,2,4,0}. Otrzymujemy:
T= 198 + 273+ 81 + 66 + 131 = 745 < 960
b= 14 + 8 + 7 + 9 = 38 > 30
Trasa nie spełnia warunków dopuszczalności. Nie mo\
emy 3 dołączyć do
trasy.
Poniewa\
wyczerpaliśmy listę mo\
liwych oszczędności, stwierdzamy, \
e
zasadnÄ… trasÄ… jest :
H1={0,1,4,2,0}, dla której T = 290 min. i b = 24 palety
Odbiorca 3 będzie obsługiwany indywidualnie co oznacza, \
e:
T = 198 + 198 = 396 min. I b = 14
Podsumowując do rozwozu towaru potrzebujemy dwóch samochodów, 38 palet
i zajmie nam to 869 min.
Wyznaczone trasy rozwozu
Poznań
1
Legnica
3
Wrocław
Jelenia Góra
0
4
2
Wałbrzyc
h
Rozdział zadań przewozowych
Zadania przydziału
W przykładzie dotyczącym wyznaczania tras dla wielu pojazdów operowaliśmy
umowną wielkością zarówno ładunku jak i pojazdu. W rzeczywistości
ładunki ró\
nią się składem produktów, równie\
pojazdy nie zawsze sÄ…
przystosowane do przewozu danego typu Å‚adunku. Powstaje wtedy problem
odpowiedniego przydziału pojazdów do tras przewozów (klientów). Jest to
zadanie ogólniejsze, znane w literaturze jako zadanie przydziału.
Zało\
enia problemu:
1. Mamy n jednostek wykonawczych Ri , i = 1,& , n, ( osób, maszyn,
samochodów ) oraz n zadań Zj , j = 1,& , n, do wykonania
2. Zakładamy, \
e ka\
da jednostka Ri mo\
e wykonać dowolne zadanie Zj ale
efektywność wykonania ka\
dego z zadań jest ró\
na
3. Efektywność wykonania zadania mo\
e być wyra\
ona albo przez miarÄ™
korzyści ( dij) albo przez miarę nakładu (kij)
Celem zadania jest przydzielenie jednostkom Ri zadania Zj tak aby efekt
sumaryczny był najkorzystniejszy.
Wprowadz
my zmienne xij , i =1,& ,n, j = 1,& ,n, które będą odzwierciedlały, czy
jednostce wykonawczej Ri zostało przydzielone zadanie Zj , czy nie. Wobec
tego znaczenia zmiennej xij są następujące:
1, gdy Ri otrzymuje zadanie zj
Å„Å‚
xij =
òÅ‚
ół0, w przeciwnym przypadku
Jednoznaczność przyporządkowań uzyskamy wprowadzając równania:
n
x = 1 , i = 1,..., n
" ij
i = 1
n
x = 1 , i = 1,..., n
" ij
j = 1
Gdy efektywność jest wyra\
ana przez miary korzyści, najkorzystniejszy efekt
wyra\
a funkcja kryterium:
n n
zl = d " xij max.
" " ij
i =1 j =1
Gdy efektywność jest wyra\
ana przez miary nakładów, najkorzystniejszy efekt
wyra\
a funkcja kryterium:
n n
zk = kij " xij min.
" "
i =1 j =1
Algorytm Węgierski
Krok I
Przekształcamy macierz współczynników funkcji kryterium ( D = [ dij ] lub K= [
kij ] ) tak, aby w ka\
dym wierszu i ka\
dej kolumnie występowało
przynajmniej jedno zero. W tym celu od ka\
dego wiersza macierzy
odejmujemy najmniejszy jego element, a następnie ( je\
eli trzeba ) od
ka\
dej kolumny tak przekształconej macierzy odejmujemy jej najmniejszy
element.
Krok II
W przekształconej macierzy współczynników funkcji kryterium nale\
y skreślić
wiersze i kolumny zawierajÄ…ce zera mo\
liwie najmniejszÄ… liczbÄ… linii
poziomych i pionowych. Je\
eli liczba tych linii jest równa wymiarowi
macierzy, czyli N, to mo\
na wyznaczyć rozwiązanie optymalne  nale\
y
przejść do kroku 3. Je\
eli liczba ta jest mniejsza ni\
N  nale\
y przejść do
kroku 4.
Krok III
Ustalenie rozwiÄ…zania optymalnego, polegajÄ…ce na takiej konstrukcji macierzy
X , aby jedynki znalazły się tylko na tych polach , na których w przekształconej
macierzy współczynników funkcji kryterium występują zera i aby w ka\
dym
wierszu i w ka\
dej kolumnie wystąpiło tylko jedno zero.
Krok IV
Je\
eli liczba linii pokrywajÄ…cych zera jest mniejsza od wymiaru macierzy, czyli
N, w bie\
ącej (przekształconej) macierzy współczynników funkcji kryterium
nale\
y znalez
ć najmniejszy nie skreślony element i ten element:
Odjąć od elementów nie skreślonych
Dodać do elementów podwójnie skreślonych
Elementy skreślone jedną linią pozostawić bez zmian
A następnie przejść do kroku 2 i powtarzać procedurę a\
do uzyskania
rozwiÄ…zania optymalnego
Kilka uwag na temat Algorytmu Węgierskiego:
1. Algorytm węgierski w opisanej postaci ma zastosowanie wyłącznie do
rozwiązywania problemów minimalizacji. Aby rozwiązać problem
maksymalizacji, nale\
y macierz współczynników funkcji kryterium
przekształcić tak, aby jej elementy miały przeciwne znaczenie, np. mno\
Ä…c
je przez -1, lub odejmując od największego elementu wszystkie pozostałe.
2. Model omawianego zagadnienia, a tym samym algorytm zakłada, \
e liczba
zadań do wykonania jest równa liczbie jednostek wykonawczych, a wiec
macierz współczynników funkcji kryterium jest macierzą kwadratową.
Tymczasem w wielu problemach zadań jest więcej ni\
jednostek
wykonawczych lub odwrotnie. W takich przypadkach do macierzy nale\
y
wprowadzić dodatkowy wiersz lub dodatkową kolumnę ( fikcyjną jednostkę
wykonawczą lub fikcyjne zadanie), których elementy są równe 0.
3. W praktyce zdarzajÄ… siÄ™ tak\
e sytuacje , \
e pewne przydziały są
niedopuszczalne ( tzn. określone elementy macierzy X z zało\
enia sÄ…
równe zeru). W takich przypadkach do macierzy współczynników funkcji
kryterium w miejscach, gzie ma być spełniony ten warunek wprowadza się
bardzo du\
Ä… liczbÄ™, np. M, takÄ…, \
e odjęcie od niej jakiejkolwiek liczby
praktycznie nie zmieni jej wartości.