Comment résoudre le problème du voyageur de commerce avec Microsoft Excel

■■ Comment puis-je utiliser Excel pour résoudre des problèmes de séquencement?

■■ Comment puis-je utiliser Excel pour résoudre un problème de vendeur ambulant (TSP)?

Réponses aux questions de cet article

Cette section fournit les réponses aux questions répertoriées au début de cet article.

Comment puis-je utiliser Excel pour résoudre des problèmes de séquencement?

De nombreux problèmes commerciaux impliquent le choix d’une séquence optimale. Voici deux exemples:

■■ Dans quel ordre une imprimerie devrait-elle travailler sur 10 travaux afin de minimiser le délai total avant que les travaux ne respectent pas leurs échéances? Les problèmes de ce type sont appelés problèmes de planification d’atelier.

■■ Un vendeur habite à Boston et souhaite visiter 10 autres villes avant de rentrer chez lui. Dans quel ordre doit-il visiter les villes pour minimiser la distance totale qu’il parcourt? Ceci est un exemple du TSP classique.

Voici deux autres exemples de TSP:

■■ Un chauffeur-livreur doit effectuer 20 arrêts aujourd’hui. Dans quel ordre doit-elle livrer des colis pour minimiser son temps sur la route?

■■ Un robot doit percer 10 trous pour produire une seule carte de circuit imprimé. Quel ordre de perçage des trous minimise le temps total nécessaire pour produire une carte de circuit imprimé?

Le solveur Microsoft Excel  facilite la résolution des problèmes de séquençage. Choisissez simplement Evolutionnaire Solver, sélectionnez vos cellules changeantes et définissez Toutes les contraintes différentes. La configuration des contraintes avec Tout Different garantit que si vous avez 10 cellules changeantes, Excel attribuera les valeurs de 1, 2,. . . 10 aux cellules changeantes, chaque valeur apparaissant exactement une fois. En général, si vous sélectionnez une plage de n cellules changeantes pour être différente, Excel s’assure que les cellules changeantes prennent les valeurs 1, 2,. . . , n, chaque valeur possible apparaissant exactement une fois. Découvrez comment utiliser Dif pour résoudre facilement un problème de vendeur itinérant.

Comment puis-je utiliser Excel pour résoudre un problème de vendeur ambulant (TSP)?

Résolvez le problème suivant.

Willie Lowman est un vendeur qui vit à Boston. Il doit visiter chacune des villes énumérées dans Figure 1 ci-dessous puis retour à Boston. Dans quel ordre Willie devrait-il visiter les villes pour minimiser le total  de la distance qu’il parcourt? Votre travail se trouve dans le fichier .

FIGURE 1 : Voici les données du TSP.

Pour modéliser ce problème dans une feuille de calcul, vous devez noter que tout ordre ou permutation des nombres 1 à 11 représente un ordre pour visiter les villes. Par exemple, la commande du 2-4-6-8-10-1- Le 3-5-7-9-11 peut être considéré comme voyageant de Boston (Ville 1) à Dallas (Ville 3), à LA (Ville 5) et enfin à SF (Ville 10) avant de retourner à Boston. Parce que la commande est vue depuis l’emplacement de Ville 1, il y en a 10! = 10 × 9 × 8 × 7 × 6. . . × 2 × 1 = 3 628 800 commandes possibles pour Willie.

Pour commencer, vous devez déterminer la distance totale parcourue pour une commande donnée pour visiter les villes. La fonction INDEX est parfaite pour cette situation. Rappelons du chapitre 3, «La fonction INDEX», que la syntaxe de la fonction INDEX est INDEX (plage, ligne #, colonne #). Excel recherche dans la plage de cellules nommées Plage et sélectionne l’entrée spécifiée dans la ligne # et la colonne #. Dans ce cas, vous pouvez utiliser la fonction INDEX pour trouver la distance totale parcourue en visitant toutes les villes.

Commencez par entrer un ordre des entiers 1 à 11 dans la plage F16: F26. Ensuite, nommez les distances de la plage G4: Q14 et entrez la formule INDEX (distances, F26, F16) dans la cellule G16. Cette formule détermine la distance entre la dernière ville listée (en F26) et la première ville listée (en F16). Entrer le INDEX (Distances, F16, F17) formule dans la cellule G17 et copiez-la dans la plage G18: G26. Dans G17, la formule calcule la distance entre la première et la deuxième ville répertoriée, la deuxième et la troisième ville, etc. Vous pouvez maintenant calculer la cellule cible (distance totale parcourue) dans la cellule G27 avec la formule SOMME (G16: G26).

À ce stade, vous êtes prêt à invoquer le solveur évolutionnaire. Réduisez la cellule G27, cliquez sur Ajouter une contrainte et sélectionnez la plage F16: F26. Sélectionnez Dif pour Tous différents. Cela garantit que le solveur conserve toujours les cellules changeantes dans la plage sélectionnée, en supposant que les valeurs 1, 2, jusqu’à 11. Chaque valeur se produira exactement une fois. La boîte de dialogue Paramètres du solveur est illustrée à la figure ci-dessous. Avant d’exécuter Solver, augmentez le taux de mutation à 0,5.

FIGURE 2 : Le solveur est configuré pour un problème de vendeur itinérant.

La distance minimale possible pour voyager est de 8 995 miles. Pour voir l’ordre dans lequel les villes sont visitées, commencez dans la rangée par un 1 (correspondant à la maison de Willie, Boston) et suivez les villes dans l’ordre indiqué. Les villes sont visitées dans l’ordre suivant: Boston – NY – Pittsburgh – Chicago – Denver – Seattle – San Francisco – Los Angeles – Phoenix – Dallas – Miami – Boston. De nombreuses autres séquences pour visiter les villes donnent également la distance de voyage totale minimale de 8 995 miles.

S’abonner
Notifier de
0 Commentaires
Inline Feedbacks
Voir tous les commentaires

Initiation à Excel

Fonctions Excel

Excel VBA

Macros VBA Utiles

Plus d'outils

Sur Facebook

Sur YouTube

0
Nous aimerions avoir votre avis, veuillez laisser un commentaire.x