ÎncepețiÎncepe gratuit

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,

Acest exercițiu face parte din cursul

Analitică în lanțul de aprovizionare cu Python

Vezi cursul

Exercițiu interactiv practic

Încearcă acest exercițiu completând acest cod de exemplu.

# 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=____)
Editează și rulează codul