LE NOMBRE CACHÉ DU VOYAGEUR DE COMMERCE, ENCERCLÉ

Usage d’IA déclaré. Dans une section « Disclosure of AI Use », les auteurs indiquent avoir utilisé l’outil d’IA GPT-5.6 Sol Pro pour préparer l’article, avoir relu et vérifié tous les résultats, et assumer l’entière responsabilité de son contenu. Leur code est disponible sur demande.

Le problème du voyageur de commerce demande la plus courte tournée qui passe une fois par chaque point d’un ensemble et revient au départ. Rendons les points aléatoires : jetons n points uniformément dans un carré de côté 1 et demandons quelle est la longueur de la plus courte tournée.

En 1959, Beardwood, Halton et Hammersley ont démontré une réponse frappante. Quand n grandit, la longueur de la meilleure tournée devient presque sûrement égale à β√n, où β est une constante universelle — la même pour tout éparpillement aléatoire. Ils ont aussi montré que 0,625 ≤ β ≤ 0,9212.

Plus de soixante-cinq ans après, personne ne connaît β. Il n’existe pas de formule. De grandes expériences sur ordinateur le placent vers 0,7124, mais une expérience n’est pas une preuve. Jusqu’ici, les meilleures bornes démontrées étaient 0,6277 ≤ β ≤ 0,90367. Ces constantes comptent en logistique, où elles servent à estimer la longueur de tournées de livraison sans les calculer — d’où un résultat venu de la McCombs School of Business de l’université du Texas à Austin, signé Zhuolun Dong et Junyu Cao.

Le nouvel encadrement

L’article démontre :

0,6421 ≤ β ≤ 0,8810

et, par échantillonnage aléatoire, montre que 0,6536 ≤ β ≤ 0,8749 avec une probabilité d’au moins 1 − 2 × 10⁻⁴. Cette probabilité porte sur le hasard du calcul par échantillonnage, pas sur β lui-même, qui est un nombre fixe.

Par en dessous : couper les longues arêtes

Pour prouver que toute tournée est forcément longue, les auteurs regardent ce qui se passe si l’on supprime toutes les arêtes d’une tournée plus longues qu’une certaine longueur r. La tournée se brise en morceaux de chemin, et chaque morceau reste dans un amas de points distants de moins de r les uns des autres. Plus un amas demande de chemins pour être couvert, plus la tournée devait avoir d’arêtes longues. En additionnant sur toutes les valeurs de r, on retrouve la longueur de la tournée :

ℓ(H) = ∫₀^∞ N_H(r) dr,

où N_H(r) compte les arêtes plus longues que r.

Les points isolés et les extrémités de chemins donnent l’ancien terme 5/8 = 0,625 — exactement la borne de 1959. L’ingrédient nouveau est une série de corrections venues des petits amas de 3, 4 et 5 points, chacune étant une intégrale sur les positions possibles des points. Ces intégrales ne se calculent pas exactement : les auteurs découpent leur domaine en minuscules cubes et minorent chaque cube, en arrondissant chaque nombre irrationnel dans le sens défavorable pour que le résultat soit une vraie borne :

β ≥ 0,625 + 0,01113528859 + 0,005040573276 + 0,001015487669 > 0,6421.

Par au-dessus : zigzaguer par blocs de cinq

Pour une borne supérieure, il suffit d’une bonne tournée. La recette classique découpe le carré en bandes horizontales et les parcourt en zigzag, de gauche à droite, puis de droite à gauche. La nouveauté : dans chaque bande, les points sont pris par blocs de cinq, et chaque bloc est visité dans le meilleur de ses 24 ordres possibles.

La longueur moyenne d’un bloc est une intégrale à onze dimensions — cinq écarts horizontaux entre points et six hauteurs. Les auteurs la majorent numériquement sur une grille fine, là encore avec des rationnels arrondis du bon côté, et obtiennent β < 0,8810.

L’écart qui reste

La fourchette s’est resserrée d’une largeur d’environ 0,28 à environ 0,24, mais la valeur empirique 0,7124 reste bien à l’intérieur. Des grilles plus fines, de meilleures estimations des aires de disques qui se chevauchent et des blocs plus longs pourraient la resserrer encore. Combler la distance restante, écrivent les auteurs, « pourrait demander de nouvelles techniques ».