Bonsoir à tous! j'ai un probléme de cas "Tournée de livraison"
Plan de transport et Gestion des livraisons
Les problèmes de tournées de véhicules sont souvent très complexes à résoudre. Les contraintes à prendre en compte peuvent être multiples : capacité des véhicules, fenêtres de temps pour visiter le client, temps maximum de conduite .... De nombreuses variantes de problèmes existentce qui en fait son intérêt pour les industriels et les scientifiques.
Le plus simple d’entre eux (avec un seul véhicule), le problème du « voyageur de commerce »qui consiste à partir d’un entrepôt, à réaliser les N livraisons programmées puis de revenir au point de départ tout en essayant de minimiser la distance parcourue ou le temps passé est mathématiquement très difficile à résoudre. Le nombre de combinaisons à envisager (N!) est très vite énorme même pour des petite valeur de N et les temps de calcul pour les évaluer toutes deviennent prohibitifs. .Dans certains cas la solution optimale n’est pas trop difficile à trouver, c’est le cas où dans véhicules doivent effectuer une série de ramassages et de livraisons successives tout en respectant des dates de mise à disposition du ramassage. C’est typiquement le cas de livraisons inter-usines où un où plusieurs véhicules doivent alimenter des usines de montage à partir d’usines fournissant les pièces détachées, les dates de mise à disposition devenant des dates impératives dans un contexte de juste à temps.
On considère le petit exemple suivant avec 7 livraisons à effectuer, caractérisées par un chargement sur un site expéditeur suivi d’une livraison sur le site destinataire. L’heure de chargement est à respecter impérativement pour chaque livraison, elle est donnée dans le
tableau ci-dessous :
N° Livraison____________1__ 2__ 3__ 4__ 5__ 6__ 7__
Heures de chargemement 8h_11h_ 12h_ 12h_ 10h_ 10h_ 9h
exour la livraison 1 c'est fait à 8H, 2 à 11H....etc
Compte tenu des volumes à transporter, un véhicule ne peut assurer qu’une livraison (enlèvement suivi de la livraison) à la fois. D’autre part, connaissant les points de déchargement de chaque livraisons, on peut calculer les temps Tij pour réaliser la livraison et ensuite se rendre au rendre au point d’enlèvement de la livraison j. En remarquant qu’aucune livraison ne peut suivre les livraisons 3 et 4, et que 1 ne peut succéder à aucune livraisons les temps Tij sont données dans le tableau ci-dessous :
(PL=Point de livraison)
Tij (en heures)
PL__________point de ramasse j______
_______ 2 3 4 5 6 7
__1____ 2 3 3 3 2 2
__2____ - 4 1 2 1 1
__5____ 3 2 2 - 1 2
__6____ 1 2 1 1 - 1
__7 ____ 1 2 2 1 2 -
Par exemple T14 = 3 car il faut 3 heures pour réaliser la livraison 1 (chargement, transport,déchargement) et se rendre au point d’enlèvement de la livraison 4. Bien sûr, pour un chargement, un véhicule peut arriver en avance et attendre. On cherche ainsi un plan de transport qui minimise le nombre de véhicules utilisés. Il en faut au moins 2 puisque les livraisons 3 et 4 ne peuvent être réalisés par le même véhicule mais combien exactement ?
1. Résoudre à la main l’exemple donné ici.
2. Proposer une ou plusieurs stratégies (i.e. règles de choix pour planifier les livraisons) et les comparer pour décider de la meilleure à choisir sur l’exemple donné. Y a-t-il une règle permettant de trouver une solution optimale ?
3. En regardant ce problème sous l’angle de l’optimisation, donner le modèle mathématique correspondant et implémenter celui-ci sur l’outil de votre choix (Excel, Xpress...).
Merci d'avance, Chezka
-----