Wykład1

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

pobrane z jednego magazynu (

) i dostarczane do

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

4. Produkty b

rozwo

one identycznymi

rodkami transportu o ładowno

(

Q > bi, i=1,…,n

5. Czas przebywania na trasie, ka

dego pojazdu, nie mo

e przekroczy

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

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

ęś

ciowych:

1. Przydziału

2. Wyznaczania tras

Stosowane oznaczenia:

•

– dowolna trasa rozpoczynaj

ca si

w punkcie

i przebiegaj

ca przez

punkty

i1,i2,…ir

i ko

ca si

w punkcie

•

tij

- czas przejazdu z punktu

do punktu

, przy zało

eniu,

+ t

≤

•

t(H) = t

+ t

+…+ t

o ,

t(H)

≤

- czas przejazdu dowolnej trasy

•

b(H) = b

+ … + b

, b(H)

≤

- ł

czna wielko

ść

zamówie

dowolnej trasy

Wariant wyj

ciowy:

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:

)

(

∑

)

(

)

(

•

Wspólna obsługa:

Obliczaj

c ró

nic

czasów otrzymujemy:

Warto

ść

okre

la wielko

ść

zaoszcz

dzonego czasu.

−

Algorytm oszcz

dno

ciowego ł

czenia tras.

Zało

enia startowe:

1. Znamy czasy przejazdów

, i,j=0,1,…n

. Na podstawie tych czasów

obliczamy potencjalne oszcz

dno

ci czasów przejazdu

. Warto

porz

dkujemy malej

co, odrzucaj

c wcze

niej wszystkie

≤

;

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

ść

i odczytujemy wskazania numerów

odbiorców. Je

eli zbiór jest pusty post

powanie si

czy. Otrzymali

rozwi

zanie .

Krok 2

Sprawdzamy, jak

pozycj

zajmuj

wskazani odbiorcy

oraz

w swych trasach

i w zale

ci od ich umiejscowienia albo dokonujemy ł

czenia tras albo

pozostawiamy bez zmian.

Przypadek I

Gdy ani

, ani

nie nale

Ŝą

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

nale

y do pewnej grupy, natomiast

jest obsługiwany indywidualnie,

musimy uwzgl

dni

, jakie miejsce w trasie zajmuje i:

1. Je

eli

jest odbiorc

rednim w swej grupie – nie rozpatrujemy

doł

czenia

do grupy.

2. Je

eli

jest odbiorc

kra

cowym, sprawdzamy, czy doł

czenie

do trasy nie

naruszy warunków dopuszczalno

ci przewozu. Je

eli warunki przewozu s

spełnione, odbiorc

doł

czmy do trasy zawieraj

cej

, przy czym

dzie

obsługiwany:

– Przed

, gdy

wyst

pował w trasie jako pierwszy, czyli tworzymy tras

{0,j,i,…,0}

– Po

, gdy

wyst

pował jako ostatni, czyli tworzymy tras

{0,…,i,j,0}

Przypadek

III

eli

nale

y do trasy

do np.:

To poł

czenie tras ma sens, gdy

zarówno

jak i

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

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

Pozna

Wrocław

Wałbrzyc
h

Legnica

Jelenia Góra

Czasy przejazdów mi

dzy miejscowo

ciami rejonu dystrybucji i

zapotrzebowanie odbiorców.

Wrocław

198

131

Wałbrzyc
h

273

Legnica

277

Pozna

198

273

277

288

Jelenia
Góra

131

288

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:

= 151 > S

= 143 > S

= 80 > S

= 41 > S

= 8

Iteracja I

= 151. Zarówno 1 jak 4 s

obsługiwani indywidualnie, mo

emy wi

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

={0,1,4,0}

151

-1

143

-1

151

143

Iteracja II

= 143. 4 nale

y do trasy H

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

, otrzymuj

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

Iteracja III

= 80. Zarówno 1 jak i 2 nale

Ŝą

do trasy H

. Nie rozpatrujemy tworzenia

nowej trasy.

Iteracja IV

= 41. 4 nale

y do trasy H

i jest odbiorc

rednim. Nie rozpatrujemy

tworzenia nowej trasy.

Iteracja V

= 8. 1 nale

y do trasy H

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

trasy.

Poniewa

wyczerpali

my list

liwych oszcz

dno

ci, stwierdzamy,

zasadn

tras

jest :

={0,1,4,2,0}, dla której T = 290 min. i b = 24 palety

Odbiorca 3 b

dzie obsługiwany indywidualnie co oznacza,

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.

Rozdział zada

przewozowych

Zadania przydziału

W przykładzie dotycz

cym wyznaczania tras dla wielu pojazdów operowali

umown

wielko

zarówno ładunku jak i pojazdu. W rzeczywisto

ładunki ró

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

, i = 1,…, n

, ( osób, maszyn,

samochodów ) oraz n zada

, j = 1,…, n

, do wykonania

2. Zakładamy,

e ka

da jednostka

e wykona

dowolne zadanie

ale

efektywno

ść

wykonania ka

dego z zada

jest ró

3. Efektywno

ść

wykonania zadania mo

e by

wyra

ona albo przez miar

korzy

ci (

) albo przez miar

nakładu (

)

Celem zadania jest przydzielenie jednostkom

zadania

tak aby efekt

sumaryczny był najkorzystniejszy.

Wprowad

my zmienne

, i =1,…,n, j = 1,…,n

, które b

odzwierciedlały, czy

jednostce wykonawczej

zostało przydzielone zadanie

, czy nie. Wobec

tego znaczenia zmiennej

nast

puj

ce:

Jednoznaczno

ść

przyporz

dkowa

uzyskamy wprowadzaj

c równania:







przypadku

przeciwnym

zadanie

otrzymuje

gdy

∑

1,...,

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:

∑ ∑

→

∗

max.

∑ ∑

→

∗

min.

Algorytm W

gierski

Krok I

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

D = [ d

] lub K= [

]

) 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

dej kolumny tak przekształconej macierzy odejmujemy jej najmniejszy

element.

Krok II

W przekształconej macierzy współczynników funkcji kryterium nale

y skre

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

, to mo

na wyznaczy

rozwi

zanie optymalne – nale

przej

ść

do kroku 3. Je

eli liczba ta jest mniejsza ni

– nale

y przej

ść

kroku 4.

Krok III

Ustalenie rozwi

zania optymalnego, polegaj

ce na takiej konstrukcji macierzy

, 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

eli liczba linii pokrywaj

cych zera jest mniejsza od wymiaru macierzy, czyli

, 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

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

problem

maksymalizacji, nale

y macierz współczynników funkcji kryterium

przekształci

tak, aby jej elementy miały przeciwne znaczenie, np. mno

Ŝą

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

wprowadzi

dodatkowy wiersz lub dodatkow

kolumn

( fikcyjn

jednostk

wykonawcz

lub fikcyjne zadanie), których elementy s

równe 0.

3. W praktyce zdarzaj

tak

e sytuacje ,

e pewne przydziały s

niedopuszczalne ( tzn. okre

lone elementy macierzy

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.