Heuristique pour le voyageur de commerce

Question

Je travaille sur l'optimisation évolutionnaire et pour ce projet j'ai besoin de heuristiques pour le problème du voyageur de commerce. Dans ce contexte, algorithmes génétiques, nous appliquons de petites mutations et espérons que quelque part les choses s'amélioreront. Je suis donc à la recherche d'une heuristique simple pour transformer la solution qui pourrait potentiellement conduire à une amélioration.

Merci de nous faire part de vos suggestions.

Answer 1

Une référence que je souhaite recommander est Paquet TSP de R . (Consultez-le même si vous n'utilisez pas R.) Leur vignette sur TSP est excellent et contient de nombreuses astuces basées sur la programmation dynamique que vous pouvez essayer pour améliorer votre mise en œuvre de l'AG.

Section 2.4 de la vignette en particulier parle de Heuristique de construction de circuits que vous pouvez intégrer. C'est ce que je cite :

Algorithme du plus proche voisin : il s'agit d'une procédure gourmande très simple : L'algorithme commence par une tournée contenant un ville choisie au hasard, puis ajoute toujours à la dernière ville de la tournée la ville la plus proche non encore visitée. la ville la plus proche qui n'a pas encore été visitée. L'algorithme s'arrête lorsque toutes les villes sont sur la tournée.

Une extension de cet algorithme consiste à le répéter point de départ et de renvoyer la meilleure tournée trouvée. Cette heuristique est Cette heuristique est appelée le plus proche voisin répétitif.

Algorithmes d'insertion. commencent par une tournée composée d'une ville arbitraire et choisissent à chaque étape une ville qui ne fait pas encore partie de la tournée. Cette ville ville est insérée dans la tournée existante entre deux villes consécutives i et j consécutives, de telle sorte que le coût d'insertion (c'est-à-dire l'augmentation de la longueur de la tournée) soit minimisé. de la tournée) soit minimisé. Les algorithmes s'arrêtent lorsque toutes les villes sont sur la tournée.

Insertion la plus proche La ville k est choisie à chaque étape comme étant la ville la plus proche d'une ville de la tournée.

Insertion la plus éloignée La ville k est choisie à chaque étape comme étant la ville la plus éloignée de toutes les villes de la tournée.

Insertion la moins chère La ville k est choisie à chaque étape de manière à ce que le coût d'insertion de la nouvelle ville soit minimal.

Vous trouverez beaucoup plus de détails et d'autres techniques mentionnées dans la rubrique vignette .

Answer 2

Je pense que vous recherchez une heuristique d'amélioration des tournées et je peux vous suggérer ce qui suit Lin-Kernighan algorithme pour vous. Mais cet algorithme peut être trop difficile pour vous. Vous pouvez donc rechercher 2-opt ou l'algorithme 3-opt.