Discussion :

[chtrec]

Bonjour à tous,

Nouveau sur ce site qui m'a l'air vraiment très intéressant !

J'ai besoin d'avoir un peu d'aide.

Je cherche à résoudre le problème suivant :

* Il y a 3 magasins dans une ville, M1, M2, M3
* Je connais la liste des prix de tous les articles de ces magasins.
* Je connais les coûts de transport entre les magasins et mon domicile et ceux inter magasin.
* J'ai une liste de courses à faire.

Quel est le circuit que je dois emprunter pour avoir la facture totale la plus basse ?

----

Je pense que ce problème doit pouvoir se résoudre par un algorithme résolvant le problème du voyageur de commerce mais je n'en suis pas sur du tout car il y a le problème des prix des marchandises en plus...

----

Merci de vos réponses

[ToTo13]

Bonjour,

la première question est : comment souhaites tu résoudre ce problème ? De manière optimale, une heuristique, etc.

Si tu veux que ce soit optimal, tu peux faire une recherche exhaustive. Sinon tu as tout ce qui est méta-heuristiques (taboo, recuit simulé).

[chtrec]

Merci de la réponse...

je pense que ce problème peut effectivement se résoudre par une énumération. Cependant, comme vous le savez tous très bien si le nombre de variables augmente on va vite arriver à un nombre de solutions très très important.

Mon problème était de savoir si un algorithme de résolution du "voyageur de commerce" pouvait résoudre ce problème ou donner une valeur approchée de la solution optimale.

En effet, il existe des différences notables entre un "voyageur de commerce" et ce problème :

* La personne n'est pas obligée d'aller dans tous les magasins, et à mon sens l'optimal sera même plutôt souvent d'aller dans un seul.
* Il y a des produits qui sont dans la liste de course et qui peuvent ne pas être présents dans tous les magasins.
* Il y a le coût du trajet à prendre en compte qui vient s'ajouter au coût des articles.

[khayyam90]

Etant donné que tu n'es pas obligé de passer par toutes les villes, les méthodes de résolution du voyageur de commerce ne s'appliquent pas en l'état.

Tu peux toujours déterminer une liste de magasins à visiter par une heuristique de ton choix, puis déterminer le meilleur parcours entre ces magasins via un voyageur de commerce. Mais bien sûr le résultat sera biaisé puisque tu choisiras les magasins sans tenir compte du meilleur parcours entre ces magasins.

[ToTo13]

En effet, il existe des différences notables entre un "voyageur de commerce" et ce problème :

pas tant que ça en fait. Je pense que l'on peut très facilement adapté tous les algorithmes de résolution d'un voyageur de commerce à ton problème.
En fait, si on regarde, seul la fonction coût est légèrement différente, ainsi que la condition de fin qui ne s'intéresse pas au nombre de ville visitée, mais au nombre de vêtements en ta possession.

Donc :
- si le nombre de variable est raisonnable, une recherche exhaustive c'est toujours très bien.
- sinon, les deux méta-heuristiques qui ont résolu le plus de voyageurs de commerce sont le recuit simulé (big boss de la discipline) et la méthode taboo (préférée depuis quelques année au recuit simulé pour sa plus grnade souplesse, fiabilité et sa facilité d'initialisation). Il y a aussi l'algorithme génétique, mais ce n'est pas le plus adapté au problème. Si tu es un peu joueur ou curieux, tu peux implémenter une colonie de fourmi.

[chtrec]

Pour khayyam90 :

Tu peux toujours déterminer une liste de magasins à visiter par une heuristique de ton choix, puis déterminer le meilleur parcours entre ces magasins via un voyageur de commerce. Mais bien sûr le résultat sera biaisé puisque tu choisiras les magasins sans tenir compte du meilleur parcours entre ces magasins.

Exactement... les deux choix ne sont pas indépendants mais plutôt très interdépendants. La différence de prix entre les magasins doit compenser le coût de transport entre ceux-ci.

Pour Toto13

pas tant que ça en fait. Je pense que l'on peut très facilement adapté tous les algorithmes de résolution d'un voyageur de commerce à ton problème.
En fait, si on regarde, seul la fonction coût est légèrement différente, ainsi que la condition de fin qui ne s'intéresse pas au nombre de ville visitée, mais au nombre de vêtements en ta possession.

Effectivement, la fonction coût est différente car elle doit ajouter le coût des articles à celui du transport et je retiens la condition de fin qui est le nombre d'articles...

----

Si pour mes trois magasins j'ai 10 articles de sélectionnés, cela me fait 30 couples article/magasin (que l'on peut assimiler à des villes à visiter) et je peux associer des coûts entre eux, correspondant au coût de transport éventuels (0 si c'est le même magasin) plus le coût de l'article de départ (ou d'arrivée).

J'ai fini mon parcours quand j'ai mon nombre d'articles et il ne faut pas oublier de rentrer à la maison

ça doit le faire... Je vais donc regarder la méthode TABOO qui selon vous apparaît comme étant la plus intéressante par rapport à mon problème.

----

Merci de votre aide. Je vous tiens au courant de la résolution.

PS : bon, je sais c'est peut-être un peu trop demander mais y a t-il des TABOO libres d'utilisation et implémentés en VB ?

[ToTo13]

Bonjour,

oui pour la Tabou. Il est vrai que c'est une méthode que j'affectionne, car elle est simple, efficace et particulièrement bien adapté à un problème binaire (dans un magasin tu prends ou non l'article).