Strona główna

Optymalizacja bazy transportowej Wyznaczanie najkrótszej drogi w sieci


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

j=6, d6:=, d4+c46=35+34=69 d6:=69 i Q:={3,5,6}.

Wyniki przejściowe zawiera tabela 1.4.




i

1

2

3

4

5

6

7

dj

0

30

43

35

60

69



(i)

*

1

2

1

2

4

-

Tab. Zapis wyników iteracji 3.
ITERACJA 4

W zbiorze Q={3,5,6} wyznaczamy węzeł h, dla którego dh= min di.

Korzystając z wyników trzeciej iteracji otrzymujemy h=3.

Wykreślamy węzeł 3 ze zbioru Q i otrzymujemy Q={5,6}.

Dla h=3 mamy S(3)={2,4,5,6,7}.

Rozpatrujemy kolejno:

j=2, d2:=30, d3+c32=43+14=57 d2:=30

j=4, d4:=35, d3+c34=43+15=58 d4:=35

j=5, d5:=60, d3+c35=43+38=81 d5:=60

j=6, d6:=69, d3+c36=43+27=70 d6:=69

j=7, d7:=, d3+c37=43+46=89 d7:=89 i Q:={5,6,7}.

Wyniki przejściowe przedstawia tabela 1.5.




i

1

2

3

4

5

6

7

dj

0

30

43

35

60

69

89

(i)

*

1

2

1

2

4

3

Tab. Zapis wyników iteracji 4.

ITERACJA 5


W zbiorze Q={5,6,7} wyznaczamy węzeł h, dla którego dh= min di.

Korzystając z wyników czwartej iteracji otrzymujemy h=5.

Wykreślamy węzeł 5 ze zbioru Q i otrzymujemy Q={6,7}.

Dla h=5 mamy S(5)=7.

Dla węzła 7 otrzymujemy:
j=7, d7:=89, d5+c57=60+18=78 d7:=78.
Wyniki przejściowe przedstawia tabela 1.6.


i

1

2

3

4

5

6

7

dj

0

30

43

35

60

69

78

(i)

*

1

2

1

2

4

5

Tab. Zapis wyników iteracji 5.

ITERACJA 6


W zbiorze Q={6,7} wyznaczamy węzeł h, dla którego dh= min di.

Korzystając z wyników czwartej iteracji otrzymujemy h=6.

Wykreślamy węzeł 6 ze zbioru Q i otrzymujemy Q={7}.

Dla h=6 mamy S(6)={7}.

Dla węzła 7 otrzymujemy:
j=7, d7:=78, d6+c67=69+20=89 d7:=78.
Wyniki przejściowe przedstawia tabela 1.7.


i

1

2

3

4

5

6

7

dj

0

30

43

35

60

69

78

(i)

*

1

2

1

2

4

5

Tab. Zapis wyników iteracji 6.

ITERACJA 7


Ponieważ Q={7} otrzymujemy natychmiast h=7 i po wykreśleniu tego węzła, Q=0.

Dla h=7 mamy S(7)=0.

Postępowanie kończy się, a wyniki odczytujemy z ostatniej tabeli.

Odczytajmy drogę od węzła 1 do węzła 7. Jej długość wynosi 78. Bezpośrednim poprzednikiem węzła 7 jest węzeł 5, dla węzła 5 bezpośrednim poprzednikiem jest węzeł 2, dla węzła 2 bezpośrednim poprzednikiem jest węzeł 1.Wobec tego drogę wyznacza ciąg węzłów [1,2,5,7].

Analogicznie odczytujemy wyniki dla pozostałych węzłów:


  • Drogę z węzła 1 do węzła 2 o długości 30 wyznacza ciąg [1,2].

  • Drogę z węzła 1 do węzła 3 o długości 43 wyznacza ciąg [1,2,3].

  • Drogę z węzła 1 do węzła 4 o długości 35 wyznacza ciąg [1,4].

  • Drogę z węzła 1 do węzła 5 o długości 60 wyznacza ciąg [1,2,5].

  • Drogę z węzła 1 do węzła 6 o długości 69 wyznacza ciąg [1,4,6].



Algorytm Dijkstry II

W przypadku, gdy w grafie nie wyróżniamy kierunków przemieszczania, a więc gdy rolę strzałek przejmują krawędzie, algorytm ulega pewnej modyfikacji, która pociąga za sobą zmiany w zapisie postępowania. Ponieważ w rozpatrywanych zadaniach nie pojawiają się pętle typu [i,j,i], nie będziemy rozpatrywać przemieszczeń z i do j i z powrotem. Upraszcza to zapis postępowania, gdyż nie musimy zapamiętywać bezpośrednich poprzedników.


Algorytm

Założenia startowe:

Zadany jest graf nie skierowany, wartościowany z wyróżnionym węzłem startowym w, np. w=1.

Każdemu węzłowi i będziemy przyporządkowywać cechę tymczasową dit oraz cechę stałą dis.

Cecha tymczasowa odpowiada wyznaczonej na bieżąco odległości od węzła startowego, cecha stała określa ostateczną odległość, wobec czego po jej wyznaczeniu nie ulega ona zmianie w trakcie dalszego postępowania. Dla węzłów mających cechę stałą, nie rozpatrujemy cechy tymczasowej.



Start

Rozpoczynamy od pewnego określonego węzła, np. w=1. Przypisujemy mu cechę stałą d1s=0. Pozostałe węzły nie maja cechy stałej. Jako wartości cech tymczasowych przyjmujemy dit:=, i1.


Iteracje

Krok I

Rozpatrujemy wszystkie węzły połączone bezpośrednio z węzłem w, któremu nadaliśmy cechę stałą. Wykorzystamy tutaj symbol zbioru następników i powiemy, że wyznaczamy zbiór S(w).



Krok II

Sprawdzamy, czy w zbiorze S(w) wszystkie węzły mają cechę stałą.



  • Jeżeli tak, przechodzimy do kroku 4.

  • Jeżeli istnieje przynajmniej jeden węzeł nie mający cechy stałej przechodzimy do kroku 3.

Krok III

Rozpatrujemy kolejno wszystkie węzły zbioru S(w), które nie maja cechy stałej. Dla każdego z nich obliczamy sumę cechy stałej węzła w i odległości danego węzła od węzła w i sprawdzamy, czy jest spełniona nierówność:

dws+cwiit.

Jeżeli nierówność jest prawdziwa, starą cechę tymczasową zastępujemy nową: dit:=dws+cwi.

W przeciwnym wypadku pozostawiamy dit bez zmiany.

Krok IV

Sprawdzamy, czy istnieją węzły, które maja cechę tymczasową.

Jeżeli taki węzeł nie istnieje – postępowanie kończy się.
W przeciwnym przypadku, spośród węzłów mających cechę tymczasową wyznaczamy węzeł o najniższej jej wartości. Przyporządkowana cechę tymczasową tego węzła uznajemy za jego cechę stałą, a jednocześnie węzeł ten przejmuje rolę węzła w.
Przykład

Zmodyfikowane postępowanie przedstawimy na przykładzie, w którym graf przedstawiony na rysunku 1.4 odzwierciedla rzeczywiste połączenia między miejscowościami wokół Wrocławia. Korzystając z algorytmu Dijkstry II, wyznaczymy najkrótsze drogi z Wrocławia do każdej z wymienionych miejscowości.

Odległości zaznaczone na grafie 1.4 przedstawia tabela 1.8.

W tabeli wymieniamy jedynie odległości odzwierciedlające bezpośrednie połączenia między miastami. Dla połączeń oznaczonych gwiazdkami najkrótsze drogi wymagają przejazdu przez inną miejscowość.














































Rys. Graf połączeń.

Miejscowość




1

2

3

4

5

6

7

8

9

10

11

Wrocław

1



34

31

62

56

*

27

*

58

*

*

Brzeg Dolny

2

34



58

43

62

*

*

*

*

*

*

Oleśnica

3

31

58



64

51

68

44

*

*

*

*

Rawicz

4

62

43

64



41

*

*

*

*

*

*

Milicz

5

56

62

51

41



71

*

*

*

*

*

Ostrów Wlkp.

6

*

*

68

*

71



*

*

*

*

*

Oława

7

27

*

44

*

*

*



15

60

*

*

Brzeg

8

*

*

*

*

*

*

15



73

96

40

Dzierżoniów

9

58

*

*

*

*

*

60

73



41

109

Kłodzko

10

*

*

*

*

*

*

*

96

41



109

Opole

11

*

*

*

*

*

*

*

40

109

109




Tab. Tabela odległości między miastami wokół Wrocławia.
ITERACJA 1

Mamy w=1 i d1s=0, dit=, i1.

Identyfikujemy S(1)={2,3,4,5,7,9}. Żaden z nich nie ma cechy stałej. Dla każdego z nich określamy cechę tymczasową.

d2t:= , d1s+c12=0+34=34, d2t:=34,

d3t:= , d1s+c13=0+31=31, d3t:=31,

d4t:= , d1s+c14=0+62=62, d4t:=62,

d5t:= , d1s+c15=0+56=56, d5t:=56,

d7t:= , d1s+c17=0+27=27, d7t:=27,

d9t:= , d1s+c19=0+58=58 d9t:=58.

Wyniki pierwszej iteracji zapisane są w tabeli 1.9.





Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

1

ds

dt



0

-


-

34


-

31


-

62


-

56


-

-


-

27

-

-


-

58


-

-


-

-



27


Tab. Cechy stałe i tymczasowe po pierwszej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 7. Przyporządkowana mu cechę tymczasową zamieniamy na cechę stałą d7s=27. Węzeł 7 przejmuje rolę węzła w.
ITERACJA 2

Mamy w=7 i d7s=27.

Identyfikujemy S(7)={1,3,8,9}. Cechy stałej nie mają węzły 3,8,9. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d3t:=31, d7s+c73=27+44=71 d3t:=31,

d8t:=, d7s+c78=27+15=42 d8t:=42,

d9t:=58, d7s+c79=27+60=87 d9t:=58.


Wyniki drugiej iteracji zapisane są w tabeli 1.10.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

2

ds

dt



0

-


-

34


-

31

-

62


-

56


-

-


27

-


-

42


-

58


-

-


-

-



31


Tab. Cechy stałe i tymczasowe po drugiej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 3. Przyporządkowana mu cechę tymczasową zamieniamy na cechę stałą d3s=31. Węzeł 3 przejmuje rolę węzła w.
ITERACJA 3

Mamy w=3 i d3s=31.

Identyfikujemy S(3)={1,2,4,6,7}. Cechy stałej nie maja węzły 2,4,6. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d2t:=34, d3s+c32=31+58=89 d2t:=34,

d4t:=62, d3s+c34=31+64=95 d4t:=62,

d6t:=, d3s+c36=31+68=99 d6t:=99.


Wyniki trzeciej iteracji przedstawione są w tabeli 1.11.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

3

ds

dt



0

-


-

34

31

-


-

62


-

56


-

99


27

-


-

42


-

58


-

-


-

-



34


Tab. Cechy stałe i tymczasowe po trzeciej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 2. Przyporządkowana mu cechę tymczasową zamieniamy na cechę stałą d2s=24. Węzeł 2 przejmuje rolę węzła w.
ITERACJA 4

Mamy w=2 i d2s=34.

Identyfikujemy S(2)={1,3,4,5}. Cechy stałej nie mają węzły 4,5. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowana.

d4t:=62, d2s+c24=34+43=77 d4t:=62,

d5t:=56, d2s+c25=34+62=96 d5t:=56.
Wyniki czwartej iteracji przedstawia tabela 1.12.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

4

ds

dt



0

-


34

-


31

-


-

62


-

56


-

99


27

-


-

42

-

58


-

-


-

-



42


Tab. Cechy stałe i tymczasowe po czwartej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 8. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d8s=42. Węzeł 8 przejmuje rolę węzła w.

ITERACJA 5

Mamy w=8 i d8s=42.

Identyfikujemy S(8)={7,9,10,11}. Cechy stałej nie mają węzły 9,10,11. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d9t:=58, d8s+c89=42+73=115 d9t:=58,

d10,t:=, d8s+c8,10=42+96=138 d10t:=138,

d11,t:=, d8s+c8,11=42+40=82 d11,t:=82.


Wyniki piątej iteracji przedstawia tabela 1.13.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

5

ds

dt



0

-


34

-


31

-


-

62


-

56

-

99


27

-


42

-


-

58


-

138


-

82



56


Tab. Cechy stałe i tymczasowe po piątej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 5. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d5s=56. Węzeł 5 przejmuje rolę węzła w.
ITERACJA 6

Mamy w=5 i d5s=56.

Identyfikujemy S(5)={1,2,4,6}. Cechy stałej nie mają węzły 4,6. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d4t:=62, d5s+c54=56+41=97 d4t:=62,

d6t:=99, d5s+c56=56+71=127 d4t:=99.
Wyniki szóstej iteracji przedstawia tabela 1.14.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

6

ds

dt



0

-


34

-


31

-


-

62


56

-


-

99


27

-


42

-


-

58

-

138


-

82



58


Tab. Cechy stałe i tymczasowe po szóstej iteracji.

Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 9. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d9s=58. Węzeł 9 przejmuje rolę węzła w.


ITERACJA 7

Mamy w=9 i d9s=58.

Identyfikujemy S(9)={1,7,8,10,11}. Cechy stałej nie mają węzły 10,11. Dla każdego z nich określamy cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d10,t:=138, d9s+c9,10=58+41=99 d10,t:=99,

d11,t:=82, d9s+c9,11=58+109=167 d4t:=82.
Wyniki siódmej iteracji przedstawia tabela 1.15.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

7

ds

dt



0

-


34

-


31

-


-

62

56

-


-

99


27

-


42

-


58

-


-

99


-

82



62


Tab. Cechy stałe i tymczasowe po siódmej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 4. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d4s=62. Węzeł 4 przejmuje rolę węzła w.
ITERACJA 8

Mamy w=4 i d4s=62.

Identyfikujemy S(4)={1,2,3,5}. Wszystkie węzły mają cechę stałą. Przechodzimy więc do analizy tabeli po zmianie cechy dla węzła 4.
Wyniki przedstawia tabela 1.16.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

8

ds

dt



0

-


34

-


31

-


62

-

56

-


-

99


27

-


42

-


58

-


-

99


-

82


82


Tab. Cechy stałe i tymczasowe po ósmej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Jest nim 11. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d11,s=82. Węzeł 11 przejmuje rolę węzła w.
ITERACJA 9

Mamy w=11 i d11,s=82.

Identyfikujemy S(11)={8,9,10}. Cechy stałej nie ma węzeł 10. Określamy dla niego cechę tymczasową po sprawdzeniu z wcześniej przyporządkowaną.

d10,t:=99, d11,s+c11,10=82+109=191 d10,t:=99.

Wyniki dziewiątej iteracji przedstawia tabela 1.17.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

9

ds

dt



0

-


34

-


31

-


62

-

56

-


-

99

27

-


42

-


58

-


-

99


82

-


99


Tab. Cechy stałe i tymczasowe po dziewiątej iteracji.
Wskazujemy węzeł mający najmniejszą cechę tymczasową. Z dwóch mających identyczne wartości wybieramy 6. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d6s=99. Węzeł 6 przejmuje rolę węzła w.
ITERACJA 10

Mamy w=6 i d6s=99.

Identyfikujemy S(6)={3,5}. Wszystkie węzły mają cechę stałą. Przechodzimy więc do analizy tabeli po zmianie cechy dla węzła 6.
Wyniki przedstawia tabela 1.18.


Iteracja




1

2

3

4

5

6

7

8

9

10

11

min

10

ds

dt



0

-


34

-


31

-


62

-

56

-


99

-

27

-


42

-


58

-


-

99

82

-


99


Tab. Cechy stałe i tymczasowe po dziesiątej iteracji.
Wybór węzła, który przejmuje rolę w jest jednoznaczny. Jest nim 10. Przyporządkowaną mu cechę tymczasową zamieniamy na cechę stałą d10,s=99.

Otrzymujemy tabelę 1.19.




Iteracja




1

2

3

4

5

6

7

8

9

10

11

min




ds

dt



0

-


34

-


31

-


62

-

56

-


99

-

27

-


42

-


58

-


99

-

82

-




Tab. Cechy stałe i tymczasowe po zakończeniu postępowania.
Ponieważ wyczerpaliśmy tym samym zbiór węzłów nie mających cechy stałej, postępowanie kończy się. Cechy stałe ostatniej tabeli określają poszukiwane odległości.

Zestawienie, które pozwala szybko odczytywać każda drogę zaczynającą się w węźle 1, przedstawia tabela 1.20., w której podajemy numer węzła końcowego, długość drogi do niego i węzeł bezpośrednio go poprzedzający.

Odczytujemy teraz przykładowo: dla węzła 11 poprzednikiem jest 8, dla 8 poprzednikiem jest 7, a dla 7 poprzednikiem jest 1. Mamy więc drogę 1-7-8-11 o długości 82.


Węzeł końcowy

1

2

3

4

5

6

7

8

9

10

11

Długość drogi

0

34

31

62

56

99

27

42

58

99

82

Węzeł poprzedzający

-

1

1

1

1

3

1

7

1

9

8


Tab. Zestawienie odległości i dróg z Wrocławia do pozostałych miast.


  1. Planowanie tras dostaw dla wielu pojazdów

2.1 Zasady tworzenia tras

Rozpatrzymy zadanie dostaw produktów do klientów. Przyjmujemy, że są spełnione następujące założenia:



    • Wspólna miara ładowności ze względu na jednorodność produktów

    • Symbolem Lo oznaczamy magazyn produktów producenta, z którego pobieramy produkty i dostarczamy do na odbiorców

    • Symbolami Bi,….Bn oznaczamy potencjalnych odbiorców

    • Małe bi to zamówienie odbiorcy

    • Q – ładowność środków transportowych

    • Ładowność środków transportowych musi być większa niż zamówienie odbiorcy, czyli Q>bi, i=1,2…n

    • Dopuszczalny czas trwania przewozu przez jeden środek transportu ( od producenta do klienta i z powrotem ) nie może przekroczyć T jednostki czasu

    • Czas wyładowania ładunku jest równy zero

Nasze zadnie sformułujemy następująco: należy wyznaczyć ilość środków transportowych od trasy ich przejazdów pozwalające obsłużyć wszystkie zamówienia klientów przy zachowaniu warunków przewozu tak, aby łączny czas obsługi wszystkich klientów był minimalny. Sformułowanie zadania składa się z dwóch zadań częściowych:

  • Przydziału klientów do określonego środka transportu

  • Wyznaczenia tras dla każdego z nich

Jako H oznaczamy dowolną trasę rozpoczynającą się w punkcie Lo, czyli od magazynu producenta, przebiegającą przez punkty i1, i2….ir i kończąca się ponownie w punkcie Lo. Niech ty ozncza czas przejazdu z punktu i do punktu j. na mocy przyjętego założenia o dopuszczalnym czasie trwania przejazdu musimy mieć spełnioną nierówność:

t +t T


reprezentujemy trasę H=[0,i1,i2,....ir,o]

  • Czas przejazdu tej trasy wynosi: t(H)=toi1+ti1i2+….=tiro

  • Łączna wielkość zamówień odbiorców tej trasy: b(H)=bi1+…bir

Trasę H nazwiemy dopuszczalna gdy

B(H) Q i t(H) T

Na początku załóżmy, że każdy klient jest obsłużony indywidualnie. Oznacza to, że dla obsługi wszystkich n klientów potrzebujemy n pojazdów i każdy z nich ma prosta trasę z punktu Lo do swojego klienta i z powrotem. Łączny czas trwania dosta wynosi wtedy:

Z= (t + t )

Teraz rozpatrzmy dwóch odbiorców i i produktów, których mógłby obsłużyć jeden pojazd w ramach całej trasy, wtedy łączny czas trwania dostaw przy indywidualnej ich obsłudze wynosi:

To=(toi+tio)+(toj+tjo)











1   2   3   4


©snauka.pl 2016
wyślij wiadomość