Product Design, Manufacturing & Innovation Resources
Maison » En vedette » Le problème du voyageur de commerce, pour l'industrie et l'innovation

Le problème du voyageur de commerce, pour l'industrie et l'innovation

Problème du voyageur de commerce

Imagine a busy distribution center where machines and workers move optimally between each working and storage locations. Routes need to be planned well to meet strict time limits and keep costs and other factors low. This challenge is at the heart of the historically so-called traveling salesman problem (TSP). It’s not only in the logistic applications. This piece explores how the traveling salesman problem can be used in real life and manufacturing. It looks at how one can improve their route planning in all the industry.

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).

  • Pour les petits n (disons n < 20), les algorithmes exacts (force brute, programmation dynamique) fonctionnent.
  • Techniques approximatives/heuristiques : le plus proche voisin, l'algorithme de Christofides, les algorithmes génétiques sont souvent utilisés pour les cas les plus importants.
  • Mais, en général, il n'existe pas de méthode rapide garantissant la meilleure réponse possible dans tous les cas.

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éesItinéraires / combinaisons possibles
36
424
5120
6720
75040
206 × 1016 (près de 2 millénaires si chaque calcul d'itinéraire nécessitait une microseconde)
25plus que l'âge de notre univers si chaque calcul d'itinéraire nécessitait une microseconde

Histoire du problème du voyageur de commerce

Vaste étendue de connaissances historiques, le voyage du problème du voyageur de commerce se déroule devant nous. Au premier plan, une carte tentaculaire ornée de lignes et d'itinéraires, retraçant l'évolution de ce défi d'optimisation emblématique. Au milieu, une collection de diagrammes analytiques et d'équations mathématiques, les outils qui ont façonné notre compréhension de ce problème au fil du temps. À l'arrière-plan, un collage d'étapes importantes et de personnages clés, chacun contribuant à la riche tapisserie de l'histoire du problème du voyageur de commerce. Éclairée par un éclairage chaleureux d'inspiration vintage, cette scène capture la profondeur et la complexité d'un problème qui continue de captiver et d'inspirer les chercheurs, les logisticiens et les personnes chargées de résoudre les problèmes.
Une vaste étendue de connaissances historiques, le voyage du problème du voyageur de commerce se déroule. Le problème du voyageur de commerce : applications réelles dans l'industrie et la logistique. Planification des livraisons

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.

🔒

The rest of this article is reserved for members

To limit scraping bots (currently 40,000 hits per day!),
we had to restrict access to full articles and tools to registered members only.

Log in →  or  Register (100% free) →

to access all the rest.

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 ?

Le TSP est utilisé dans de nombreux domaines, notamment pour rendre les itinéraires de livraison plus efficaces et gérer les chaînes d'approvisionnement. Il est également utile dans le domaine des soins de santé pour la planification des visites et dans le domaine de la santé publique. robotique pour le guidage des mouvements ou dans le domaine de l'électronique de fabrication pour positionner ou tester de petits composants et des circuits en cuivre.

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.

Glossaire des termes utilisés

Deoxyribonucleic Acid (DNA): Molécule composée de deux brins formant une double hélice, constituée de nucléotides codant l'information génétique par des séquences de quatre bases : adénine, thymine, cytosine et guanine. Elle constitue le patrimoine héréditaire de la plupart des organismes vivants.

Printed Circuit Board (PCB): Carte plate en matériau isolant qui supporte et connecte les composants électroniques par des circuits conducteurs, généralement gravés dans des feuilles de cuivre. Elle sert de base à l'assemblage des circuits et facilite les connexions électriques entre les composants.

Unmanned Aerial Vehicle (UAV): Un aéronef télépiloté ou autonome conçu pour diverses applications, notamment la surveillance, la reconnaissance et le largage de colis, sans pilote à bord. Il fonctionne via des stations de contrôle au sol ou des systèmes d'automatisation embarqués, souvent équipés de capteurs et de caméras pour la collecte de données.

Very-large-scale Integration (VLSI): une technologie permettant de créer des circuits intégrés en combinant des milliers à des millions de transistors sur une seule puce, permettant de miniaturiser des systèmes électroniques complexes et d'améliorer les performances, l'efficacité énergétique et la fonctionnalité d'appareils tels que les ordinateurs et les smartphones.

Sujets abordés : Problème du voyageur de commerce, optimisation, planification des itinéraires, logistique, algorithme, efficacité, réduction des coûts, méthodes heuristiques, programmation dynamique, NP-hard, optimisation combinatoire, algorithmes d'approximation, ISO 9001, ISO 14001, ISO/IEC 27001, ISO 31000, et ISO 50001.

Contexte historique

1829
1850
1854
1854
1895
1899
1900
1828
1848
1850
1854
1884
1896
1900
1903

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Les images en pleine résolution et les téléchargements sont uniquement disponibles, et 100% gratuits, pour les membres inscrits.