Vypracoval: Jiří Meixner

Úloha 5:

Problém obchodního cestujícího

Zadání:

Problém obchodního cestujícího je specifikován následovně. Musí se navštívit každé z N měst a to právě jednou nebo modifikované řešení, alespoň jednou. Na konci své cesty se musí vrátit zpět do počátečního města. Úkolem je najít minimální cestu, nebo-li pořadí jednotlivých měst tak, aby projitá vzdálenost byla minimální.

Zadání instancí problému je dáno distanční maticí, neboli tabulkou udávající vzdálenosti mezi danými dvěma městy.

Problém obchodního cestujícího patří mezi jedny z nejvíce studovaných problémů v kombinatorické optimalizaci. Problém jako takový je jednoduše formulovatelný, ale těžko řešitelný.

 

Rozbor řešení:

Problém obchodního cestujícího patří do množiny NP-úplných problémů. To je třída problémů, pro něž se zatím nepovedlo najít polynomiální algoritmus a jejichž časová složitost je pravděpodobně exponenciální. Pokud by však byl nalezen polynomiální algoritmus pro jeden z NP-úplných problémů je jisté že existují polynomiální algoritmy i pro všechny ostatní. Obecně se však věří, že pro tuto třídu žádný polynomiální algoritmus neexistuje.

Není však vyloučeno, že existuje algoritmus, jehož průměrná doba výpočtu je polynomiální. Problém obchodního cestujícího však můžeme vyřešit za pomocí heuristických algoritmů, které nedávají vždy optimální řešení, ale snaží se k němu přiblížit, což se jim daří s chybou až v řádu jednotek procent.

Pro řešení TSP lze například použít algoritmus založený jen na přidávání nejbližšího souseda k danému městu což je konstruktivní řešení. Tento algoritmu je však velmi jednoduchý a proto nedosahuje nejlepších výsledků. Vzdálenosti na počátku cesty budou krátké, ale se zmenšujícím se počtem měst se budou velmi prodlužovat. Tento algoritmus je však vhodný pro použití k nalezení počáteční cesty a následné optimalizace.

K optimalizaci či-li zlepšování cesty můžeme například použít algoritmus zvaný 2-opt pak se jedná o iterativní řešení. Algoritmus je založen na nahrazování dvou hran grafu (města jsou uzly a silnice jsou hrany) v cestě jinými dvěmi hranami tak, aby se celková délka cesty zlepšila. Pokud již žádnou záměnou nelze řešení zlepšit je cesta 2-optimální. Podobně lze použít i algoritmu 3-opt, obecně pak n-opt. Platí ovšem, že řešení za použití 3-opt je mnohem lepší než 2-opt, ale 4-opt se již vzhledem k poměru své složitosti ku zlepšení oproti 3-opt nevyplatí implementovat. Úplným zobecněním tohoto principu vznikl Linův-Kernighanův algoritmus zvaný  k-opt, kde k se v průběhu výpočtu mění. Jedná se o vysoce efektivní algoritmus. Mezi další algoritmy pak patří například tabu prohledávání, simulované ochlazování a jeho modifikace, genetické algoritmy a elastické neuronové sítě (pouze pro euklidovské TSP). Mnoho z těchto algoritmů má analogii v přírodě, jelikož z přírody jsou známy podobné problémy.

 

Popis použitých algoritmů:

Řešení lze nalézt dle následujících kroků:

  1. Nalezení počáteční cesty (nějaká cesta)
    1. Výběr počátečního města
    2. Prodlužování cesty dokud v ní nejsou všechny města
    3. Modifikace cesty tak, aby se poslední město dalo spojit s prvním
  2. Optimalizace počáteční cesty (hledání minimální cesty)

 

Algoritmus pro nalezení počáteční cesty je de facto algoritmus pro nalezení Hamiltonovy kružnice. Implementovaný algoritmus funguje dle následujících bodů:

  1. Vyberte počáteční město s nejvíce silnicemi, aby se zvýšila pravděpodobnost spojení posledního města s počátečním.
  2. Prodlužujte cestu o další město, neexistující v cestě, dokud to jde. Vyzkoušel jsem následující prodlužování (existují i další):
    1. O první město spojené s posledním.
    2. O město s minimálním počtem silnic spojené s posledním.
    3. O město s maximálním počtem silnic spojené s posledním.
    4. O město s nejkratší silnicí s posledním městem.
  3. Pokud jsou v cestě obsažena všechna města a poslední město lze spojit s počátečním, tak je nalezena Hamiltonova kružnice. Konec algoritmu.
  4. Modifikujte cestu:
    1. Najděte nezakázanou silnici z města M v cestě vedoucí do posledního města P.
    2. Silnici z města M do následujícího města N v cestě přidejte do zakázaných silnic.
    3. Otočte pořadí měst (orientaci silnic) v cestě od města N do konce, nebo-li N se stane posledním městem a P se stane následníkem M.
  5. Pokud došlo k modifikaci cesty, tak jděte zpět na bod 2.
  6. Vložte do cesty město neexistující v cestě, nebo-li hledejte město neexistující v cestě, které má silnici s městem v cestě i s jeho následovníkem. Takto zkoušejte všechna města neexistující v cestě.
  7. Pokud jsou v cestě obsažena všechna města a poslední město nelze spojit s počátečním:
    1. Vkládejte poslední město do cesty dokud to jde nebo dokud ho nelze spojit s počátečním.
    2. Pokud lze spojit poslední město s počátečním, tak je nalezena Hamiltonova kružnice. Konec algoritmu.
    3. Vložte první město do cesty.
    4. Pokud lze spojit poslední město s počátečním, tak je nalezena Hamiltonova kružnice. Konec algoritmu.
    5. Pokud došlo k modifikaci cesty v bodě 7c, tak jděte zpět na bod 7.
  8. Pokud došlo k modifikaci cesty v bodě 6, tak jděte zpět na bod 6.
  9. Vytvořte pěšinku:
    1. Na městech, neexistujících v cestě, nalezněte cestu2 dle tohoto algoritmu (nemusí dojít ke spojen posledního města s prvním).
    2. Pokud je cesta2 neprázdná, tak ji spojte s cestou fiktivní silnicí, kterou nazvěte pěšinka a ohodnoťte ji nekonečnem (velké číslo).
    3. Pokud je cesta2 prázdná, tak spojte pěšinkou poslední město v cestě s počátečním a tím je nalezena Hamiltonova kružnice. Konec algoritmu.
    4. Opakujte bod 9.

 

Pro optimalizaci počáteční cesty jsem zvolil simulované ochlazování:

  1. Najdi dva páry silnic k prohození mezi sebou a zvyš čítač.
    1. První město první silnice je následující město prvního z minulého volání
    2. První město druhé silnice je voleno náhodně
  2. Pokud by se po prohození párů cesta zlepšila tak je prohoď.
  3. Pokud by se po prohození párů cesta zhoršila, ale zhoršení je v rámci okolí tak je také prohoď.(je splněna podmínka rand<exp(zlepseni/t) , kde zlepšení má vždy zápornou hodnotu.)
  4. Pokud se čítač nedočítal na nastavenou horní mez, tak jdi zpět na bod 1.
  5. Zmenši okolí dle funkce chladnutí. (okolí násobeno koeficientem chladnutí z (0-1) )
  6. Pokud je okolí větší než minimální nastavené okolí, tak jdi zpět na bod 1.

 

Naměřené hodnoty:

Statistika měřených souboru:

Soubor

Testík

A

B

C

D

E

F

G

H

I

J

K

Průměr

Počet měst

81

2187

625

2187

200

256

2187

1296

236

2187

2048

1296

1232,17

Počet silnic

5682

32790

24408

10492

6664

8448

14426

4304

4114

6558

40550

7338

13814,5

O celkové délce

89092

358128

351414

90184

107642

137422

137716

32488

62376

42648

517052

84468

167553

Délka průměrné silnice

15,67969

10,9219

14,3975

8,5955

16,1528

16,2668

9,54638

7,54833

15,1619

6,5032

12,751

11,511

12,0863

Počet silnic průměrneho města

70,14815

14,9931

39,0528

4,79744

33,32

33

6,59625

3,32099

17,4322

2,99863

19,7998

5,66204

20,9268

Délka silnic průměrneho města

1099,901

163,753

562,262

41,2364

538,21

536,805

62,9703

25,0679

264,305

19,5007

252,467

65,1759

302,638

 

Kvalita řešení ze simulovaného ochlazování je velmi závislá na vhodně zvolených parametrech a také na počátečním řešení, které optimalizuje. Existují zde následující parametry:

 

Následující grafy znázorňují výsledky řešení pro soubory D a Testík při změně vždy jednoho z parametrů.

Dle těchto grafů jsem zvolil několik vhodných sad parametrů pro výpočet zadaných souborů. Pro velké soubory jsem při volbě parametrů ještě přihlížel na celkovou časovou náročnost výpočtu. Výsledky ukazuje následující tabulka.

Cesta po ochlazování RAND=0,36

Testík

A

B

C

D

E

F

G

H

I

J

K

Délka T0=26 CH=0,99 ABS0=0,1 ITER=1000

140

 

1834

 

539

576

 

 

811

 

 

 

Délka T0=4,5 CH=0,95 ABS0=0,9 ITER=220

194

19519

2156

14819

617

463

15430

5143

1532

 

21397

5968

Délka T0=5 CH=0,99 ABS0=0,01 ITER=1000

139

 

1807

 

570

405

 

 

1345

 

 

 

Délka T0=11,5 CH=0,99 ABS0=0,01 ITER=1000

129

 

1822

 

592

543

 

 

933

 

 

 

Počet pěšin po ochlazování

0

0

0

63

0

0

42

135

2

 

0

96

Délka počáteční cesty

185

19824

3657

14806

814

566

15421

5107

4060

13252

21535

5913

Počet pěšin počáteční cesty

0

0

0

65

0

0

43

144

2

119

0

103

Čas pro celkový výpočet

3,19s

48,18min

10,16min

14,20h

39,77s

75,14

7,71h

135,7min

225,91s

>>60h

8,6min

83,23min

 

Silně jsou vyznačeny nalezené minimální cesty. Čas výpočtu je pro ne kurzívou psané výsledky.

Průběh ochlazování pro soubory D, E a Testík při parametrech T0=5 resp. 26 Ch=0,99 ABS0=0,1 resp. 0,01 MAXITER=1000 a RAND=0,36 ukazuje následující graf.

 

Závěr:

Jak již bylo řečeno simulované ochlazování je velice náchylné na vhodnou volbu parametrů a taktéž na počáteční řešení. Počáteční řešení jsem měnil dle strategie prodlužování (viz. bod 2 v algoritmu Hamiltonovské kružnice). Při volbě města s minimem nebo maximem silnic se vytvořilo vždy několik pěšin, které se však při ochlazování odstranily. Nejlepších výsledků jsem však dosáhl při strategii „nejbližší město“ a pro ni jsou také veškeré zde uváděné výsledky.

            Výsledky jsou taktéž závislé na funkci pro hledání párů hran k prohození. Opět jsem vyzkoušel několik strategií v závislosti na volbě prvních měst první a druhé silnice. Buďto jsem je volil náhodně nebo jako následníky resp. předchůdce prvního města první silnice resp. druhé silnice z minulého volání této funkce. Nejlepších výsledků jsem docílil při volbě prvního města první silnice jakožto následníka a náhodně zvoleného prvního města druhé silnice.

            Parametry ochlazování jsem zvolil dle grafů se změnami parametrů. I přesto je však nelze považovat za nejlepší, jelikož jsou mezi jednotlivými parametry ovlivňující vazby a já jsem vždy měnil pouze jeden z parametrů a ostatní zůstávali konstantní. Také platí, že nejvhodnější nalezené parametry jsou pouze pro daný soubor a pro jiný již neplatí. Z tohoto důvodu jsem si udělal statistiku daných souborů (viz. tabulka výše). Za velice překvapující považuji, že výsledek souboru E, který je dle statistiky velmi podobný souboru D, jsou  při použití „optimálních“ parametrů pro D tak špatný. Zřejmě u těchto souborů zprůměrování vytvořilo mylnou představu o podobnosti souborů. Na konec bych se chtěl ještě pozastavit u parametru RAND, jehož optimum vyšlo 0,36. exp(-1) je přibližně roven 0,36 což tedy znamená, že algoritmus ochlazování prohazuje hrany vždy, když dochází ke zlepšení a v případě zhoršení prohodí hrany pouze pokud je zhoršení menší než aktuální okolí reprezentované teplotou. Nebo-li čím menší je teplota tím méně může docházet ke zhoršování cesty.

 

Soubory ke stažení:

tsp.cpp – zdrojový soubor C++ programu vytvořený v Builderu 5

tsp.exe – spustitelný program,

bez parametrů, pak se dosadí T0=5, Ch=0.99, ABS0=0.01, MAXITER=1000, RAND=0.36

s parametry oddělenými mezerou v pořadí T0 Ch ABS0 MAXITER RAND

výstupy – adresář s výstupy jednotlivých souborů