CHAPITRE 6 : OPTIMISATION COMBINATOIRE

Introduction
L'optimisation combinatoire permet de représenter ombreux problèmes économiques, nous nous intéressons ici
pour l'essentiel à la méthode de-Stepping Stone et à l'algorithme de
Kruskal.

1. LA METHODE DE STEPPING STONE

Elle se caractérise par l'existence des éléments suivants : un ensemble de m origines, un ensemble de n
destinations, une offre de même nature ai à chacune des origines, une demande de même nature b] à chacune des
destinations, un ensemble de coûts Unitaires de transport des origines vers les destinations, Xij représente es
quantités transportés des origines vers destinations. On essaye de satisfaire la de e au coût minimal, la méthode obéit
à trois étapes selon qu'on passe par le coin nord-ouest ou que l'on passe par houthakker.
Destination 1 2 3 4 Total
Dépôts

5 C1,5 C2,5 C3,5 C4,5 A

X1,5
X2,5 X3,5 X4,5
6 C1,6 C2,6 C3,6 C4,6 B
X1,6 X2,6 X3,6 X4,6
7 C1,7 C2,7 C3,7 C3,7 C
X1,7 X2,7 X3,7 X4,7
Total D E F G

Les contraintes1 possibles sont les suivantes.

Contraintes logiques ou non négatives ≥ 0≥ 0
: :XijXij ;;
0O0O
A A
Contraintes des origines :

1
les contraintes sont sous la forme d'une maximisation, parce que le principe de cette méthode consiste à saturer progressivement les
capacités disponibles au niveau des origines pour satisfaire la demande.
 Contraintes des destinations :

1- Méthode du coin Nord-Ouest

Application
Trois (03) dépôts A. B et C disposent respectivement de 30, 20 et 45 tonnes de marchandises, quatre (04)
destinations D, E, F et G, en demande des quantités respectives de 10, 25, 20 et 40 tonnes. La matrice des coûts
unitaires de transport est la suivante :
E
A 12 27 61 49
B 23 39 78 28
C 67 56 90
Etablir le meilleur plan de transport c'est-à-dire celui qui assure au moindre coût le transport des quantités demandés
on utilisera la méthode de stepping stone (coin nord-ouest).
Solution
Cette méthode consiste à commencer la saturation par le coin du tableau (origine) jusqu'à la dernière destination.
Pour le faire, on procède en trois étapes.

NB: chaque solution aura n * m - (n + m - 1) cases vides.

a- Détermination de la solution de base
Le tableau de base aura : n * m - (n + m - 1)= 3 * 4 - (3 + 4 -1) = 6 cases vides
Destination D E F G Total

Dépôts
A 12 27 61 49 30

10 20
B 23 39 78 28 20
5 15
C 67 56 90 24 45
5 40
Total 10 25 20 40

Il faut toujours s'assurer que total demande = total offre si non, on ajoute une ligne ou une colonne fictive égal à la
différence.
La solution de base consistera à transporter
 10 unités du dépôt A vers le magasin D,
 20 unités du dépôt A vers le magasin E,
 5 unités du dépôt B vers le magasin E,
 15 unités du dépôt B vers le magasin F,
  5 unités du dépôt C vers le magasin F,
 40 unités du dépôt C vers le magasin G.
Le coût total (CT) = 10*12 + 20*27 + 5*39 + 15*78 + 5*90 + 40*24 = 3435
Une solution sera dite optimale si tous les coûts marginaux calculés sont positifs ou nuls.
Il faut toujours se poser la question : La solution de base est-elle optimale ?
Pour répondre à cette question, il faut calculer des couts marginaux dans les cases vident il s'agit ici d'évaluer ce qui
couterait à l'entreprise une unité additionnelle dans une case qui initialement était vide, on va ainsi calculer 6 coûts
marginaux.
Calcul des coûts marginaux :

δ(B,D) =(B,D)-(A,D)+(A,E)-(B,E) = 23-12+27-39 = -1

δ(C,D)=(C,D)—(A,D)+(A,E)-(B,E)+(B,F)-(C,F)= 67-12+27-39+78-90 = 31
δ(C,E)= (C, E) - (C,F) + (B, F) - (B,E) = 56 - 90 + 78 - 39 = 5
δ(A,F)=(A,F)-(B,F)+(B,E)-(A,E)= 61-27+39-78 = -5
δ(A,G)=(A,G)—(C,G)+(C,F)-(B,F)+(B,E)-(A,E)= 49-24+90-78+39-27 = 49
δ(B,G)= (B, G) - (B, F) + (C,F) - (C, G) = 28 - 78 + 90 - 24 = 16
D'après le résultat du calcul des coûts marginaux, on constate que la solution de base n'est pas optimale puisque
δ(B,D) = -1 et δ(A,F) = -5 sont négatifs.
b- Amélioration de la solution de base

pour améliorer la solution de base, nous allons considérer le coût marginal le plus négatif c'est-à- dire δ(A,F) = -5. Il
s'agit de regarder dans la chaine de substitution permettant son calcul et identifier les cases qui viennent en
soustraction, il s'agit des cases (B, F) et (A, E).
Dans la case (A, E) la quantité transportée est 20 alors que dans la case (B, F) la quantité transportée est 15, on va
alors transporter la plus petite quantité 15 dans la chaine de substitution de la case (B, F).
Le tableau amélioré :

Destination D E F G Total

Dépôts
A 12 27 61 49 30

10 5 15
B 23 39 78 28 20
20
C 67 56 90 24 45
5 40
Total 10 25 20 40
 La nouvelle solution consiste à transporter 10 unités du dépôt A vers le magasin D, 5 unités du dépôt A vers le
magasin E, 15 unités du dépôt A vers le magasin F, 20 unités du dépôt B vers le magasin E, 5 unités du dépôt C
vers le magasin F, 40 unités du dépôt C vers le magasin G.
Le coût total : 10*12 + 5*27 + 15*61 + 20*39 + 5*90 + 40*24 = 3360

On constate que le coût total de la nouvelle solution a diminué, mais cette solution de base est- elle Optimale ?
Pour répondre à cette question, il faut calculer à nouveau les couts marginaux dans les cases vides.

Calcul des coûts marginaux :

δ(B,D) = (B,D) - (A,D) + (A,E) - (B,E) = 23 - 12 + 27 - 39 = - 1
δ(C,D) = (C,D) - (A,D) + (A,F) - (C,F) = 67 -12 + 61 - 90 = 26
δ(C,E) = (C,E) - (C,F) + (A,F) - (A,E) = 56 - 90 + 61 — 27 O
δ(B,F) = (B,F) - (A,F) + (A,E) - (B,E) 78 - 61 + 27 - 39 5
δ(B,G) = (B,G) - (C,G) + (C,F) - (A,F) + (A,E) - (B,E) = 28 - 24 + 90 - 61 + 27 - 39 = 21

δ(A,G) = (A,G) - (C,G) + (C,F) - (A,F) = 49 - 24 + 90 - 61 = 54

Pour améliorer la solution ci-dessus, nous allons considérer le coût marginal le plus négatif c'est-à-dire δ(B,D) = -
1. Il s'agit de regarder dans la chaine de substitution permettant son calcul et identifier les cases qui viennent en
soustraction, il s'agit des cases (A, D) et (B, E).
Dans la case (A,D) la quantité transportée est 1(), alors que dans la case (B,E) la quantité transportée est 20, on va
alors transporter la plus petite quantité 10 dans la chaine de substitution de la case (B, D).
c) Détermination de la solution optimale

Destination D E F G Total

Dépôts
A 12 27 61 49 30

15 15
B 23 39 78 28 20
10 10
C 67 56 90 24 45
5 40
Total 10 25 20 40
La nouvelle solution consiste à transporter 10 unités du dépôt B vers le magasin D, 10 unités du dépôt B vers le
magasin E, 15 unités du dépôt A vers le magasin F, 15 unités du dépôt A vers le magasin E, 5 unités du dépôt C vers
le magasin F, 40 unités du dépôt C vers le magasin G.

Le Coût total (CT) = 10*23 + 15*27 + 15*61 + 10*39 +5*90 + 40*24 = 3350
On constate que le coût total de la nouvelle solution a diminué, mais cette solution est elle optimale ? Pour
répondre à cette question, il faut calculer à nouveau les coûts marginaux dans les cases vides.
Calcul des coûts marginaux :
 δ(B,D) = 12 – 23 + 39 – 27 = 1
δ(C,D) = 67-23 + 39-27 + 63 - 90 = 29
δ(C,E) = 56 - 90 + 61 - 27 = 0
δ(B,F) = 78 - 61 + 27 - 39 = 5
δ(B,G) = 28 – 24 + 90 -61 +27 -39 = 21
δ(A,G) = 49 — 24 + 90 — 61 = 54
Le résultat du calcul des coûts marginaux montre que tous sont positifs ou nul, par conséquent nous sommes à
l'optimum et on a :
(B,D) = 10 ; (B,E) = 10 ; (A,E) = 15. (A,F) = 15 ; (C,F) = 5 ; (C,G) = 40

2- Méthode Houthakker

Exemple :
Trois (03) dépôts A, B et C disposent respectivement de 9, 17 et 9 tonnes de marchandises, quatre

(04) destinations D, E, F et G en demande des quantités respectives de 10,14, 7 et 4 tonnes. La matrice des coûts
unitaires de transport est la suivante :

A 260 150 170

B 280 250 150 310
C 200 160 70 280
Etablir le meilleur plan de transport c'est-à-dire celui qui assure au moindre coût le transport des quantités
demandés on utilisera la méthode de stepping stone (méthode houthakker).
Solution :
a- Détermination de la solution de base

Cette méthode consiste à commencer la saturation des liaisons au plus faible coût conduit :
A alimenter la demande totale de F par C ;
A livrer la totalité de la production de A à E ;
A livrer le solde de la production de C à E ;
A répartir la production B pour solder la demande de E, D et G.
Remarque :
Si deux cases sont de coût minimum, on choisira celle où l'on peut attribuer le plus grand nombre ceci aura pour
effet de mettre comme coefficient du coût minimum la plus grande valeur d'une variable.
Le tableau de base :
Destination D E F G Total

Dépôts
A 260 150 140 170 9

9
 B 280 250 150 310 17
10 3 4
C 200 160 70 280 9
2 7
Total 10 14 7 4 35
Le Coût total (CT) = 10*280 + 9*150 + 3*250 + 2*160 + 7*70 + 4*310 = 6950
La solution de base est-elle optimale ? Pour répondre à cette question, il faut calculer des coûts marginaux dans les
cases vident il s'agit ici d'évaluer ce qui couterait à l'entreprise une unité additionnelle dans une case qui initialement
était vide, on va ainsi calculer 6 coûts marginaux
Calcul des coûts marginaux .
(A.G) = - 40 ; ABF) = - 10
D'après le résultat du calcul des coûts marginaux, on constate que la solution de base n'est pas optimale puisqu'on
a deux coûts marginaux négatifs. Pour améliorer la solution de base on va procéder à des permutations.
Pour le cout marginal (A, G) : on peut alimenter la demande totale de G par A , à livrer le solde de la
production de A à E à transporter la demande totale de G à E en passant par
Pour le cout marginal (B, F) : on peut alimenter la demande totale de F par B, à transporter la demande
totale de F à E en passant par C ; à soustraire la demande totale de F à E en passant par B.
b) Détermination de la solution optimale

Destination D E F G Total

Dépôts
A 260 150 140 170 9

5 4
B 280 250 150 310 17
10 7
C 200 160 70 280 9
9 7
Total 10 14 7 4 35
Le Coût total = 6950 – (4*40 + 7*10) = 6720

Le Coût total (CT) = 10*280 + 5*150 + 9*160 + 7*150 + 4*170 = 6720

Le résultat du calcul des coûts marginaux montre que tous sont positifs ou nul, par conséquent nous sommes à
l'optimum et on a :

11. METHODE DES ECARTEMENTS : ALGORITHME DE KRUSKAL ( GESTION

 DES TOURNEES)

La planification des tournées de livraison peut s'effectuer suivant deux techniques :

 la tournée fixe;
 la tournée variable.
La tournée fixe : comme son nom l'indique consiste à fixer des tournées, à partir de données établies au préalable, et
pour une période donnée (semaine, mois.. Ce principe est simple mais présente plusieurs inconvénients notamment :
 il ne garantit pas le remplissage optimal des véhicules;
 il fige le planning de tournées de livraison donc n'optimise pas l'organisation en termes de client à livrer et de
distance minimum à parcourir.
La tournée variable : elle consiste à fixer chaque jour les tournées en fonction de la demande (quantité à livrer,
localisation des clients) et des véhicules disponibles. On engage ainsi un nombre variable de véhicules lesquels
parcourent un circuit variable, en fonction du tonnage à distribuer et de la localisation des clients à livrer.
a- La recherche d'une solution optimale
La résolution d'un tel problème ne peut se faire manuellement compte tenu du nombre de possibilités de solutions
qui existent. De nombreux progiciels d'optimisation permettent de traiter ce type de problème. Ils utilisent le plus
souvent l'algorithme des écartements conçu par Kruskal. Cette méthode fournit une approche d'une solution mais
pas nécessairement la meilleure.
Son objectif vise à minimiser la distance à parcourir ou la durée de chaque tournée. Elle repose sur la notion simple
de gain ou d'écartement défini comme suit :

 - - l ière solution

2e solution

Soit un dépôt O et deux clients A et B. On veut trouver le plus court chemin permettant de livrer

A et B à partir de O.
Deux solutions s'offrent à nous :
 Approvisionner A, retourné au dépôt, puis livrer B et revenir en O.
 Approvisionner A puis B au cours de la même tournée.
Les distances parcourues s'écrivent alors :
 le solution : D1 = 2 d(O,A) + 2 d(O,B)
 2e solution : D2 = 2 d(O,A) + d(A,B) + 2 d(O,B)
 On appelle gain ou écartement du couple de points A, B par rapport au centre O, la différence entre ces deux
solutions c'est-à-dire en termes de quantités :
G(A,B) = D2 – D1 = 2 d(O,A) + d(O,B) + 2 d(A,B)
G(A,B) représente donc le gain obtenu en intégrant ces deux points dans une même tournée. La détermination
des tournées va débuter en considérant, en premier lieu, les couples de points présentant l'écartement le plus
élevé possible.
On démontre que, pour une localisation donnée du dépôt, minimiser la longueur de la tournée revient à maximiser la
somme des écartements.
La procédure d'application de la méthode se définit comme suit :
- calculer les écartements de tous les couples de points par rapport au centre ;
- les classer par importance décroissante;
- sélectionner chaque couple de la liste; abandonner ceux formant une boucle ou une fourche avec ceux
précédemment sélectionner (on s'interdit de passer plusieurs fois en chaque point);
- arrêter la procédure en fonction des contraintes de tonnage, de temps...
- joindre le centre à ces deux extrémités.
a- Le nombre d'écarts est calculé à partir de la formule :
n*(n - 1)
Cn =
2
2

où n est le nombre de villes à desservir.

b- le taux de remplissage de chaque véhicule est calculé par la formule :
Charge
Taux de remplissage = x 100
Charge utile

Application
Une entreprise P doit livrer cinq clients A, B, C, D, E à partir de son dépôt O avec un véhicule de
10 tonnes. L'objectif est de composer une tournée de livraison dans le but de parcourir la plus petite distance.
Tonna e à livrer Dépôt A B D E
C
A 23 32 38 15 17

B 1,8 15 28 19 25
-
C 1,2 18 38
- 35
D 2,3 24 20
-
33
-
Sont indiqués dans le tableau suivant :
 les distances entre chaque client (en km);
 les distances entre l'entreprise et chaque client (en km);
  les tonnages à livrer par jour et par client.
Solution :
- Le nombre d'écarts est calculé à partir de la formule :

n*(n - 1)
C 2n = 2

AN
5(5 – 1)
= 10 écarts
C 2n = 2

- On calcule le gain pour chaque couple de points par rapport à l'entreprise O, comme suit :
G(A,B) = d(O,A) + d(O,B) - d(A,B) = 23 + 15 - 32 = 6 ;
G(A,C) = d(O,A) + d(O,C) - d(A,C)= 23 + 18 – 38 = 3 ;
G(B,C) = d(O,B) + d(O,C) - d(B,C) = 15 + 18 - 28= 5 ;
G(C,D) = d(O,C) + d(O,D) - d(C,D)= 18 + 24 – 7 = 7 ;
G(A,D) = d(O,A) + d(O,D) - d(A,D) = 23 + 24 - 15 = 32;
G(B,D) = d(O,B) + d(O,D) - d(B,D)= 15 + 24 - 19=20 ;
G(C,E) = d(O,C) + d(O,E) - d(C,E)= 18 + 33 -38 = 13 ;
G(A,E) = d(O,A) + d(O,E) - d(A,E)= 23 + 33 - 17=39 ;
G(B,E) = d(O,B) + d(O,E) - d(B,E) = 15 + 33 - 25=23 ;
G(D,E) = d(O,D) + d(O,E) - d(D,E)= 24 + 33 - 20=37.
Ensuite, on classe les gains des couples par ordre décroissant :
(A,E) ; (D,E); (A,D); (B,E); (B,D); (C,E); (C,D) ; (B,C) ; (A,C).

On trace alors la tournée en sélectionnant chaque couple les uns après les autres sans considérer les clients déjà
intégrés et en évitant de former des boucles dans la tournée ce qui donne : [A,E]; [D,E]; pas [A,D] (car cela
formerait une boucle); pas [B,EI•, [B,D]; pas [C,E]•, pas [C,D]•, [B,C] puis on joint le dépôt O.

La tournée de livraison donne :

On vérifie que :
 La somme des tonnages livrés ne dépasse pas la charge utile du véhicule :
(3+2,3+1,8+1,2+1 = 9,3 tonnes) ;
  La longueur de la tournée (23+17+20+19+28+18=125 km).

Cette méthode est utilisée par de nombreux gestionnaires de transport, consciemment ou non, mais toujours
à l'aide de logiciels au vue du nombre de données à traiter. Cependant, comme toujours cette méthode a des
limites et les résultats peuvent être variables suivant les contraintes à considérer :
- les distances et les tonnages doivent être fiables;
- la contrainte horaire (que ce soit celle du chauffeur ou celle des clients à livrer) peut être déterminante;
- enfin, le relief du parcours est une donnée totalement absente de la procédure.
- Il semble donc indispensable de bien poser les données au départ, c'est alors une méthode incontournable
par sa fiabilité.