Voyageur de commerce

Bonjour,

Je cherche à résoudre le problème du voyageur de commerce.

Plus précisément, je ne voudrais intégrer des méthodes de résolutions du voyageur de commerce à un de mes projets Android (Java). Le mieux serrait de tout pouvoir faire en natif. Mais j'ai le sentimens que ça va être dur.

Je n'ai pas beaucoup de contraintes, l'essentiel étant de trouver une solution dans un premier temps.

Pour l'instant, je voudrais réutiliser un API déjà existant. Comme par exemple OpenStreet. Ou GraphHopper. Mais au final, ce serrait bien que j'arrive à recoder une heristique qui puisse convenir.

Je suis à peu près certain que certains des agrumes ont déjà été face à ce problème. S'ils pouvaient présenté rapidement comment ils ont gérer le problème du voyageur de commerce, ça pourrait m'être d'une grande utilité.

Merci !

Salut, tu peux te renseigner sur l'algorithme de little, il me semble que la méthode est exacte ce qui présente un problème de temps de calcul qui devient rapidement (trop) conséquent.

Je n'ai pas beaucoup de contraintes, l'essentiel étant de trouver une solution dans un premier temps.

Trouver une solution, c'est plutôt facile non ? Surtout si tu n'as pas de contraintes… Ca revient juste à trouver un cycle et ça se fait linéairement en la taille de ton graphe.

Pour l'instant, je voudrais réutiliser un API déjà existant. Comme par exemple OpenStreet. Ou GraphHopper. Mais au final, ce serrait bien que j'arrive à recoder une heristique qui puisse convenir.

Je suis à peu près certain que certains des agrumes ont déjà été face à ce problème. S'ils pouvaient présenté rapidement comment ils ont gérer le problème du voyageur de commerce, ça pourrait m'être d'une grande utilité.

Il y a eu beaucoup de recherches et d'implémentations. Pourquoi vouloir réimplémenter un algorithme ? Comme tu le mentionnes, il y a des API qui permettent de faire ça à ta place…