Programme linéaire inspiré du problème du voyageur de commer

[admiré]

Bonjour à tous,

Je suis depuis un bon moment sur cette variante du problème de voyageur du commerce..
Je ne parviens pas à la résoudre. S'ils vous plait, pourriez-vous me donner quelques orientations pour y parvenir?


Voici le problème et un exemple:


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.

É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.

[url="http://www.hebergementimages.com/image-04e093208fd062aa9234774b73fc5c6d_VRP.bmp.html"][/url]
Lien sponsorisé : [url="http://www.reductionet.com"]reduction[/url]




Merci d'avance de votre aide!

[fatal_error]

salut,

ya que le graphe qui change non.
J'imagine que tu sais résoudre le pvc avec prog linéaire.

Donc au tout début mettons, tu calcules un itinéaires.
Une fois calculé, tu le parcours.
A chaque fois que tu passes par un entrepot, tu marques l'entrepot.

Soudain, un évènement arrive et un nouvel entrepot est à visiter.
Tu recalcules pour chaque entrepot que tu n'as pas visité la distance avec le nouvel entrepot.
Ca te fait un nouveau graphe (ou on a enlevé les entrepots marqués (vu que t'es passés dessus, ils servent plus a rien)).
Pis rebelotte.

[admiré]

salut,

ya que le graphe qui change non.
J'imagine que tu sais résoudre le pvc avec prog linéaire.

Donc au tout début mettons, tu calcules un itinéaires.
Une fois calculé, tu le parcours.
A chaque fois que tu passes par un entrepot, tu marques l'entrepot.

Soudain, un évènement arrive et un nouvel entrepot est à visiter.
Tu recalcules pour chaque entrepot que tu n'as pas visité la distance avec le nouvel entrepot.
Ca te fait un nouveau graphe (ou on a enlevé les entrepots marqués (vu que t'es passés dessus, ils servent plus a rien)).
Pis rebelotte.

Merci beaucoup pour votre réponse.

Il n ' y a pas un moyen pour résoudre le problème sans refaire un autre programme chaque fois un nouveau évènement apparait? Y a t-il une technique qui permet d'intégrer la dimension dynamique au programme sans refaire un nouveau programme ?

Merci de votre réponse.

[fatal_error]

re,

a mon avis (c'est que mon avis) je pense que on est obligé de recomputer.
Là, comme ca, pour intégrer ton problème de manière dynamique, je vois que de la prog dynamique (...).

Le problème, c'est qu'a supposer qu'on se fasse une prog dynamique (a la place de l'opti linéaire), bien qu'on construit une table avec les minimums des distances des chemins entre chaque noeud, on intègre pas au plus petit détail ce que ca donnerait avec notre nouveau noeud.

De fait, il faudrait recomputer la table (du moins l'étage du bas (ou ya les plus cours chemins de trois noeuds), avec eventuellement les répercussions sur les étages du dessus).
Bref, je suis sceptique, mais ca me dépasse un peu. Pe est-ce possible.

J'ajoute qu'en revanche on peut toujours essayer de faire une heuristique avec des clusters des noeuds les plus proches et de faire appartenir le nouveau noeud à un cluster de manière à "minimiser" les longs trajets (entre clusters)

[admiré]

re,

a mon avis (c'est que mon avis) je pense que on est obligé de recomputer.
Là, comme ca, pour intégrer ton problème de manière dynamique, je vois que de la prog dynamique (...).

Le problème, c'est qu'a supposer qu'on se fasse une prog dynamique (a la place de l'opti linéaire), bien qu'on construit une table avec les minimums des distances des chemins entre chaque noeud, on intègre pas au plus petit détail ce que ca donnerait avec notre nouveau noeud.

De fait, il faudrait recomputer la table (du moins l'étage du bas (ou ya les plus cours chemins de trois noeuds), avec eventuellement les répercussions sur les étages du dessus).
Bref, je suis sceptique, mais ca me dépasse un peu. Pe est-ce possible.

J'ajoute qu'en revanche on peut toujours essayer de faire une heuristique avec des clusters des noeuds les plus proches et de faire appartenir le nouveau noeud à un cluster de manière à "minimiser" les longs trajets (entre clusters)

Merci beaucoup pour votre réponse.
L'objectif est de proposer une formulation mathématique pour résoudre le problème et de le tester en utilisant méthode exacte comme Branch and Bound implantéedans Ilog CPLEX ou LINGO

Une dernière question SVP, si on procède à résoudre le problème par la programmation linéaire en nombre entier, comment faire l'expérimentation sur des jeux de données?(car les modèles sont dissociés, non?) :help:

Merci d'avance.

[fatal_error]

salut,

je peux pas t'en dire plus, je connais pas la prog linéaire en nombre entiers, et même si j'avoue que ca m'intrigue, j'ai pas le temps (probablement) pour bien y piger. Donc j'peux pas t'aider plus :triste: