Imaginez un centre de distribution très actif où les machines et les travailleurs se déplacent de manière optimale entre chaque lieu de travail et de stockage. Les itinéraires doivent être bien planifiés pour respecter des délais stricts et maintenir les coûts et autres facteurs à un niveau bas. Ce défi est au cœur de ce que l'on appelle historiquement la "gestion de l'information". problème du voyageur de commerce (TSP). Il ne s'agit pas seulement d'applications logistiques. Cet article explore la manière dont le problème du voyageur de commerce peut être utilisé dans la vie réelle et dans l'industrie manufacturière. Il examine comment on peut améliorer la planification des itinéraires dans toutes les industries.
Bien que ce problème soit un classique des mathématiques pures et des études algorithmiques, également étudié dans le domaine de la logistique avec une approche plus pratique, il est pratiquement inconnu dans d'autres industries et domaines de fabrication.
Ce billet se concentre sur un algorithme de notre billet "les 10 principaux algorithmes et méthodologies à connaître en ingénierie".
A Retenir
- Le problème du voyageur de commerce (TSP) consiste à trouver l'itinéraire le plus optimisé entre plusieurs points.
- Ce problème a commencé à susciter de l'intérêt dans les années 1930-1940.
- Il aide les organisations à améliorer l'efficacité et à réduire les coûts de leurs opérations, à limiter les ressources et à améliorer la prestation de services.
- Le problème est largement applicable dans différents secteurs et industries, et pas seulement dans la logistique et les transports.
- Dès qu'il y a plus de 12-20 points, le problème devient trop complexe pour calculer une solution parfaite.
- Plusieurs algorithmes ont été inventés pour trouver de bonnes approximations, mais pas l'approximation parfaite.
Qu'est-ce que le problème du voyageur de commerce ?
Le problème du voyageur de commerce : Trouver le moyen le plus efficace pour un vendeur de visiter plusieurs villes et de revenir au point de départ. Il ne doit visiter chaque ville qu'une seule fois, en essayant de réduire la distance totale au minimum.
Pour comprendre la définition du TSP, il faut savoir que le nombre d'itinéraires augmente au fur et à mesure que l'on ajoute des villes. Par exemple, quatre villes signifient qu'il y a 24 chemins possibles. L'ajout de villes augmente le défi, ce qui entraîne un trop grand nombre d'itinéraires potentiels à prendre en compte.
De nombreuses entreprises, notamment dans les domaines de la logistique, des télécommunications et de la fabrication, sont souvent confrontées à ce problème. Une bonne solution au problème du voyageur de commerce pourrait permettre d'économiser de l'argent et d'améliorer l'efficacité. Il montre comment la recherche théorique liée aux mathématiques aide à résoudre des problèmes de la vie réelle.
Pourquoi est-ce un problème de pensée ?
S'il y a n villes, il y a (n-1)!/2 tournées uniques (le /2 vient si la tournée est un cycle et que les directions n'ont pas d'importance).
En outre, de légers changements dans les données (par exemple, des distances ou de nouvelles villes) modifient complètement l'itinéraire optimal, ce qui rend le problème très sensible et complexe à résoudre. | Villes visitées | Itinéraires / combinaisons possibles |
| 3 | 6 | |
| 4 | 24 | |
| 5 | 120 | |
| 6 | 720 | |
| 7 | 5040 | |
| … | … | |
| 20 | 6 × 1016 (près de 2 millénaires si chaque calcul d'itinéraire nécessitait une microseconde) | |
| 25 | plus que l'âge de notre univers si chaque calcul d'itinéraire nécessitait une microseconde |
Histoire du problème du voyageur de commerce
Le problème du voyageur de commerce a vu le jour au début des années 1900, grâce à quelques mathématiciens intelligents. William Rowan Hamilton et Karl Menger sont les grands noms qui nous ont aidés à comprendre comment naviguer sur des chemins complexes. Ils se sont attachés à faciliter la recherche du meilleur itinéraire.
Dans les années 1930, on a commencé à définir plus clairement la PST. Des chercheurs de Vienne et de Harvard ont travaillé ensemble sur ce sujet. Ils ont commencé à voir comment ils pouvaient résoudre des problèmes réels, comme l'amélioration des itinéraires des bus scolaires. C'est ainsi que de plus en plus de personnes se sont intéressées à la résolution du PST.
Le PST s'est avéré très utile pour les entreprises, en particulier celles des secteurs de l'expédition et du transport. Dans les années 1950 et 1960, la RAND Corporation a pris les choses en main. Elle a proposé des solutions intelligentes pour résoudre le problème du PST, qui sont devenues un élément clé du bon fonctionnement de la logistique.
Pourquoi s'agit-il d'un problème NP-Hard ?
Le problème du voyageur de commerce est une énigme difficile en informatique. Il est connu pour être un problème NP-hard parce qu'il est vraiment difficile à résoudre car il croît exponentiellement plus vite qu'un ordinateur ne peut le faire s'il y a beaucoup de villes.
Qu'est-ce qu'un problème "NP-hard" ? En informatique et en théorie de la complexité, "NP" signifie Non-deterministic Polynomial time (temps polynomial non déterministe). Un problème NP-difficile est au moins aussi difficile que les problèmes les plus difficiles de NP, ce qui signifie que tous les problèmes de NP peuvent y être réduits en temps polynomial. Contrairement aux problèmes NP-complets qui peut être vérifié en un temps polynomial, tl n'existe pas d'algorithme connu qui permette de résoudre les problèmes NP-hard en temps polynomial.
C'est pourquoi les experts utilisent des raccourcis spéciaux et des suppositions intelligentes. Ces astuces leur permettent de trouver d'assez bons chemins sans avoir besoin d'une puissance de calcul démesurée pour obtenir une solution décente qui fonctionne suffisamment bien dans la vie réelle. Le chapitre ci-dessous présente certaines de ces approches pour les aider à gérer le nombre considérable de chemins possibles.
Applications industrielles
Le problème du voyageur de commerce aide différents secteurs d'activité améliorer des éléments tels que les itinéraires et les processus. De nombreux domaines tels que la logistique, le transport et la fabrication utilisent TSP pour faciliter leur travail. Les solutions approximatives de TSP et leurs variantes sont utilisées dans :
TransportationLes utilisations les plus similaires au problème original du vendeur :
| Routage
|
You have read 50% of the article. The rest is for our community. Already a member? Se connecter
(and also to protect our original content from scraping bots)
Communauté mondiale de l'innovation
Se connecter ou s'inscrire (100% gratuit)
Voir la suite de cet article et tous les contenus et outils réservés aux membres.
Uniquement de vrais ingénieurs, fabricants, concepteurs et professionnels du marketing.
Pas de bot, pas de hater, pas de spammer.
FAQ
Qu'est-ce que le problème du voyageur de commerce (TSP) ?
Le problème du voyageur de commerce (TSP) est une énigme importante. Il s'agit de trouver le chemin le plus court qui ne passe qu'une seule fois à chaque endroit et retourne au point de départ. C'est un élément clé pour les entreprises qui doivent planifier des itinéraires de manière efficace. La principale difficulté réside dans le nombre considérable d'itinéraires possibles, qui augmente avec chaque nouvel emplacement. En outre, des problèmes concrets tels que la circulation et les délais rendent la planification encore plus difficile.
Pourquoi le TSP est-il considéré comme un problème NP-hard ?
Le PST est difficile car le nombre d'itinéraires potentiels augmente de façon exponentielle avec chaque ville supplémentaire. Il est donc très difficile de trouver rapidement le meilleur itinéraire, surtout lorsque plus de 20 localités sont ajoutées.
Quelles sont les applications courantes de la TSP ?
TSP is used in many areas, like making delivery routes more efficient and managing supply chains. It’s also helpful in healthcare for scheduling visits and in robotique for guiding movements or in manufacturing electronics positioning or testing small components and copper routes.
Quel est le lien entre la théorie des graphes et les algorithmes heuristiques et le TSP ?
La théorie des graphes est le principe mathématique qui sous-tend le TSP. Elle utilise des points (sommets) pour représenter les villes et des lignes (arêtes) pour les chemins qui les relient. Elle permet de développer des méthodes pour résoudre efficacement les problèmes TSP. Les algorithmes heuristiques sont des raccourcis intelligents pour résoudre les TSP. Ils permettent de trouver rapidement des itinéraires suffisamment bons, même s'ils ne sont pas parfaits. Des méthodes telles que les algorithmes du plus proche voisin et de la cupidité sont des exemples courants. Des techniques comme le recuit simulé et les algorithmes génétiques sont également particulièrement utiles pour les gros problèmes.
Quel est l'impact du TSP sur l'efficacité de la chaîne d'approvisionnement ?
Le TSP renforce l'efficacité de la chaîne d'approvisionnement en affinant les itinéraires de transport. Cela permet de réduire les coûts, de mieux utiliser les ressources et d'améliorer la coordination entre toutes les parties concernées. Dans le domaine des soins de santé, le TSP optimise la manière dont les soins à domicile et les services d'urgence sont fournis. Il garantit que les fournitures médicales sont livrées rapidement, ce qui améliore les soins et la satisfaction des patients.
Articles Similaires
101 sur la meilleure façon de lire un brevet (pour un non-avocat en brevets)
Les 20 meilleures astuces pour une recherche de brevets gratuite + bonus
Meilleures invites d'IA pour l'ingénierie électrique
Meilleur Répertoire de Prompts d'IA pour Sciences et Ingénierie
Meilleures invites d'IA pour l'ingénierie mécanique
L'« effet Dantzig » pour l'innovation