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

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,

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?

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

Merci encore.

Bonjour,

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

Cite quelques références.

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 ?

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 ?