Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie

Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie Tome 3 - Problème du Voyageur de commerce - Une méthode d'approximation basée sur des principes simples Par Laurent OTT Date de publication : 23 avril 2017 Ce cours est une suite de la série sur « apprendre la programmation en VBA pour Excel par la pratique ». Après le tome 1, qui a donné les bases avec un exemple d'implémentation d'un algorithme de QuickRanking, et le tome 2 qui a introduit la programmation graphique, dans ce tome 3, il s'agira d'aborder un problème relativement complexe : le parcours du voyageur de commerce. Merci pour vos avis. Commentez En complément sur Developpez.com • Tome 1 - Des bases de la programmation à l'algorithme de classement rapide QuickRanking • Tome 2 - Des bases de la programmation en mode graphique à la programmation d'un jeu d'arcade en VBA et Microsoft Excel Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie par Laurent OTT I - Introduction..............................................................................................................................................................3 II - Le Tour de France en 45 villes............................................................................................................................. 3 III - L'amélioration 2-opt...............................................................................................................................................8 IV - L'amélioration 3-opt.............................................................................................................................................. 9 V - L'amélioration Lin-Kernighan............................................................................................................................... 10 VI - Le défi des 250 villes......................................................................................................................................... 11 VII - Obtenir un meilleur tracé prometteur................................................................................................................ 13 VIII - Les Algorithmes évolutionnaires.......................................................................................................................14 IX - La solution au défi des 250 villes...................................................................................................................... 14 X - Utiliser des distances réelles entre deux villes................................................................................................... 15 XI - Utiliser la fonction PVDC....................................................................................................................................17 XII - Pseudo-code simplifié de la fonction PVDC..................................................................................................... 20 XIII - Conclusion........................................................................................................................................................ 21 Annexe 1 : Un peu de vocabulaire............................................................................................................................21 Annexe 2 : Les fichiers EXCEL joints....................................................................................................................... 22 XIV - Remerciements.................................................................................................................................................22 - 2 - Copyright ® 2017 Laurent OTT. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://laurent-ott.developpez.com/tutoriels/programmation-excel-vba-tome-3/ Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie par Laurent OTT I - Introduction Le sujet de ce mémento peut vous surprendre, car le problème du voyageur de commerce (traveling salesman problem) ne se rencontre pas souvent dans les forums de programmation en VBA. Pour ceux qui n'en ont jamais entendu parler, je rappelle ici la présentation qu'en fait Wikipédia : « Étant donné n points (des "villes") et les distances séparant chaque point, trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque point et revienne au point de départ ». Dit autrement, un voyageur de commerce doit optimiser sa tournée, sans passer deux fois dans la même ville. Le plus simple est de tester tous les chemins possibles. Par exemple, si notre voyageur part de la ville A et doit visiter trois villes, BCD, avant de rentrer chez lui, il faut tester ABCDA, ABDCA, ACBDA, ACDBA, ADBCA, ADCBA. Soit (1x2x3) = 6 combinaisons. Le tout peut être divisé par deux, car les chemins parcourus dans un sens ou l'autre sont identiques. ABCDA est égal à ADCBA. Soit trois combinaisons à tester. Facile et rapide. Seulement, le nombre de combinaisons explose avec le nombre de villes à visiter. D'après la formule (n!/2), avec dix villes (n=10) il y a déjà 1 814 400 combinaisons (1x2x3x4…x10)/2, et avec vingt villes il y en a 1,2x1018, soit un temps de calcul estimé à plusieurs milliers d'années. Avec un algorithme basique qui explore toutes les combinaisons, il est donc impossible de trouver la solution si 250 villes doivent être visitées… Sauf que des méthodes plus sophistiquées ont été développées par des mathématiciens et des informaticiens pour optimiser les calculs, de telle sorte que, aujourd'hui, « des algorithmes existent et donnent de bons résultats dans des temps raisonnables ». Ces algorithmes (écrits en C ou autres langages réservés aux scientifiques) faisant appel à des mathématiques qui me dépassent, je vais me contenter dans ce mémento de présenter une méthode d'approximation qui reprend des principes simples, à la portée de tous, rien de très original donc et qui ne permet pas de rivaliser avec les meilleurs, mais qui donne une combinaison cohérente et pas ridicule… Ce qui pourrait peut-être vous suffire dans vos applications. Par exemple pour planifier la tournée d'un livreur. Vous trouverez le code source dans le fichier EXCEL joint. À défaut d'être parfait, cet algorithme permet en tout cas d'avoir un code en VBA, ce qui n'est pas facile à glaner sur Internet. Mais avant d'examiner l'appel à la fonction PVDC, qui retourne la meilleure combinaison trouvée, je vais vous présenter ces fameux principes si simples qu'ils semblent évidents. Cette étude vous permettra de mieux comprendre les paramètres utilisés, que vous devrez peut-être configurer pour adapter la fonction à vos besoins. II - Le Tour de France en 45 villes Pour présenter les principes utilisés par la méthode d'approximation que je vous propose, nous allons étudier une carte de France constituée de 45 villes (points) à visiter. Vous pouvez l'imprimer et essayer, à la main, de trouver le chemin optimal, vous le comparerez plus tard avec la solution calculée par l'algorithme. Pour cet exemple purement théorique, les trajets sont effectués « à vol d'oiseau », ne tenez pas compte pour le moment des contraintes liées aux distances réelles, ni aux obstacles géographiques. - 3 - Copyright ® 2017 Laurent OTT. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://laurent-ott.developpez.com/tutoriels/programmation-excel-vba-tome-3/ Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie par Laurent OTT 45 villes, mais par où commencer ? J'ai retenu la solution la plus rationnelle : en sélectionnant les quatre points cardinaux. Puisqu'en principe le chemin optimal devrait passer par ces points et dans cet ordre : Le parcours de base est constitué de quatre points avec un retour à l'origine : Perpignan, Brest, Calais, Strasbourg, Perpignan. Puis j'analyse chaque point restant en calculant la distance du parcours si j'ajoute ce point entre Perpignan et Brest, entre Brest et Calais, entre Calais et Strasbourg, entre Strasbourg et Perpignan. Et je vais retenir celui qui va augmenter le moins la distance du parcours. Cette technique est appelée « l'insertion de moindre coût ». Je vous rappelle la formule de calcul de la distance entre deux points que vous avez apprise au collège. Distance entre A et B = racine carrée de ((ordonnée de A - ordonnée de B) au carré) + (abscisse de A - abscisse de B) au carré). - 4 - Copyright ® 2017 Laurent OTT. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://laurent-ott.developpez.com/tutoriels/programmation-excel-vba-tome-3/ Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie par Laurent OTT Après analyse des 41 points restants, un passage par La Rochelle entre Perpignan et Brest est la solution qui augmente le moins la distance du parcours. Je répète l'opération sur les 40 points restants en incluant à l'analyse le point retenu, La Rochelle. Passer par Colmar entre Strasbourg et Perpignan est la solution qui permet de minimiser le parcours en ajoutant une ville. À la fin du traitement de tous les points, j'obtiens un résultat qui, visuellement, est cohérent. - 5 - Copyright ® 2017 Laurent OTT. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. http://laurent-ott.developpez.com/tutoriels/programmation-excel-vba-tome-3/ Apprendre la programmation en VBA pour EXCEL par la pratique - Troisième partie par Laurent OTT Pourtant en regardant de près, on devine qu'il y a un chemin plus court que Rennes, Brest, Perros- Guirec, Saint-Malo, Cherbourg. Voir le cercle ci-contre. Nous avons l'intuition que ce tracé peut être amélioré. Comment ? Il faut analyser les différentes combinaisons des trois villes entre Rennes et Cherbourg : soit six combinaisons comme nous l'avons vu dans l'introduction, et non divisible par deux, car nous devons suivre un sens non réciproque. L'optimisation de Rennes - Brest - Perros-Guirec - Saint-Malo - Cherbourg peut être représentée par l'analyse de la combinaison A - BCD - E. Comme A et E restent fixes, cela représente six différentes combinaisons possibles pour BCD. Et retenir la combinaison de la plus faible distance. Le nombre de villes analysées (ou niveau d'analyse) comprises entre la ville de départ et la ville d'arrivée détermine la durée du traitement : Pour 3 villes : 6 combinaisons. Pour 4 villes : 24 combinaisons. Pour 5 uploads/Geographie/ tome-3.pdf