Discussion :

[Trysac]

Bonjour ;
Nous recherchons à créer un algorithme de résolution du problème de tournée de véhicules et nous savons pas quel est l'algorithme le plus performant : colonie de fournis, recuit simulé, algorithme génétique, ...
Avez vous déjà chercher à résoudre un tel problème ? Si oui, avec quel algorithme ?
Merci d'avance.

T.

[JulienDuSud]

J'avais déjà résolu ce problème, et il me semble que je faisais du DFS avec une sélection/expansion BnC. Associé à une bonne heuristique ça marche plutôt bien, avec une heuristique très bonne on peut atteindre un temps polynomial.

L'algo de Lin-Kernighan est, il me semble l'une des meilleures pour ce problème.

Si tu ne vois pas ce que c'est, fait une recherche sur deep first search et branch and cut.

Toutes manières, ce topic serait plus à sa place dans le forum algo je pense

[Trysac]

merci pour cette piste, je vais regarder par la

[moudi_191]

est ce que tu as résolu le problème? comment? parce que moi j'ai le même algo a faire et j ai pensé a recherche tabou

[cedriku]

L'algorithme supreme qui bat tous les autres algorithmes sur toutes les instances de problemes possibles... ca n'existe pas (ca se saurait sinon). Dans ton cas, si j'ai bien compris tu as identifié parfaitement le probleme à resoudre et tu cherches un algo existant efficace pour le resoudre.

L'algo ultime qui marche tout le temps sur ce type de probleme n'existant pas, tu dois te poser certaines questions. Tout d'abord, t'interesse tu a un probleme de decision ou d'optimisation ? Si tu es dans le cas d'un probleme d'optimisation, veux-tu toujours la meilleure solution (donc le temps de calcul est secondaire, ce qui compte c'est la qualité de la solution avant tout) ou bien tu privilegie le temps de calcul (par exemple si t'as des contraintes de temps reel) et donc tu peux te contenter de solution proche de l'optimum (avec ou sans garantie de performances). Ceci amene donc a la question : cherches-tu un algo complet ou incomplet ?

Et il y a beaucoup d'autres question a te poser pour choisir l'algo qui te conviendra. Mais ca c'est deja les questions de base.

Par exemple, tu demandes l'algo le plus performant entre colonie de fourmis, recuit simulé, algo genetique... Deja ce type d'algorithme n'a aucune garantie de performances tout simplement parce que leur qualité va dependre de leurs (nombreux) parametres. Si tu trouve les bons parametres (par exemple pour colonies de fourmi, les parametres vont etre le nombre de fourmis, le nombre de cycles, le alpha et beta : diversification/intensification...), il se peut que l'algo soit performant sur un type de probleme... mais encore faut il trouver les bons parametres et rien ne dit qu'avec ces meme parametres, l'algo sera bon sur d'autres types de problemes.

Typiquement, pour moi ce type d'algo n'est utile que lorsque l'on a des contraintes a respecter sur le temps de calcul (probleme de temps reel), et qu'il faut absolument trouvé une solution dans la seconde et tant pis si cette solution n'est pas optimale.