Okružní dopravní problém

OKRUŽNÍ DOPRAVNÍ PROBLÉM

Firma xxxxxx

 

2003

Po – 17:30

 

Pražská firma xxxxxxxx se zabývá výrobou kojeneckého oblečení. Toto zboží pak dále rozváží do svých pěti obchodů na území České republiky.

Jsou to města: Kladno, Brno, Poděbrady, Tábor, Liberec.

V Praze má firma velkosklad přímo v místě svého působení, nakupují zde pouze velkoobchodníci, kteří si pro zboží dojíždí, rozvoz je tak v Praze zajištěn odběrateli – velkoobchodníky.

Firma má k dispozici dva zaměstnance, kteří mají rozvoz zboží na starost. Oba vyjíždí z Prahy a každý objede 2 a 3 obchody a pak se vrací zpět do Prahy.

Naším úkolem je nalézt pro oba zaměstnance co nejvýhodnější (nejkratší) cestu mezi obchody.

 

1) Matice vzdáleností v km

	Praha	Kladno	Brno	Poděbrady	Tábor	Liberec
Praha		31	202	54	83	102
Kladno	31		233	85	114	133
Brno	202	233		181	168	239
Poděbrady	54	85	181		137	87
Tábor	83	114	168	137		185
Liberec	102	133	239	87	185

 

 

2) Rozdělíme si města do jednotlivých tras pomocí Mayerovy metody

 

1. trasa

Praha – Tábor – Kladno

 

2. trasa

Praha – Poděbrady – Liberec – Brno

 

3) Musím najít optimální kruh metodou nejbližšího souseda

 

1. Zaměstnanec (Praha – Tábor – Kladno)

 

	Praha	Tábor	Kladno
Praha		83	31
Tábor	83		114
Kladno	31	114

 

Praha – Kladno – Tábor – Praha = 31 + 114 + 83 = 228

Tábor – Praha – Kladno – Tábor = 83 + 31 + 114 = 228

Kladno – Praha – Tábor – Kladno = 31 + 83 + 114 = 228

 

Praha – Kladno – Tábor – Praha (228 km)

 

2. zaměstnanec (Praha – Poděbrady – Liberec – Brno)

 

	Praha	Poděbrady	Liberec	Brno
Praha		54	102	202
Poděbrady	54		87	181
Liberec	102	87		239
Brno	202	181	239

 

Praha – Poděbrady – Liberec – Brno – Praha = 54 + 87 + 239 + 22 = 582

Poděbrady – Praha – Liberec – Brno – Poděbrady = 54 + 102 + 239 + 181 = 576

Liberec – Poděbrady – Praha – Brno – Liberec = 87 + 54 + 202 + 239 = 582

Brno – Poděbrady – Praha – Liberec – Brno = 181 + 54 + 102 + 239 = 576

 

Praha – Liberec – Brno – Poděbrady – Praha (576 km)

 

Obě vozidla najedou celkem 804 km.

 

4) Vyřešení okruhu 2. zaměstnance Vogelovou aproximační metodou

 

	Praha	Poděbrady	Liberec	Brno
Praha		54	102	202	48
Poděbrady	54		87	181	33	33
Liberec	102	87		239	15	137	137
Brno	202	181	239		21	37	202
	48	33	15	21
	48		152	58
	100			239

  

1. Nejdříve vypočítáme sloupcové a řádkové diference, ze kterých vybereme nejvyšší číslo. V daném sloupci potom zvolíme nejnižší sazbu. Z Prahy vozidlo pojede do Poděbrad.
2. Přepočítáme diference a postup se opakuje. Z Poděbrad pojede vozidlo do Liberce.
3. Další vozidlo pojede z Liberce do Brna a zpět z Brna do Prahy.

 

Praha – Poděbrady – Liberec – Brno – Praha = 54 + 87 + 239 + 202 = 582