{"id":1,"date":"2020-08-10T23:31:57","date_gmt":"2020-08-10T21:31:57","guid":{"rendered":"http:\/\/maths-code.fr\/cours\/?p=1"},"modified":"2023-01-18T23:20:46","modified_gmt":"2023-01-18T22:20:46","slug":"le_voyageur","status":"publish","type":"post","link":"https:\/\/maths-code.fr\/cours\/2020\/08\/10\/le_voyageur\/","title":{"rendered":"Le voyageur de commerce"},"content":{"rendered":"\n

Le probl\u00e8me du voyageur de commerce \u2013 Traveling Salesman Problem<\/em> TSP -, \u00e9tudi\u00e9 depuis le 19e si\u00e8cle, est l\u2019un des plus connus dans le domaine de la recherche op\u00e9rationnelle. William Rowan Hamilton a pos\u00e9 pour la premi\u00e8re fois ce probl\u00e8me sous forme de jeu d\u00e8s 1859.<\/p>\n\n\n\n

\n

\u00ab Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir \u00e0 son point d\u2019origine. Trouvez l\u2019ordre de visite des villes qui minimise la distance totale parcourue par le voyageur \u00bb.<\/p>\n<\/blockquote>\n\n\n

Ce probl\u00e8me d\u2019optimisation combinatoire appartient \u00e0 la classe des probl\u00e8mes NP-Complets.<\/p>\n

Les domaines d\u2019application sont nombreux : probl\u00e8mes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de probl\u00e8mes d\u2019ordonnancement. Certains probl\u00e8mes rencontr\u00e9s dans l\u2019industrie se mod\u00e9lisent sous la forme d\u2019un probl\u00e8me de voyageur de commerce, comme l\u2019optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte \u00e9lectronique le plus vite possible ?<\/p>\n

Pour un ensemble de $n<\/code>$ points, il existe au total $n!<\/code>$ chemins possibles. Le point de d\u00e9part ne changeant pas la longueur du chemin, on peut choisir celui-ci de fa\u00e7on arbitraire, on a ainsi $(n-1)!<\/code>$ chemins diff\u00e9rents. Enfin, chaque chemin pouvant \u00eatre parcouru dans deux sens et les deux possibilit\u00e9s ayant la m\u00eame longueur, on peut diviser ce nombre par deux. Par exemple, si on nomme les points, $a, b, c, d$, les chemins $<\/code>abcd, bcda, cdab, dabc, adcb, dcba, cbad, badc<\/code>$ ont tous la m\u00eame longueur, seul le point de d\u00e9part et le sens de parcours change. On a donc $\\frac{1}{2}(n-1)<\/code>$ chemins candidats \u00e0 consid\u00e9rer. \\ Par exemple, pour $71<\/code>$ villes, le nombre de chemins candidats est sup\u00e9rieur \u00e0 $5 \u00d7\u202f10^{80}<\/code>$ qui est environ le nombre d’atomes dans l’univers connu. (Probl\u00e8me du voyageur de commerce\u00a0<\/em><\/a>–<\/em> wikipedia <\/a><\/em><\/a>).<\/p>\n

Heuristique gloutonne<\/h4>\n

L’objectif de ce TP (voir le cours algorithme glouton<\/a> pour l’\u00e9nonc\u00e9 adapt\u00e9) est de r\u00e9aliser un algorithme glouton pour r\u00e9soudre le TSP.<\/p>\n

Pour cela vous avez \u00e0 votre disposition :<\/p>\n