Le problème du voyageur de commerce (TSP) est un défi classique d'optimisation combinatoire
cherchant le chemin le plus court pour visiter un ensemble de villes exactement une
fois et revenir au point de départ. Ce problème déjà complexe, ne capture pas certains aspects
opérationnels comme les dépendances temporelles. Le Time Dependent TSP (TDTSP) est une
variante du TSP prenant en compte cet aspect.

Contrairement au TSP classique où les distances entre les villes sont constantes, le TDTSP
intègre des temps de trajet variables, modélisant des conditions réelles où les temps de déplacement fluctuent en fonction de l'heure de la journée, du trafic ou d'autres facteurs temporels. Des temps d'attente entre les villes sont aussi à déterminer. Cette complexité supplémentaire engendre des défis algorithmiques majeurs, car trouver le chemin optimal implique désormais non seulement la distance la plus courte, mais aussi le timing le plus efficace. Le TDTSP revêt une importance significative dans divers domaines tels que la logistique, la planification des transports et les réseaux de distribution où la temporalité des déplacements joue un rôle crucial dans la prise de décision stratégique. Rajouter de nouvelles informations temporelles se modélise très facilement avec le formalisme de modélisation d'Hexaly.

Nous comparons les résultats obtenus par Hexaly pour les problèmes TDTSP et TDTSPTW à ceux présents dans la littérature. Hexaly améliore près de 25 % des instances comportant jusqu'à 100 points, tout en maintenant un écart proche de 0 % sur les autres instances.