Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

1

Piotr Sawicki

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 748, tel. [phone]

E-mail: [e-mail]
URL: www.put.poznan.pl/~piotr.sawicki

Wydział Maszyn Roboczych i Transportu
pok. 748, tel. [phone]

E-mail: [e-mail]
URL: www.put.poznan.pl/~piotr.sawicki

Zarządzanie systemami
transportu drogowego

Zarządzanie systemami
transportu drogowego

Problemy sieciowe

Problemy sieciowe

33

2

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Plan prezentacji

Istota problemów sieciowych

•

definicje podstawowych pojęć

•

typowe problemy sieciowe

Analiza głównych problemów sieciowych

•

problem najkrótszej drogi

•

problem minimalnie rozgałęzionego drzewa

•

problem maksymalnego przepływu

Podsumowanie

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

2

33

3

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Definicje podstawowych pojęć

•

•

sie

sie

ć

ć (graf)
połączenie wielu

punktów o różnej lokalizacji

przykład:

– przystanki

autobusowe/tramwajowe

– centra dystrybucji

– terminale bankomatowe

– sieć połączeń

teleinformatycznych

33

4

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Definicje podstawowych pojęć

•

•

w

w

ę

ę

ze

ze

ł

ł
punkt sieci

(wierzchołek grafu) o
określonych parametrach

– lokalizacja

– przepustowość

– popyt / podaż

– inne

•

•

ga

ga

łąź

łąź (łuk)
odcinek łączący

dwa sąsiednie węzły; odcinek
o określonych własnościach

– przepustowość

– długość

– max. prędkość

– koszt przemieszczenia po łuku

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

3

33

5

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Definicje podstawowych pojęć

•

•

ga

ga

łąź

łąź

skierowana

skierowana
gałąź (łuk) o

zdefiniowanym kierunku przepływu

– przepływ jednokierunkowy

– przepływ dwukierunkowy

•

•

ga

ga

łąź

łąź

nieskierowana

nieskierowana
gałąź

(łuk) o niezdefiniowanym kierunku
przepływu

•

•

sie

sie

ć

ć

skierowana

skierowana
układ węzłów

połączonych wyłącznie gałęziami
(łukami) skierowanymi

•

•

droga

droga
sekwencja gałęzi (łuków)
pomiędzy węzłem początkowym i
końcowym

– droga skierowana

– droga nieskierowana

33

6

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Definicje podstawowych pojęć

•

rodzaje dróg

–

–

droga otwarta

droga otwarta

droga,

której węzeł początkowy i
końcowy są różnymi węzłami

–

–

droga zamkni

droga zamkni

ę

ę

ta

ta

droga,

której węzeł początkowy i
końcowy jest tym samym
węzłem (droga obiegowa)

•

rodzaje punktów

–

–

punkt pocz

punkt pocz

ą

ą

tkowy

tkowy
punkt

nadania towaru

–

–

punkt ko

punkt ko

ń

ń

cowy

cowy
punkt

dostawy towaru

–

–

punkt po

punkt po

ś

ś

redni

redni
punkt

przez który przechodzi droga
z punktu początkowego do
końcowego

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

4

33

7

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Problem 1

W jaki sposób przejechać z określonego punktu początkowego

do punktu końcowego drogi, aby

•

długość drogi była minimalna?

•

czas przejazdu był minimalny?

•

koszt przejazdu był minimalny?

Problem 1

problem

najkrótszej drogi (ścieżki)

33

8

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Problem najkrótszej drogi

przykłady

zastosowań

•

przejazd pogotowia i straży pożarnej do odległego
miejsca wypadku

jaka droga jest najszybsza?

•

przewóz międzymagazynowy towarów o krótkim
terminie przydatności (FMCG)

jak droga jest najszybsza?

•

awaryjna (pilna) dostawa węgla do elektrociepłowni

jaka droga jest najszybsza?

•

inne

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

5

33

9

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Problem 2

Jak zorganizować przewóz towaru, aby wykorzystać dostępną

przepustowość wszystkich połączeń komunikacyjnych?

Problem 2

problem

maksymalnego przepływu

h

h

h

h

h

h

h

Poziom obciążenia gałęzi = 80%

h

Poziom obciążenia gałęzi = 50%

h

33

10

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Problem maksymalnego przepływu

przykłady

zastosowań

•

sterowanie ruchem miejskim

jak zaprogramować sterowniki sygnalizacji świetlnej w

celu równomiernego rozłożenia ruchu miejskiego?

•

wyznaczenie trasy przewozu towarów przy znanym
obciążeniu poszczególnych łuków sieci

jak dokonać przewozu dużego ładunku nawozów

sztucznych?

•

inne

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

6

33

11

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Problem 3

Które gałęzie systemu transportowego łączą wszystkie jej

węzły w taki sposób aby całkowita długość połączeń była minimalna?

Problem 3

problem

minimalnie rozgałęzionego
drzewa

33

12

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Wprowadzenie

Istota problemów sieciowych

Problem minimalnie rozgałęzionego drzewa

przykłady zastosowań

•

wybór dróg przeznaczonych do odśnieżania w
pierwszej kolejności

jak zapewnić połączenia ze wszystkimi miastami?

•

budowa sieci informatycznej

jak połączyć terminale za pomocą sieci przewodów o

minimalnej długości?

•

inne

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

7

33

13

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytmy rozwiązania

Modelowanie i rozwiązywanie problemu najkrótszej drogi

algorytm najbliższego
sąsiedztwa

metoda ograniczeń i
rozgałęzień

algorytm najbliższego
sąsiedztwa

metoda ograniczeń i
rozgałęzień

Metoda rozwi

Metoda rozwi

ą

ą

zania

zania

w postaci grafu
nieskierowanego

w postaci grafu
skierowanego i za
pomocą programowania
całkowitoliczbowego

w postaci grafu
nieskierowanego

w postaci grafu
skierowanego i za
pomocą programowania
całkowitoliczbowego

Sformu

Sformu

ł

ł

owanie problemu

owanie problemu

33

14

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Modelowanie problemu w postaci grafu nieskierowanego

•

zakładamy, że rozważaną sieć transportową można przedstawić w postaci graf
nieskierowanego

G = 〈V, E〉

gdzie:

V – zbiór węzłów, v

i

∈

V

E – zbiór łuków nieskierowanych o znanej długości, e

i

∈

E

•

problem polega na znalezieniu najkrótszej ścieżki od węzła początkowego do
węzła końcowego

Metoda rozwiązania

ALGORYTM NAJBLIŻSZEGO SĄSIEDZTWA

•

algorytm pozwala znaleźć drogę z punktu początkowego do punktu końcowego

•

w wyniku zastosowania procedury znajdowana jest jednocześnie najkrótsza droga z
punktu początkowego do wszystkich pozostałych punktów sieci (grafu)

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

8

33

15

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

P

R

P – punkt początkowy R – punkt końcowy

Analiza

ALGORYTMU NAJBLIŻSZEGO SĄSIEDZTWA

na przykładzie

•

znajdź najkrótszą drogę z Poznania do Rzeszowa

– w Poznaniu zlokalizowany jest magazyn centralny

– w Rzeszowie otwarto nowy magazyn regionalny

•

wykorzystaj istniejącą sieć połączeń
komunikacyjnych

•

poszczególne węzły rozważanej
sieci odpowiadają stacjom węzłowym

33

16

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Kroki postępowania

•

(1) znajdź węzeł najbliższy do P

•

(2) znajdź kolejny węzeł najbliższy w
stosunku do P

•

(3) znajdź kolejne węzły najbliższe w
stosunku do P,

•

(4) za każdym razem odrzuć (skreśl)
łuk nie leżący na drodze z
poprzednio rozważanego węzła do
kolejnego węzła, najbliższego w
stosunku do P

– P
Gd: 234+348 > 296
– P
Wa: 212+134 > 310
– P
Wa: 296+339 > 310
– P
Ka: 212+196 > 178+199
– P
Ka: 310+297 > 178+199
– P
B: 296+379 > 310+188
– P
R: 452+165 > 310+303

23

4

348

2

9

6

310

212

13

4

3

39

379

18

8

1

7

8

19

9

75

165

2

9

7

1

9

6

3

0

3

4

3

0

P

R

P – punkt początkowy R – punkt końcowy

178

212

234

296

310

377

452

498

613

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

9

33

17

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Interpretacja rozwiązania

•

znaleziono 9 dróg

– P
Wr:

178km

– P
Ł:

212km

– P
Sz:

234km

– P
Gd:

296km

– P
Wa:

310km

– P
Ka (P-Wr-Ka):

377km

– P
Kr (P-Wr-Ka-Kr): 452km
– P
B (P-Wa-B):

498km

– P
R (P-Wa-R):

613km

23

4

348

2

9

6

310

212

13

4

3

39

379

18

8

1

7

8

19

9

75

165

2

9

7

1

9

6

3

0

3

4

3

0

P

R

178

212

234

296

310

377

452

498

613

P – punkt początkowy R – punkt końcowy

33

18

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Znajdź najkrótszą drogę:

Białystok (B)

Wrocław (W)

23

4

348

2

9

6

310

212

13

4

3

39

379

18

8

1

7

8

19

9

75

165

2

9

7

1

9

6

3

0

3

4

3

0

W

B

P – punkt początkowy R – punkt końcowy

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

10

33

19

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Rozwiązanie problemu

•

znaleziono 9 dróg

– B
Wa:

188km

– B
Ł (B-Wa-Ł):

322km

– B
G:

379km

– B
R:

430km

– B
P (B-Wa-P):

498km

– B
Ka (B-Wa-Ka):

485km

– B
Kr (

B-Wa-Ka-Kr

):

560km

– B
Wr (B-Wa-P-W): 676km
– B
Sz (B-G-Sz):

727km

23

4

348

2

9

6

310

212

13

4

3

39

379

18

8

1

7

8

19

9

75

165

2

9

7

1

9

6

3

0

3

4

3

0

W

B

379

188

430

322

485

560

498

727

676

P – punkt początkowy R – punkt końcowy

33

20

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Sformułowanie problemu najkrótszej drogi w postaci zadania

programowania całkowitoliczbowego

•

zakładamy, że rozważaną sieć transportową można przedstawić w postaci graf
skierowanego

gdzie:

V – zbiór węzłów, v

ij

∈

V

E

>

– zbiór łuków skierowanych e

ij

∈ E

>

o znanej długości

c

ij

•

dla każdego łuku należy zdefiniować zmienną decyzyjną

x

ij

określającą,

czy dany łuk

wchodzi w skład najkrótszej drogi, czy też nie

(zmienna binarna)

>

>

=

E

V

G

,







→

=

wypadku

przeciwnym

w

0

drogi

do

należy

łuk

jeżeli

1

j

i

x

ij

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

11

33

21

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Model matematyczny problemu

zadanie programowania całkowitoliczbowego

•

funkcja celu

•

przy ograniczeniach

gdzie:

r – węzeł początkowy (nadania)

s – węzeł końcowy (odbioru)

∑

>

∈

=

E

j

i

e

ij

ij

x

c

)

,

(

Min

∑

∑

>

>

∈

=

∈

=











−

=

−

E

j

i

e

ji

E

j

i

e

ij

x

x

)

,

(

)

,

(

0

1

1

dla i=r

dla i=s

w pozostałych przypadkach

0

≥

ij

x

i

j

x

ij

x

ji

łuki „wychodzące” z węzła i

łuki „wchodzące” do węzła i

33

22

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Algorytm rozwiązania

Konstrukcja modelu

•

funkcja celu

Min Z = 310x

PWa

+ 212x

PŁ

+ 134x

ŁWa

+ 178x

PW

+ 199x

WKa

+ 196x

ŁKa

+ 297x

WaKa

+ 75x

KaKr

+ 165x

KrR

+ 303x

WaR

•

ograniczenia

dla węzła początkowego (P):

(1)

x

PWa

+ x

PŁ

+ x

PW

= 1

dla węzła końcowego (R):

(2)

– x

WaR

– x

KR

= – 1

dla węzłów pośrednich:

(3)

– x

PW

+ x

WKa

= 0

(4)

– x

PŁ

+ x

ŁWa

+ x

ŁKa

= 0

(5)

– x

PWa

– x

ŁWa

+ x

WaKa

+ x

WaR

= 0

(6)

– x

WKa

– x

ŁKa

– x

WKa

+ x

KaK

= 0

(7)

– x

KaK

+ x

KR

= 0

310

212

13

4

1

7

8

19

9

75

165

2

9

7

1

9

6

3

0

3

P

R

W

Ł

Wa

Ka

K

Przykła d

Przykła d

c

PWa

c

PŁ

c

ŁWa

…

c

WaR

…

Wrocław

Wrocław

Łódź

Łódź

Warszawa

Warszawa

Katowice

Katowice

Kraków

Kraków

Zarządzanie Systamami Transportu Drog.

Piotr Sawicki / WMRiT / PP

12

33

23

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Rozwiązanie z zastosowaniem Solvera

Konstrukcja modelu w Solverze MS Excel

33

24

Piotr Sawicki / Zarządzanie systemami transportu drogowego

Problem najkrótszej ścieżki

Rozwiązanie z zastosowaniem Solvera

Analiza rozwiązania

310

212

13

4

1

7

8

19

9

75

165

2

9

7

1

9

6

3

0

3

P

R

W

Ł

Wa

Ka

K

Wrocław

Wrocław

Łódź

Łódź

Warszawa

Warszawa

Katowice

Katowice

Kraków

Kraków