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

t

oi

+ t

io

≤

T

•

t(H) = t

oi

1

+ t

i

1

i

2

+…+ t

ir

o ,

t(H)

≤

T

- czas przejazdu dowolnej trasy

•

b(H) = b

i

1

+ … + b

i

r

, b(H)

≤

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 :

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:

•

Indywidualna obsługa:

)

(

1

oi

n

i

io

t

t

z

+

=

∑

=

)

(

)

(

0

jo

oj

io

oi

t

t

t

t

t

+

+

+

=

i

0

j

t

0i

t

i0

t

j0

t

0j

•

Wspólna obsługa:

Obliczaj

ą

c ró

ż

nic

ę

czasów otrzymujemy:

Warto

ść

s

ij

okre

ś

la wielko

ść

zaoszcz

ę

dzonego czasu.

jo

ij

oi

t

t

t

t

+

+

=

i

i

j

j

0

t

ij

t

i0

t

j0

ij

j

i

ij

t

t

t

t

t

s

−

+

=

−

=

0

0

1

0

Algorytm oszcz

ę

dno

ś

ciowego ł

ą

czenia tras.

Zało

ż

enia startowe:

1. Znamy czasy przejazdów

t

ij

, i,j=0,1,…n

. Na podstawie tych czasów

obliczamy potencjalne oszcz

ę

dno

ś

ci czasów przejazdu

s

ij

. Warto

ś

ci

s

ij

porz

ą

dkujemy malej

ą

co, odrzucaj

ą

c wcze

ś

niej wszystkie

s

ij

≤

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

ść

s

ij

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

H

1

,

a

j

do np.:

H

2

.

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

ą

s

ij

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 przewie

źć

Q=30 palet produktów, a czas

przebywania kierowcy na trasie nie mo

ż

e przekroczy

ć

T=16 godzin.(960

min.)

4

3

2

1

0

Pozna

ń

Wrocław

Wałbrzyc
h

Legnica

Jelenia Góra

Czasy przejazdów mi

ę

dzy miejscowo

ś

ciami rejonu dystrybucji i

zapotrzebowanie odbiorców.

00

0

1

1

2

3

4

b

i

Wrocław

0

0

83

78

198

131

0

Wałbrzyc
h

1

83

0

81

273

63

8

Legnica

2

78

81

0

277

66

7

Pozna

ń

3

198

273

277

0

288

14

Jelenia
Góra

4

131

63

66

288

0

9

Macierz S dla przewozów w rejonie dystrybucji

Tworzymy ci

ą

g malej

ą

cych warto

ś

ci z dodatnich elementów macierzy S. Jest on

nast

ę

puj

ą

cy:

S

14

= 151 > S

24

= 143 > S

12

= 80 > S

34

= 41 > S

13

= 8

Iteracja I

S

14

= 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

H

1

={0,1,4,0}

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

Iteracja II

S

24

= 143. 4 nale

ż

y do trasy H

1

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 H

1

, otrzymuj

ą

c

:

H

1

={0,1,4,2,0}

Iteracja III

S

12

= 80. Zarówno 1 jak i 2 nale

żą

do trasy H

1

. Nie rozpatrujemy tworzenia

nowej trasy.

Iteracja IV

S

34

= 41. 4 nale

ż

y do trasy H

1

i jest odbiorc

ą

po

ś

rednim. Nie rozpatrujemy

tworzenia nowej trasy.

Iteracja V

S

13

= 8. 1 nale

ż

y do trasy H

1

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 :

H

1

={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

4

3

2

1

0

Pozna

ń

Wrocław

Wałbrzyc
h

Legnica

Jelenia Góra

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

R

i

, i = 1,…, n

, ( osób, maszyn,

samochodów ) oraz n zada

ń

Z

j

, j = 1,…, n

, do wykonania

2. Zakładamy,

ż

e ka

ż

da jednostka

Ri

mo

ż

e wykona

ć

dowolne zadanie

Z

j

ale

efektywno

ść

wykonania ka

ż

dego z zada

ń

jest ró

ż

na

3. Efektywno

ść

wykonania zadania mo

ż

e by

ć

wyra

ż

ona albo przez miar

ę

korzy

ś

ci (

d

ij

) albo przez miar

ę

nakładu (

k

ij

)

Celem zadania jest przydzielenie jednostkom

Ri

zadania

Zj

tak aby efekt

sumaryczny był najkorzystniejszy.

Wprowad

ź

my zmienne

x

ij

, 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

x

ij

s

ą

nast

ę

puj

ą

ce:

Jednoznaczno

ść

przyporz

ą

dkowa

ń

uzyskamy wprowadzaj

ą

c równania:







=

przypadku

przeciwnym

w

,

0

z

zadanie

otrzymuje

R

gdy

,

1

j

i

ij

x

∑

∑

=

=

=

=

=

=

n

1

j

1

n

1,...,

i

,

1

n

1,...,

i

,

1

ij

n

i

ij

x

x

Gdy efektywno

ść

jest wyra

ż

ana przez miary korzy

ś

ci, najkorzystniejszy efekt

wyra

ż

a funkcja kryterium:

Gdy efektywno

ść

jest wyra

ż

ana przez miary nakładów, najkorzystniejszy efekt

wyra

ż

a funkcja kryterium:

∑ ∑

=

=

→

∗

=

n

i

n

j

ij

ij

l

x

d

z

1

1

max.

∑ ∑

=

=

→

∗

=

n

i

n

j

ij

ij

k

x

k

z

1

1

min.

Algorytm W

ę

gierski

Krok I

Przekształcamy macierz współczynników funkcji kryterium (

D = [ d

ij

] lub K= [

k

ij

]

) 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 znale

źć

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.