Okružní dopravní problém

transcript

Okružní dopravní problémOkružní dopravní problém

Literatura:Literatura:

Šubrt a kol.: Ekonomicko matematické metody Šubrt a kol.: Ekonomicko matematické metody II, Aplikace a cvičeníII, Aplikace a cvičení

Okružní problémOkružní problém

Nalezení nejkratší Nalezení nejkratší cestycesty, která , která obsahuje všechny vrcholyobsahuje všechny vrcholy

Víceokruhový problémVíceokruhový problém

Nalezení několika kružnicNalezení několika kružnic– obsahují centrální vrcholobsahují centrální vrchol– dohromady obsahují všechny ostatní vrcholy dohromady obsahují všechny ostatní vrcholy – jednotlivé okruhy splňují dodatečné jednotlivé okruhy splňují dodatečné

podmínkypodmínky

Jednookruhový okružní problémJednookruhový okružní problém

Je dáno Je dáno nn míst míst Je třeba všechna místa projet a vrátit Je třeba všechna místa projet a vrátit

se do výchozíhose do výchozího Postup pro nalezení matematického Postup pro nalezení matematického

optima neexistujeoptima neexistuje Počet možností roste exponenciálně Počet možností roste exponenciálně

s rostoucím s rostoucím nn NP úplná úlohaNP úplná úloha

PříkladPříklad

Turista vyjíždí z Catanzara a chce Turista vyjíždí z Catanzara a chce postupně navštívit všechna města v postupně navštívit všechna města v tabulce a vrátit se zpátky. tabulce a vrátit se zpátky.

Naplánujte trasu tak, aby ujel co Naplánujte trasu tak, aby ujel co nejméně kilometrů.nejméně kilometrů.

Vzájemné vzdálenosti jsou v tabulceVzájemné vzdálenosti jsou v tabulce

CatanzaroCatanzaro CosenzaCosenza CrotoneCrotone ReggioReggio ScaleaScalea TropeaTropea

CatanzaroCatanzaro -- 9797 7676 158158 152152 9494

CosenzaCosenza 9797 -- 116116 187187 9595 124124

CrotoneCrotone 7676 116116 -- 221221 202202 157157

ReggioReggio 158158 187187 221221 -- 242242 104104

ScaleaScalea 152152 9595 202202 242242 -- 178178

TropeaTropea 9494 124124 157157 104104 178178 --

Tabulka dopravních vzdálenostíTabulka dopravních vzdáleností

Řešení jednookruhového problémuŘešení jednookruhového problému Princip: přidávání hran grafu tak, aby Princip: přidávání hran grafu tak, aby

nevytvořili kružnici dříve, než budou nevytvořili kružnici dříve, než budou zařazeny všechny vrcholyzařazeny všechny vrcholy

Volba hran podle ohodnocení - Volba hran podle ohodnocení - momentální výhoda ale může být v momentální výhoda ale může být v budoucnu nevýhodoubudoucnu nevýhodou

Metoda nejbližšího sousedaMetoda nejbližšího souseda Vogelova aproximační metodaVogelova aproximační metoda

Vogelova aproximační metodaVogelova aproximační metoda

Výpočet Vogelových diferencíVýpočet Vogelových diferencí Volba nejkratší trasy v řadě s největší Volba nejkratší trasy v řadě s největší

diferencídiferencí Vyřazení trasy předčasně uzavírající Vyřazení trasy předčasně uzavírající

okruhokruh Opakujeme, dokud nejsou všechna Opakujeme, dokud nejsou všechna

místa zařazena do okruhumísta zařazena do okruhu

CatanzarCatanzaroo

CosenzCosenzaa

CrotonCrotonee

ReggiReggioo

ScaleScaleaa

TropeTropeaa

Řádkové Řádkové diferencediference

CatanzaroCatanzaro -- 9797 7676 158158 152152 9494 1818

CosenzaCosenza 9797 -- 116116 187187 9595 124124 22CrotoneCrotone

7676 116116 -- 221221 202202 157157 4040ReggioReggio

158158 187187 221221 -- 242242 104104 5454

ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 1010Sloupcové Sloupcové diferencediference 1818 22 4040 5454 5757 1010

Vogelova metodaVogelova metoda Výpočet diferencí Výpočet diferencí

po řádcích dvě nejvýhodnější sazby, podobně po sloupcíchpo řádcích dvě nejvýhodnější sazby, podobně po sloupcích

CatanzarCatanzaroo

CosenzCosenzaa

CrotoneCrotone ReggiReggioo

ScaleaScalea TropeaTropea

CatanzarCatanzaroo -- 9797 7676 158158 152152 9494 1818

CosenzaCosenza 9797 -- 116116 187187 9595 124124 22

CrotoneCrotone 7676 116116 -- 221221 202202 157157 4040ReggioReggio 158158 187187 221221 -- 242242 104104 5454ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 1010

1818 22 4040 5454 5757 1010

Nejmenší sazba v řadě s max diferencí - vybereme do okruhu

Škrtáme řádek a sloupec u vybrané trasy a trasu, která předčasně uzavírá okruh

Vogelova metoda Vogelova metoda

Cosenza

Scalea

Vogelova metodaVogelova metoda

Vyřazení trasy, která před časně uzavírá okruh u izolovaných tras pouze cesta zpátky

CatanzaroCatanzaro CosenzCosenzaa

CrotoneCrotone ReggioReggio ScaleaScalea TropeaTropea

CatanzarCatanzaroo -- 9797 7676 158158 152152 9494 18,1818,18

CosenzaCosenza 9797 -- 116116 187187 9595 124124 2,192,19

CrotoneCrotone 7676 116116 -- 221221 202202 157157 40,8140,81

ReggioReggio 158158 187187 221221 -- 242242 104104 54,5454,54

ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 10,5310,53

18,1818,18 22 40,4040,40 54,5454,54 57,2657,26 10,1010,10

Vogelova metodaVogelova metoda Přepočet diferencí a volba další trasyPřepočet diferencí a volba další trasy

Cosenza

Scalea

Vyřazení trasy, která před časně uzavírá okruh u izolovaných tras cesta zpátky

Crotone Catanzaro76

CatanzarCatanzaroo

CosenzCosenzaa

CatanzaroCatanzaro -- 9797 7676 158158 152152 9494 18,1818,18

CosenzaCosenza 9797 -- 116116 187187 9595 124124 2,192,19

CrotoneCrotone 7676 116116 -- 221221 202202 157157 40,8140,81

ReggioReggio 158158 187187 221221 -- 242242 104104 54,5454,54

ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 10,1010,10

18,1818,18 22 40,4040,40 54,5454,54 57,2657,26 10,1010,10

Vyloučení tras, které se nebudou zařazovatVyloučení tras, které se nebudou zařazovat

CatanzarCatanzaroo

CosenzCosenzaa

CatanzarCatanzaroo -- 9797 7676 158158 152152 9494 18,18,5818,18,58

CosenzaCosenza 9797 -- 116116 187187 9595 124124 2,19,82,19,8

CrotoneCrotone 7676 116116 -- 221221 202202 157157 40,8140,81

ReggioReggio 158158 187187 221221 -- 242242 104104 54,54,11754,54,117

ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 10,10,5310,10,53

18,1818,18 2240,40,40,40,

10510554,54,54,54,

545457,26,2657,26,26 10,10,1010,10,10

Přepočet diferencí a volba další trasyPřepočet diferencí a volba další trasy

Vyřazení trasy, která před časně uzavírá okruh u izolovaných tras cesta zpátky

Cosenza

Scalea

Crotone Catanzaro76

Tropea

Reggio

CatanzaroCatanzaro CosenzCosenzaa

CatanzarCatanzaroo -- 9797 7676 158158 152152 9494 18,18,5818,18,58

CosenzaCosenza 9797 -- 116116 187187 9595 124124 2,19,82,19,8

CrotoneCrotone 7676 116116 -- 221221 202202 157157 40,8140,81

ReggioReggio 158158 187187 221221 -- 242242 104104 54,54,11754,54,117

ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 10,10,5310,10,53

18,1818,18 2240,40140,4010505

54,54,54,54,

545457,26 57,26

262610,10,10,10,

Vyloučení tras, které se nebudou zařazovatVyloučení tras, které se nebudou zařazovat

CatanzarCatanzaroo

CosenzCosenzaa

CatanzarCatanzaroo -- 9797 7676 158158 152152 9494 18,18,58,618,18,58,6

CosenzaCosenza 9797 -- 116116 187187 9595 124124 2,19,8,712,19,8,71

CrotoneCrotone 7676 116116 -- 221221 202202 157157 40,8140,81

ReggioReggio 158158 187187 221221 -- 242242 104104 54,54,11754,54,117

ScaleaScalea 152152 9595 202202 242242 -- 178178 5757

TropeaTropea 9494 124124 157157 104104 178178 -- 10,10,53,2110,10,53,21

18,1818,18 2240,40,40,40,

105,41105,4154,5454,54

54,2954,2957,26 57,26

26,2626,2610,1010,101010

Vogelova metodaVogelova metoda Přepočet diferencí a volba další trasyPřepočet diferencí a volba další trasy

Vyřazení trasy, která před časně uzavírá okruh

Cosenza

Scalea

Crotone Catanzaro76

Reggio Tropea104

CatanzarCatanzaroo

CosenzCosenzaa

CatanzaroCatanzaro -- 9797 7676 158158 152152 9494

CosenzaCosenza 9797 -- 116116 187187 9595 124124

CrotoneCrotone 7676 116116 -- 221221 202202 157157

ReggioReggio 158158 187187 221221 -- 242242 104104

ScaleaScalea 152152 9595 202202 242242 -- 178178

TropeaTropea 9494 124124 157157 104104 178178 --

Zbývají poslední dvě trasy – ukončení okruhuZbývají poslední dvě trasy – ukončení okruhu

Doplnění posledních tras a uzavření okruhu

Cosenza

Scalea

Crotone Catanzaro76

Reggio

Tropea

116 158

Doporučená trasaDoporučená trasa

Catanzano – 158-Reggio-104-Tropea-Catanzano – 158-Reggio-104-Tropea-178-Scalea-95-Cosenza-116-Crotone-178-Scalea-95-Cosenza-116-Crotone-7676

Celkem délka - 727 kmCelkem délka - 727 km

Metoda nejbližšího souseda IMetoda nejbližšího souseda I CatanzanoCatanzano-76-Crotone-116-Cosenza-95--76-Crotone-116-Cosenza-95-

Scalea-178-Tropea-104-Reggio-158-zpětScalea-178-Tropea-104-Reggio-158-zpět– Celkem:Celkem:727727 km km

CosenzaCosenza-95-Scalea-152-Catanzaro-76--95-Scalea-152-Catanzaro-76-Crotone-157-Tropea-104-Reggio-187-zpětCrotone-157-Tropea-104-Reggio-187-zpět– Celkem:Celkem:771771 km km

CrotoneCrotone-76-Catanzaro-94-Tropea-104-Reggio--76-Catanzaro-94-Tropea-104-Reggio-187-Cosenza-95-Scalea-202-zpět187-Cosenza-95-Scalea-202-zpět– Celkem:Celkem:758758 km km

ReggioReggio-104-Tropea-94-Catanzaro-76-Crotone--104-Tropea-94-Catanzaro-76-Crotone-116-Cosenza-95-Scalea-242 -zpět116-Cosenza-95-Scalea-242 -zpět– Celkem:Celkem:727727

Scalea-Scalea-95-Cosenza-97-Catanzaro-76-Crotone-95-Cosenza-97-Catanzaro-76-Crotone-157-Tropea-104-Reggio-242 -zpět157-Tropea-104-Reggio-242 -zpět– Celkem:Celkem:771771

TropeaTropea-94-Catanzaro-76-Crotone-116-Cosenza--94-Catanzaro-76-Crotone-116-Cosenza-95-Scalea-242 - Reggio-104 -zpět95-Scalea-242 - Reggio-104 -zpět– Celkem:Celkem:727727

Řešení jako v předchozím případěŘešení jako v předchozím případě

Metoda nejbližšího souseda IIMetoda nejbližšího souseda II

Okružní dopravní problém

Documents