Obecný problém cestujícího prodejce

K nejjednodušším heuristickým metodám řešení zobecněného problému obchodního cestujícího patří chamtivý algoritmus , který v každém kroku vybírá hranu s nejnižšími náklady ze sady hran, které nenarušují správnost řešení, a také efektivnější Nearest Neighbor. metoda, která začíná z libovolného vrcholu a v každém kroku přidává k řešení vrchol nejblíže poslednímu přidaný. Existují také další heuristiky, které jsou modifikacemi známých heuristiek pro problém běžného obchodního cestujícího.

Často se používají zejména následující typy místního vyhledávání :

• 2-opt , který je široce používán v mnoha kombinatorických optimalizačních problémech, se redukuje na odstranění dvou hran z obchůzky a vložení dvou nových hran, které nenarušují správnost řešení (v případě 2-opt, hrany, které mají být vloženy jsou jednoznačně určeny). Prohlídka se považuje za lokální minimum, pokud v ní nejsou dvojice hran, jejichž nahrazení by vedlo ke zlepšení řešení. Tedy jak velikost okolí, tak složitost heuristiky jsou , kde  je počet shluků.
• 3-opt je podobný 2-opt, ale ne dva, ale tři okraje na každém. V případě 3 opt existuje osm netriviálních způsobů, jak vložit nové hrany pro obnovení správnosti obchůzky. Jeden z těchto způsobů zachovává směr každého z fragmentů prohlídky, což je důležitá vlastnost pro asymetrické problémy. Velikost okolí a složitost heuristiky jsou .
• Existují přirozené modifikace 2-opt a 3-opt algoritmů, které navíc zahrnují hledání optimálních vrcholů v rámci měnících se shluků.
• "Vložení" je speciální případ 3-op. Při každé iteraci algoritmus odstraňuje vrchol a snaží se pro něj najít výhodnější pozici. Složitost algoritmu je . Široce se používá modifikace, která uvažuje vložení nejen vzdáleného vrcholu, ale také jakéhokoli jiného vrcholu odpovídajícího clusteru.
• Optimalizace klastrů je místní vyhledávání specifické pro obecný problém cestujících obchodníků. Podstatou algoritmu je najít nejkratší cestu danou sekvencí shluků. Jinými slovy, okolí algoritmu zahrnuje všechny cesty, které se od originálu neliší o více než výběr vrcholů v každém ze shluků. Velikost zkoumané čtvrti je:

kde  je shluk očíslován . Použitím hledání nejkratší cesty ve speciálně vytvořeném grafu algoritmus najde lokální minimum pro , kde . Cluster Optimization tedy patří do třídy lokálních vyhledávání s velmi velkým sousedstvím , to znamená, že zkoumá exponenciální okolí v polynomiálním čase.