1. Learn
    2. /
  2. Cursuri
    3. /
  3. Analitică în lanțul de aprovizionare cu Python
Connected

exercițiu

Problema comis-voiajorului (TSP)

Problema comis-voiajorului (TSP) este o problemă celebră cu aplicații în logistică. În TSP, unui comis-voiajor i se oferă o listă de orașe și distanța dintre fiecare pereche. El caută cel mai scurt traseu care pleacă din orașul de origine, trece prin toate punctele și se întoarce la punctul de plecare. Aceasta este o problemă dificil de rezolvat din punct de vedere computațional, însă Miller-Tucker-Zemlin (MTZ) au demonstrat că poate fi soluționată prin Programare Liniară în Numere Întregi. În acest exercițiu vei defini funcția obiectiv și câteva constrângeri pentru TSP pe un set mic de date cu 15 orașe (vezi imaginea de mai jos). Scopul tău este să exersezi utilizarea LpVariable.dicts împreună cu list comprehension.

Photo of Cities

Trei variabile Python — n, cities și dist — au fost create pentru tine \(^{1}\). Variabila n reprezintă numărul de orașe, cities este o listă a orașelor numerotate, iar dist este un DataFrame pandas cu distanțele pereche dintre fiecare oraș. Le poți explora în consolă. De asemenea, modelul a fost inițializat pentru tine.

\(^{1}\) Setul de date provine din Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Instrucțiuni 1/3

undefined XP
    1
    2
    3
  • Folosește LpVariable.dicts pentru a crea un dicționar x care conține variabile binare pentru fiecare pereche de orașe, și un dicționar u care conține câte un LpVariable de tip întreg pentru fiecare oraș.