Strona główna

Optymalizacja bazy transportowej Wyznaczanie najkrótszej drogi w sieci


Pobieranie 394.18 Kb.
Strona4/4
Data18.06.2016
Rozmiar394.18 Kb.
1   2   3   4

Rys. indywidualna obsługa dwóch odbiorców


Gdyby jednak w miejsce dwóch odrębnych tras zaproponowalibyśmy jedna wspólną od 0 do i potem do j i z powrotem do 0. Wtedy czas obsługi wyniósłby:

t1=toi+tij+tjo





Rys. Połączenie obsługi dwóch odbiorców

Obliczając różnice otrzymujemy:

sij=to-ti=tio+toj-tij

Jeśli sij>0, to sumaryczny czas indywidualnej obsługi trwa dłużej niż czas obsługi w ramach połączonej trasy. Wartość ta określa wielkość zaoszczędzonego czasu sij<0 oznacza ujemna oszczędność, tzn. że indywidualny tras nie powinno się łączyć we wspólną trasę.

Rozważamy przypadek dwóch tras:

H=[0,h,…i,0]

H=[0,j,….k,0]

W każdej z tych tras wyróżniliśmy dwóch klientów, którzy są obsługiwani jako pierwsi (h,j) i jako ostatni (i,k). Będziemy ich nazywać odbiorcami krańcowymi w swoich trasach. Pozostali to odbiorcy pośredni. Dokonujemy połączenia tych dwóch tras w jedną. Po odwiedzeniu klienta z pierwszej trasy powinien nastąpić powrót do punktu startu. Zamiast tego następuje wizyta u pierwszego klienta drugiej trasy i dalej kontynuacja odwiedzin zgodnie z wytyczona druga trasą. Wyróżnienie która z tras jest pierwsza a która druga odgrywa jedynie rolę ilustracyjną podobnie jak wyróżnienie strzałek na rysunku.














Rys. Połączenie dwóch tras


Nowa trasa H = [0,h,…i,j….k,0] wymaga realizacji dostaw o łącznej ładowności:

b(h )=b(H1)+b(H2),

a czas jej przejazdu wynosi:

t(H)=t(H1)+t(H2)-toi-toj+tij=t(H1)+t(H2)-sij


Gdy nastąpi skrócenie łącznego czasu przejazdu i będą zachowane warunki dopuszczalności przejazdu, czyli b(H )< Q oraz t(H ) < T to trasę H uznamy za oszczędną. Wraz z oszczędnością czasu przejazdu uzyskujemy zmniejszenie liczby środków transportu, gdyż w miejsce dwóch wysyłamy na trasę tylko jeden pojazd. Liczba tras będzie równoznaczna z liczbą pojazdów potrzebnych do obsługi klientów.

Są przypadki w których nie ma sensu rozpatrywanie łączenia tras. Są to:



  • Odbiorcy, którzy już zostali uwzględnieni w tej samej trasie

  • Nowi odbiorcy – dołączenie do trasy może nastąpić albo do jej początku albo na jej koniec, czyli nie ma sensu rozpatrywanie oszczędności czasu między nowym a jakimkolwiek pośrednim odbiorcą grupy uwzględnionej już w trasie.


2.2 Oszczędnościowe łączenie tras

Założenia startowe:



    • Rozpatrujemy zadanie w którym znamy czasy przejazdów tij, i, j=0,1…n. Na podstawie czasów tij obliczamy potencjalne oszczędności czasów przejazdu sij. Wartości sij porządkujemy malejąco, odrzucając wcześniej wszystkie sij<0

    • Przyjmujemy początkowo, że każdy odbiorca jest obsługiwany indywidualnie, co oznacza że do obsługi kierujemy n pojazdów, co oznacza, że wstępnie dopuszczamy

Przykład:

Producent ma swój magazyn we Wrocławiu. Odbiorcy maja swe lokalizacje w różnych miejscach rejonu dystrybucji. Rysunek przedstawia mapę połączeń komunikacyjnych między miejscowościami rejonu dystrybucji. W tabeli mamy przedstawione czasy przejazdu między miejscowościami w minutach oraz wielkość dostawy do danej miejscowości z magazynu producenta. Jednostką dostawy jest paleta. Podstawową jednostką transportową jest samochód mogący przewieźć Q=32 palety produktów, a czas przebywania kierowcy w trasie nie może przekroczyć T=16 godzin, czyli 960 minut.













































Rys. Mapa połączeń komunikacyjnych dystrybutora z Wrocławia








0

1

2

3

4

5

6

7

8

9




Wrocław

0

0

83

78

198

156

212

309

361

216

131

0

Wałbrzych

1

83

0

81

273

228

282

380

439

291

63

8

Legnica

2

78

81

0

277

211

292

396

450

307

66

7

Poznań

3

198

273

227

0

156

345

466

427

90

288

14

Kalisz

4

156

228

211

156

0

200

338

271

268

274

6

Częstochowa

5

212

282

292

345

200

0

139

157

81

336

5

Kraków

6

309

380

396

466

338

139

0

158

93

451

15

Kielce

7

361

439

450

427

271

157

158

0

207

512

12

Katowice

8

216

291

307

390

268

81

93

207

0

346

11

Jelenia Góra

9

131

63

66

288

274

336

451

512

346

0

9


Tab. Czasy przejazdów między miejscowościami rejonu dystrybucji

W tym przykładzie zakładamy, że mamy określone czasy przejazdu między każdymi dwoma miejscowościami, nawet gdy nie ma między nimi bezpośredniego połączenia. Z mapy połączeń można odczytać, że z Wrocławia do Krakowa można dojechać przez Katowice, albo przez Częstochowę. Pierwsza trasa ma czas przejazdu 216+93=309 min , natomiast druga 212+139=351 min. W tabeli czasów przejazdu uwzględniana jest krótsza, pierwsza trasa.



Wyznaczamy teraz macierz S, której elementy sij=tio+tjo-tij, dla i, j=1,…n,i>j oraz sij=0 dla i=j. bierzemy największą wartość sij i odczytujemy wskazania numerów odbiorców. Jeżeli zbiór tych wartości jest pusty – postępowanie się kończy.




0

1

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

0

0

0

1

0

0

80

8

11

13

12

5

8

151

2

0

80

0

-1

23

-2

-9

-11

-13

143

3

0

8

-1

0

198

65

41

132

24

41

4

0

11

23

198

0

168

127

246

104

13

5

0

13

-2

65

168

0

382

416

347

7

6

0

12

-9

41

127

382

0

512

432

-11

7

0

5

-11

132

246

416

512

0

370

-20

8

0

8

-13

24

104

347

432

370

0

1

9

0

151

143

41

13

7

-11

-20

1

0


Tab. Planowanie tras dostaw dla wielu pojazdów

Macierz S dla przewozów w rejonie dystrybucji

Tworzymy teraz ciąg malejących wartości z dodatnich elementów macierzy S. Jest on następujący:


S67> S68> S57> S56> S78> S58> S47> S34> S45> S19>

  1. 432> 416> 382> 370> 347> 246> 198> 168> 151>

S29> S37> S46> S48> S12> S35> S39= S36> S38> S24>

143> 132> 127> 104> 80> 65> 41= 41> 24> 23>

S49= S15> S16> S14> S18= S13> S59> S17> S89

13= 13> 12> 11> 8= 8> 7> 5> 1

Rozwiązaniem startowym jest indywidualna obsługa każdego z klientów, co oznacza, że powinniśmy dysponować 9 samochodami. W kolejnych interakcjach będziemy sprawdzać, czy można trasy i tym samym zmniejszać liczbę samochodów.
INTERAKCJA 1

S67=512. Zarówno 6 jak i 7 są obsługiwani indywidualnie, a więc tworzymy grupę {i,j} i sprawdzamy, czy trasa H=[0,6,7,0] spełnia warunki dopuszczalności przewozu. Gdy warunki są spełnione - tworzymy trasę [0,6,7,0]. W przeciwnym wypadku skreślamy s z listy i przechodzimy do następnego wskaźnika oszczędności.

Mamy zatem:

T=309+158+361=828<960 – dopuszczalny czas przewozu

b=15+12=27<32 – ładowność

trasa spełnia warunki dopuszczalności. Przyjmujemy zatem:

H=[0,6,7,0]

INTERAKCJA 2

S62=432. 6 należy do trasy H i jest odbiorcą krańcowym, a konkretnie – pierwszym. Natomiast 8 jest obsługiwany indywidualnie. Odbiorca i jest więc odbiorcą krańcowym, sprawdzamy zatem, czy dołączenie odbiorcy j do trasy nie naruszy warunków dopuszczalności przewozu. Jeśli warunki przewozu są spełnione to odbiorcę j dołączamy do trasy zawierającej i przy czym j będzie obsługiwany:



  • Przed i, gdy i występował w trasie jako pierwszy






















Rys. Dołączenie j do trasy przed i

Trasa wygląda następująco [0,j,i….0]



  • Po i, gdy i występuje jako ostatni z obsługiwanych


















Rys. Dołączenie j do trasy po i

Trasa wygląda następująco [0,….,i,j,0]

Możemy w tej interacji rozpatrywać trasę H=[0,8,6,7,0]. Dopuszczalny czas przejazdu wynosi:

T=216+93+158+361=828<960

B=11+15+12=38>32

Jeden warunek przewozu dotyczący dopuszczalności nie został spełniony i dlatego nie możemy odbiorcy 8 dołączyć do trasy.

INTERACJA 3

S67=416. 7 należy do trasy H1 i jest odbiorca krańcowym, a konkretnie ostatnim. Natomiast 5 jest obsługiwany indywidualnie. Możemy rozpatrywać trasę H=[0,6,7,5,0].

Mamy:

T=309+158+157+212=830<960



b=15+!2+5=32=32

5 dołączamy do trasy H11 i obsługujemy po i, czyli7, gdyż i występował jako ostatni z obsługiwanych. Otrzymujemy trasę:

H1=[0,6,7,5,0]

Zauważamy, że pojemność samochodu trasy H1 jest w pełni wykorzystana, zatem w następnych interacjach możemy z góry odrzucać możliwości połączenia tej trasy z innymi.



INTERACJA 9

S45=168. 4 należy do trasy H2, natomiast 5 do trasy H1. 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. Zatem połączenie tych tras jest niemożliwe.



INTERACJA 11

S29=143. 2 jest obsługiwana indywidualnie, natomiast 9 należy do trasy H3, gdzie jest odbiorcą krańcowym – konkretnie ostatnim. Możemy wieć rozpatrywać trasę:

H=[0,1,9,2,0]
Mamy:

T=83+63+66+78=290<960

b=8+9+7=24<32

Modyfikujemy trasę H3, gdyż warunki przewozu zostały spełnione:

H3=[0,1,9,2,0]

INTERACJA 14

S48=104. 4 należy do trasy h2 jako ostatni odbiorca, natomiast 8 jest odbiorca indywidualnym. Tworzymy trasę:

H=[0,3,4,8,0]

Mamy:


T=198+156+268+216=838<960

b=14+6+11=31<32

Modyfikujemy więc trasę H2=[0,3,4,8,0]

Po wyczerpaniu listy możliwych stwierdzimy, że zasadnicze są trasy:

H1=[0,6,7,5,0], dla której T=830 min. i b =32 palety

H2=[0,3,4,8,0], dla której T=838 min. i b = 31 palety

H2=[0,1,9,2,0], dla której T=290 min. i b = 24 palety

Wyznaczone trasy są przedstawione na rysunku.























Rys. Trasy przewozu w rejonie dystrybucji

Wprowadzając nazwy miejscowości mamy:

H1: Wrocław-Kraków-Kielce-Częstochowa-Wrocław

H2: Wrocław-Poznań-Kalisz-Katowice-Wrocław

H3: Wrocław-Wałbrzych-Jelenia Góra-Legnica-Wrocław

3. Rozdział zadań przewozowych
3.1 Zadania przyporządkowania

Określenie tras przewozu i ilości pojazdów nie gwarantuje, że są to trasy o podobnej skali przewozów. Także ładunki różnią się składem produktów, również pojazdy nie zawsze są dostosowane do przewozu danego typu ładunku. Powstaje wtedy problem odpowiedniego przyporządkowania pojazdów do tras przewozów. Jest to zadanie ogólniejsze, znane w literaturze, jako zadanie przyporządkowania.

Uściślijmy najpierw założenia problemu:


  1. mamy n jednostek wykonawczych Ri , i = ,....,n (osób, maszyn, samochodów) oraz n zadań Zj , j = ,....,n do wykonania

  2. przyjmijmy, że każda jednostka Ri może właściwie wykonać dowolne zadanie Zj, ale efektywność wykonania każdego z nich jest różna

  3. efektywność wykonania zadania Zj przez Ri może być wyrażona albo przez miarę korzyści – oznaczamy ją dij albo przez miarę nakładu – oznaczamy ją kij

Cel zadania sformułujemy następująco: należy jednostkom Ri tak przyporządkować zadania Zj, aby efekt sumaryczny był jak najkorzystniejszy.

Należy wprowadzić zmienne x, i = ,....,n; j = 1,....,n, które będą odzwierciedlać czy jednostce wykonawczej Ri zostało przyporządkowane zadanie Zj czy też nie.

1, gdy Ri otrzymuje zadanie Zj

xij =

0, w przeciwnym przypadku

Gdy efektywność jest wyrażana poprzez miary korzyści, najkorzystniej efekt wyraża funkcja kryterium:
ZL = dij * xij max
Gdy efektywność jest wyrażona przez miary nakładów, najkorzystniejszy efekt wyraża funkcja kryterium:

Zk = kij * xij min


Algorytmy rozwiązywania zadań tej klasy są na ogół formułowane przy założeniu poszukiwania minimum. Zadanie, w którym poszukiwane jest maksimum efektywności można zastąpić zadaniem poszukiwania minimum w następujący sposób:
ZL max
Możemy teraz wprowadzić standardowe oznaczenia współczynników funkcji kryterium, mianowicie cij. Zadanie przyporządkowania możemy zatem sformułować następująco:

(Jest to tzw. Zadanie prymalne)

Wprowadzone zmienne xij są zmiennymi binarnymi, czyli xij = 1 lub xij = 0. Praktycznie zapis zadania sprowadza się do macierzowego ujęcia zmiennych xij oraz współczynników cij
c11 c1j c1n

C = cil cij cin


cn1 cnj cnn

Wskazane przyporządkowanie jest, w tej konwencji równoznaczne ze wskazaniem elementu macierzy C. Jeżeli zostanie wskazany np. element c23 to odczytujemy, że jednostka wykonawcza R2 otrzymała zadanie Z3.

Gdy zadanie (minimalizacja) nie jest symetryczne tzn. gdy liczba wykonawców nie jest równa liczbie zadań, sprowadzamy go do symetrycznego wprowadzając pomocnicze kolumny lub wiersze z elementami będącymi liczbami „dużymi” zwanymi „big – M”. W zadaniu z maksymalizacją wprowadzane współczynniki muszą być równe 0. Gdy chcemy zablokować pewien przedział, przyjmujemy, że wartość współczynnika c jest równa „big – M”.
3.2 Własności zadań przyporządkowań

Zadania przyporządkowania należą do klasy zadań liniowych o specjalnej strukturze. Ponieważ w omawianym dalej postępowaniu będziemy korzystać z zapisu macierzy C, w pierwszej kolejności musimy odpowiednio przeformułować interpretację bazowego rozwiązania dopuszczalnego. Podobnie jak w klasycznych zadaniach transportowych wprowadzamy macierz przyporządkowań X, której elementami są poszukiwane zmienne xij;


i = 1,....,n; j = 1,...., n. Ma ona postać zgodną z zapisem macierzy C (zwany wektorem przyporządkowań).

x11 x1j x1n


X = xi1 xij xin
Xn1 xnj xnn

W trakcie wyznaczania rozwiązania będziemy dokonywać przekształceń macierzy C. Będą to przekształcenia nie mające wpływu na wyznaczanie wektora przyporządkowań x.


1 własność przekształceń macierzy C – jeżeli w macierzy C do każdego elementu pewnego wiersza dodamy liczbę α lub do każdego elementu pewnej kolumny dodamy liczbę β nie ma to żadnego wpływu na wektor przyporządkowań x. Zmienia się jedynie wartość funkcji kryterium.

Istotne warunki komplementarności wiążące rozwiązania obu zadań. Są one określane przez równanie:

(ui + vj – cij) * xij = 0, i = 1,....,n; j = 1,....,n.

Wykorzystamy zależności między zadaniami dualnymi, aby poprzez zadanie dualne uzyskać rozwiązanie zadania prymalnego. W tym celu przeprowadzimy redukcję elementów macierzy C.



  • najpierw w kolejnych wierszach od każdego elementu odejmujemy liczbę równą wartości minimalnej w tym wierszu i otrzymujemy:


  • w następnej kolejności w kolejnych kolumnach od każdego elementu zmodyfikowanej macierzy odejmujemy liczbę równą wartości minimalnej w tej kolumnie i otrzymujemy:

Po redukcji macierzy C w każdej kolumnie i w każdym wierszu otrzymujemy co najmniej jedno 0. Przekształcenia macierzy C sprawiają, że otrzymujemy w niej elementy równe 0, które mają różne znaczenie. Wyróżniamy więc pewne kategorie zer:



  • zera niezależne – dwa zera nazywamy zerami niezależnymi jeżeli w zredukowanej macierzy C1 nie mają wspólnej kolumny ani wiersza.

Macierz, w której występują elementy zerowe ma własność, którą przedstawia twierdzenie Königa i Egerváry’ego. Jeżeli macierz zawiera elementy zerowe, to maksymalna liczba możliwych do wybrania zer niezależnych jest równa minimalnej liczbie linii, którymi można pokryć te wszystkie zera.

Linie tworzą minimalne pokrycie zer w macierzy. Wykorzystujemy je do sprawdzenia czy wyznaczyliśmy optymalne przyporządkowanie. Jeżeli bowiem liczba linii będzie mniejsza od n, będzie to oznaczało, że poszukiwanie rozwiązania należy kontynuować.

Przyjmijmy, że mamy zmodyfikowaną macierz Ck i wprowadzone linie pokrycia.

Wyróżniamy teraz:



  • Ip – zbiór pokrytych wierszy

  • Inp – zbiór nie pokrytych wierszy

  • Jp – zbiór pokrytych kolumn

  • Jnp – zbiór nie pokrytych kolumn

W macierzy Ck rozpatrujemy elementy ckcj, które znajdują się w nie pokrytych wierszach, a więc i należące do Inp i nie pokrytych kolumnach czyli j należące do Jnp.

Mamy następujące proste reguły modyfikacji elementów macierzy Ck:


  • jeżeli element jest pokryty przez dwie linie (poziomą i pionową) – dodajmy

  • jeżeli element nie jest pokryty przez żadną linię – odejmujemy

  • pozostałe elementy pozostają bez zmian


3.3 Algorytm węgierski

Założenia startowe:

Znamy macierz kwadratową C, której elementy są nie ujemne. W zadaniu poszukujemy minimum funkcji kryterium



Start


Wyznaczamy zredukowaną macierz C1 dokonując operacji:

  • dla i = 1, ...., n wyznaczamy kolejno

ui = min cij i = 1,....,n


i tworzymy macierz C o elementach
cij = cij – ui i = 1,....,n j = 1,....,n;


  • dla j = 1,....,n określamy kolejno:

vj = min cij i = 1,....,n j = 1,....,n


i tworzymy macierz C1 o elementach:
ckij = cij – vj i = 1,....,n j = 1,....,n.
W macierzy C1 a w następnych interacjach w macierzach Ck, otrzymujemy zera, które podzielimy na różne kategorie. Wyróżniamy zera, które podzielimy na różne kategorie. Wyróżniamy zera:

  • „wskazujące przyporządkowanie” a więc te, które w ramach danej iteracji wskazują przyporządkowanie xij = 1.

  • „wykluczone”, które ze względu na dokonane już przyporządkowania nie mogą być brane pod uwagę,

  • „swobodne”, które nie są ani wskazującymi przyporządkowanie ani wykluczonymi.



Interacje

Krok 1


Wskazujemy wiersz lub kolumnę o najmniejszej liczbie zer „swobodnych”. Jedno z tych zer uznajemy za „wskazujące przyporządkowanie” wszystkie inne zera zamieniamy na „wykluczone”

Powtarzamy ten krok aż do uzyskania sytuacji, gdy w macierzy nie będzie zer „swobodnych.


Krok 2


Sprawdzamy liczbę zer „wskazujących przyporządkowanie”

  • jeżeli liczba tych zer jest równa n – mamy optymalne przyporządkowanie i następuje koniec postępowania,

  • w przeciwnym przypadku przechodzimy do kroku 3.

Krok 3


Oznaczamy wszystkie wiersze, które nie zawierają żadnego zera „wskazującego przyporządkowanie”

Krok 4


Wykonujemy na przemian następujące operacje:

  1. oznaczamy wszystkie kolumny, które w już oznaczonych wierszach mają przynajmniej jedno zero „wykluczone”

  2. oznaczamy wszystkie wiersze, które w kolumnach oznaczonych w 1 podpunkcie mają przynajmniej jedno zero „wskazujące przyporządkowanie”

Operacje 1) i 2) powtarzamy na przemian dopóki nie wyczerpiemy możliwości oznaczania


Krok 5


Pokrywamy liniami oznaczone wiersze oraz oznaczone kolumny

Krok 6


Wśród nie pokrytych elementów wierszy i kolumn wyznaczamy

Krok 7


Dokonujemy modyfikacji macierzy Ck

  • do elementów pokrytych przez dwie linie dodajemy

  • od elementów nie pokrytych żadną linią odejmujemy

  • pozostałe elementy pozostawiamy bez zmian

Jako wynik otrzymujemy macierz Ck+1 dla której powtarzamy interację.
1   2   3   4


©snauka.pl 2016
wyślij wiadomość