ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA DOPRAVNÍ BAKALÁŘSKÁ PRÁCE

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA DOPRAVNÍ

BAKALÁŘSKÁ PRÁCE Návrh řešení údržby místních komunikací města Zdice

Anna Jíchová 2011

Zadání BP originál (kopie)

Čestné prohlášení

Prohlašuji, že jsem předloženou práci vypracovala samostatně a že jsem uvedla veškeré použité informační zdroje v souladu s Metodickým pokynem o etické přípravě vysokoškolských závěrečných prací. Nemám závažný důvod proti užívání tohoto školního díla ve smyslu §60 zákona č. 121/2000Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne: ……………………………

Podpis: ……………………………

5

Poděkování

Na úvod své práce bych ráda poděkovala všem, kteří mi poskytli potřebné informace, podklady, materiály a za cenné rady pro vznik této práce. Především své vedoucí Ing. Denise Mockové, Ph.D. za vedení bakalářské práce, za ochotu při konzultacích, za informace a její čas, který mně a této práci věnovala. Dále městu Zdice za poskytnuté potřebné podklady. Nakonec je mou povinností poděkovat všem svým blízkým za morální i materiální podporu, které se mi dostávalo při vypracování této bakalářské práce i po celou dobu mého bakalářského studia.

6

Abstrakt

Autor: Anna Jíchová Název: Návrh řešení údržby místních komunikací města Zdice Škola: České vysoké učení technické v Praze, Fakulta dopravní Rok vydání: Praha 2011

Bakalářská práce se zabývá analýzou a optimalizací trasy pro pracovní četu provádějící udržovací práce na dílčím úseku sítě místních komunikací ve městě Zdice. Práce stručně popisuje stávající trasu a řeší návrh nové trasy pro údržbu těchto komunikací, včetně optimálního místa začátku a ukončení těchto prací. Teoretická část optimalizace představuje aparát teorie grafů a v praktické části je použita metoda čínského pošťáka, včetně Edmondsova algoritmu. Pro výběr nejvhodnějšího možného řešení byly vyšetřeny všechny vrcholy. Závěr práce zhodnocuje stávající a nově navrhované řešení.

Abstrakt Author: Anna Jíchová Title of the bachelor thesis: Design of maintenance of local communications of city of Zdice School: Czech Technical University in Prague, Faculty of Transportation Sciences Imprint date: Prague 2011

This bachelor thesis deals with the analysis and optimization of working routes for a team of labourers conducting maintenance work on the sub-section of the local network of roads in the city of Zdice. It briefly describes the existing route and brings forward a new route proposal for the maintenance of these roads, including the optimal location of the start and the completion of these works. The theoretical part of the optimization represents an apparatus of graph theory. In the applied part of this thesis, the Chinese Postman method including Edmonds algorithm, were used. All the peaks were investigated in order to select the best possible solutions. In the conclusion both the existing and new proposed solutions were evaluated.

7

Obsah: Seznam použitých zkratek ................................................................................................ 10 Seznam obrázků................................................................................................................. 10 Seznam tabulek .................................................................................................................. 11 Úvod .................................................................................................................................... 12 1.

Popis stávajícího stavu ............................................................................................... 13

1.1 Místní komunikace podle zákona o pozemních komunikacích ................................... 14 1.2 Místní komunikace ve městě Zdice ............................................................................. 15 2.

Výběr vhodné metody aparátu teorie grafů............................................................. 23

3.

Aplikace dané metody do návrhu ............................................................................. 25

3.1 Vytvoření základního grafu ......................................................................................... 25 3.2 Označení vrcholů lichého stupně – 1. krok ................................................................. 28 3.3 Kompletní graf z lichých vrcholů - 2. krok ................................................................ 29 3.4 Minimální párování – 3. krok ...................................................................................... 31 4.

Vlastní návrh dopravní obsluhy ................................................................................ 33

4.1 Konstrukce grafu se začátkem ve vrcholu V1 .............................................................. 35 4.2 Konstrukce grafu se začátkem ve vrcholu V2 .............................................................. 36 4.3 Konstrukce grafu se začátkem ve vrcholu V3 .............................................................. 37 4.4 Konstrukce grafu se začátkem ve vrcholu V4 .............................................................. 38 4.5 Konstrukce grafu se začátkem ve vrcholu V5 .............................................................. 39 4.6 Konstrukce grafu se začátkem ve vrcholu V6 .............................................................. 40 4.7 Konstrukce grafu se začátkem ve vrcholu V7 .............................................................. 41 4.8 Konstrukce grafu se začátkem ve vrcholu V8 .............................................................. 42 4.9 Konstrukce grafu se začátkem ve vrcholu V9 .............................................................. 43 4.10 Konstrukce grafu se začátkem ve vrcholu V10............................................................. 44 4.11 Konstrukce grafu se začátkem ve vrcholu V11............................................................. 45 4.12 Konstrukce grafu se začátkem ve vrcholu V12............................................................. 46 4.13 Konstrukce grafu se začátkem ve vrcholu V13............................................................. 47 4.14 Konstrukce grafu se začátkem ve vrcholu V14............................................................. 48 4.15 Konstrukce grafu se začátkem ve vrcholu V15............................................................. 49 4.16 Konstrukce grafu se začátkem ve vrcholu V16............................................................. 50 4.17 Konstrukce grafu se začátkem ve vrcholu V18............................................................. 51 8

4.18 Konstrukce grafu se začátkem ve vrcholu V19............................................................. 52 4.19 Konstrukce grafu se začátkem ve vrcholu V20............................................................. 53 4.20 Konstrukce grafu se začátkem ve vrcholu V21............................................................. 54 5.

Porovnání a zhodnocení jednotlivých řešení............................................................ 55

6.

Závěr ............................................................................................................................ 58

7.

Použitá literatura ........................................................................................................ 60

9

Seznam použitých zkratek c. k.

– císařsko královského mocnářství

MK

– místní komunikace

MP

– městský podnik

Seznam obrázků 1

Mapa oblasti ................................................................................................................. 13

2

Mapa města Zdice s vyznačením všech MK ve vlastnictví a správě města ................. 17

3

Mapa oblasti řešených ulic ........................................................................................... 20

4

První část mapy s označením podle pasportu místních komunikací ........................... 21

5

Druhá část mapy s označením podle pasportu místních komunikací ........................... 22

6

Základní graf podle stávajících ulic, křižovatky ulic představují uzly ......................... 25

7

Vyznačení cesty pro pěší .............................................................................................. 26

8

Vyznačení slepé hrany.................................................................................................. 27

9

Vyznačení vrcholů lichého stupně................................................................................ 28

10 Vyznačení délek jednotlivých hran grafu s vyznačenými vrcholy lichého stupně ...... 29 11 Kompletní graf z vrcholů lichého stupně ..................................................................... 30 12 Doplněný původní graf o dvojice minimálního párování............................................. 32 13 Doplněný graf s doplněnými délkami .......................................................................... 33 14 Úplný graf včetně slepých ulic ..................................................................................... 34 15 Graf s výchozím vrcholem V1....................................................................................... 35 16 Graf s výchozím vrcholem V2....................................................................................... 36 17 Graf s výchozím vrcholem V3....................................................................................... 37 18 Graf s výchozím vrcholem V4....................................................................................... 38 19 Graf s výchozím vrcholem V5....................................................................................... 39 20 Graf s výchozím vrcholem V6....................................................................................... 40 21 Graf s výchozím vrcholem V7....................................................................................... 41 22 Graf s výchozím vrcholem V8....................................................................................... 42 23 Graf s výchozím vrcholem V9....................................................................................... 43 24 Graf s výchozím vrcholem V10 ..................................................................................... 44 25 Graf s výchozím vrcholem V11 ..................................................................................... 45 10

26 Graf s výchozím vrcholem V12 ..................................................................................... 46 27 Graf s výchozím vrcholem V13 ..................................................................................... 47 28 Graf s výchozím vrcholem V14 ..................................................................................... 48 29 Graf s výchozím vrcholem V15 ..................................................................................... 49 30 Graf s výchozím vrcholem V16 ..................................................................................... 50 31 Graf s výchozím vrcholem V18 ..................................................................................... 51 32 Graf s výchozím vrcholem V19 ..................................................................................... 52 33 Graf s výchozím vrcholem V20 ..................................................................................... 53 34 Graf s výchozím vrcholem V21 ..................................................................................... 54 35 Mapa s výchozím stanovištěm čety městského podniku .............................................. 55

Seznam tabulek 1

Souhrnný přehled MK III. a IV. třídy na území města ............................................... 16

2

Přehled délek a ploch vozovek, chodníků a odstavných pruhů ................................... 18

3

Přehled vozovek z hlediska povrchu ............................................................................ 18

4

Označení a délky MK III. třídy .................................................................................... 19

5

Označení a délky MK IV. třídy .................................................................................... 19

6

Matice nejkratších vzdáleností lichých vrcholů ........................................................... 30

7

Celková délka trasy podle výchozího vrcholu.............................................................. 56

11

Úvod Tato práce se zabývá v jednotlivých kapitolách návrhem trasy čety městského podniku města Zdice, která zajišťuje údržbu místních komunikací v tomto městě. Je požadováno, aby celková délka navržené trasy byla nejmenší ze všech délek možných tras. Je řešeno, ze které křižovatky (vrcholu) zahájí četa údržbu komunikací a ve kterém údržba skončí, právě tak, aby četa prošla ulicí právě jen jednou, popřípadě minimálně jednou. V této práci je zjišťováno, zda začátek i konec prací je v témže vrcholu či ve vrcholu rozdílném. Ke zjištění je použito metody z operačního výzkumu (teorie dopravy) a to metody tzv. čínského pošťáka, která je pro obsluhu hran vhodná. V první kapitole je popsán stávající stav. Pro tuto práci je vybrána pouze dílčí část ulic z celkové dopravní sítě místních komunikací města, ve které je aplikován budoucí návrh řešení. Z této části ulic a křižovatek je vytvořen základní síťový graf, který je tvořen uzly (vrcholy) a hranami. Uzly (vrcholy) představují stávající křižovatky a hrany obsluhované komunikace. Druhá kapitola se zabývá výběrem vhodné metody z aparátu teorie grafů, včetně jejích postupů. Ve třetí kapitole je provedena aplikace dané metody do návrhu. Je zde řešeno, kolik vrcholů je lichého stupně a následně rozhodnuto, který algoritmus bude použit. Pro již navržený graf s vyznačenými vrcholy je použit Fleuryho algoritmus, pokud jsou pouze dva vrcholy lichého stupně. Pokud těchto vrcholů je více než dva, je použit Edmondsův algoritmus. Dále je určeno párování minimální délky hran.

Ze základního grafu

je vytvořen graf, do kterého jsou přidány fiktivní hrany minimálního párování a smyčky, které představují slepé ulice. Ve čtvrté kapitole, vlastním návrhu dopravní obsluhy, je vyšetřeno, který vrchol je nejvýhodnější pro zahájení práce čety. Postupně jsou vyšetřeny všechny vrcholy. K výchozímu vrcholu je připočítána i minimální délku cesty pro příjezd čety na stanoviště, ze kterého zahajuje svou práci. V páté kapitole jsou varianty tvořené jednotlivými výchozími vrcholy vzájemně porovnány. Varianta s nejkratší celkovou délkou je variantou nejvhodnější z hlediska nejméně ujetých kilometrů pracovní čety. Závěrem je v šesté kapitole porovnána a zhodnocena stávající používaná trasa čety a navrhované řešení. 12

1.

Popis stávajícího stavu Město Zdice (268 m n. m.) se nachází cca 40 km západně od Prahy. Poprvé se

Zdice písemně připomínají v roce 1147. Ve 13. století obec patřila pražskému biskupství, které zde na zemské cestě vybíralo clo. Ve Zdicích se křižovaly důležité obchodní cesty. Z bývalé obchodní stezky vznikla v 18. století podstatná část pozdější císařská silnice. Na ní byla již v 16. století zřízena poštovní stanice, která s rozvojem pošt postupně nabývala na významu. V roce 1862 byla uvedena do provozu tzv. Česká západní dráha z Prahy do Plzně. Po ní v roce 1875 se připojila Rakovnicko – protivínská dráha. Zdice se tak staly na dlouhou dobu důležitou železniční křižovatkou [7]. Dne 6. 5. 1872 byly Zdice, vyhlášením od c. k. místodržitele, povýšeny na městys [7]. 1. července 1994 určil předseda Poslanecké sněmovny Parlamentu ČR Zdice městem. V současné době mají Zdice téměř 4 tisíce obyvatel [7].

Obrázek 1: Mapa oblasti

(zdroj: mapa města Zdice [6])

13

Západní část území města Zdice protíná dálnice D5, která tvoří součást mezinárodní evropské silniční sítě. Zpřístupnění tělesa je umožněno mimoúrovňovou křižovatkou v km 28 (exit 28 dálničního značení). Dále město protíná silnice II/605 (doprovodná silnice k dálnici D5), II/30 (Zdice – Jince), II/236 (Zdice – Svatá), III/1171 (Zdice – Hředle), III/00524 (Zdice – Knížkovice), III/2302 (Zdice (Černín) – Levín), Koněprusy),

III/11545 (Zdice –

III/11546 (Zdice – Chodouň), III/1174 (Zdice – Stašov), elektrifikovaná

dvojkolejná železniční trať Praha – Plzeň č. 17 a železniční jednokolejná trať Zdice – Lochovice č. 20 [5]. Místní komunikace a cesty – mimo silnici II/605 není umožněna propustnost města ve směru východ – západ.

Zásadním skeletem dopravy je síť silnic v zastavěném

a zastavitelném území města, které plní převážně sběrnou a obslužnou funkci [5].

1.1

Místní komunikace podle zákona o pozemních komunikacích Ze zákona č. 13/1997 Sb. o pozemních komunikacích, ve znění pozdějších novel

a dodatků, definuje v § 6 místní komunikace Odst. 1) místní komunikace je veřejně přístupná pozemní komunikace, která slouží převážně místní dopravě na území obce [3]. Odst. 2) místní komunikace může být vystavěna jako rychlostní komunikace, která je určena pro rychlou dopravu a přístupná pouze silničním motorovým vozidlům, jejichž nejvyšší povolená rychlost není nižší, než stanoví zvláštní předpis. Rychlostní místní komunikace má obdobné stavebně technické vybavení jako dálnice [3]. Odst. 3) místní komunikace se rozdělují podle dopravního významu, určení a stavebně technického vybavení do těchto tříd: Písm. a) místní komunikace I. třídy, kterou je zejména rychlostní komunikace, Písm. b) místní komunikace II. třídy, kterou je dopravně významná sběrná komunikace s omezením přímého připojení sousedních nemovitostí, Písm. c) místní komunikace III. třídy, kterou je obslužná komunikace, Písm. d) místní komunikace IV. třídy, kterou je komunikace nepřístupná provozu silničních motorových vozidel nebo na které je umožněn smíšený provoz [3]. 14

Odst. 4) prováděcí předpis blíže vymezí znaky pro rozdělení místních komunikací do jednotlivých tříd [3]. § 2 - označení dálnic, silnic a místních komunikací (k § 6 odst. 4 a § 9 odst. 4 zákona) Odst. 5) pro evidenční účely se místní komunikace označují arabskými číslicemi, počínaje číslem 1.

Zásadně odděleně pro každou třídu místních komunikací. K označení třídy se

používá alfabetický znak: a) Pro místní komunikace I. třídy písm. a), např. 1a, 2a, b) Pro místní komunikace II. třídy písm. b), např. 2a, 4b, c) Pro místní komunikace III. třídy písm. c), např. 1c, 8c, d) Pro místní komunikace IV. třídy písm. d), např. 1d, 12d [3, 4].

1.2

Místní komunikace ve městě Zdice Ve Zdicích jsou místní komunikace v souladu se schváleným pasportem místních

komunikací zařazeny do III. a IV. třídy. V souladu s § 3 odst. 3 a 4 (k § 6 odst. 4 zákona) – místními komunikacemi III. třídy jsou obslužné místní komunikace ve městech a obcích umožňující přímou dopravní obsluhu jednotlivých objektů, pokud jsou přístupné běžnému provozu motorových vozidel. Místními komunikacemi IV. třídy jsou samostatné chodníky, stezky pro pěší, cyklistické stezky v chatových oblastech, podchody, lávky, schody, pěšiny, zklidněné komunikace. Obytné a pěší zóny apod. [4]. Na základě ustanovení zákonných předpisů se na území města Zdice nevyskytují místní komunikace I. třídy (rychlostní komunikace), ani místní komunikace II. třídy (sběrné komunikace, které spojují části měst navzájem nebo napojují města, případně jejich části na pozemní komunikace vyšší třídy nebo kategorie). Spojení částí města navzájem je realizováno silnicemi II. a III. třídy [4]. Na území města Zdic se vyskytují místní komunikace III. třídy (obslužné komunikace) a místní komunikace IV. třídy (obytné zóny, samostatné komunikace pro pěší, schodiště a chodníky podél průjezdních úseků silnic.)

Dále jsou zahrnuty

i parkovací plochy podél silnic mimo průjezdní profil silnice (ul. Husova a Komenského) [4]. 15

MK III. třídy

Délka [m] 27 707

MK IV. třídy – vozovky (obytné zóny)

2 486

MK IV. třídy – samostatné chodník

2 462

MK IV. třídy – chodníky při silnicích

6 820

MK IV – celkem

11 768

MK – celkem

39 475

Typ komunikace

Účelové komunikace

165

Tabulka 1: Souhrnný přehled MK III. a IV. třídy na území města (zdroj:Pasport místních komunikací města Zdice [4])

16

Obrázek 2: Mapa města Zdice s vyznačením všech MK ve vlastnictví a správě města (zdroj: pasport místních komunikací města Zdice [4])

17

Chodníky

Vozovky

Odstavné pruhy

(všechny)

Přehled celkový Délka

Plocha

Délka

Plocha

Délka

Plocha

Na MK III. třídy

27 707

111 626

11 293

17 218

255

1 275

Na MK IV. třídy

2 486

11 606

9 318

17 948

0

0

Celkem

30 193

123 232

20 611

35 166

255

1 275

0

0

0

0

1 011

6 676

Účelové komunikace

165

495

0

0

0

0

Celkem

165

495

0

0

1 011

2 676

30 358

123 727

20 611

35 166

1 266

3 951

Odstavné pruhy při silnicích

CELKEM

Tabulka 2: Přehled délek a ploch vozovek, chodníků a odstavných pruhů (zdroj: Pasport místních komunikací města Zdice [4])

Plochy

Účelové

odstavné

komunikace

11606

2676

495

76399

11226

2676

0

589

589

0

0

0

Velká dlažba 16

1283

1283

0

0

0

Panely

1988

1988

0

0

0

Bet. zámková dlažba

250

250

0

0

0

Beton

315

315

0

0

0

32953

32078

380

0

495

Povrch vozovek

Celkem

MK III.

MK IV.

Celkem

127678

112901

Asfalt

90302

Drobná dlažba 10x 10

Nezpevněný

Tabulka 3: Přehled ploch vozovek z hlediska povrchu (zdroj: Pasport místních komunikací města Zdice [4])

V rámci této práce je řešena pouze část místních komunikací města, a to v lokalitě Samohelka. 18

Graf je tvořen z místních komunikací III. a IV. třídy s označením c a d.

Délka

Název ulice

Označení

K Samohelce

63c

43,7

Stará Zvonice

64c

20,0

K Samohelce

65c

52,5

Na Vyhlídce

66c

365,0

Dělnická + Stará Zvonice Nad Úvozem

67c

404,0

68c

47,5

Knížkovická

69c

26,5

[m]

Tabulka 4: Označení a délky MK III. třídy (zdroj: pasport místních komunikací města Zdice [4])

Název ulice

Označení

Délka [m]

Vorlova

15d

415,0

K Samohelce

46d

43,5

K Samohelce

47d

337,0

Na Nové

48d

355,0

Knížkovická

50d

386,0

Hornická

51d

257,0

Knížkovická + Pod Šachtou Nad Cihelnou

52d

112,5

53d

186,0

Nad Úvozem

54d

312,5

Za Skálou

55d

52

Knížkovická

56d

63,0

Tabulka 5: Označení a délky MK IV. třídy (zdroj: Pasport místních komunikací města Zdice [4]) 19

Údržbu místních komunikací v současnosti zajišťuje Město Zdice prostřednictvím své rozpočtové organizace Městského podniku Zdice. V rámci údržby i úklidových prací má úklidová četa navrženou trasu ulicemi Vorlova, Na Vyhlídce, Stará Zvonice, Dělnická, Na Nové, K Samohelce, Za Skálou, Nad Úvozem, Hornická, Knížkovická, Pod Šachtou, Nad Cihelnou a zpět Vorlova. Městský podnik trvale má šest stálých zaměstnanců, kteří tvoří dvě čety. Na zimní i jinou údržbu místních komunikací město Zdice sezóně najímá pracovníky z úřadu práce. Vorlova ulice je silnicí III/00524, kterou vlastní Česká republika a správu zajišťuje Krajská správa a údržba silnic, proto jejich údržba nebude v této práci řešena. Na komunikacích, které jsou předmětem řešení, je prováděna zimní údržba – odklízení sněhu, zimní posyp při náledí a následný úklid a průběžný úklid komunikací, včetně mytí ulic v letních měsících. Běžná údržba a opravy komunikací je prováděna v souladu s přílohou č. 5 k vyhlášce č. 104/1997 Sb., ve znění pozdějších novel a dodatků, kterou se provádí zákon o pozemních komunikacích.

Obrázek 3: Mapa oblasti řešených ulic (zdroj: mapa města Zdice[6]) 20

Obrázek 4: První část mapy s označením podle pasportu místních komunikací (zdroj: Pasport místních komunikací města Zdice [4])

21

Obrázek 5: Druhá část mapy s označením podle pasportu místních komunikací (Zdroj: Pasport místních komunikací města Zdice [4])

22

2. Výběr vhodné metody aparátu teorie grafů V této práci se jedná o dopravní obsluhu hran (ulic) dopravní sítě, která je tvořena specifikovanou množinou místních komunikací. Při této obsluze, kdy četa provádí údržbu komunikací, je kladena podmínka, aby četa prošla či projela ulicí právě jednou nebo alespoň jednou a ušla či ujela co nejméně kilometrů. Protože je připuštěna podmínka, aby četa prošla ulicí alespoň jednou, je požadováno, aby vícekrát procházela pouze co nejkratší cestou. Musíme určit, ze kterého vrcholu četa zahájí, a ve kterém ukončí své práce a zvolit trasu tak, aby celková délka navržené trasy byla nejmenší ze všech délek možných tras. Ke zjištění je použito metody z operačního výzkumu (teorie grafů) a to metody tzv. čínského pošťáka, která je pro obsluhu hran vhodná [1]. Pro tuto práci je vybrána pouze dílčí část ulic z celkové dopravní sítě místních komunikací města (lokalita Samohelka), ve které je aplikován budoucí návrh řešení. Z této části ulic a křižovatek je vytvořen základní síťový graf, který je tvořen uzly (vrcholy) a hranami. Uzly (vrcholy) představují stávající křižovatky a hrany - obsluhované komunikace. Protože v předmětné lokalitě nejsou žádné jednosměrné ulice, kde je určen směr jízdy, je graf neorientovaný. Je předpokládáno, že počet lichých vrcholů grafu je větší než dva, a proto je použit Edmondsův algoritmus. Pokud se toto nepotvrdí a vrcholy lichého stupně jsou pouze dva, bude použit Fleuryho algoritmus. Při použití Fleuryho algoritmu, kdy právě dva vrcholy jsou lichého stupně, jsou spojeny tyto dva vrcholy násobnou hranou, která je řešena jako první. Po dokončení uzavřeného eulerovského tahu je hrana opět vypuštěna, tím vznikne otevřený eulerovský tah. V případě použití Edmondsova algoritmu, který je v daném případě předpokládán, je postupováno v následujících pěti krocích: 1. krok - v grafu určím vrcholy sudého stupně, kterých musí být vždycky sudý počet, 2. krok - sestrojím z vrcholů lichého stupně fiktivní kompletní graf, jehož hrany jsou ohodnoceny vzdáleností příslušných vrcholů v původním (základním) grafu, 23

3. krok - určím minimální párování délky a fiktivní hrany minimálního párování přidám do původního grafu mezi příslušné vrcholy, 4. krok – v grafu sestrojím uzavřený eulerovský tah minimální délky Fleuryho algoritmem, 5. krok – v eulerovském tahu nahradím každou hranu minimálního párování odpovídající cestou minimálního párování. Dostanu uzavřený eulerovský sled minimální délky [1] Také je zjišťováno, zda se jedná o otevřený či uzavřený eulerovský sled. Což představuje, zda četa svou práci zahájí i skončí ve stejném uzlu (vrcholu) nebo uzlu jiném (koncovém). Pojem eulerovský sled znamená, že všechny hrany v síti jsou procházeny minimálně jednou. Eulerovský tah znamená, že všechny hrany v síti jsou procházeny právě jednou. Lze předpokládat, že se v tomto konkrétním případě bude jednat o uzavřený eulerovský sled.

24

3. Aplikace dané metody do návrhu 3.1

Vytvoření základního grafu Mapu na obrázku 3, 4 a 5 si převedeme na grafické zobrazení. Součástí grafu je

i silnice III/00524. Tato komunikace je v majetku státu, na které údržbu provádí Krajská správa a údržba komunikací Středočeského kraje, ale pro potřeby výpočtu v teoretické úrovni je do grafu zahrnuta, ale ve skutečnosti údržba není prováděna, pouze je využívána pro průjezd a přístup. Tyto komunikace (hrany) jsou v grafu zobrazeny čárkovaně a jsou mezi vrcholy V1-V11-V21. Také zde nejsou uváděny dvě ulice, které jsou slepé, a tudíž obsluha těchto ulic je vždy řešena průjezdem tam a zpět.

V11

V1

V2

V6

V12

V7

V13

V3

V4

V8

V5

V9

V14

V19 V15

V10

V18

V21

V16 V17

V20

Obrázek 6: Základní graf podle stávajících ulic, křižovatky ulic představují uzly (zdroj: vlastní) 25

Dále z grafu lze vypustit cesty pro pěší, které se neudržují, a tudíž se nepoužijí pro výpočet. Jedná se o hrany mezi vrcholy V8 - V9, V16 - V17, V19 - V21.

V1

V2

V11

V6

V3 V7

V4

V8

V5

V9

V13

V14

V19 V15

V10

V18

V21

V16 V17

Obrázek 7: Vyznačené cesty pro pěší (zdroj: vlastní) Po této úpravě se hrana mezi vrcholy V17-V20 stala slepou ulicí a smyčka ve vrcholu V5 také. Tyto hrany (ulice) umožňují vozidlům průjezd tam a zpět. Proto tyto hrany z grafu vynecháme. Po této úpravě získáme graf, který budeme řešit pomocí aparátu teorie grafů (operační výzkum).

26

V1

V2

V6

V3

V7

V4

V8

V5

V12

V13

V14

V19

V9 V15

V10

V18

V21

V16 V17 V20

Obrázek 8: Vyznačení slepé hrany (zdroj: vlastní)

27

3.2

Označení vrcholů lichého stupně – 1. krok

V1

V2

V3

V11

V6

V7

V4

V8

V5

V9

V12

V13

V14

V19 V15

V18 V21

V10

V16

V20 Obrázek 9: Vyznačení vrcholů lichého stupně (zdroj: vlastní)

Vrcholy lichého stupně jsou V2, V3, V4, V6, V7, V9, V12, V13, V18, V19. Celkem se jedná o 10 vrcholů, čímž je splněna podmínka, že těchto vrcholů musí být vždy sudý počet. Pro další postup je nutné ke každé hraně vyznačit její skutečnou délku, a to z Pasportu místních komunikací Města Zdice [4].

28

V1

V11

188 m

56 m

V2

138 m

115 m

48 m

83 m

97 m

V3

V6

V7

V12 35 m

38 m

V13 344 m

V4

131 m

V8

126 m

V14 91 m

90 m

V5

415 m

160 m

73 m

135 m

V9

60 m 138 m

45 m

V15

72 m

V19

V18

V21

92 m

215 m

60 m

V10

203 m

V16 20 m

V20 Obrázek 10: Vyznačení délek jednotlivých hran grafu s vyznačenými vrcholy lichého stupně (zdroj: vlastní)

3.3

Kompletní graf z lichých vrcholů - 2. krok Ve druhém kroku vytvoříme kompletní graf z vrcholů lichého stupně. Pokud bychom

vyznačili nejkratší vzdálenosti do tohoto grafu, byl by značně nepřehledný. Tento graf je znázorněn na obrázku 11. Plnou čarou jsou znázorněny hrany, jejichž ohodnocení známe a přerušovanou čárou jsou vyznačeny hrany, které budou dopočítány. Pro přehlednost jsme zvolili matici, do které jsou uvedeny nejkratší vzdálenosti mezi lichými vrcholy, viz tabulka 6.

29

V6

V2

V12

V7

V3

V13

V4

V19

V9

V18

Obrázek 11: Kompletní graf z vrcholů lichého stupně (zdroj: vlastní) Označení vrcholu V2 V3 V4 V6 V7 V9 V12 V13 V18 V19

V2

V3

V4

V6

V7

V9

V12

V13

V18

V19

0 115 188 138 212 413 186 221 472 544

115 0 73 180 97 298 170 135 386 458

188 73 0 253 170 225 243 208 348 420

138 180 253 0 83 441 48 83 334 406

212 97 170 83 0 395 73 38 289 361

413 298 225 441 395 0 393 355 183 255

186 170 243 48 73 393 0 35 286 358

221 135 208 83 38 355 35 0 251 323

472 386 348 334 289 183 286 251 0 72

544 458 420 406 361 255 358 323 72 0

Tabulka 6: Matice nejkratších vzdáleností lichých vrcholů (zdroj: vlastní) 30

3.4

Minimální párování – 3. krok Třetím krokem bude minimální párování všech lichých vrcholů: d(V2, V3 ) + d(V4, V6 ) + d(V7, V9 ) + d(V12, V13 ) + d(V18 , V19 )= 115 + 235 + 395 + 35 + 72 = 852 d(V2 , V4 ) + d(V3, V6 ) + d(V7, V9 ) + d(V12, V13 ) + d(V18, V19 )= 188 + 180 + 395 + 35 + 72 = 870 d(V2, V7 ) + d(V3, V6 ) + d(V4, V9 ) + d(V12, V13 ) + d(V18, V19 )= 212 + 180 + 225 + 35 + 72 = 724 d(V2, V12 ) + d(V3, V6 ) + d(V4, V9 ) + d(V7, V13 ) + d(V18, V19 )= 186 + 180 + 225 + 38 + 72 = 701 d(V2, V18 ) + d(V3, V6 ) + d(V4, V9 ) + d(V7, V13 ) + d(V12, V19 )= 544 + 180 + 225 + 38 + 358 = 1345 d(V2, V6 ) + d(V4, V3 ) + d(V7, V9 ) + d(V12, V13 ) + d(V18, V19 )= 138 + 73 + 395 + 35 + 72 = 713 d(V2, V9 ) + d(V4, V3 ) + d(V7, V6 ) + d(V12, V13 ) + d(V18, V19 )= 413 + 73 + 83 + 35 + 72 = 676 d(V2, V13 ) + d(V4, V3 ) + d(V7, V6 ) + d(V12, V9 ) + d(V18, V19 )= 221 + 73 + 83 + 393 + 72 = 842 d(V2, V19 ) + d(V4, V3 ) + d(V7, V6 ) + d(V12, V9 ) + d(V18, V13 )= 544 + 73 + 83 + 393 + 251 = 1344 d(V2, V3 ) + d(V4, V7 ) + d(V6, V9 ) + d(V12, V13 ) + d(V18, V19 )= 115 + 170 + 441 + 35 + 72 = 833 d(V2, V3 ) + d(V4, V12 ) + d(V6, V9 ) + d(V7, V13 ) + d(V18, V19 )= 115 + 243 + 441 + 38 + 72 = 909 d(V2, V3 ) + d(V4, V18 ) + d(V6, V9 ) + d(V7, V13 ) + d(V12, V19)= 115 + 348 + 441 + 38 + 358 = 1300 d(V2, V3 ) + d(V4, V6 ) + d(V7, V12 ) + d(V9, V13 ) + d(V18, V19 )= 115 + 253 + 73 + 355 + 72 = 868 d(V2, V3 ) + d(V4,V6 ) + d(V7, V18 ) + d(V9, V13 ) + d(V12, V19)= 115 + 253 + 289 + 355 + 358 = 1370 d(V2 , V3 ) + d(V4, V6 ) + d(V7, V9 ) + d(V18 ,V18 ) + d(V13 ,V19)= 115 + 253 + 395 + 286 + 323 = 1372 31

d(V2, V3 ) + d(V4, V6 ) + d(V7, V9 ) + d(V12, V19 ) + d(V18, V13)= 115 + 253 + 395 + 358 + 251 = 1372 Minimální párování tvoří dvojice hran (V2, V9 ), (V4, V3 ), (V7, V6 ), (V12, V13 ), (V18 , V19), které doplníme do původního grafu.

V1

V2

V6

V3

V7

V4

V8

V12

V13

V14 V19

V9 V5 V15

V10

V18

V21

V16

V20 Obrázek 12: Doplněný původní graf o dvojice minimálního párování (zdroj: vlastní)

32

4. Vlastní návrh dopravní obsluhy

V1

188 m

56 m

V2

V6

138 m 83 m

V3

35 m

83 m

115 m 97 m

V7

V12

48 m

38 m

35 m

V13

415 m 344 m

73 m

73 m

131 m

V4 413 m

160 m

V8

126 m

90 m

V5

V14 91 m

60 m 135 m

V9

72 m 138 m

45 m

V19

72 m

V15

V18

V21

215 m 92 m

V10

60 m

V16 20 m

203 m

V20 Obrázek 13: Doplněný graf s doplněnými délkami (zdroj: vlastní) Pro úplnost doplníme do grafu i ulice (smyčky), které jsou slepými a tudíž průjezd je možný v rámci údržby pouze tam a zpět.

33

V1

188 m

56 m

V2

V6

138 m 83 m

V3

35 m

83 m

115 m 97 m

V7

V12

48 m

35 m

V13

38 m

415 m 344 m

73 m

73 m

131 m

V4 413 m

160 m

V8

126 m

90 m

V5

V14 91 m

60 m 135 m

V9

72 m 138 m

45 m

V19

72 m

V15

52 m x 2

V18

V21

215 m 92 m

V10

60 m

V16 365 m x 2

203 m

20 m

V20 Obrázek 14: Úplný graf včetně slepých ulic (zdroj: vlastní) Protože graf není velký, je vyšetřen počátek možné cesty obsluhy z každého vrcholu. Konstrukce grafu je zahájena ve zvoleném vrcholu a dále postupně zařazovány ostatní incidentní hrany s uzly, kterými je procházeno. Až jsou všechny hrany zařazeny do grafu, pak poslední propojený tah je eulerovský. Postup po jednotlivých hranách je v grafu pro zjednodušení znázorněn pořadovými čísly u jednotlivých hran.

34

4.1

Konstrukce grafu se začátkem ve vrcholu V1

V1 1 35 V2

28 34

19 V3

V6

33 32 V7 22

V12

31 29 23

30 V13 2

21

14

V4

16

24

20

15 V5

V8

13

V14 25

12 17

26

V9

V19

7 11

18

27

V15

V18

6

10

V21 8

V10

5 3

V16 9

4

V20

Obrázek 15: Graf s výchozím vrcholem V1 (zdroj: vlastní)

Eulerovský sled podle grafu: V1-V11-V21-V20-V20-V19-V18-V15-V16-V10-V9-V15-V14-V8V4-V5-V5-V9-V2-V3-V4-V3-V7-V13-V14-V18-V19-V11-V12-V13-V12-V6-V7-V6-V2-V1. Výsledná délka je 4 860m. K tomuto řešení je nutné připočítat i cestu nutnou pro příjezd čety, a to je 603 m (V21-V11-V1) k vrcholu V1. Celková délka trasy je 5 463 m.

35

4.2


V1 34 35 V2

28 26

25

V7

V12

27

21 20 22

V3

V6

17 19

18 V13 33

23

9

V4

7

16

24

8 V5

V8

10

V14 15

11 6

14

V9

V19

12 5

1

29

V15

V18

13

2

V21 4 V10

30 32

V16 3

31

V20

Obrázek 16: Graf s výchozím vrcholem V2 (zdroj: vlastní)

Eulerovský sled podle grafu: V2-V9-V10-V16-V15-V9-V5-V5-V4-V8-V14-V15-V18-V19-V18V14-V13-V12-V13-V7-V6-V7-V3-V4-V3-V2-V6-V12-V11-V19-V20-V20-V21-V11-V1-V2. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 657 m (V21-V11-V12-V6-V2) k vrcholu V2. Celková délka trasy je 5 517 m.

36

4.3


V1 5 6 V2

4 V6

7 35

2 1

V3

V12

3

8 V7

10 9

11 V13 16

30

28

V4

32

12

29

31 V5

V8

27

V14 13

26 33

14

V9

V19

21 25

34

15

V15

V18

20

24

V21 22

V10

19 17

V16 23

18

V20

Obrázek 17: Graf s výchozím vrcholem V3 (zdroj: vlastní) Eulerovský sled podle grafu je V3-V7-V6-V12-V11-V1-V2-V6-V7-V13-V12-V13-V14-V18V19-V11-V21-V20-V20-V19-V18-V15-V16-V10-V9-V15-V14-V8-V4-V3-V4-V5-V5-V9-V2-V3. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 573 m (V21-V20-V19-V18-V14-V8-V4-V3) k vrcholu V3. Celková délka je 5 433 m.

37

4.4


V1 32 33 V2

V6

22 34

4 2

V3

24

3 V7

V12

23 6 5

7 V13 31

35

17

V4

19

8

1

18 V5

V8

16

V14 15

20

9

V9

27

V19

14 13

21

25

V15

V18

26

12

V21 10

V10

28 30

V16 11

29

V20

Obrázek 18: Graf s výchozím vrcholem V4 (zdroj: vlastní) Eulerovský sled podle grafu je V4-V3-V7-V6-V7-V13-V12-V13-V14-V15-V16-V10-V9-V15V18-V14-V8-V4-V5-V5-V9-V2-V6-V12-V11-V19-V18-V19-V20-V20-V21-V11-V1-V2-V3-V4. Výsledná délka je 4 860m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 500 m (V21-V20-V19-V18-V14-V8-V4) k vrcholu V4. Celková délka je 5 360 m.

38

4.5


V1

11 12

V2

V6

4 13

5 16

V3

10 V12

7

6 V7

8 17

9 V13 22

15

34

V4

1

18

14

35 V5

V8

33

V14 19

2

32

V9

20

V19

27 31

3

21

V15

V18

26

30

V21 28

V10

25 23

V16 29

24

V20

Obrázek 19: Graf s výchozím vrcholem V5 (zdroj: vlastní) Eulerovský sled podle grafu je V5-V5-V9-V2-V6-V7-V6-V12-V13-V12-V11-V1-V2-V3-V4V3-V7-V13-V14-V18-V19-V11-V21-V20-V20-V19-V18-V15-V16-V10-V9-V15-V14-V8-V4-V5. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 470 m (V21-V20-V19-V18-V15-V9-V5) k vrcholu V5. Celková délka je 5 330 m.

39

4.6


V1 5 6 V2

V6

35 7

1 8

V3

4 V12

3

2 V7

10 9

11 V13 27

16

14

V4

18

12

15

17 V5

V8

13

V14 24

23 19

25

V9

V19

32 33

34

26

V15

V18

31

20

V21 22

V10

30 28

V16 21

29

V20

Obrázek 20: Graf s výchozím vrcholem V6 (zdroj: vlastní) Eulerovský sled podle grafu je V6-V7-V6-V12-V11-V1-V2-V3-V7-V13-V12-V13-V14-V8-V4V3-V4-V5-V5-V9-V10-V16-V15-V14-V18-V19-V11-V21-V20-V20-V19-V18-V15-V9-V2-V6. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 486 m (V21-V20-V19-V18-V14-V13-V12-V11-V6) k vrcholu V6. Celková délka je 5 346 m.

40

4.7


V1 4 5 V2

6 34

3 V12

2

1 V7

9 8

V8

26

14 V14 12

32

25

V9

13

V19

20 24

33

15

11 27

30 V5

10 V13

28

V4

31

7 35

V3 29

V6

V15

V18

19

23

V21 21

V10

18 16

V16 22

17

V20


41

4.8


V1 11 10 V2

9 28

8 3

V3 29

V6

12 V12

6

7 V7

5 4

V13

1

V8

35

31

V14

32

34

V9

16

V19

23 33

27

21

15

30 V5

20

14

2

V4

13

V15

V18

22

26

V21 24

V10

17 19

V16 25 18

V20

Obrázek 22: Graf s výchozím vrcholem V8 (zdroj: vlastní) Eulerovský sled podle grafu je V8-V4-V3-V7-V13-V12-V6-V7-V6-V2-V1-V11-V12-V13-V14V18-V19-V20-V20-V21-V11-V19-V18-V15-V16-V10-V9-V2-V3-V4-V5-V5-V9-V15-V14-V8. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 369 m (V21-V20-V19-V18-V14-V8) k vrcholu V8. Celková délka je 5 229 m.

42

4.9


V1 19 20 V2

6 5

8 12

V3 13

V6

18 V12

9

7 V7

10 11

14

V8

15

2

29 28

V14 26

3 V5

V13 16

4

V4

17

1

V9

25

27

35

V19

34 V15

V18

33

21

V21

22

24

V10

32 30

V16 23 31

V20

Obrázek 23: Graf s výchozím vrcholem V9 (zdroj: vlastní) Eulerovský sled podle grafu je V9-V5-V5-V4-V3-V2-V6-V7-V6-V12-V13-V7-V4-V8-V14V13-V12-V11-V1-V2-V9-V10-V16-V15-V14-V18-V19-V11-V21-V20-V20-V19-V18-V15-V9. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 335 m (V21-V20-V19-V18-V15-V9) k vrcholu V9. Celková délka je 5 195 m.

43

4.10 Konstrukce grafu se začátkem ve vrcholu V10

V1 29 28 V2

27 20

23 21

V3 15

V6

30

22 V7

V12

26 25 24

13

V8

12

17

9 V14

18

33

V9

4

V19

3 34

19

8

11

16 V5

V13 32

14

V4

31

V15

V18

10

35

V21 2

V10

5 7

V16 1 6

V20

Obrázek 24: Graf s výchozím vrcholem V10 (zdroj: vlastní) Eulerovský sled podle grafu je V10V16-V15-V18-V19-V20-V20-V21-V11-V19-V18-V14-V8V4-V3-V4-V5-V5-V9-V2-V3-V7-V6-V7-V13-V12-V6-V2-V1-V11-V12-V13-V14-V15-V9-V10. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 492 m (V21-V20-V19-V18-V15-V16-V10) k vrcholu V10. Celková délka je 5 352 m.

44


V1 35 34 V2

33 26

29 27

V3 21

V6

6

28 V7

V12

32 7 30

V13 8

20 19

V4

V8

18

23

5 V14

24

17

V9

10

V19

12 16

25

1

9

22 V5

31

V15

V18

11

15

V21 13

V10

4 2

V16 14 3

V20

Obrázek 25: Graf s výchozím vrcholem V11 (zdroj: vlastní) Eulerovský sled podle grafu je V11-V21-V20-V20-V19-V11-V12-V13-V14-V18-V19-V18-V15V16-V10-V9-V15-V14-V8-V4-V3-V4-V5-V5-V9-V2-V3-V7-V6-V7-V13-V12-V6-V2-V1-V11. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 415 m (V21-V11) k vrcholu V11. Celková délka je 5 275 m.

45


V1 2 3 V2

4 22

5 10

V3 21

V6

1 V12

7

6 V7

8 9

V13 34

11 12

V4

V8

13

19

31 V14

18

14

V9

26

V19

25 24

23

30

33

20 V5

35

V15

V18

32 V21

17 15 V10

27 29

V16 16 28

V20

Obrázek 26: Graf s výchozím vrcholem V12 (zdroj: vlastní) Eulerovský sled podle grafu je V12-V11-V1-V2-V6-V7-V6-V12-V13-V7-V3-V4-V8-V14-V15V16-V10-V9-V5-V5-V4-V3-V2-V9-V15-V18-V19-V20-V20-V21-V11-V19-V18-V14-V13-V12. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 438 m (V21-V20-V19-V18-V14-V13-V12) k vrcholu V12. Celková délka je 5 298 m.

46


V1 3 4 V2

12 5

11 6

V3 18

V6

2 V12

9

10 V7

1 7

V13

19

V8

20

V5

V14

14

21

V9

27

V19

26 25

13

32

34

16 15

31

35

17

V4

8

V15

V18

33

24

V21 22

V10

28 30

V16 23 29

V20


47


V1 7 8 V2

15 9

22

27

V7

V12

18

17 16 21

V3

V6

26 20

23

V8

24

V5

28 V14

13

35

V9

2

V19

30 31

14

6

1

11 12

V13 25

10

V4

19

V15

V18

29

32

V21 34

V10

3 5

V16 33 4

V20


48


V1 13 14 V2

15 22

20 21

V3 28

V6

12

19 V7

V12

16 17 18

29

V8

30

V5

7 V14

24

31

V9

2

V19

1 35

23

6

9

26 25

V13 10

27

V4

11

V15

V18

8

34

V21 32

V10

3 5

V16 33 4

V20

Obrázek 29: Graf s výchozím vrcholem V15 (zdroj: vlastní) Eulerovský sled podle grafu je V15-V18-V19-V20-V20-V21-V11-V19-V18-V14-V13-V12-V11V1-V2-V6-V12-V13-V7-V6-V7-V3-V2-V9-V5-V5-V4-V3-V4-V8-V14-V15-V16-V10-V9-V15. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 197 m (V21-V20-V19-V18-V15) k vrcholu V15. Celková délka je 5 057 m.

49


V1 18 17 V2

16 7

21 14

V3 13

V6

19

15 V7

V12

20 23 22

12

V8

11

V5

28 V14

3

10

V9

27

V19

34 9

8

29

26

5 4

V13 25

6

V4

24

V15

V18

33

2

V21 35

V10

32 30

V16 1 31

V20


50


V1 12 13 V2

14 32

V3 31

V6

16 15 V7 20

11 V12

17 18 19

22

V8

23

V5

6 V14

28

24

V9

1

V19

35 34

33

5

8

30 29

V13 9

21

V4

10

V15

V18

7

27

V21 25

V10

2 4

V16 26 V20 3

Obrázek 31: Graf s výchozím vrcholem V18 (zdroj: vlastní) Eulerovský sled podle grafu je V18-V19-V20-V20-V21-V11-V19-V18-V14-V13-V12-V11-V1V2-V6-V7-V6-V12-V13-V7-V3-V4-V8-V14-V15-V16-V10-V9-V5-V5-V4-V3-V2-V9-V15-V18. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 152 m (V21-V20-V19-V18) k vrcholu V18. Celková délka je 5 012 m.

51


V1 20 19 V2

23 24

28 27

V3 26

V6

21

29 V7

V12

22

31 32 30

14

V8

13

V5

V14

17

12

V9

6

V19

7 11

18

5

34

15 16

4

33

25

V4

V13

V15

V18

35

10

V21 8

V10

1 3

V16 9 2

V20

Obrázek 32: Graf s výchozím vrcholem V19 (zdroj: vlastní) Eulerovský sled podle grafu je V19-V20-V20-V21-V11-V19-V18-V15-V16-V10-V9-V15-V14V8-V4-V5-V5-V9-V2-V1-V11-V12-V6-V2-V3-V4-V3-V7-V6-V7-V13-V12-V13-V14-V18-V19. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 80 m (V21-V20-V19) k vrcholu V19. Celková délka je 4 940 m.

52


V1 27 28 V2

29 20

22 21

V3 15

V6

26

23 V7

V12

30 25 24

13

V8

12

V5

3 4

V14 33

16 17

V13 32

14

V4

31

18

V9

11

5

7

V15 19

V19

6 V18

34

8

V21 10 V10

35 2

V16 9 V20 1

Obrázek 33: Graf s výchozím vrcholem V20 (zdroj: vlastní) Eulerovský sled podle grafu je V20-V20-V21-V11-V19-V18-V15-V9-V10-V16-V15-V14-V8V4-V3-V4-V5-V5-V9-V2-V3-V7-V6-V7-V13-V12-V11-V1-V2-V6-V12-V13-V14-V18-V19-V20. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 20 m (V21-V20) k vrcholu V20. Celková délka je 4 880 m.

53


V1 34 33 V2

32 25

28 26

V3 20

V6

5

27 V7

V12

31 6 29

18

V8

17

22

4 V14

23

16

V9

9

V19

11 15

24

35

8

21 V5

V13 7

19

V4

30

V15

V18

10

14

V21 12

V10

3 1

V16 13 V20 2

Obrázek 34: Graf s výchozím vrcholem V21 (zdroj: vlastní) Eulerovský sled podle grafu je V21-V20-V20-V19-V11-V12-V13-V14-V18-V19-V18-V15-V16V10-V9-V15-V14-V8-V4-V3-V4-V5-V5-V9-V2-V3-V7-V6-V7-V13-V12-V6-V2-V1-V11-V21. Výsledná délka je 4 860 m. K tomuto řešení je nutné připočítat i minimální cestu nutnou pro příjezd čety - 0 m k vrcholu V21. Celková délka je 4 860 m.

54

5. Porovnání a zhodnocení jednotlivých řešení Z předchozího návrhu vyplývá, že při obsluze všech hran (ulic) za podmínky, aby četa prošla ulicí alespoň jednou a vícekrát pouze co nejkratší úseky, je po provedeném minimálním párování a doplnění fiktivních hran mezi příslušné vrcholy jasné, že konečné číslo bude vždy 4 860 m obslužných komunikací. Protože graf vycházel z reálných komunikací města, je nutné vzít do úvahy i výchozí polohu městského podniku, který tuto údržbu (či obsluhu) provádí. Na obrázku 35 vpravo dole je patrné, kde se podnik nachází.

Obrázek 35: Mapa s výchozím stanovištěm čety městského podniku (zdroj: mapa města Zdice [6]) Vzdálenost základny městského podniku k nejbližšímu vrcholu grafu V21, který je křižovatkou ulic Vorlova, Stará Zvonice a Zdíkova náměstí je 1 101 m. Tato vzdálenost není do grafu započítána, protože by se jednalo o konstantu, která by ke každému výchozímu vrcholu byla vždy připočítána. K základně je nejbližší vrchol daného grafu vrchol V21.

55

Je nezbytné připočítat i minimální (nejkratší) cestu k výchozímu vrcholu grafu, který je ve zvoleném grafu počátečním uzlem (výchozím vrcholem) údržby. Je třeba se na dané výchozí místo (reprezentované výchozím vrcholem) dopravit, a proto je tato připočítaná cesta nutná, ale pro četu ztrátová. Pokud chceme eliminovat tuto ztrátu je pro četu nejvýhodnější zahájit svou práci ve vrcholu V21, kde ji také ukončí.

Výchozí vrchol V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15 V16 V18 V19 V20 V21

Minimální délka trasy k výchozímu vrcholu [m] 603 357 573 500 470 486 441 369 335 492 415 438 403 243 197 289 152 80 20 0

Celková délka trasy [m] 5 463 5 517 5 433 5 360 5 330 5 346 5 301 5 229 5 195 5 352 5 275 5 298 5 263 5 103 5 057 5 149 5 012 4 940 4 880 4 860

Tabulka 7: Celková délka trasy podle výchozího (počátečního) vrcholu (zdroj: vlastní) Pokud bychom chtěli otevřený eulerovský sled, ukončíme práci v grafu s výchozím vrcholem V21 ve vrcholu V1, ale protože četa se musí i vrátit na svou základnu, která je znázorněna na obrázku 35 (na mapě vpravo dole), je nejkratší cesta přes vrcholy V1-V11V21. Po zařazení do grafu se tudíž bude ve výsledku jednat o uzavřený eulerovský sled, protože je naplněna podmínka, abychom cestu prošli minimálně jednou. 56

Výsledná délka obslužné trasy této jedné čety je 4 860 m (vlastní délka trasy komunikací, na kterých četa vykonává údržbu) + 1101 m (délka cesty čety na stanoviště ze základny) + 1101 m (délka zpáteční cesty čety na základnu). Výsledkem je délka trasy ze základny, vykonání potřebných udržovacích prací a zpáteční cesta jedné čety na základnu, a to v celkové délce 7 062 m.

57

6. Závěr Tato práce se v jednotlivých kapitolách zabývala návrhem trasy pracovní čety městského podniku města Zdice. Řeší, ze kterého vrcholu (uzlu) zahájí četa údržbu komunikací, a ve kterém údržba skončí. Tak, aby četa prošla ulicí právě jen jednou, popřípadě minimálně jednou. V této práci bylo zjišťováno, zda začátek i konec prací bude v témže vrcholu nebo ve vrcholu rozdílném. Ke zjištění je použito metody z operačního výzkumu (teorie grafů) a to metody tzv. čínského pošťáka, která je pro obsluhu hran vhodná. Pro tuto práci byla vybrána pouze dílčí část ulic (s místním názvem Samohelka) z celkové dopravní sítě místních komunikací města, ve které byl aplikován budoucí návrh řešení. Z této části ulic a křižovatek byl vytvořen základní síťový graf. Je zjištěno, že vrcholů lichého stupně je deset. Současně je splněna podmínka, že se jedná o sudý počet (těchto vrcholů), proto je rozhodnuto o použití Edmondsova algoritmu. Je vytvořen graf z vrcholů lichého stupně a následně určeno párování minimální délky hran. Vytvořený kompletní graf z vrcholů lichého stupně je značně nepřehledný, proto byla pro přehlednost zvolena matice nejkratších vzdáleností lichých vrcholů. Základní graf byl rozšířen o fiktivní hrany minimálního párování a smyčky (představující slepé ulice). Postupně je vyšetřeno, který vrchol je nejvýhodnější pro zahájení práce čety. Jsou vyšetřeny všechny vrcholy V1 - V21. Ke zvolenému výchozímu vrcholu je připočítána i minimální délka příjezdové cesty pracovní čety na stanoviště, ze kterého bude zahajovat svou práci. Nakonec jsou varianty tvořené jednotlivými výchozími vrcholy vzájemně porovnány. Pro větší přehlednost jsou varianty uvedeny v tabulce 7. Varianta, která je ohodnocena nejmenší celkovou délkou, je variantou nejvýhodnější z hlediska nejméně ujetých kilometrů pracovní čety. Závěrem zhodnotíme stávající způsob provádění údržby města pouze ve zvoleném segmentu místních komunikací. Při stávajícím řešením (viz část 1.) četa projíždí celkem 5 419 m, to je s cestou ze základny tam a zpět celkem 7 621 m. Nově navrhovaná trasa měří pouhých 4 860 m, spolu s cestou ze základny tam a zpět 7 062 m, což je o 559 m méně než doposud využívaná trasa. V přepočtu se jedná o úsporu ve výši 11,5% oproti původnímu řešení. Stávající délka místních komunikací v řešené části podle pasportu místěních komunikací [4] je 3166,2 m, nově navrhovaná trasa je délky 4 860 m, v přepočtu 58

je navýšení délky o 53,49%. Když tuto úsporu převedeme na všechny místní komunikace, na kterých městský podnik údržbu provádí, což je 30 193 m v celém městě, délka nové trasy, po které by měla četa projíždět, bude přibližně 46 342,2 m a započtení zjištěné úspory 11,5% (ze stávající trasy), tak stávající trasu zkrátíme o 5 329,5 m. V rámci této práce bylo zjištěno, že pracovní četa provádí úklid po celých ulicích, podle názvů a ne od křižovatky ke křižovatce (od vrcholu k vrcholu). Tudíž provádí údržbu v celkové délce 5 419 m. Při uplatnění navrhovaného řešení do praxe, by četa jen v tomto úseku ušetřila 559 m na svých cestách, které jsou v současném řešení bez užitku. Toto se děje i v jiných městech nejen ve Zdicích. Vždyť často vidíme dopravní značky zákaz zastavení, které jsou dány v ulicích v souladu se zákonem o pozemních komunikacích deset dní dopředu, spolu s dodatkovou tabulkou s datumem čištění či údržby dané ulice města, bez návaznosti na ostatní křižující se komunikace. Pokud by město ze své dopravní sítě vytvořilo základní graf, který by byl rozdělen do logických podgrafů, na kterých by jednotlivé čety prováděly údržbu, došlo by ke zkrácení cest bez provádění jakékoliv činnosti. Tím zefektivnění práce těchto čet. Potom by vlastník komunikací, čištění a údržbu mohl provádět po jednotlivých podgrafech daného grafu dopravní sítě, které by na sebe vzájemně navazovaly. Nebo by byly dané práce prováděny v systému sudých a lichých podgrafů s centrálním vrcholem, který by jednotlivé podgrafy navzájem propojoval.

59

7. Použitá literatura [1] Mocková, D.: Základy teorie dopravy, úlohy, ČVUT, Praha 2007, ISBN 978-80-0103791-1 [2] Pastor, O., Tuzar, A.: Teorie dopravních systémů, ASPI, Praha, 2007, ISBN 978-807357-257-285-3 [3] Fastr, P.: Zákon o pozemních komunikacích s komentářem a vyhláškou, Linde Praha, Praha, 2004, ISBN 80-7201-495-1 [4] Město Zdice, (Melies s.r.o.): Pasport místních komunikací města Zdice, Praha, 2008 [5] Město Zdice, (Hána, W.): Územní plán města, Praha, 2002, schválení Zastupitelstvem města Zdice dne 24. 6. 2003 usnesením č. 7/2003, bod l./1 (spolu s obecně závaznou vyhláškou č. 2/2003) [6] Město Zdice, (Pacovská, A.): Zdice, plán města, Kompakt s.r.o., Poděbrady, 2004 [7] Město Zdice: Zdice kapitoly z historie a současnosti města, Gemmapress Nučice, Nučice, 2004

60

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE FAKULTA DOPRAVNÍ BAKALÁŘSKÁ PRÁCE

Recommend Documents