UMĚLÁ INTELIGENCE V AUTOMOTIVE / David et al.

kde d ij je vzdálenost mezi bodem i a bodem j , rozhodovací proměnná x ij = 1 je trasou vykonanou obchodním cestujícím (včetně trasy mezi body i a j ), x ij = 0 je trasou, která není obchodním cestujícím provedena. |S| znamená počet prvků obsažených v sadě S . (5.1) Funkce (5.1) slouží k určení nejmenší vzdálenosti, vztahy (5.2) a (5.3) specifikují podmínky návštěvy a opuštění bodů (měst) obchodním cestujícím. Z těchto vztahů vy plývá, že každý bod (město) bude obchodním cestujícím navštíveno a opuštěno pouze jed nou, což vytváří potenciál pro vznik okruhu. Vztah (5.4) dále zakazuje vytváření smyček v rámci skupin bodů (měst), což přispívá k matematické optimalizaci trasy obchodního cestujícího. Tato restrikce zajišťuje, že každý bod (město) bude navštíveno pouze jednou a že žádná trasa nebude obsahovat opakující se průchody body (městy). [5.17] Metody řešení pro problém obchodního cestujícího (TSP) rozdělujeme do dvou hlavních variant: exaktní a heuristické metody. Exaktní metody dále rozdělujeme na přesné algoritmy nebo přibližné algoritmy. Exaktní metody se zaměřují na nalezení optimálního řešení TSP prostřednictvím matematického modelování a algoritmů, jako je například metoda větví a mezí. Na dru hé straně heuristické metody, jako je například genetické algoritmy nebo simulované ží hání, se snaží nalézt přijatelné řešení TSP v přijatelném čase prostřednictvím efektivních algoritmů a optimalizace parametrů. Přesný algoritmus pro řešení TSP – lineární programování Strategie řešení TSP pomocí lineárního programování představuje jednu z pů vodních metod, která byla vyvinuta pro řešení tohoto problému. Tato strategie, zejména při využití přístupu řezné roviny v celočíselném programování, využívá LP (lineární programování) k vytvoření modelu s pomocí dvou omezení. Následně je hledána řezná rovina prostřednictvím přidání dalšího, odlišného omezení, s cílem postupně se přiblížit k optimálnímu řešení. Tato technika pro identifikaci řezné plochy je často závislá na praxi toho, kdo ji aplikuje. Tato strategie není obecně považována za univerzální. [5.17] Dynamické programování Dynamické programování je efektivní algoritmická technika pro řešení problémů optimalizace, která využívá principu rozděl a panuj (divide and conquer). V kontextu dynamického programování je množina S definována jako podmnožina množiny {2, 3, ..., n }, přičemž k ∈ S a C(S,k) a reprezentuje optimální trasu cesty od bodu 1 přes body definované v S a končící v bodě k . Pro případ, kdy | S | = 1, platí C{{k}, k} = d 1k , kde d 1k značí vzdálenost mezi body 1 a k , a to pro každé k . Pokud je velikost množiny |S| > 1 , podle principu optimality lze rovnici dynamického programování pro obchodního cestujícího zapsat jako C(S,k) = min [C(S – {j,k},j) + d jk ] , kde C(S,k) představuje délku nejkratší cesty pro množinu bodů (měst) S , která končí v bodě (městě) k , d jk je vzdálenost mezi body (městy) j a k a S – {j,k} značí množinu S bez bodů (měst) j a k . Řešení tohoto problému lze získat iterační metodou založenou na dynamickém programování, která poskytuje systematický přístup k řešení problé-

67