P R A C E N A U K O W E P O L I T E C H N I K I W A R S Z A W S K I E J

z. 70

Transport

2009

Edward MICHLOWICZ

Akademia Górniczo – Hutnicza im. St. Staszica w Krakowie

Wydział In ynierii Mechanicznej i Robotyki

Al. Mickiewicza 30, 30-059 Kraków

e-mail: [e-mail]

PROBLEM KOMIWOJAĩERA DLA KILKU CENTRÓW

DYSTRYBUCJI

Streszczenie

Problem rozdziału zada przewozowych w typowym zadaniu transportowym jest mało przydatny dla

rednich firm transportowych obsługujcych wiele centrów dystrybucji. Z kolei problem komiwoja era dotyczy
tylko wybranych firm. Połczenie obydwu tych zagadnie mo e przynie wiele korzyci. W artykule
zaproponowano rozwizanie problemu przy zastosowaniu algorytmu ewolucyjnego. Przedstawiono formalizacj
zadania transportowego oraz formuł minimalnej macierzy wykorzystanej do budowy algorytmu genetycznego.
Problem komiwoja era został rozwa ony dla ka dego z wybranych centrów dystrybucji towarów.

Słowa kluczowe: problem komiwoja era, centrum dystrybucyjne

1. AKTUALNE PROBLEMY OPERATORÓW LOGISTYCZNYCH

Przed operatorem logistycznym staje czsto zadanie ustalenia takiego planu przewozów

towarów, który dawałby optymalne wyniki ze wzgldu na przyjte kryterium optymalizacyjne.
W sytuacji, gdy przedsibiorstwo posiada tylko jedno centrum dystrybucyjne, z którego
dostarcza towary na rynek, wyznaczenie optymalnego planu przewozów wi e si ze
znalezieniem najkrótszej drogi pomidzy poszczególnymi nabywcami towaru. Jeli natomiast
takich baz, zlokalizowanych w ró nych miejscach, jest wicej, celem jest ustalenie, z którego
centrum dystrybucyjnego ma by zaopatrywany w towar dany odbiorca i w jakiej kolejnoci
maj by oni „odwiedzani”, tak aby koszty transportu towaru były jak najmniejsze, przy
jednoczesnym uwzgldnieniu zasobu dysponowanego przez centra dystrybucyjne towarów.

Okrelenie połcze dostawcy – odbiorcy przy małej liczbie punktów dostaw i odbioru

nie stanowi wikszego problemu. Jednak, gdy w gr wchodzi wiksza liczba tych punktów,
wyznaczenie optymalnego planu przewozów nie jest ju takie oczywiste. W takim przypadku
istnieje wiele kombinacji ró nych połcze i wybór kombinacji optymalnej bez wykorzystania
odpowiedniej metody byłby niezwykle trudny.

Powszechnie znane s metody umo liwiajce wyznaczenie optymalnej drogi pomidzy

nabywcami towaru funkcjonujce w literaturze [2, 6, 8] pod nazw „problem komiwoja era”,
takie, jak chocia by: algorytm Little’a, algorytm włczania, algorytm poszukiwa lokalnych
2-optymalny i 3-optymalny oraz inne. Metody te daj rozwizanie jedynie wtedy, gdy
odbiorcy zaopatrywani s z jednego centrum dystrybucyjnego. W przypadku, gdy takich

Edward Michlowicz

miejsc zaopatrujcych w towary jest wicej, do rozwizania problemu mo na wykorzysta,
szeroko stosowane w ró nych dziedzinach nauki algorytmy ewolucyjne.

Problem komiwoja era (w skrócie TSP, od angielskiej nazwy „travelling salesperson

problem”) jest jednym z najstarszych problemów optymalizacyjnych wystpujcych
w działalnoci transportowej. Przenoszc zagadnienie do jzyka teorii sieci, problem polega
na znalezieniu najkrótszego cyklu długoci

n

(zwanego cyklem Hamiltona)

w n-wierzchołkowej sieci pełnej. Znalezienie właciwego cyklu Hamiltona, zwanego
w logistyce marszrut, jest zadaniem bardzo trudnym obliczeniowo. Zadanie to jest zaliczane
do problemów NP-trudnych i jak do tej pory nie udało si znale  sposobu, dla którego czas
rozwizania problemu byłby proporcjonalny do wielomianu zmiennej n.

Poszukiwanie najkrótszej marszruty poprzez sprawdzenie i porównanie wszystkich

mo liwych marszrut prowadzi do wykładniczej klasy zło onoci obliczeniowej O(n!).

Formułujc przedstawiony problem w sposób bardziej formalny: dany jest zbiór n miast

oraz nieujemna, kwadratowa macierz odległoci (kosztów) C=[c

ij

] stopnia n:

11

12

1

21

22

2

1

2

....

....

....

....

....

....

....

n

n

n

n

nn

c

c

c

c

c

c

C

c

c

c

ª

º

«

»

«

»

=

«

»

«

»

¬

¼

(1)

gdzie:

c

ij

-okrela odległo (koszt przejazdu) midzy miastem i a miastem j.

Rozpatrywane zagadnienie sprowadza si do znalezienia drogi zamknitej (i

1

,i

2

,...,i

n

,i

1

),

czyli marszruty, dla której suma

1 2

2 3

1

1

...

n

n

n

i i

i i

i

i

i i

c

c

c

c

−

+

+ +

+

osi

ga minimum.

Problem komiwoja

era mo na przedstawi jako zadanie wyznaczenia takiego x

ij

oraz

z

j

, aby:

1

1

min

ij

n

n

ij

i

j

c x

=

=

→

¦¦

(2)

gdzie:

x

ij

– zmienna decyzyjna,

( )

1,

je

eli marszruta zawiera odcinek

,

0

w przeciwnym przypadku.

ij

i j

x

­

= ®

¯

(3)

Ograniczenia:

1

1

i

N

n

ij

j

x

∈

=

∀

=

¦

(4)

1

1

j

N

N

ij

i

x

∈

=

∀

=

¦

(5)

,

i

j

ij

i

j

(z z

nx )

n-1, i

j, z , z

i j

N

R

∈

−

∀

+

≤

≠

∈

(6)

¯

®

­

−

−

=

∀

∈

przypadku

przeciwnym

w

0

j)

(i,

odcinek

zawiera

marszruta

1

,

ij

N

j

i

x

(7)

gdzie:

z

i

, z

j

– parametry ograniczenia.

114

Problem komiwoja era dla kilku centrów dystrybucji

Funkcja celu (2) postuluje minimalizacj

 długoci (kosztu) marszruty. Warunki

(4) oznaczaj

, e z ka dego miasta komiwoja er musi wyjecha jeden raz, a warunki (5), e

do ka

dego miasta mo e wjecha tylko jeden raz. Warunki (6) zapewniaj, e ze zbioru

n odcinków mo e by utworzona marszruta przechodzc przez n miast, czyli, e elementy
zbioru {(i,j): x

ij

=1} mo na ustawi w cig

¢ (i

1

,i

2

),(i

2

,i

3

),(i

n-1

,i

n

),(i

n

,i

1

)

² . Oznacza to, e

warunki (6) zapobiegaj

 przed pojawieniem si rozwizania składajcego si z marszruty nie

przechodz

cej przez wszystkie miasta.

Znanych jest kilka odmian zdefiniowanego powy

ej problemu, a mianowicie:

• wagi połcze nie musz by symetryczne (czyli

ij

ji

c

c

≠

) – w tym przypadku mamy do

czynienia z sieci

 skierowan, a rozpatrywany problem nosi nazw asymetrycznego

problemu komiwoja

era.

• rozwa any graf nie jest pełny, czyli zawiera par nie połczonych wierzchołków.

Wszystkie grafy pełne maj

 cykl długoci n, natomiast graf, który nie jest pełny, nie musi

mie

 takiego cyklu. W takich grafach problem komiwoja era nie ma rozwizania.

• komiwoja er po odwiedzeniu wszystkich miejscowoci (dokładnie raz), nie musi wraca

do miejscowo

ci, z której wyruszył. W takim przypadku nale y znale  najkrótsz drog

o długo

ci n-1, zamiast cyklu długoci n.

Problem komiwoja

era jest jednym z tych problemów optymalizacji kombinatorycznej,

dla których nie jest znany efektywny algorytm rozwi

zywania, tj. algorytm, który znajdowałby

rozwi

zanie optymalne w czasie wielomianowym, czyli w czasie bdcym wielomianem

zmiennej n, reprezentuj

cej liczb wierzchołków w sieci.

Rozpatruj

c problemem tak du ych rozmiarów, w celu jego rozwizania, mo na

zastosowa

 jedno z praktycznych podej [3, 4], polegajce na osłabieniu dania, by

algorytm dostarczał rozwi

zania optymalne i zadowoli si rozwizaniami przybli onymi,

odpowiednio bliskimi rozwi

za optymalnych.

Osłabienie warunku optymalno

ci pozwala czsto zredukowa czas oblicze

z wykładniczego do wielomianowego, przy niewielkiej utracie optymalno

ci. Algorytmy

przybli

one stanowi jedyny realistyczny sposób rozwizywania obliczeniowo trudnych

problemów du

ych rozmiarów. Istnieje wiele algorytmów przybli onych rozwizywania

problemu komiwoja

era, z których jednym z najbardziej efektywnych jest algorytm

przeszukiwa

 lokalnych.

Jedn

 z najbardziej znanych i stosowanych z najwikszym powodzeniem heurystyk

otrzymywania niemal optymalnych rozwi

za problemu komiwoja era jest algorytm

przeszukiwaĔ lokalnych. Polega on na wyznaczeniu dowolnej marszruty (G) i usuniciu z niej
r odcinków. Otrzymuje si w ten sposób r dróg (z których niektóre mog by izolowanymi
wierzchołkami), które ł

czc z innymi r odcinkami tworz marszrut (G'). Marszruty

G i G' ró ni si od siebie dokładnie r odcinkami, natomiast pozostałe (n – r) odcinków maj
takie same. Przykładow

 ilustracj wymiany dwóch łuków (marszruty G i G’) przedstawiono

na rysunku 1.

115

Edward Michlowicz

G-a-b G'=(G-a-b)+x+y

Rys. 1. Ilustracja wymiany dwóch łuków (wg [7])

ródło: opracowanie własne.

Je

li waga }(G') marszruty G' jest mniejsza od wagi }(G) marszruty G, to marszruta

G zastpowana jest marszrut G' i wymiana zostaje ponawiana. W przeciwnym przypadku
nale

y spróbowa wymieni inny zbiór r odcinków z marszruty G. Ten sposób wymiany jest

kontynuowany do momentu, w którym nie jest mo

liwe dalsze polepszanie rozwizania.

Rozwi

zanie kocowe, którego poprawa poprzez wymian r odcinków nie jest ju mo liwa,

nazywane jest rozwi

zaniem r-optymalnym.

Na ogół ta procedura wymiany odcinków ko

czy działanie poprzez wyznaczenie

lokalnego optimum, daj

c w ten sposób przybli one rozwizanie problemu komiwoja era.

Przedstawiony powy

ej algorytm jest przykładem ogólnego podejcia do rozwizywania

wielu problemów optymalizacji kombinatorycznej, zwanego przeszukiwaniem lokalnym lub
przeszukiwaniem s

siedztwa. Metoda sukcesywnego polepszania trasy komiwoja era za

pomoc

 wymiany r odcinków mo e by stosowana zarówno do problemów symetrycznych,

jak te

i niesymetrycznych.

Dla sieci symetrycznej z n (n > 5) wierzchołkami, r mo

e si zmienia od 2 do

n. Natomiast dla sieci skierowanej r nie mo e by mniejsze od 3.

Ogólnie, im wi

ksza jest ilo odcinków r podlegajcych wymianie w procedurze, tym

lepsze otrzymuje si

 rozwizanie. Z drugiej jednak strony, ka dy wzrost iloci odcinków

r znacznie zwiksza czas oblicze. Marszruta z n krawdziami zawiera

n

r

§ ·

¨ ¸

© ¹

podzbiorów

zło

onych z r krawdzi. Oznacza to, e czas wykonania zamiany ka dego z podzbiorów

przynajmniej raz wynosi O(n

r

). Nale y wic dokona przemylanego wyboru rozwa ajc

z

jednej strony dokładno

 rozwizania, a z drugiej nakład oblicze. Std te przy

podejmowaniu decyzji nale

y opiera si na intuicji i badaniach empirycznych.

2. WYZNACZANIE TRAS TRANSPORTU PRZY KILKU DOSTAWCACH

W przypadku, w którym przedsi

biorstwo posiada kilka centrów dystrybucyjnych

(magazynów), problem operatora logistycznego polega na takim przydzieleniu dostawcom
odpowiednich odbiorców, aby suma zapotrzebowa

 odbiorców nie przekraczała mo liwoci

zaopatrzeniowych poszczególnych dostawców oraz aby całkowity koszt transportu był
mo

liwie najmniejszy.

Na rysunku 2 przedstawiono interpretacj

 tego problemu w postaci grafu.

116

Problem komiwoja era dla kilku centrów dystrybucji

Rys. 2. Graf rozdziału zada przewozowych

ródło: opracowanie własne.

Opisany wy

ej problem funkcjonuje w literaturze pod pojciem zadanie transportowe.

Zadanie to (zagadnienie) mo

na interpretowa w ten sposób, e z poszczególnych centrów

dystrybucyjnych, wyje

d a tylu komiwoja erów ilu jest odbiorców zaopatrywanych z danego

magazynu. W takim przypadku ka

dy komiwoja er obsługuje jednego odbiorc, po czym

wraca do miejsca, z którego wyruszył (rys.3).

Alternatyw

 dla tego zagadnienia jest opracowanie algorytmu, dla którego z ka dego

magazynu wysyłany jest tylko jeden komiwoja

er, który odwiedza wszystkich przydzielonych

mu odbiorców, po czym wraca do miejsca pocz

tkowego. Problem ten na potrzeby

niniejszego opracowania został nazwany „Problemem komiwoja

Īera z wieloma centrami

dystrybucyjnymi” (w skrócie TSP-ZT), a jego graficzn interpretacj przedstawiono na
rysunku 4.

Rys. 3. Graf struktury dla zadania transportowego

ródło: opracowanie własne.

Problem komiwoja

era z wieloma centrami dystrybucyjnymi jest połczeniem dwóch

opisanych wcze

niej zagadnie: problemu komiwojaĪera oraz zadania transportowego.

117

Edward Michlowicz

Rys. 4. Graf struktury problemu komiwoja era z wieloma centrami dystrybucyjnymi

ródło: opracowanie własne.

Zatem zadanie mo

na interpretowa nastpujco:

Danych jest n dostawców, z których ka

dy dysponuje odpowiednio a

i

jednostkami

towaru (i=1, 2,…,n), oraz m odbiorców, z których ka

dy zgłasza zapotrzebowanie na towar

w wysoko

ci b

j

jednostek (j=1, 2,…,m). Ka

dy z dostawców mo e zaopatrywa dowolnych

odbiorców i odwrotnie, ka

dy odbiorca mo e otrzymywa towar od dowolnych dostawców.

Ka

dy komiwoja er mo e tylko raz wyruszy z bazy i po dostarczeniu towaru do odbiorców

musi do tej bazy powróci

. Ka de z miast mo e by odwiedzone przez danego dostawc tylko

jeden raz, przy czym miasta mog

 by odwiedzane w dowolnej kolejnoci. Zakłada si, e

odległo

ci a tym samym koszty transportu midzy ka d par miejscowoci s znane, a tak e

suma dostaw do poszczególnych odbiorców równa jest ich zapotrzebowaniu oraz suma
dostaw wysłanych przez dostawców nie przekracza ilo

ci, jak ka dy z dostawców dysponuje.

Całkowity koszt transportu natomiast jest równy sumie kosztów transportu ka

dego

z dostawców.

Zadanie transportowe sprowadza si

 wic do znalezienia minimum funkcji:

0 0

0

0

1

min z

(

)

n

ki

ki

j i

j i

jk

jki

i

j M k M

c x

c x

c x

= ∈

∈

=

+

+

¦ ¦ ¦

(8)

gdzie: i

– dostawca nale

cy do zbioru dostawców N,

j, k – odbiorcy pomidzy którymi odbywa si przewóz, nale cy do zbioru

odbiorców M,

c

jk

– koszt przewozu pomi

dzy odbiorcami j i k,

c

0ki

– koszt przewozu pomi

dzy i-tym dostawc a k-tym odbiorc,

c

j0i

– koszt przewozu pomi

dzy j-tym odbiorc a i-tym dostawc,

x

jki

– zmienna binarna okre

lajca, czy pomidzy odbiorcami j i k dostawca

i wykonuje przewóz,

x

0ki

– zmienna binarna okre

lajca, czy pomidzy dostawc i a odbiorc k jest

wykonywany przewóz,

118

Problem komiwoja era dla kilku centrów dystrybucji

x

j0i

– zmienna binarna okre

lajca, czy pomidzy odbiorc j a dostawc i jest

wykonywany przewóz.

Warunki ograniczaj

ce:

0

1

1

i

N

m

ki

k

x

∈

=

∀

=

¦

(9)

0

1

1

i

N

m

j i

j

x

∈

=

∀

=

¦

(10)

jki

k M

2; j

k,

x

i

N

j

M

∈

∈

∈

∀

∧

∀

<

≠

¦

(11)

l

j

k,

j

0;

M

l

jli

M

k

kji

M

j

N

i

x

x

≠

≠

=

−

∀

∧

∀

¦

¦

∈

∈

∈

∈

, (12)

i

m

1

j

ij

N

i

a

q

≤

∀

¦

=

∈

, (13)

j

n

1

i

ij

M

j

b

q

=

∀

¦

=

∈

, (14)

0

q

ij

M

j

N

i

≥

∀

∧

∀

∈

∈

(15)

gdzie:

ij

q – wielko zaopatrzenia od i-tego dostawcy do j-tego odbiorcy.

Warunek (9) zapewnia,

e komiwoja er wyje d a z bazy tylko raz, a warunek (10) – e

wje

d a tylko raz. Warunek (11) zapewnia, e komiwoja er mo e wjecha do okrelonego

miasta maksymalnie jeden raz, natomiast warunek (12) gwarantuje,

e po wjechaniu do

danego miasta komiwoja

er musi z tego miasta wyjecha. Warunek (13) oznacza, e ilo

towaru, w jak

 dostawca zaopatruje odbiorców nie przekracza jego mo liwoci

dystrybucyjnych, warunek (14) –

e wielko zaopatrzenia od dostawców musi by równa

ilo

ci, jakiej oczekuj odbiorcy, natomiast warunek (15) chroni przed wprowadzaniem

zaopatrze

 ujemnych.

3. ROZWI

ĄZANIE ZADANIA

Przedstawione powy

ej zagadnienie nale y do zada NP-trudnych i jedynym

racjonalnym podej

ciem do jego rozwizania jest zastosowanie heurystycznych algorytmów

optymalizacyjnych. Wykorzystane do tego celu zostan

 algorytmy ewolucyjne, które co

prawda nie gwarantuj

 otrzymania rozwiza optymalnych, ani nawet nie pozwalaj

oszacowa

 błdów rozwiza przybli onych, ale w wielu przypadkach prowadz do

rozwi

za dostatecznie dobrych z punktu widzenia praktycznych zastosowa.

Algorytmy ewolucyjne [1] to

cile zdefiniowane matematyczne procedury stosowane

do rozwi

zywania niektórych problemów optymalizacyjnych lub decyzyjnych, dla których

standardowe algorytmy s

 nieznane lub ich czas działania jest zbyt długi, by mogły by

praktycznie zastosowane.

Podstawowe typy algorytmów ewolucyjnych:

• algorytm genetyczny,

• strategie ewolucyjne,

- strategia (1+1),

119

Edward Michlowicz

- strategia (

~+\),

- strategia (

~, \),

• programowanie ewolucyjne.

Algorytm ewolucyjny mo

e koczy swoje działanie:

• gdy przystosowanie osobników jest odpowiednio du e,

• gdy stan populacji bazowej wiadczy o stagnacji algorytmu,

• po okrelonej z góry iloci cyklów ewolucyjnych.

Terminologia wykorzystywana w nazewnictwie elementów algorytmów ewolucyjnych

jest do

 specyficzna, bowiem powstała wskutek inspiracji genetyk i ewolucj.

Działanie algorytmu ewolucyjnego polega na przetwarzaniu populacji osobników,

z których ka

dy stanowi propozycj rozwizania postawionego problemu. Ka dy osobnik jest

wyposa

ony w informacj tzw. genotyp, na podstawie, którego generowany jest fenotyp –

zestaw cech, które podlegaj

 ocenie rodowiska. Proces tworzenia fenotypu z genotypu

nazywa si

 kodowaniem. Fenotyp jest punktem w przestrzeni rozwiza problemu, genotyp

za

 – punktem w przestrzeni kodów. Przystosowania osobnika na podstawie jego genotypu

dokonuje si

 za pomoc funkcji przystosowania. Funkcja ta mo e by stacjonarna, zmienna w

czasie lub mo

e zawiera element losowoci. Genotyp osobnika zło ony jest z chromosomów,

z których co najmniej jeden zawiera kod okre

lajcy fenotyp. Chromosomy natomiast składaj

si

 z mniejszych elementów, zwanych genami, które reprezentuj elementarne informacje.

Wraz z rozwojem i coraz wi

kszym zainteresowaniem algorytmami ewolucyjnymi

podstawowe typy algorytmów zacz

ły si do siebie nawzajem upodabnia. W programowaniu

ewolucyjnym sposób optymalizacji numerycznej został zbli

ony do strategii ewolucyjnych.

Algorytmy genetyczne wprowadziły schematy selekcji znane ze strategii ewolucyjnych
i programowania ewolucyjnego, natomiast strategie ewolucyjne, opieraj

c si na algorytmach

genetycznych, wzbogaciły operacje genetyczne o operator krzy

owania. W wyniku

wzajemnego przenikania si

, algorytm genetyczny, strategia ewolucyjna czy programowanie

ewolucyjne w swoich pierwotnych postaciach praktycznie ju

nie wystpuj, a nowo powstałe

algorytmy wykorzystuj

ce ich własnoci nosz ogóln nazw: algorytmy ewolucyjne.

Do rozwi

zania zadania komiwoja era obsługujcego kilka centrów dystrybucji został

napisany program komputerowy „Vitrans” przy u

yciu narzdzia programistycznego Borland

C++ Builder, przeznaczonego do tworzenia aplikacji w j

zyku C++.

Program „Vitrans” oparty o własno

ci algorytmów ewolucyjnych, umo liwia

wyznaczenie zada

 przewozowych dla standardowego problemu komiwoja era, jak równie

dla jego rozszerzonej wersji z wieloma centrami dystrybucyjnymi.

Posługuj

c si nazewnictwem stosowanym w algorytmach ewolucyjnych, program

wyznacza osobnika o najlepszym przystosowaniu, czyli takiego, dla którego całkowity koszt
transportu jest najmniejszy spo

ród wszystkich rozpatrywanych rozwiza.

Przystosowanie osobnika obliczane jest na podstawie informacji, w które ka

dy osobnik

jest wyposa

ony (genotyp, fenotyp). Dla rozpatrywanych problemów genotypem s

miejscowo

ci reprezentujce dostawców i odbiorców towaru, natomiast fenotypem –

poł

czenia (trasy) pomidzy tymi miejscowociami.

W algorytmie ewolucyjnym przetwarzana jest populacja składaj

ca si z jednego

osobnika. Do inicjacji pocz

tkowego rozwizania bazowego wykorzystano metod „minimum

macierzy kosztów”.

120

Problem komiwoja era dla kilku centrów dystrybucji

Otrzymane rozwi

zanie pocztkowe poddawane zostaje ocenie rodowiska, podczas

której obliczane jest przystosowanie osobnika na podstawie funkcji przystosowania osobnika
(funkcja z wg równania 8).

Zało

ono, e koszt przewozu zwizany jest bezporednio z odległoci d pomidzy

poszczególnymi miejscowo

ciami reprezentujcymi dostawców i odbiorców, dlatego te do

oblicze

 przyjto warto odległoci pomidzy miejscowociami. Odległo d mierzona jest

w linii prostej na podstawie współrz

dnych geograficznych i wyliczana z nastpujcego

wzoru:

d = R a cos (sin(lat

1

)sin(lat

2

) + cos(lat

1

)cos(lat

2

)cos(lon

1

– lon

2

)

(16)

gdzie: R

– promie

 Ziemi (równikowy); R=6378,137 km,

lat1(2) – szeroko

 geograficzna,

lon1(2)

–

długo

 geograficzna.

Po obliczeniu przystosowania osobnika program przyst

puje do głównej ptli, w której

ilo

 iteracji uzale niona jest od wprowadzonej przez u ytkownika wartoci.

W p

tli głównej osobnik bazowy poddawany jest reprodukcji, w wyniku czego

stworzona zostaje jego kopia, która jest przechowywana w pami

ci, natomiast procesom

mutacji poddawany jest osobnik bazowy.

Mutacja nast

puje w trzech etapach. Ka dy etap powtarzany jest dopóty, dopóki

warunek stopu nie zostanie spełniony. Zatrzymanie p

tli ka dego etapu mutacji zawiera

w sobie element losowo

ci, dlatego te nie mo na okreli iloci powtórze ka dego etapu,

a jedynie prawdopodobie

stwo jego zajcia.

W pierwszym etapie losowo wybrani odbiorcy zmieniaj

 swoj kolejno

„odwiedzania” ich przez przydzielonych im dostawców, czyli rozwi

zywany jest typowy

problem komiwoja

era. Prawdopodobiestwo zajcia mutacji w tym etapie wynosi 70%.

W drugim etapie nast

puje przydzielenie odbiorcom nowych dostawców wg równa

z rozdziału 2, w taki sposób, aby całkowita ilo

 dostaw ka dego z dostawców nie uległa

zmianie. Mutacja w tym etapie zachodzi wówczas, gdy odbiorców zaopatruje wi

cej ni jeden

dostawca a jej prawdopodobie

stwo zajcia wynosi 60%.

Trzeci etap mutacji zachodzi wtedy, gdy mamy do czynienia z wieloma centrami

dystrybucyjnymi a ponadto, gdy całkowita ilo

 dostaw przekracza całkowit ilo

zapotrzebowa

. W etapie tym nastpuje przerzucanie dostaw pomidzy dostawcami, przy

zachowaniu odpowiednich równa

, a prawdopodobiestwo jego zajcia wynosi 80%.

Po zako

czonym procesie mutacji osobnik poddawany jest ocenie rodowiska,

a nast

pnie jego przystosowanie porównywane jest z przystosowaniem jego kopii sprzed

etapu mutacji. W nast

pnej iteracji osobnikiem bazowym staje si ten, który charakteryzuje

si

 lepszym przystosowaniem.

4. PRAKTYCZNE ZASTOSOWANIE PROGRAMU „VITRANS V1.0”

W celu sprawdzenia działania programu „Vitrans” oraz przedstawienia jako

ci

generowanych przez program wyników, wyznaczono trasy transportu towarów dla danych
zawartych w tablicy 1.

Na rysunku 5 przedstawiono okno główne programu po wprowadzeniu powy

szych

danych. Ilo

 iteracji programu ustawiono na 100 tysicy kroków.

121

Edward Michlowicz

Rys. 5. Okno główne programu Vitrans V1.0 z naniesionymi danymi.

ródło: opracowanie własne.

Ilo

 całkowitego zasobu dysponowanego przez dostawców wynosiła 540 jednostek

towaru, z czego Kraków miał w dyspozycji 160 jednostek, Łód

– 100, Warszawa –

150, natomiast Wrocław 130 jednostek. Ka

demu z odbiorców przydzielono wymagan ilo

towaru, która w sumie wyniosła 515 jednostek. Po rozdysponowaniu towaru pomi

dzy

odbiorcami w magazynach pozostało 25 jednostek towaru zapasu, przy czym w Krakowie
pozostało 11 jednostek, w Łodzi – 5, w Warszawie – 6, a we Wrocławiu – 3 jednostki.
Całkowita droga do pokonania przez komiwoja

erów wyniosła 3449.17 km.

Rozwi

zanie zadania dla

10

5

iteracji

przedstawiono na rysunku 6.

Rys. 6. Okno programu z rozwizaniem dla 105 iteracji

ródło: opracowanie własne.

122

Problem komiwoja era dla kilku centrów dystrybucji

Tablica 1. Zestawienie danych zadania.

Lp. Dostawca

Limit

towaru Lp. Odbiorca

Zapotrzebowanie

1 Kraków

160

1 Białystok

20

2 Łód 100

2

Bielsko-Biała 18

3 Warszawa

150

3 Chełm

21

4 Wrocław

130

4 Chorzów

22

SUMA =

540

5 Dbica 20
6 Elblg 19
7 Ełk

20

8 Gdask 25
9 Gniezno

18

10 Grudzidz 20
11 Jarocin

14

12 Kalisz

17

13 Kielce

24

14 Kołobrzeg

20

15 Krosno

21

16 Lubin

19

17 Malbork

17

18 Nysa

23

19 Płock

23

20 Pozna

26

21 Przemyl 24
22 Radom

22

23 Sandomierz

20

24 Suwałki

17

25 Szczecin

25

SUMA

= 515

ródło: opracowanie własne

Program „Vitrans” do wyznaczania tras transportu wykorzystuje własno

ci algorytmów

ewolucyjnych, dlatego te

nie wiadomo czy wygenerowane rozwizanie jest rozwizaniem

optymalnym, ani te

jak bardzo si od niego ró ni. W celu okrelenia jakoci otrzymanego

rozwi

zania przeprowadzono kilka symulacji tego samego problemu dla ró nych wartoci

liczby iteracji. Wyniki symulacji przedstawiono na poni

szym wykresie (rys. 7).

Dla niewielkiej liczby kroków (100) program wygenerował rozwi

zanie o blisko 30%

gorsze, ni

dla 10

5

kroków. Jednak dalsze zwi

kszanie liczby iteracji, powy ej 10

5

kroków,

nie spowodowało wygenerowania rozwi

zania lepszego, a w przypadku liczby iteracji równej

10

6

otrzymano nawet rozwi

zanie niewiele gorsze, co mo e sugerowa, e dalsze zwikszanie

liczby kroków nie polepszy znacz

co rozwizania, a jedynie zwikszy czas wykonywania

oblicze

 przez program. Mo e to oznacza, e rozwizanie, dla którego całkowita droga

transportu wynosi 3449.17 km jest rozwi

zaniem optymalnym lub le cym bardzo blisko

takiego rozwi

zania.

123

Edward Michlowicz

Rys.7. Wykres zale noci wygenerowanego rozwizania od liczby iteracji.

ródło: opracowanie własne

4. PODSUMOWANIE I DALSZE BADANIA

Problem wyznaczenia optymalnego planu przewozów towarów pomi

dzy dostawcami

a odbiorcami jest problemem NP-trudnym, co oznacza,

e nie istnieje algorytm rozwizujcy

ten problem w czasie wielomianowym. Przy rozwi

zywaniu takich problemów (du ych

rozmiarów) cz

sto rezygnuje si ze spełnienia warunku by algorytm dostarczał rozwizanie

optymalne i zadowala rozwi

zaniem przybli onym, le cym blisko rozwizania optymalnego.

Zastosowanie heurystycznych algorytmów optymalizacyjnych cz

sto pozwala zredukowa

czas oblicze

 z wykładniczego do wielomianowego, przy niewielkiej utracie optymalnoci.

Do napisania programu „Vitrans” wykorzystano jeden z heurystycznych algorytmów

optymalizacyjnych, jakim jest algorytm ewolucyjny, ze wzgl

du na jego prostot schematu,

dzi

ki któremu algorytmy tego typu znajduj liczne zastosowania praktyczne w ró nych

dziedzinach nauki.

W zastosowanym algorytmie bazowe rozwi

zanie pocztkowe nie jest generowane

losowo, lecz przy wykorzystaniu metody „minimum macierzy kosztów”, dzi

ki czemu ju na

pocz

tku otrzymane rozwizanie jest w znacznym stopniu przybli one do optymalnego.

Program „Vitrans” w krótkim czasie generuje rozwi

zanie bardzo trudnych

obliczeniowo zada

, co czyni go programem atrakcyjnym dla operatorów logistycznych, firm

spedycyjnych czy te

firm produkcyjno – dystrybucyjnych.

Rozwa

any w opracowaniu problem warto rozwin. Znane w badaniach operacyjnych

tzw. zadanie transportowo – produkcyjne dotyczy optymalizacji ł

cznych kosztów transportu

i przerobu jednorodnych surowców dostarczonych do zakładów przetwarzaj

cych te surowce

na wyroby gotowe. W odniesieniu do zakładów przetwórstwa odpadów powstaje zło

ony

problem zbierania, gromadzenia i przetwarzania tych odpadów przy nieliniowej funkcji
kosztów przerobu. W wielu przypadkach zgromadzenie odpowiednio uzasadnionej

124

Problem komiwoja era dla kilku centrów dystrybucji

ekonomicznie ilo

ci odpadów (masa, objto) w miejscach składowania (centrach) wymaga

wielokrotnej obsługi rozproszonych punktów zbiórki odpadów. Z wst

pnych bada [5] mo na

wywnioskowa

, e koszty utylizacji mog by aproksymowane wielomianami drugiego

stopnia. Uwzgl

dniaj one tylko koszty zmienne, czyli zale ne od rozmiarów produkcji.

Rozwi

zanie tak postawionego zadania transportowo – produkcyjnego z kwadratow

funkcj

 kosztów przerobu polega na wyznaczeniu takiego planu dostaw surowca (odpadów)

do poszczególnych zakładów i jego przetworzenia w tych zakładach, aby ł

czne koszty

transportu i przerobu były minimalne.

LITERATURA

[1]

Arabas J.: Wykłady z algorytmów ewolucyjnych. WNT, Warszawa 2001.

[2]

Ignasiak E.: Badania operacyjne. PWE, Warszawa 2001.

[3]

Jacyna M., Jachimowski R., Pryciski P.: Wspomaganie komputerowe wyznaczania
optymalnych tras w wieloszczeblowym systemie dystrybucji. Wybrane Zagadnienia Logistyki
Stosowanej. Wydawnictwa AGH, Kraków 2009.

[4]

Michlowicz E.: Optymalizacja zadaĔ operatora logistycznego. Logistyka nr 3/2009.

[5]

Michlowicz E.: Transportation

− Production Task Pertaining to Waste Disposal with Use of

Cost Convex Function. Polish Journal of Environmental Studies. Vol. 18, No. 3A, 2009. Hard
Publishing Comp., Olsztyn 2009.

[6]

Sikora W.: Badania operacyjne. PWE, Warszawa 2008.

[7]

Sysło M.M., Deo N., Kowalik J.S.: Algorytmy optymalizacji dyskretnej.PWN, Warszawa 1995.

[8]

Waters D.: Zarządzanie operacyjne: towary i usługi. PWN, Warszawa 2001.

TRAVELING SALESMAN PROBLEM FOR A NUMBER OF DISTRIBUTION CENTERS

Abstract

The problem of allocation tasks in a typical transport issue is not useful for medium-sized transport

companies operating multiple distribution centers. The bagman problem affects only the selected companies. The
combination of both of these issues can bring many benefits. This paper proposes a solution to the problem using
the evolutionary algorithm.

Key words: travelling salesperson problem, distribution center

Recenzent: Marianna Jacyna

125