TAS:Situace/Řešitel (F5 nebo F6)/Zásady řešitele

• Tasha je postavena na principu zničit a obnovit a na adaptivním large Neighbourhood search.
• Princip ruin and recreate (zničit a znovu vytvořit) účinně rozbíjí části původního řešení a snaží se je znovu vytvořit. Je známo, že je účinný u složitých řešení. Při prohledávání velkého okolí algoritmus uvolňuje některá omezení, aby umožnil rozsáhlé změny oproti původnímu řešení. Výzkumy ukazují, že tyto principy řešení jsou známy lepšími výsledky, ale jsou náročnější na zpracování. O těchto přístupech existuje mnoho literatury: http://www.diku.dk/~sropke/Papers/PDPTW_techRep.pdf http://www.staff.uni-mainz.de/schneidj/papers/ruinandrecreate.pdf.
• Jedná se o algoritmus stimulovaného žíhání, což znamená, že uživatelská nastavení určují rozsah změn během optimalizace řešení (od malých změn až po změny velkého rozsahu). To lze nastavit v rámci možností řešitele.
• Klíčovým rysem algoritmu je použití náhodných čísel při řešení, což znamená, že je možné generovat různé odpovědi na stejný problém, pokud se ostatní faktory prostředí nezmění.

Metodika řešitele:

• Řešitel vytvoří počáteční řešení s údaji, které se skládají ze svozů i dodávek. Toto počáteční řešení je obvykle velmi špatné a neefektivní, ale je proveditelné.
• 1. heuristika je ruina. Tasha se podívá na řešení a náhodně odebere určité procento řešení.
• Tasha používá 4 různé typy ruin: Náhodné, Geografické odstranění, odstranění Shaw (odstraňuje "časové" shluky) a odstranění vozidel.
• Každý typ ruiny se používá v různých bodech procesu řešení. Pokud ruina nezlepšuje řešení, je nepravděpodobné, že by byla použita znovu.
• Po zničení se algoritmus začne obnovovat tak, že se podívá, kolik stojí naložení každé zastávky na nejlevnější kamion a pak na druhý nejlevnější. Nenakládá automaticky každou zastávku na nejlevnější nákladní vozidlo.
• Druhá heuristika spočívá v postupném naplnění každého nákladního vozu.
• Algoritmus opakovaně provádí proces zničení a obnovení.
• Je důležité si uvědomit, že se tím nutně nenajde lepší řešení, ale pouze se prozkoumá alternativa, aby se zjistilo, zda je levnější než původní vygenerované řešení.
• Princip simulovaného žíhání: Systém začíná při teplotě definované uživatelem. Na začátku se zkoumají nejdramatičtější změny řešení, jakmile se teplota ochladí, změny jsou již minimálnější a jsou do jisté míry předurčeny původním řešením. S ochlazováním teploty se možná zkoumají neefektivnější řešení. Nakonec se řešení ochladí a pak již nemůžeme akceptovat neefektivnější řešení.
• Ve složitých scénářích byste použili vyšší počáteční teplotu, ale u jednodušších problémů byste vysokou teplotu nepoužili, což je výpočetně neefektivní.