Problème du voyageur de commerce (TSP)

Le Problème du Voyageur de Commerce (TSP) est un classique, avec des applications en logistique. Dans le TSP, un vendeur reçoit une liste de villes et 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 d’un point de vue computationnel, mais Miller-Tucker-Zemlin (MTZ) ont montré qu’on peut le résoudre via la programmation linéaire en nombres entiers. Dans cet exercice, vous allez définir la fonction objectif et quelques contraintes du TSP pour un petit jeu de données de 15 villes (voir l’image ci-dessous). Votre objectif est d’expérimenter 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 correspond au 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 issu de Gerhard Reinelt, TSPLIB - A Traveling Salesman Problem Library, ORSA Journal on Computing,

Cet exercice fait partie du cours

<cours>Analyse de la chaîne d’approvisionnement en Python</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

Cet exercice fait partie du cours

<cours>Analyse de la chaîne d’approvisionnement en Python</cours>

IntermédiaireNiveau de compétence

4.8+

Commencer le cours gratuitement

La Programmation Linéaire (LP) est une technique clé pour l’optimisation de la chaîne d’approvisionnement. Le framework PuLP est un outil simple d’utilisation pour traiter des problèmes de LP et permet au programmeur de se concentrer sur la modélisation. Dans ce chapitre, nous abordons les bases des problèmes de LP et commençons à apprendre à utiliser PuLP pour les résoudre.

Exercise 1: Notions fondamentales d’optimisation Exercise 2: LP ou pas IP ?Exercise 3: Choisir une routine d’entraînement Exercise 4: Notions de base de la modélisation avec PuLP Exercise 5: Premiers pas avec LpProblem()Exercise 6: Exercice simple de planification des ressources Exercise 7: Utiliser lpSum Exercise 8: Essayer lpSum Exercise 9: Problème de planification logistique

Dans ce chapitre, nous poursuivons l’apprentissage de la modélisation des problèmes de LP et d’IP avec PuLP. Nous abordons l’usage de PuLP pour des problèmes de grande taille. Nous lançons également notre étude de cas : comment résoudre le modèle de localisation d’usines avec capacité (Capacitated Plant Location).

Exercise 1: Fonction de dictionnaire LpVariable Exercise 2: Problème de planification logistique 2 Exercise 3: Problème du voyageur de commerce (TSP)

Exercice actuel

Exercise 4: Exemple de problème d’ordonnancement Exercise 5: Problème de planification des salariés Exercise 6: Planification de la maintenance préventive Exercise 7: Implantation d’usines capacitaires – étude de cas P1 Exercise 8: Passer en revue les données pour l’étude de cas Exercise 9: Variables de décision de l’étude de cas Exercise 10: Fonction objectif de l’étude de cas Exercise 11: Contraintes logiques Exercise 12: Exercice sur une contrainte logique Exercise 13: Contraintes logiques : exercice 2

Ce chapitre passe en revue des erreurs courantes lors de la création de contraintes et détaille les étapes de résolution du modèle. Une fois que nous avons une solution à notre modèle de LP, comment savoir si elle est correcte ? Nous présentons aussi une démarche pour vérifier la plausibilité (sanity check) des résultats. En outre, nous poursuivons notre étude de cas sur le modèle de localisation d’usines avec capacité en finalisant toutes les contraintes nécessaires.

Exercise 1: Erreurs courantes sur les contraintes Exercise 2: Exercice sur la contrainte de demande dépendante Exercise 3: Exercice sur la combinaison de contraintes Exercise 4: Localisation d’usines avec capacité – étude de cas P2 Exercise 5: Contraintes de l’exercice de l’étude de cas Exercise 6: Ajouter une contrainte logique dans l’étude de cas Exercise 7: Résoudre le modèle PuLP Exercise 8: Choisir le statut du modèle Exercise 9: Résoudre l’exercice de plan de production Exercise 10: Vérifier la cohérence de la solution Exercise 11: Exercice : passer en revue la spécification du modèle Exercise 12: Exercice de vérification de cohérence

Dans ce dernier chapitre, nous étudions l’analyse de sensibilité des contraintes via les prix d’ombre et les écarts (slack). Nous examinons également les tests de simulation de nos modèles de LP. Ces différentes techniques nous permettent de répondre à des questions métier sur nos modèles, comme la capacité disponible et les coûts marginaux. Enfin, nous achevons notre étude de cas en nous concentrant sur l’utilisation de l’analyse de sensibilité et des tests de simulation pour répondre aux questions concernant notre modèle.

Exercise 1: Analyse de sensibilité des prix d’ombre Exercise 2: Exercice d’analyse de sensibilité Exercise 3: Exercice sur les prix d’ombre et les marges pt1 Exercise 4: Prix d’ombre et marge d’écart : exercice, partie 2 Exercise 5: Localisation d’usines avec capacité — étude de cas P3 Exercise 6: Résoudre l’exercice d’étude de cas du modèle Exercise 7: Exercice d’étude de cas sur l’analyse de sensibilité Exercise 8: Solution du test par simulation Exercise 9: Exercice : tester la solution par simulation Exercise 10: Quel est le risque Exercise 11: Localisation d’usines avec capacité — étude de cas P4 Exercise 12: Test de simulation du modèle capacitaire Exercise 13: Exercice : interpréter des résultats de simulation Exercise 14: Résumé final