Programmation linéaire - optimisation tournée logistique - solveur
Salut à tous!
Dans le cadre d'un projet d'études, je souhaite optimiser une tournée de transport.
Le but de cette modélisation est d'optimiser les flux B2B entre les entreprises du schéma dispo dans la feuille "Présentation" du xls ci-joint.
Les flèches couleurs foncées représentent un trajet avec un camion chargé ; les flèches de couleurs claires représentent un trajet avec un camion vide.
L'optimisation consiste donc à ne faire qu'une seule tournée (un seul camion) afin d'avoir un minimum de camions vides.
J'ai créé la feuille suivante :
Tableau bleu D : distance inter-entreprises
Tableau vert Y : contraintes ; soit le volume que souhaite transporter une entreprise, sous la forme y_i,j (cellule H14 = 2m^3 à transférer de B vers A)
Tableau jaune X : les étapes de la tournée du camion optimisée (c'est le solveur qui rempli ce tableau)
Les cellules conditions sont pour le solveur, le camion doit passer par chaque entreprise (nb_p et nb_s)
Z correspond à la cellule B20, soit la somme du produit de la matrice D (tableau bleu) par la matrice X (tableau jaune).
Mon problème est le suivant :
Comment prendre en compte mes contraintes Y (tableau vert) dans ma modélisation ? Autrement dit, comment faire pour que le solveur sache que le camion doit déplacer 2m^3 de B vers à A.
++!
PS : je suis désolé je ne peux pas encore up de captures car je viens tout juste de m'inscrire
Vous avez une réponse a votre problème ici:
Cdt
Merci pour votre réponse ; je m'aide justement de ce bouquin pour construire mon modèle mais je butte quand même...
J'étais partis sur l'exemple type loueur de voiture puis livraison de fioul. Mais je n'arrive toujours pas à trouver comment prendre en compte ma contrainte de livraison.
C'est la livraison de fioul qui peut vous mettre sur la voie, je n'ai plus le livre et je pense que la solution doit-être assez compliquée, bon courage!
Yes, merci!
J'ai un peu avancé et nouveau problème : le solveur ne respecte pas la condition X = binaire (X étant ma matrice d'étapes, en jaune).
Si quelqu'un a une idée, je suis preneur !
Bonne soirée à tous
Hey!
Je bosse toujours sur le sujet, si quelqu'un à une idée, qu'il n'hésite pas !
Bon après-midi !
Bonjour,
L'optimisation consiste donc à ne faire qu'une seule tournée (un seul camion)
ceci signifie-t-il que la demande ne peut jamais être supérieure à la capacité d'un seul camion ?
si c'est le cas, le problème se limite à trouver le chemin le plus court pour visiter tous les clients qui ont commandé quelque chose, il n'est pas nécessaire de gérer la quantité commandée dans le calcul d'optimisation.
l'utilisation du solver est-elle imposée ?
Yes c'est ça ; la contrainte de quantité est clairement facultative.
L'utilisation du solver n'est pas imposé mais il me semble que ce problème peut être résolu avec le solver. Si tu as une idée plus simple, je suis très intéressé
Bonsoir,
cela revient à résoudre le problème classique du voyageur de commerce.
une solution en vba, car le solveur a parfois du mal à gérer les contraintes (type bin, dif, ent, ...)
introduire le tableau des distances en G3 (maximum 12 destinations), commencer par le point de départ.
la macro recherche un chemin optimum partant du point de départ, visitant toutes les destinations pour revenir au point de départ.
Bonjour,
Merci pour l'aide!
Cependant, j'ai quand même une question : comment faire pour que la macro prenne en compte "par où passer en premier" ?
Je m'explique, la macro propose le trajet suivant : départ-A-B-C-E-D-départ. Le hic, c'est que A doit être livré de pièce B et C, donc il n'est pas possible de commencer la tournée par A (cf le schéma sur la feuille "présentation").
Bonne journée
re-bonjour,
voici une solution similaire à ma solution vba mais avec le solver. (Qui tient compte de la dernière contrainte que tu as mentionnée)
on demande au solveur de trouver l'ordre de passage (numéros tous différents et entier) pour chaque destination, minimisant le trajet.
pour indiquer qu'une destination doit être atteinte avant une autre, il suffit d'ajouter des contraintes sur le numéro de passage. (in casu, le n° de passage de A doit être supérieur au n° de passage de B et de C)
Merci beaucoup pour ta contribution.
Je pense avoir compris ce que tu proposes ; malheureusement la résolution via GRG non linéaire fait planter Excel à chaque fois et le Simplex n'est pas applicable..
Décidément, je pensais que je pourrais gérer les contraintes de livraison via une matrice type x_i,j mais ça m'a l'air assez compliqué au final.
re-bonjour,
malheureusement la résolution via GRG non linéaire fait planter Excel à chaque fois et le Simplex n'est pas applicable..
je n'ai pas de problème avec la solution proposée sur ton fichier. (je te confirme que le simplex n'est pas applicable).