Slajd 1

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/01

Kierowca wyrusza samochodem z hurtowni A po zakup produktów od wytwórcy
zlokalizowanego w punkcie G, rozwożąc po drodze towar do punktów sprzedaży
detalicznej B, C, D, E i F. Rysunek 1 przedstawia lokalizację poszczególnych punktów
oraz odległości między nimi:

Rys. 1. Lokalizacja punktów obsługiwanych przez samochód i odległości między nimi (km)

W drodze powrotnej samochód wraca od producenta G bezpośrednio do hurtowni.

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/02

Należy wyznaczyć najkrótszą trasę tak, aby samochód w drodze z A do G dotarł do
wszystkich punktów sprzedaży. Ponadto należy wyznaczyć najkrótszą trasę przejazdu
powrotnego.

Odpowiedź:
Powyższe zagadnienie można rozwiązać tzw. metodą listowania. Początkową czynnością
jest zestawienie wszystkich kierunków możliwych do obsłużenia z każdego punktu z
odpowiednią odległością ( tabela 1.1):

AB =9

AC = 11

BC = 9

BE = 14

BA = 9

CD = 15

CE = 11

CA = 11

CB = 9

DG = 15

DF = 10

DC = 14

DE = 7

ED = 7

EF = 10

EB = 14
EC = 11

FE = 10

FD = 10
FG = 11

GD = 15

GF = 11

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/03

Rozwiązanie następuje poprzez procedurę iteracyjną. Punkt rozpoczęcia trasy przejazdu
(w naszym przykładzie jest to punkt A) otrzymuje wartość zerową. Następnie sporządza
się nowe zestawienie, w którym wymazuje się wszystkie drogi prowadzące do punktu A.
Kroki te, jak również wszystkie pozostałe iteracje przedstawiają tabele 1.2.

Drugi krok polega na wyborze najkrótszego dystansu z miejsca startu (w naszym

przykładzie AB = 9 km). Punkt B otrzymuje wówczas wartość 9, a wszystkie trasy
prowadzące do B zostają wymazane z listy.

Trzeci krok to wybór najkrótszego odcinka drogi rozpoczynającej się w punkcie B (w

naszym przykładzie jest to BC = 9 km). W kolejnej iteracji punkt C otrzymuje
skumulowaną wartość punktu B plus dystans BC, tzn. 18. Wszystkie pozostałe trasy
prowadzące do C zostają wymazane.

Kroki te powtarza się tak długo, aż zostanie ustalona kolejność wszystkich punktów.

Procedura znajdowania najkrótszej bezpośredniej drogi powrotnej z G do A jest
następująca:

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/04

Krok 1: Wymazanie tras zmierzających do A

A = 0

AB =9

AC = 11

BC = 9

BE = 14

CD = 14

CE = 11

CB = 9

DG = 15

CF = 10

DC = 14

DE = 7

ED = 7

EF = 10

EB = 14

EC = 11

FE = 10

FD = 10
FG = 11

GD = 15

GF = 11

Krok 2: Wymazanie tras zmierzających do B

A = 0

AC = 11

BC = 9

BE = 14

CD = 14

CE = 11

DG = 15

DF = 10

DC = 14

DE = 7

ED = 7

EF = 10

EC = 11

FE = 10

FD = 10
FG = 11

GD = 15

GF = 11

Optymalna trasa = A – B = 9

Krok 3: Wymazanie tras zmierzających do C

A = 0

B = 9

C = 18

BE = 14

CD = 14

CE = 11

DG = 15

DF = 10

DE = 7

ED = 7

EF = 10

FE = 10

FD = 10
FG = 11

GD = 15

GF = 11

Optymalna trasa = A – B – C = 18

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/05

Krok 4: Wymazanie tras zmierzających do E

A = 0

B = 9

C = 18

E = 29

CD = 14

DG = 15

DF = 10

ED = 7

EF = 10

FD 10

FG = 11

GD = 15

GF = 11

Optymalna trasa = A – B – C – E = 29

Krok 5: Wymazanie tras zmierzających do D

A = 0

B = 9

C = 10

D = 36

E = 29

DG = 15

DF = 10

EF = 10

FG = 11

GF = 11

Optymalna trasa = A – B – C – D – E = 36

Krok 6: Wymazanie tras zmierzających do F

A = 0

B = 9

C = 18

D = 36

E = 29

F = 46

DG = 15

FG = 11

Optymalna trasa = A – B – C – D – F = 46

Krok 7: Trasa optymalna

A = 0

B = 9

C = 18

D = 36

E = 29

F = 46

G = 57

Optymalna trasa = A – B – C – E – D – F = 57

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/06

W naszym przykładzie trasa ostateczna przebiega od A – B – C – E – D – F – G (długość
wynosi 57 km).

Procedura znajdowania najkrótszej bezpośredniej drogi powrotnej z G do A jest

następująca:
Pierwszy punkt, który należy oznaczyć jako węzeł rozwiązany to punkt G – miejsce
startu w drodze powrotnej. Węzły powiązane bezpośrednio z G i jeszcze nie rozwiązane
to D i F. Pierwszy krok polega na zestawieniu tych wszystkich węzłów i wyborze węzła F
jako rozwiązanego. Węzeł F przyjmuje status węzła rozwiązanego. Następnie
wyszukujemy najbliższe węzły nie rozwiązane połączone bezpośrednio z rozwiązanymi
G i F. Są to węzły : G D, F D, F E. Zestawiamy je w 2 kroku. Należy
zauważyć, że aby osiągnąć jakiś węzeł już połączony, musimy minimalną odległość
potrzebną do osiągnięcia rozwiązanego węzła dodać do odległości wcześniejszego
połączenia. Oznacza to, że osiągnięcie D lub E poprzez F wymaga pokonania łącznej
odległości DF+FD lub GF+FE, czyli 11 + 10 = 21km. Porównując łączne odległości do
osiągnięcia nie rozwiązanego węzła w 2 kroku widzimy, że najkrótsza odległość wynosi
15 km przy połączeniu G i D. D jest teraz węzłem rozwiązanym. Krok 3 wiąże się z
wyszukaniem węzłów nie rozwiązanych, które połączone są z węzłami rozwiązanymi.
Sumujemy odległość od miejsca rozpoczęcia podróży (czyli G) do odpowiednich węzłów
nie rozwiązanych.

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/07

Krok

Węzły

rozwiązane

połączone

bezpośrednio

z nie

rozwiązanymi

Najbliższy

węzeł

nie

rozwiązany

Odległość

całkowita

Najbliższy

węzeł

Jego

odległość

minimalna

Jego

ostatnie

połączenie

G
G

15
11

F
F

D
D

11+10=21
11+10=21

Minimalna odległość 21 km odpowiada połączeniu FE. E jest teraz kolejnym węzłem
rozwiązanym.

Procedura ta powtarza się, aż do osiągnięcia punktu A. Minimalna wyznaczona trasa ma

odległość 40 km. Całość trasy wyznaczają odpowiednie odcinki, poczynając od miejsca
startu do miejsca przeznaczenia. Połączenia te oznaczono strzałkami

. Powrotna trasa

optymalna to: G D C A

Politechnika Śląska, Wydział Transportu, Katedra Transportu Szynowego, Europejskie Centrum Doskonałości TRANSMEC

1/08

D
D

15+7=22

15+14=29

11+10=21

E
E

C
C
B

15+14=29

21+11=32

21+14=35

C
C

B
B

21+14=35

29+9=38

29+11=40

C
B

A
A

29+11=40

35+9=44

Najkrótsza trasa