CommencezCommencez gratuitement

Problème du voyageur de commerce (TSP)

Le problème du voyageur de commerce (TSP) est bien connu et a des applications en logistique. Dans le TSP, un vendeur reçoit une liste de villes ainsi que la distance entre chaque paire. Il cherche l'itinéraire le plus court partant de la ville d'origine, passant par tous les points, puis revenant à la ville d'origine. Ce problème est difficile à résoudre sur le plan informatique, mais Miller–Tucker–Zemlin (MTZ) ont montré qu'on peut le formuler avec la programmation linéaire en nombres entiers. Dans cet exercice, vous allez définir la fonction objectif et certaines contraintes du TSP pour un petit jeu de données de 15 villes (voir l'image ci-dessous). Votre but est d'essayer LpVariable.dicts avec une compréhension de liste.

Photo of Cities

Trois variables Python, n, cities et dist, ont été créées pour vous \(^{1}\). La variable n est le nombre de villes, cities est une liste des villes numérotées et dist est un DataFrame pandas contenant les distances par paires entre chaque ville. Vous pouvez les explorer dans la console. De plus, le modèle a été initialisé pour vous.

\(^{1}\) Jeu de données provenant de Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Cette activité fait partie du cours

Analytique de la chaîne d'approvisionnement avec Python

Voir le cours

Exercice interactif pratique

Essayez cet exercice en complétant ce code d’exemple.

# 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=____)
Modifier et exécuter le code