TP2 - GSO 6114 tournées des véhicules

[pic 1][pic 2]

Travail 2 : Planification des tournées de véhicules

Professeur : Jean-Philippe Gagliardi

GSO 6114

[pic 3]

Table des matières

1. INTRODUCTION        2
2. Question 1        2
3. Question 2        7
4. Partie B        8

1. Question 1        8
2. Question 2        9
3. Question 3        9

1. Annexes        11

1. Matrice des distances        11
2. Matrices des temps        11
3. Matrice des économies de distance        12
4. Matrice des économies de temps        12

1. INTRODUCTION

La planification des tournées est un enjeu essentiel de la logistique et son bon déroulement dépend étroitement des connaissances en mathématiques et nécessite d’avoir des connaissances permettant de résoudre des problèmes de type voyageur de commerce. Pour notre mandat, nous allons effectuer une planification de tournées de véhicule a laide de l’heuristique constructive de Clarke et Wright. D’une manière complémentaire et dynamique, nous allons réaliser une étude analytique ou nous calculons les matrices d’économie qui nous permettront par la suite de dresser les routes optimales pour notre camion de livraison sur le logiciel Optiroutes. De ce fait notre objectif est de trouver les routes qui sont les plus bénéfiques pour que l’entreprise puisse réaliser un grand nombre de livraisons tout en minimisant les couts.

1. Question 1

Afin de résoudre trouver la meilleure planification de tournées de véhicules, nous avons opté pour l’algorithme Clarke and Wright. L’instance à résoudre représente 40 points de livraison avec deux contraintes :

• Le temps maximal par tournée : 540 minutes

• La charge maximale par camion : 1000 KGs

A partir du fichier CSV, nous avons eu accès aux deux matrices de distance à parcourir entres les clients, ainsi que le temps nécessaire pour l’accomplir, tel on le voit ci-dessous :

La première étape consiste à calculer la matrice des économies en termes de distance et de temps, le principe est simple : il est toujours optimal d’utiliser une tournée au lieu de faire un aller-retour du dépôt puis recommencer un nouveau trajet.

[pic 4][pic 5]

[pic 6]

Figure 2: Extrait matrice de temps entre les clients (en min.)

Dans ce qui suit, nous avons nommé :

• Le point 0 comme le dépôt

• Les clients à visiter sont numérotés de 1 à 40

• L’économie en termes de distance porte l’abréviation D et les deux points concernés (Exemple, l’économie D1-14 signifie que la tournée suit la route 0-1-14-0

• L’économie en termes de temps porte l’abréviation T et les deux points concernés

Nous avons calculé les deux matrices d’économies à l’aide d’une formule dynamique Excel :

=IF($A2=C$1,0,Distance!$B3+Distance!D$2-Distance!D3)

[pic 7][pic 8]

Figure 3: principe des économies de Clark and Wright

Ci-dessous une capture des matrices calculés :

[pic 9]

Figure 4: matrice des économies en termes de distance (en Km)

[pic 10]

Figure 4: matrice des économies en temps (en min.)

Par la suite, nous avons procédé à un classement décroissant de la plus grande économie en fonction du temps et la distance. Dans la suite de la solution, nous allons se baser sur les économies de temps pour appliquer l’algorhtme Clark and Wright, la figure ci-dessous montre un extrait des économies classées :[pic 11]

Nous avons aussi constaté que les matrices sont symétriques, ce qui veut dire que les distances entre les points X et Y est le même qu’entre Y et X. Ceci se répercute sur la formule d’économie et dicte que DX-Y est égale à DY-X.

Nous commencons alors par appliquer l’algorhytme Clark and Wright par ordre décroissant. Nous remarquons que la plus grande économie est de lié les points de livraison 35 et 36, la nouvelle route sera alors : 0-35-36-0. La durée totale sera de : 217.3 min, la distance totale

est de : 210.35 Km avec une charge de : 150 KGs, le détail du calcul est ci-bas :

• Durée de 0 à 35 et de 35 à 0 : 70.68 min x 2 = 141.36 min
• Durée de 0 à 36 et de 36 à 0 : 81.97 min x 2 = 163.94 min
• Economie T35-36 = 138 min

- 2éme Economie T17-18 et T16-17 : 216.47 km

oDeuxiéme route : 0-16-17-18-0

oDistance totale : 384.82 km – 216.47= 168.35 Km

oCharge : 177 KGs

oDurée : 240.41 min

- 3éme économie : T34-35 : 94.5 Km

oPremiére route devient : 0-34-35-36-0

oDistance totale : 210.35 Km + (49.87x2) – 94.5 Km = 215.59 Km

oCharge : 270 KGs

oDurée : 240.3 min

• 4éme économie : T34-36 : ne peut pas être faite car les points 34 et 36 font déjà partie de la même tournée
• 5éme économie : T16-18 : ne peut pas être faite car les points 16 et 18 font déjà partie de la même tournée
• 6éme économie : T32-33, T29-33, T30-33, l’économie

totale est : 238.38 min

oLa route sera : 0-29-30-32-33-0

oDistance totale : 91.17 km

oCharge : 245 Kg

...