Logiciel pour planifier l'itinéraire le plus court vers de nombreuses adresses [fermé]

8

J'ai environ 300 adresses dans une ville et j'essaie de trouver un logiciel qui peut résoudre le problème des vendeurs itinérants. J'ai essayé OptiMap, une solution basée sur un navigateur qui utilise l'API Google, mais elle est limitée à 100 destinations (même lorsque vous modifiez des limites codées en dur) et les navigateurs que j'essaie finissent par manquer de mémoire. Je sais que le problème est NP difficile mais ce n'est pas un nouveau problème, sûrement quelqu'un a déjà écrit un logiciel. Les seules solutions commerciales que j'ai vues sont basées aux États-Unis uniquement (c'est une ville australienne) ou ont de faibles limites.

Existe-t-il un logiciel gratuit ou commercial pour accomplir cette tâche et sa taille?

software-rec calculator user348998
la source
2
Vous pouvez peut-être résoudre le problème en morceaux de 100. Pouvez-vous diviser les emplacements en grappes et les alimenter en OptiMap en morceaux? Puis gérer les transitions manuellement?
uSlackr
J'ai toujours vu le problème des vendeurs itinérants utilisé comme exemple, quelque chose comme un truc foobarbaz hello world. C'est amusant de voir qu'il a un tel potentiel pratique. Soit dit en passant, NP dur ou non, les algorithmes génétiques donneront une excellente solution (pas parfaite) en quelques minutes ou moins. Aussi, 300 adresses? Cela ressemble au type de situation WTF que les développeurs d'OptiMap n'ont pas pris en compte. Déposer un bug?
Camilo Martin
Recherchez avec ces mots clés: optimisation de la livraison de logiciels logistiques. Il existe de nombreux logiciels dédiés à ce genre de problème. duckduckgo.com/...
climenole

Réponses:

1

Pas exactement "gratuit" - mais peut-être implémenter l'algorithme d'approximation pour TSP décrit dans ce manuel .

IIRC, il donne une solution TSP pour les graphes planaires d' un facteur 2 au sein de la solution optimale.

ensemble vide
la source
1
Haha, +1 pour la réponse "écrire cet algorithme"
Fopedush
Je pense que c'est drôle quand les gens pensent qu'ils vont trouver un site Web avec un logiciel écrit personnalisé pour résoudre leur scénario spécifique.
Emptyset