Problém obchodního cestujícího (TSP)
Problém obchodního cestujícího (TSP) je klasický optimalizační problém s praktickým využitím v logistice. Obchodní cestující dostane seznam měst a vzdálenosti mezi každou dvojicí. Jeho cílem je najít nejkratší trasu, která začíná ve výchozím městě, projde všemi ostatními městy a vrátí se zpět. Jde o výpočetně náročný problém, ale Miller-Tucker-Zemlin (MTZ) ukázali, že ho lze řešit pomocí celočíselného lineárního programování. V tomto cvičení definuješ účelovou funkci a část omezení pro TSP na malém datasetu s 15 městy (viz obrázek níže). Procvičíš si použití LpVariable.dicts spolu s generátorovou notací (list comprehension).
Tři proměnné n, cities a dist jsou už připravené \(^{1}\). Proměnná n udává počet měst, cities je seznam měst označených čísly a dist je pandas DataFrame se vzdálenostmi mezi každou dvojicí měst. Můžeš si je prozkoumat v konzoli. Model je také již inicializován.
\(^{1}\) Dataset pochází z: Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,
Toto cvičení je součástí kurzu
Supply Chain Analytics v Pythonu
Interaktivní cvičení na vyzkoušení si v praxi
Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.
# Define Decision Variables
x = LpVariable.dicts('X', [(____, ____) for c1 in ____ for c2 in ____],
cat='____')
u = LpVariable.dicts('U', [____ for c1 in ____],
lowBound=0, upBound=(n-1), cat=____)