TSP : Voyageur de commerce

[Cliffe]

Bonjour,

Je cherche des méthodes de résolutions exactes du TSP hormis la programmation linéaire et l'énumération de tous les chemins possibles.

Merci.

[Sylviel]

Je vais peut-être dire des bêtises mais le TSP se résout de manière exacte par tout un tas de méthodes issus de la Programmation Linéaire (Branch and Bound, Branch and Cut etc...) donc difficile de savoir ce que tu exclut quand tu dis "à part énumération et PL". Au passage : l'énumération est très rapidement hors d'atteinte.

[Cliffe]

Je ne sais pas si ce que je cherche existe enfaite ^^

Une sorte d'algo, qui prend la matrice des distances en entrée, qui va faire plein de trucs (des tris, des comparaisons, des arrangements, des classifications etc ...), et qui te sort le chemin optimale.

[Sylviel]

Ben je te l'ai dit : à ma connaissance les méthodes de résolution exacte efficace utilise des approches type programmation linéaire. Cela repose donc sur des recherche de branch and bound efficace... Mais je n'en sais pas beaucoup plus.

[Cliffe]

Je ne cherche pas forcément quelque chose d'efficace :id: