Y a-t-il des vendeurs itinérants intelligents?

Blagues à part, j'ai eu un problème de routage qui est presque un problème de vendeur ambulant (TSP):

• le point de départ est défini
• le point final coïncide avec le point de départ
• chaque nœud doit être visité
• le coût total doit être minimisé

Il y a deux ans, je pensais que TSP serait une correspondance parfaite, j'ai donc exécuté des exemples de données via tsp_solveConcorde. Heureusement, il est rapidement devenu évident que le chemin le plus court du TSP n'est pas le chemin le plus court réel , car le problème est facilité en exigeant de manière irréaliste que les nœuds soient visités une seule fois . Cette image n'est qu'une tentative manuelle en une seule étape d'optimisation de la solution calculée et elle permet déjà d'économiser sur la distance du bord utilisé le plus long.

Le problème a refait surface, alors que j'essaie de trouver des itinéraires optimaux vers des sous-ensembles de sites de cartographie / surveillance. Les données de localisation et de réseau routier sont à la fois assez précises et précises, donc un exercice comme celui-ci est logique.

J'ai examiné les généralisations du TSP, mais je n'ai pas trouvé d'algorithme approprié. Les arbres couvrant minimum ne tiennent pas compte du retour des branches (la 1ère solution ici coûte 3 de plus). D'après ce que je comprends, le problème de chemin le plus court ne se soucie finalement que de deux nœuds et ceux qui sont hors du chemin optimal seraient exclus. Un cas particulier du problème de routage des véhicules semble le mieux adapté, même si je ne sais pas s'il prend en compte les chemins non directs.

Ma question: existe-t-il un nom fixe, une définition pour ce type de problème (famille)? Quel algorithme et outil utiliseriez-vous pour le résoudre?

Je suis sûr que ce serait lourd en termes de calcul, mais je suis intéressé par les réponses générales (ressources infinies) et pratiques.

C'est TSP . Vous n'avez tout simplement pas défini de métrique de distance valide car elle ne satisfait pas l'inégalité du triangle: s'il existe un itinéraire de A à C à B qui est plus court que la distance indiquée de A à C, alors la distance indiquée de A à C est tout simplement faux. La solution consiste à mettre à jour la matrice de distance en définissant la longueur de A à C comme la longueur la plus courte de tous les itinéraires de A à C.