1. Learn
    2. /
  2. Courses
    3. /
  3. Analytique de la chaîne d'approvisionnement avec Python
Connected

Exercise

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,

Instructions 1/3

undefined XP
    1
    2
    3
  • Utilisez LpVariable.dicts pour créer un dictionnaire x contenant des variables binaires pour chaque paire de villes, et pour créer un dictionnaire u contenant une LpVariable entière pour chaque ville.