Vehicle routing problem

Deadline - 30. května 2024

Vaším úkolem bude vyřešit takzvaný Vehicle Routing Problem (VRP) pomocí algoritmu Ant Colony Optimization. VRP je ve své podstatě jen jakýmsi zobecněním problému obchodního cestujícího, kde cílem je optimalizovat dodání zásilek pro nějakou poštovní společnost. Máme dány sklady, každý s vlastními příslušnými vozidly s danou kapacitou, která začínají a nutně i končí cestu v daném skladě, a množinu zásilek, které musejí být doručeny jejich adresátům. Úkol je pak najít takovou množinu doručovacích tras, že všechny zásilky jsou doručeny svým adresátům, a že celková cena těchto tras je co nejmenší - tedy že je využito co nejméně rozvážkových vozidel a cesty jsou co nejkratší. Nejčastěji minimalizujeme jen délku cest, počet aut se navíc většinou (hlavně v našem zjednodušení s jedním skladem a stejnými vozidly) zmenšuje sám, zatímco zkracujeme cesty, a to kvůli trojúhelníkové nerovnosti pro korektní metriky.

V rámci tohoto úkolu budeme uvažovat zjednodušenou verzi tohoto problému, kde máme pouze jeden centrální sklad a neomezeně identických vozidel. Optimalizovat budete tři instance tohoto problému, které dostanete jako soubory v XML formátu - dvě malé instance a jednu větší. Každý vstupní soubor obsahuje následující:

• Seznam uzlů s příslušnými koordináty x a y určujícími jejich pozici ve světě. Uzel typu 0 je sklad, ostatní uzly s typem 1 jsou lokace zákazníků.
• Seznam vozidel (v našem případě jediný typ vozidla), spolu s jejich příslušností k danému skladu a kapacitou, kterou jsou schopny uvézt najednou.
• Seznam požadavků zákazníků, respektive zásilek, které je nutno doručit do jejich místa určení.

Své řešení mi pošlete na mail. Měli byste uvést následující:

• Popis toho, jak jste adaptovali zdrojové kódy ze cvičení na vyřešení tohoto problému
• Kód algoritmu pro případnou kontrolu
• Grafy konvergence algoritmu pro všechny tři vstupy
• Nejlepší nalezená řešení pro všechny instance