Aide formulation mathématique problème dynamique du voyageur de commerce

Voir le sujet précédent Voir le sujet suivant Aller en bas

Aide formulation mathématique problème dynamique du voyageur de commerce

Message par Invité le Sam 3 Juil - 17:08

Voici la formulation mathématique de son problème dans le cas statique( c'est la formulation du problème du voyageur de commerce):



Comment intégrer la dimension dynamique au modèle pour qu'il permette de résoudre le problème sans refaire un autre programme pour chaque nouvelle demande arrivée à l'instant t (toutes les données dans ce cas sont connues).






Bonjour à tous,

On m'avais posé le problème suivant :

Soit un camion de capacité illimité disponible dans l'entrepôt qui doit
visiter un ensemble de fournisseur pour ramasser leurs produits une et
une seule fois et retourner à son dépôt à la fin de la journée de façon à
minimiser le temps total du voyage. Certaines demandes ne sont pas
connues à l'avance. Elles ne sont connues qu'au moment où le camion est
en route.


Question : Écrire un programme linéaire permettant de déterminer l'ordre de visite
des fournisseurs une fois une nouvelle demande est arrivée de façon à
minimiser le temps total de voyage.

Auriez-vous d'idées sur la marche à suivre. Merci.

Invité
Invité


Revenir en haut Aller en bas

Re: Aide formulation mathématique problème dynamique du voyageur de commerce

Message par informix le Lun 5 Juil - 14:21

Question un peu difficile.
Tu veux remplacer la programmation dynamique par la programmation linéaire qui est statique dans le cas standard ?
c'est bien ça ou je me trompe?

_________________
informix, Ecole d'ingénieurs
Les passions font vivre l'Homme; sa sagesse le fait seulement durer.
avatar
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 3909
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Aide formulation mathématique problème dynamique du voyageur de commerce

Message par Invité le Lun 5 Juil - 16:18

Bonjour
Merci de votre réponse.
Pourrais-tu m'expliquer davantage comment utiliser cette méthode pour résoudre le problème?

Merci encore.

Invité
Invité


Revenir en haut Aller en bas

Re: Aide formulation mathématique problème dynamique du voyageur de commerce

Message par methodiX le Mer 7 Juil - 14:01

Bonjour,

Est-ce que tu as fait une étude bibliographique sur la version dynamique du problème ???

Cite quelques références.

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4637
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

Re: Aide formulation mathématique problème dynamique du voyageur de commerce

Message par hedi le Jeu 8 Juil - 12:44

bonjour,
c'est un problème très intéressant. je vais essayer de résumer. On a un ensemble de fournisseurs répartis sur un territoire, un entrepôt, et un camion qui part de cet entrepôt pour ramasser des produits chez les fournisseurs, et les ramener à l'entrepôt.
Les fournisseurs communiquent avec le conducteur, pour lui faire savoir que leurs produits sont prêts à être ramassés. Mais toutes les demandes n'arrivent pas en même temps, donc ne sont pas connues d'avance.
On va supposer pour simplifier :
- que le camion n'entame son premier voyage que s'il reçoit au moins une demande
- que quand le camionneur reçoit une ou plusieurs demandes, et qu'il est sur sa route vers un fournisseur, il ne modifie son itinéraire qu'après avoir visité ce fournisseur.
- que la méthode de résolution du problème du voyageur de commerce est connue.

On suppose aussi qu'au départ le camionneur collecte les demandes durant un certain temps, mais ce temps d'attente sera limité, sinon il attendra jusqu'à collecter toutes les demandes et ce sera un problème classique. On suppose aussi que quand il aura visité le dernier fournisseur programmé, mais qu'il restera encore des fournisseurs qui n'ont pas émis leur demandes, le camionneur décide de rentrer à l'entrepôt, et de terminer son voyage, au bout d'un certain temps d'attente fini.
Êtes vous d'accord avec ces hypothèses ?

hedi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 7
Localisation : tunis
Réputation : 6
Points : 2666
Date d'inscription : 22/06/2010

Revenir en haut Aller en bas

Re: Aide formulation mathématique problème dynamique du voyageur de commerce

Message par Invité le Jeu 8 Juil - 22:10

Merci Beaucoup Hédi pour ces explications.
C'est exactement ça!
A ton avis, peut-on le modéliser sous la forme d'un programme linéaire en nombres entier(type minimisation sous contraintes)?(Méthode de résolution prévue: logiciel commercial type LINGO ou CPLEX)

J'attends ta réponse.
Merci par avance.

hedi a écrit:bonjour,
c'est un problème très intéressant. je vais essayer de résumer. On a un ensemble de fournisseurs répartis sur un territoire, un entrepôt, et un camion qui part de cet entrepôt pour ramasser des produits chez les fournisseurs, et les ramener à l'entrepôt.
Les fournisseurs communiquent avec le conducteur, pour lui faire savoir que leurs produits sont prêts à être ramassés. Mais toutes les demandes n'arrivent pas en même temps, donc ne sont pas connues d'avance.
On va supposer pour simplifier :
- que le camion n'entame son premier voyage que s'il reçoit au moins une demande
- que quand le camionneur reçoit une ou plusieurs demandes, et qu'il est sur sa route vers un fournisseur, il ne modifie son itinéraire qu'après avoir visité ce fournisseur.
- que la méthode de résolution du problème du voyageur de commerce est connue.

On suppose aussi qu'au départ le camionneur collecte les demandes durant un certain temps, mais ce temps d'attente sera limité, sinon il attendra jusqu'à collecter toutes les demandes et ce sera un problème classique. On suppose aussi que quand il aura visité le dernier fournisseur programmé, mais qu'il restera encore des fournisseurs qui n'ont pas émis leur demandes, le camionneur décide de rentrer à l'entrepôt, et de terminer son voyage, au bout d'un certain temps d'attente fini.
Êtes vous d'accord avec ces hypothèses ?

Invité
Invité


Revenir en haut Aller en bas

Re: Aide formulation mathématique problème dynamique du voyageur de commerce

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum