1. Učit se
    2. /
  2. Kurzy
    3. /
  3. Supply Chain Analytics v Pythonu
Connected

Cvičení

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).

Photo of Cities

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,

Pokyny 1/3

undefined XP
    1
    2
    3
  • Pomocí LpVariable.dicts vytvoř slovník x s binárními proměnnými pro každou dvojici měst a slovník u s celočíselnou LpVariable pro každé město.