Département d’Informatique

Laboratoire d’Informatique d’Oran (LIO)

Thèse
Pour l'obtention du

Doctorat en LMD
Domaine : Mathématique et Informatique
Filière : Informatique
Spécialité : Informatique de la Répartition et Aide à la Décision (IRAD)
Présentée Par

Oualid GUEMRI

Proposition de solutions pour l'optimisation

des chaînes logistiques

Soutenue le 23/01/2017 à 10h devant un Jury composé de :

Mr. Karim BOUAMRANE Professeur, Université d’Oran 1, Ahmed BenBella Président du jury
Mr. Bouziane BELDJILALI Professeur, Université d’Oran 1, Ahmed BenBella Directeur de thèse
Mr. Larbi SEKHRI Professeur, Université d’Oran 1, Ahmed BenBella Examinateur
Mr. Mohamed BENYETTOU Professeur, Université USTO-MB Oran Examinateur
Mr. Zakaria El-BERRICHI Professeur, Université de Djillali Liabès Sidi Bel- Examinateur
Abbes
Mr. Mohamed Fayçal KHELFI Professeur, Université d’Oran 1, Ahmed BenBella Examinateur
Mr. Ghalem BELALEM Professeur, Université d’Oran 1, Ahmed BenBella Invité

Année universitaire 2016/2017

 Remerciements

Louange à ALLAH qui nous a donné la force et la volonté qui nous a permis d’achever les
travaux de cette thèse.

Je tiens à exprimer toute ma profonde gratitude, mes remerciements les plus vifs et mes
reconnaissances les plus sincères à Monsieur Bouziane BELDJILALI, Professeur à
l’Université d’Oran1, Ahmed BenBella, pour m’avoir encadré, aidé et soutenu durant ces
années de thèse. Je lui remercie aussi pour sa sagesse, sa patience, ses qualités humaines,
et surtout les précieux conseils et les connaissances dont il a su me faire profiter.

J’exprime ma profonde gratitude et mes très sincères remerciements à Monsieur

Ghalem BELALEM, Professeur à l’Université d’Oran 1, Ahmed BenBella, pour m’avoir
honoré en faisant partie du jury de cette thèse. Je le remercie aussi pour sa disponibilité,
ses conseils, ses orientations et ses remarques.

Mes sincères remerciements et ma profonde gratitude s’adressent à Monsieur

Karim BOUAMRANE, Professeur à l’Université d’Oran 1, Ahmed BenBella pour m’avoir
honoré en acceptant d’être président de mon jury de thèse.

J’adresse aussi ma gratitude et mes remerciements les plus profonds à Monsieur

Mohamed BENYETTOU, Professeur à l’Université des Sciences et de la Technologie
d'Oran, Mohamed Boudiaf pour m’avoir honoré en acceptant d’évaluer et d’examiner
cette thèse.

J’adresse également mes remerciements les plus sincères et ma reconnaissance à

Monsieur Zakaria El-BERRICHI, Professeur à l’Université de Sidi Bel-Abbès, Djilali
Liabès pour m’avoir honoré en acceptant de participer à mon jury de thèse et d’évaluer ce
travail.
 Mes remerciements les plus vifs et ma gratitude vont également à monsieur
Mohamed Fayçal KHELFI, Professeur à l’Université d’Oran 1, Ahmed BenBella pour
l’honneur qui m’a fait en acceptant de faire partie de mon jury de thèse.

Je voudrais aussi exprimer ma grande reconnaissance et ma profonde gratitude à

monsieur Larbi SEKHRI, Professeur à l’Université d’Oran 1, Ahmed BenBella pour
m’avoir honoré en acceptant d’examiner et d’évaluer cette thèse.

J’exprime mes vifs remerciements et mes reconnaissances à Monsieur

Abdelghani BEKRAR, maitre des conférences à l’Université de Valenciennes, France et à
Monsieur Damien TRENTESAUX, Professeur à l’Université de Valenciennes, France
pour m’avoir accueilli au sein de leur laboratoire. Je les remercie aussi pour ses
remarques, leur soutien moral et scientifique tout au long de cette thèse et les discussions
constructives qu’on a faites.

Enfin mes sincères remerciements à tous ceux qui m’ont encouragé, aidé et soutenu.
 Résumé
Dans le cadre de cette thèse nous présentons des algorithmes pour résoudre des
problèmes liés à la logistique de distribution et de transport. Premièrement, nous
développons un algorithme en deux phases pour résoudre le problème de localisation-
routage avec contrainte de capacité en utilisant la recherche Tabou et le recuit simulé.
Ensuite, nous traitons le problème d’élaboration de tournées avec gestion de stock
multi-périodes, multi-produits et multi-véhicules en proposant un algorithme (appelé
GBH) basé sur la métaheuristique GRASP (Greedy Randomized Adaptive Search
Procedure). Pour améliorer la méthode GRASP classique, nous utilisons la recherche
Tabou comme recherche locale dans le GBH. Dans notre troisième contribution, nous
développons deux algorithmes pour faire face à une nouvelle variante du problème
d’élaboration de tournées des véhicules appelée le problème de routage de navettes et
de taxis (Coach Trip with Shuttle Service Problem, CTSSP). Le premier algorithme
est une recherche Tabou et le second est une méthode GRASP. Les expériences
montrent que les algorithmes proposés et comparés avec succès avec plusieurs
méthodes de la littérature donnent de meilleurs résultats.

Mots-clés : Optimisation combinatoire, Métaheuristiques, Recherche Tabou, GRASP,

Recuit simulé, Chaînes logistique, Problèmes de transport, Routage des véhicules,
Localisation-routage, Routage avec gestion de stock.

‫ملخص‬
‫خالل هذه االطروحة اقترحنا بعض خوارزمٌات التقرٌبٌة لحل مشاكل التحسٌن فً السالسل اللوجستٌة حٌث‬
‫ اوال قمنا باقتراح خوارزمٌة تقرٌبه من‬.‫كان اهتمامنا منصبا علً الجزء المتعلق بمشاكل النقل و التوزٌع‬
‫ بحٌث المرحلة االولى كانت مخصصة لحل مشكلة التوجٌه‬،‫مرحلتٌن لحل مشكلة تحدٌد المواقع مع التوجٌه‬
‫باستعمال طرٌقة البحث طابو اما الثانٌة فكانت مخصصة لحل مشكلة تحدٌد المواقع باستعمال طرٌقة محاكاة‬
-‫ ثانٌا قمنا باقتراح خوارزمٌة تقرٌبٌة من نوع غراسب لحل مشكلة التوجٌه مع تسٌٌر المخزون متعددة‬.‫الصلب‬
‫ كما قمنا بتحسٌن هذه الخوارزمٌة عن طرٌق تعوٌض البحث‬،‫المنتجات‬-‫المراحل و متعددة‬-‫السٌارات متعددة‬
‫ ثالثا قمنا بدراسة مشكلة توجٌه‬.‫المحلً الكالسٌكً (الذي ٌستعمل غالبا فً طرق الغراسب) بطرٌقة البحث طابو‬
‫ بعد‬.‫ خوارزمٌة من نوع طابو و خوارزمٌة من نوع غراسب‬:‫جدٌدة و اقترحنا خوارزمٌتٌن تقرٌبٌتٌن لحلها‬
‫ اعطت الخوارزمٌات التً قمنا بتطوٌرها نتائج جٌدة و اثبتت كفاءتها بالمقارنة مع نظٌراتها المقترحات‬،‫تجربها‬
.‫سابقا فً اآلداب‬

‫ طرٌقة‬،‫ طرٌقة البحث غراسب‬،‫ طرٌقة البحث طابو‬،‫ الطرق التقرٌبٌة‬،ً‫ التحسٌن التوافق‬:‫الكلمات المفتاحية‬
‫ مشكلة‬،‫ مشكلة تحدٌد المواقع مع التوجٌه‬،‫ مشكلة التوجٌه‬،‫ مشاكل النقل‬،‫ السالسل اللوجستٌة‬،‫محاكاة الصلب‬
.‫التوجٌه مع تسٌٌر المخزون‬
 Abstract
This thesis presents algorithms to solve distribution and transportation problems.
First, we develop a two-stage algorithm to solve the Capacitated Location Routing
Problem (CLRP) using the tabu search and the simulated annealing metaheuristics.
Second, we deal with the Multi-product Multi-vehicle Inventory Routing Problem
(MMIRP) and we propose a GRASP-based heuristic algorithm (Greedy Randomized
Adaptive Search Procedure). To enhance the classical algorithm, we use the tabu
search as a local search within the GRASP. Third, we develop two algorithms to deal
with a new variant of the vehicle routing problem called Coach Trip with Shuttle
Service Problem (CTSSP). The first algorithm is an improved tabu search and the
second is a GRASP. Experiments show that our algorithms report best results and
successfully compared with several methods from the literature.

Key words: Combinatorial optimization, Meta-heuristics, Tabu search, GRASP,

Simulated annealing, Supply chains, Transportation problems, Vehicle routing,
Location Routing, Inventory Routing.
I
 Table des matières

Table des figures VI

Liste des tableaux VII

Introduction générale 1
1 Contexte de la thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Problématiques et contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3 Organisation de la thèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Chapitre 1 Etat de l’art sur la chaîne logistique: localisation, routage et gestion

de stock 4
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 La chaîne logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Objectifs et enjeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Structure générale d’une chaîne logistique . . . . . . . . . . . . . . . . . . 5
1.2.4 Niveaux de décisions dans une chaîne logistique . . . . . . . . . . . . . . . 6
1.3 Le transport et la distribution dans la chaîne logistique . . . . . . . . . . . . . . . 6
1.3.1 Problème de localisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
[Link] Le problème de localisation sans contrainte de capacité (Unca-
pacitated Facility Location Problem, UFLP) . . . . . . . . . . . 7
[Link] Modèle mathématique . . . . . . . . . . . . . . . . . . . . . . . . 7
[Link] Les variantes du problème de localisation sans contrainte de ca-
pacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Le problème de tournées de véhicules . . . . . . . . . . . . . . . . . . . . . 9
[Link] Le problème du voyageur de commerce . . . . . . . . . . . . . . 9
[Link] Définition du problème VRP . . . . . . . . . . . . . . . . . . . . 9
[Link] Formulation mathématique . . . . . . . . . . . . . . . . . . . . . 9
[Link] Quelques variantes du VRP . . . . . . . . . . . . . . . . . . . . . 10

II
 1.3.3 La gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Intégration entre les problèmes . . . . . . . . . . . . . . . . . . . . . . . . 13
[Link] Problème de localisation-routage (Location Routing Problem
(LRP)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
[Link] Problème de tournées avec gestion de stock (Inventory Routing
Problem (IRP)) . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Les outils pour l’optimisation de la chaîne logistique . . . . . . . . . . . . . . . . 16
1.4.1 Méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.2 Méthodes approchées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
[Link] Heuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
[Link] Metaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
[Link] Algorithmes à performance garantie . . . . . . . . . . . . . . . . 18
[Link] Approches hybrides . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Chapitre 2 Algorithme en deux phases pour le problème de localisation-routage

avec contrainte de capacité 20
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Un état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Modèle mathématique pour le CLRP . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Méthodologie de la solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1 La première phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
[Link] L’Heuristique d’Insertion (HI) . . . . . . . . . . . . . . . . . . . 25
[Link] La recherche Tabou (TS) . . . . . . . . . . . . . . . . . . . . . . 26
2.4.2 La deuxième phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
[Link] Recuit simulé (Simulated Annealing (SA)) . . . . . . . . . . . . 28
2.4.3 Algorithme complet (2-SH) . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 Réglage des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.2 Le jeu de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.3 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Chapitre 3 Résolution de problème de routage avec gestion de stock à base de la

méthode GRASP 39
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Revue de la littérature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

III
 3.3 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.3 Le modèle mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Méthodologie de solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.1 Vue générale sur l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.2 Prétraitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.3 Solution initiale pour GBH . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.4 Procédure gloutonne randomisée (GRP) . . . . . . . . . . . . . . . . . . . 45
[Link] Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
[Link] Les phases de GRP . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4.5 Recherche Tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
[Link] Structure de voisinage . . . . . . . . . . . . . . . . . . . . . . . . 48
[Link] Le moteur de sélection . . . . . . . . . . . . . . . . . . . . . . . . 49
[Link] La liste Tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.6 La gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.1 Réglage des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.2 Jeu de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.3 Résultats et comparaison avec B&C . . . . . . . . . . . . . . . . . . . . . 53
3.5.4 L’analyse du comportement de GBH . . . . . . . . . . . . . . . . . . . . . 58
3.5.5 Les résultats de GBH sur les instances de MMIRP-SD . . . . . . . . . . . 60
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Chapitre 4 Algorithmes pour le problème de routage de navettes et de taxis 63

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.1 Contraintes & fonction objectif . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Méthodologie de la solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.1 L’idée principale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
[Link] Difficultés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
[Link] L’approche proposée . . . . . . . . . . . . . . . . . . . . . . . . . 66
[Link] Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
[Link] Procédure de réparation . . . . . . . . . . . . . . . . . . . . . . . 68
4.3.2 Algorithmes pour le CTSSP . . . . . . . . . . . . . . . . . . . . . . . . . . 68
[Link] Recherche Tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
[Link] GRASP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

IV
 4.4 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.1 Réglage des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.2 La procédure de génération de jeu de données . . . . . . . . . . . . . . . . 73
4.4.3 Les résultats de TS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.4.4 La comparaison entre TS, GRASP et GRASP-LP . . . . . . . . . . . . . . 76
4.4.5 La méthode GRASP-LP sur les instances de VRP et d’OVRP . . . . . . . 76
[Link] La méthode GRASP-LP sur les instances de VRP . . . . . . . . 76
[Link] La méthode GRASP-LP sur les instances d’OVRP . . . . . . . . 77
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Conclusion générale 79

Bibliographie 82

V
 Table des figures

1.1 Structure générale d’une chaîne logistique . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Classification de méthodes d’optimisation . . . . . . . . . . . . . . . . . . . . . . 16

2.1 Exemple d’une solution pour l’UFLP. . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.1 Un exemple d’une solution pour le CTSSP . . . . . . . . . . . . . . . . . . . . . . 65

4.2 Difficultés de résolution de CTSSP : exemple 1 . . . . . . . . . . . . . . . . . . . 66
4.3 Difficultés de résolution de CTSSP : exemple 2 . . . . . . . . . . . . . . . . . . . 67
4.4 Difficultés de résolution de CTSSP : exemple 3 . . . . . . . . . . . . . . . . . . . 67

VI
 Liste des tableaux

2.1 Méthodes proposées pour le CLRP . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Le jeu de données de Harks et al. (2013) [52] . . . . . . . . . . . . . . . . . . . . 34
2.3 Les résultats de 2-SH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 Les résultats de Approx et Approx-LKH [52] . . . . . . . . . . . . . . . . . . . . 36
2.5 2-SH vs. Approx et Approx-LKH . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.1 Les notations utilisées dans la Procédure gloutonne randomisée . . . . . . . . . . 46

3.2 GBH Vs. B&C sur les instances avec K = 1 & M = 1 . . . . . . . . . . . . . . . 53
3.3 GBH Vs. B&C sur les instances avec K = 3 & M = 1 . . . . . . . . . . . . . . . 54
3.4 GBH Vs. B&C sur les instances avec K = 5 & M = 1 . . . . . . . . . . . . . . . 54
3.5 GBH Vs. B&C sur les instances avec K = 1 & M = 3 . . . . . . . . . . . . . . . 55
3.6 GBH Vs. B&C sur les instances avec K = 3 & M = 3 . . . . . . . . . . . . . . . 55
3.7 GBH Vs. B&C sur les instances avec K = 5 & M = 3 . . . . . . . . . . . . . . . 56
3.8 GBH Vs. B&C sur les instances avec K = 1 & M = 5 . . . . . . . . . . . . . . . 56
3.9 GBH Vs. B&C sur les instances avec K = 3 & M = 5 . . . . . . . . . . . . . . . 57
3.10 GBH Vs. B&C sur les instances avec K = 5 & M = 5 . . . . . . . . . . . . . . . 57
3.11 GBH Vs. B&C en regroupant les instances . . . . . . . . . . . . . . . . . . . . . . 58
3.12 Résultats d’analyse de comportement de GBH . . . . . . . . . . . . . . . . . . . . 59
3.13 GBH Vs. B&C et DH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.1 Liste des acronymes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.2 La contribution de chaque composant de TS . . . . . . . . . . . . . . . . . . . . . 74
4.3 TS Vs. GRASP Vs. GRASP-LP . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.4 Les résultats de GRASP-LP sur les instances de VRP . . . . . . . . . . . . . . . 77
4.5 Les résultats de GRASP-LP sur les instances d’OVRP . . . . . . . . . . . . . . . 78

VII
 Introduction générale

1 Contexte de la thèse
De nos jours, dans un environnement économique de plus en plus concurrentiel, l’optimisation
des chaînes logistiques occupe une place importante dans la vie industrielle des entreprises. Le
but étant l’amélioration de leur compétitivité en optimisant leurs performances et en réduisant
leurs coûts. En effet, la chaîne logistique englobe toutes les tâches réalisées pour la production
d’un service ou d’un produit, à savoir l’approvisionnement, la transformation, le stockage, et la
distribution. Bien que, la chaîne logistique englobe toutes ces tâches, des études ont montré que
les coûts de transport et de distribution constituent le tiers des coûts opérationnels d’une chaîne
logistique [77, 54]. Par conséquence, depuis plusieurs années, un nombre croissant d’entreprises
et de chercheurs constatent les bénéfices de l’optimisation de la logistique de distribution et de
transport, et elle est devenu un challenge majeur pour eux. En fait, la logistique de distribution
et de transport a trois activités principales, à savoir la localisation des infrastructures (des dépôts
et des centres de distribution), l’élaboration des tournées de véhicules afin de livrer les produits
aux clients et la gestion de stock. L’optimisation des systèmes de distribution consiste à résoudre
les problèmes liés à chaque activité.

Le problème de localisation des dépôts consiste à installer ou à ouvrir un certain nombre

de dépôts à partir d’un ensemble de candidats pour satisfaire les demandes des clients. Ainsi,
l’élaboration des tournées de véhicules est un problème très important qui consiste à déterminer
les routes d’une flotte de véhicules afin de satisfaire un ensemble de clients en tenant compte
d’un ensemble de contraintes et en réduisant les coûts. Le problème de gestion de stock consiste
à contrôler les flux d’entrée et de sortie dans un entrepôt ou un centre de distribution en évitant
les ruptures des stocks, d’un côté, et en réduisant les coûts de stockage, d’un autre côté.
Au départ, et à cause de la complexité de ces problèmes, chacun a été résolu indépendamment
et plusieurs méthodes ont été proposées pour chacun. Mais, en raison de leur interdépendance,
plusieurs études ont montré l’intérêt d’intégrer ces problèmes entre eux lors de la résolution
[88]. Parmi les problèmes résultant de l’intégration entre ces activités, on trouve le problème de
localisation-routage qui combine la localisation des dépôts avec l’élaboration des tournées, et le
problème de l’élaboration des tournées avec la gestion de stock.

2 Problématiques et contributions
Dans le cadre de cette thèse nous nous intéressons à l’étude et à la résolution de trois problèmes
d’optimisation dans le contexte de la logistique de distribution et de transport en proposant des
méthodes approchées. Le premier problème est une variante du problème de localisation-routage

1
 3. Organisation de la thèse

où une contrainte de capacité est imposée et on s’intéresse en particulier au cas de grande échelle.
Le deuxième problème est une variante du problème de l’élaboration des tournées avec la gestion
de stock en considérant le cas de multi-véhicules et multi-produits. Enfin, dans le troisième cas
d’étude, nous nous intéressons à un cas réel d’un problème de transport de personnel, qui est
considéré comme une nouvelle variante du problème de l’élaboration des tournées de véhicules.
Ces travaux ont fait l’objet de deux publications et une communication :

1. O. Guemri, A. Bekrar, B. Beldjilali, D. Trentesaux, (2016). GRASP-Based Heuristic Algo-

rithm for the Multi-product Multi-vehicle Inventory Routing Problem. 4OR - A Quarterly
Journal of Operations Research, volume 14, issue 4, pp. 377−404.

2. O. Guemri, B. Beldjilali, A. Bekrar, G. Belalem, (2016). Effective Two Stage Heuristic

Algorithm for the Large-Scale Capacitated Location Routing Problem. International Journal
of Mathematical Modeling and Numerical Optimization, volume 7, issue 1, pp. 97−119.

3. O. Guemri, A. Bekrar (2015). An improved Tabu Search heuristic Algorithm for the Coach
Trip with Shuttle Service Problem. 4th Meeting of the EURO Working Group on Vehi-
cle Routing and Logistics Optimization, Vienne, juin 2015. Invited talk as finalist of the
VeRoLog Solver challenge 2015.

3 Organisation de la thèse
Cette thèse est organisée en 4 chapitres:
Dans le premier chapitre, nous présentons un état de l’art sur la chaîne logistique en général et
la logistique de distribution et de transport en particulier. Nous allons nous concentrer sur les trois
activités décrites ci-dessus en donnant une définition détaillée avec une formulation mathématique
et en explicitant les variantes les plus connues de chaque problème. Enfin, nous terminerons ce
chapitre en décrivant les outils utilisés pour la résolution des problèmes d’optimisation des chaînes
logistiques.

Dans le deuxième chapitre, nous allons aborder le problème de localisation-routage à grande

échelle avec contrainte de capacité en proposant un nouvel algorithme de résolution. L’algorithme
est composé de deux grandes phases combinant la recherche Tabou avec le recuit simulé. Dans
cette méthode, la recherche Tabou est consacrée pour le sous-problème de routage et le sous-
problème de localisation est résolu en utilisant le recuit simulé.

Dans le troisième chapitre, nous allons étudier le problème de routage avec gestion de stock
multi-périodes, multi-produits et multi-véhicules en développant une heuristique de type GRASP.
Cette méthode se compose de deux phases : une heuristique gloutonne randomisée utilisée pour
construire une solution faisable de bonne qualité et une recherche locale. Comme recherche locale
dans le GRASP, nous allons utiliser la métaheuristique recherche Tabou.

Dans le quatrième chapitre, nous présenterons une contribution pour une nouvelle variante
du problème d’élaboration des tournées de véhicules à savoir le problème de routage de navettes
et de taxis. Il s’agit d’un problème industriel qui concerne le transport de personnel. Le but
est de transporter un ensemble de passagers depuis leurs arrêts de bus vers un dépôt central en

2
 3. Organisation de la thèse

utilisant une flotte de véhicules hétérogènes. Pour résoudre le problème, nous proposerons deux
méthodes, à savoir une recherche Tabou et une méthode de type GRASP.

Enfin, nous terminerons cette thèse avec une conclusion générale par rapport aux résultats
obtenus et un ensemble de perspectives pour des futurs travaux.

3
Chapitre 1

Etat de l’art sur la chaîne logistique:

localisation, routage et gestion de stock

Sommaire
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 La chaîne logistique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2 Objectifs et enjeux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Structure générale d’une chaîne logistique . . . . . . . . . . . . . . . . . 5
1.2.4 Niveaux de décisions dans une chaîne logistique . . . . . . . . . . . . . . 6
1.3 Le transport et la distribution dans la chaîne logistique . . . . . . . 6
1.3.1 Problème de localisation . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Le problème de tournées de véhicules . . . . . . . . . . . . . . . . . . . . 9
1.3.3 La gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4 Intégration entre les problèmes . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Les outils pour l’optimisation de la chaîne logistique . . . . . . . . . 16
1.4.1 Méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.2 Méthodes approchées . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.1 Introduction
Comme nous l’avons mentionné dans l’introduction générale, dans le cadre de cette thèse
nous nous intéressons à l’optimisation des chaînes logistiques, particulièrement aux problèmes
d’optimisation liés à la logistique de distribution et de transport. Dans ce premier chapitre nous
présentons les différents problèmes de base qui constituent le noyau de la thématique étudiée
dans cette thèse. En effet, nous divisons ce chapitre en trois parties. Dans la première partie,
nous décrivons la chaîne logistique en exposant ses définitions, sa structure générale, etc. Puis,
dans la deuxième partie, nous nous intéressons à la logistique de distribution. Nous présentons les
trois problèmes principaux inhérents à cette partie de la chaîne logistique, à savoir le problème
de localisation de dépôts, le problème d’élaboration des tournées de véhicules et le problème de
gestion de stock. Nous présentons également les deux problèmes intégrés, à savoir le problème

4
 1.2. La chaîne logistique

de localisation-routage et le problème de routage avec gestion de stock. La troisième et dernière

partie est consacrée aux outils d’optimisation de la chaîne logistique.

1.2 La chaîne logistique

1.2.1 Définitions
La logistique a pour origine un mot grec qui indique l’art du raisonnement et du calcul [80, 77].
La notion de logistique a été utilisée en premier lieu dans le domaine militaire en référant à tout
ce qui est nécessaire à l’application sur le terrain des décisions tactiques et stratégiques. Après
la fin de la seconde guerre mondiale et avec la grande évolution du marché industriel vint ce que
l’on appelle la logistique industrielle [77, 64]. Dans la littérature, plusieurs définitions ont été
données à la chaîne logistique, dans ce qui suit nous présentons quelques-unes :
Lee et Billington (1993) [67] : La chaîne logistique est "un réseau d’installations qui assure
les fonctions d’approvisionnements en matières premières, de transformation de ces matières
premières en composants puis en produits finis, et de distribution des produits finis aux clients" .
Teigen et Barbuceanu (1996) [97] : "La chaîne logistique est un réseau de fournisseurs,
d’entreprises, de dépôts, de centres de distribution et de détaillants, au travers desquels les
matières premières sont acquises, transformées, et délivrées aux clients".
Mentzer et al. (2001) [73] : "Une chaîne logistique est un groupe d’au moins trois entités
directement impliquées dans les flux amonts et avals de produits, de services, de finances et/ou
d’informations, qui vont d’une source jusqu’au client".
Ganeshan et Harisson (1995) [41] : "Une chaîne logistique est le réseau des moyens de pro-
duction et de distribution qui assurent les tâches d’approvisionnement en matières premières,
la transformation de ces matières premières en produits semi finis et en produits finis, et la
distribution de ces produits finis aux clients".
A partir de ces définitions nous pouvons constater que la chaîne logistique est un ensemble
de maillons reliés entre eux et qui collaborent pour accomplir un travail bien déterminé.

1.2.2 Objectifs et enjeux

Dans un environnement de plus en plus concurrentiel, les entreprises doivent être capables de
livrer le bon produit dans la bonne quantité au bon endroit au bon moment et avec un coût minimal
[64, 103]. Pour faire face à ce défi, l’entreprise doit adopter une bonne politique de gestion de
sa chaîne logistique dont l’objectif principal est d’augmenter le gain global en maximisant les
profits et en minimisant les coûts, y compris les coûts de fabrication, de transaction, de transport,
de stockage, etc. Dans [67], les auteurs ont annoncé : "La bataille pour dominer le marché ne
sera pas une bataille d’entreprises mais de chaînes logistiques". En effet, l’importance des chaînes
logistique provient de toutes les possibilités qu’elles offrent aux entreprises pour générer des gains
supplémentaires ce qui permet aux entreprises de résister plus efficacement face aux pressions
concurrentielles, et c’est pour cela que l’entreprise qui va réussir dans la gestion de sa chaîne
logistique va dominer les autres.

1.2.3 Structure générale d’une chaîne logistique

En prenant la définition de [41], la chaîne logistique a un ensemble de fonctions principales,
qui consistent en l’achat des matières premières, la production, le stockage, la distribution et la

5
 1.3. Le transport et la distribution dans la chaîne logistique

vente des produits finis. Dans la figure 1.1 nous présentons un exemple d’une chaîne logistique
en indiquant l’emplacement de chaque fonction dans la chaîne [40].

Figure 1.1: Structure générale d’une chaîne logistique

1.2.4 Niveaux de décisions dans une chaîne logistique

La gestion d’une chaîne logistique nécessite de prendre un ensemble de décisions. Dans les chaînes
logistiques, on distingue généralement trois niveaux de décisions selon la portée temporelle de
la décision: des décisions opérationnelles, des décisions tactiques et des décisions stratégiques
[10, 40, 102]. Nous donnons, ci-après, un bref aperçu sur chaque niveau avec des exemples.

• Décisions stratégiques : ce sont les décisions les plus importantes qui permettent de dessiner
la structure générale de la chaîne logistique : la localisation des infrastructures (l’ouverture
et la fermeture des usines, des dépôts etc.), le choix des partenaires et des fournisseurs et
enfin, le choix de mode de transport et des différentes technologies.

• Décisions tactiques : leurs influences portent sur un horizon d’une semaine jusqu’à un
mois. A titre d’exemples pour les décisions de ce niveau : l’allocation des clients aux en-
trepôts, l’affectation des produits aux sites de production et la planification des processus
de production.

• Décisions opérationnelles : leurs influences portent sur un horizon d’un jour jusqu’à une
semaine : l’élaboration des tournée de véhicules pour livrer les produits aux clients,
l’affectation des ressources aux tâches au sein des unités de production etc.

1.3 Le transport et la distribution dans la chaîne logistique

L’optimisation des systèmes de transport et de distribution est un défi majeur pour les entreprises
car les études ont montré que les coûts de transport et de distribution constituent le tiers des
coûts opérationnels d’une chaîne logistique [54, 77]. Le système de distribution est composé
d’un ensemble de fonctions principales, comprenant la localisation des centres d’entreposage et

6
 1.3. Le transport et la distribution dans la chaîne logistique

de distribution, la gestion de stock et enfin l’élaboration des tournées de véhicules pour livrer
les produits aux clients. Donc, l’optimisation des systèmes de distribution consiste à résoudre
l’ensemble des problèmes liés à ces fonctions. Dans ce qui suit, nous allons d’abord définir chaque
problème de manière séparée. Ensuite, nous allons montrer l’utilité de considérer ces problèmes en
les intégrant les uns aux autres. Enfin, nous présentons deux problèmes issus de cette intégration,
à savoir le problème de localisation-routage et le problème d’élaboration des tournées avec gestion
de stock.

1.3.1 Problème de localisation

Nous présentons ici un bref aperçu sur le problème de localisation de dépôts et ses variantes. Nous
donnons une définition du problème avec une formulation mathématique, puis nous décrivons
brièvement les principales variantes existantes dans la littérature [96, 91, 85].

[Link] Le problème de localisation sans contrainte de capacité (Uncapacitated Fa-

cility Location Problem, UFLP)
Le problème de localisation des dépôts sans contrainte de capacité consiste à choisir un certain
nombre de dépôts à partir d’un ensemble de dépôts candidats et à affecter un ensemble de clients
à ces dépôts. L’objectif est de minimiser le coût total, y compris le coût d’ouverture des dépôts
et le coût d’affectation des clients à ces dépôts. Le nombre de dépôts à ouvrir n’est pas fixé à
l’avance.

[Link] Modèle mathématique

Soit les indices et les paramètres suivants [94]:

• M : l’ensemble de dépôts candidats considérés dans le problème;

• N : l’ensemble de clients;

• fi : le coût d’ouverture de dépôt i ∈ M ;

• cij : le coût d’affectation du client j ∈ N au dépôt i ∈ M ;

Pour modéliser ce problème, deux types de variables de décisions sont utilisés:

• xij : variable binaire qui est égale à 1 si le client j est affecté au dépôt i.

• yi : variable binaire qui est égale à 1 si le dépôt i est ouvert.

L’UFLP est modélisé sous la forme du programme linéaire en nombres entiers suivant:
X X X
min z = cij xij + fi yi (1.1)
i∈M j∈N i∈M

Sous les contraintes: X

xij = 1 ∀j ∈ N (1.2)
i∈M

xij ≤ yj ∀j ∈ N ∀i ∈ M (1.3)
xij ≥ 0 ∀j ∈ N ∀i ∈ M (1.4)

7
 1.3. Le transport et la distribution dans la chaîne logistique

yi = {0, 1} ∀i ∈ M (1.5)
La fonction objectif (1.1) consiste à minimiser le coût total décrit ci-dessus. La contrainte
(1.2) impose à chaque client d’être affecté à un seul dépôt. La contrainte (1.3) oblige à ce que
chaque client j ne puisse être servi par le dépôt i si et seulement si ce dépôt est ouvert (c’est-à-dire
si yi = 1). Les contraintes (1.4) et (1.5) assurent l’intégrité sur les variables yi et xij .

[Link] Les variantes du problème de localisation sans contrainte de capacité

Différentes variantes du UFLP ont été étudiées dans la littérature. Parmi lesquelles, nous citons
les problèmes suivants [12, 91].

1. Le problème de localisation des dépôts avec contrainte de capacité (Capacitated Facility

Location Problem (CFLP))
Le CFLP est une variante de l’UFLP où la contrainte de capacité sur les dépôts est imposée.
Donc, dans ce cas la somme des demandes des clients affectés à chaque dépôt ne doit pas
excéder sa capacité.

2. Le problème P-médian (P-Median Problem (PMP))

Le problème du p-médian est un problème de localisation où nous avons un ensemble de
dépôts candidats et le but est de choisir exactement p dépôts à partir de l’ensemble de ces
candidats (un dépôt choisi est appelé médian). Les autres dépôts candidats sont ensuite
affectés aux médians choisis. L’objectif de PMP est de minimiser le coût d’affectation.

3. Le problème du p-centre (P-Centre Problem (PCP))

Le problème du p-centre est une variante similaire au problème du PMP dont l’objectif est
de minimiser le maximum des coûts d’affectation des clients.

4. Le problème de recouvrement (Set Covering Problem (SCP))

Le problème de recouvrement SCP consiste à déterminer un sous-ensemble de dépôts pour
couvrir tous les clients. Dans les problèmes de localisation en général, on doit prendre deux
décisions au même moment: Le choix des dépôts et l’affection des clients. Cependant, dans
le SCP, chaque dépôt ne couvre qu’un ensemble de clients prédéfinis et donc, pour résoudre
le SCP, nous devrons seulement choisir un sous-ensemble de dépôts pour couvrir (servir)
tous les clients.

5. Le problème de localisation des dépôts avec tolérance de panne (Fault-Tolerant Facility

Location Problem (FTFLP))
Dans le FTFLP, chaque client doit être affecté à plusieurs dépôts au lieu d’un seul afin
d’assurer le service et d’éviter tout problème de panne ou de non-disponibilité [91].

6. Le problème de localisation des dépôts avec multi-produit (Multi-Product Facility Location

Problem (MPFLP))
Le MPFLP est un problème de localisation où nous considérons que chaque client dispose
des demandes pour un certain nombre de produits, et que chaque dépôt peut être ouvert
pour livrer un ou plusieurs produits [91].

8
 1.3. Le transport et la distribution dans la chaîne logistique

1.3.2 Le problème de tournées de véhicules

Le problème de tournées de véhicules (en anglais : Vehicle Routing Problem, VRP) a été défini
pour la première fois par [29]. Vu son importance et ses multiples applications dans l’industrie
et dans la vie quotidienne, le VRP sollicite l’attention de plusieurs chercheurs et fait l’objet de
nombreux travaux de recherche. Par ailleurs, ce problème trouve ces origines dans un problème
plus ancien qui est le problème du voyageur de commerce.

[Link] Le problème du voyageur de commerce

Le problème du voyageur de commerce (en anglais : Travelling Salesman Problem, TSP) est
l’un des problèmes classiques de la recherche opérationnelle [29]. Le problème du TSP consiste
à construire une tournée pour un voyageur en visitant un ensemble de villes et en retournant à
la ville de départ. Le voyageur doit visiter l’ensemble des villes en passant une et une seule fois
par chaque ville avec pour objectif de minimiser la distance du chemin parcouru.

[Link] Définition du problème VRP

Le principe du problème de tournées de véhicules, qui est une généralisation du TSP, est de servir
un ensemble de n clients en utilisant une flotte de m véhicules [29, 74]. Le but est de construire
un ensemble de routes qui visitent ces clients en minimisant une fonction objectif donnée et
en tenant compte d’un ensemble de contraintes. La route de chaque véhicule commence et se
termine à un dépôt central en visitant un sous-ensemble de clients et où chaque client doit être
servi par un seul véhicule.

[Link] Formulation mathématique

Nous présentons ici une formulation mathématique pour le VRP [99, 85, 74]. Dans cette for-
mulation l’objectif est de minimiser la distance parcourue par les véhicules. Au départ, nous
définissons les variables utilisées :

• G = (S, A) est un graphe où S = {0, ..., n} est l’ensemble de sommets où le sommet 0 est
le dépôt central et le reste des sommets sont les clients (S 0 = S − {0}). A = {(i, j) i, j ∈ S
et i 6= j} est l’ensemble des arcs reliant les sommets,

• n: est le nombre de clients,

• K = {1, ..., k} : est la flotte de véhicules, chaque vehicle a une capacité Q.

• cij : est le coût du voyage du sommet i au sommet j.

• xijk = 1 si le véhicule k prend le chemin du sommet i vers le sommet j.

XX X
min z = cij xijk (1.6)
i∈S j∈S k∈K

Sous les contraintes: XX

xijk = 1 ∀i ∈ S 0 (1.7)
k∈K j∈S
XX
xijk = 1 ∀j ∈ S 0 (1.8)
k∈K i∈S

9
 1.3. Le transport et la distribution dans la chaîne logistique
X X
xipk − xpjk = 0 ∀p ∈ S 0 , k ∈ K (1.9)
i∈S j∈S
X
xi0k ≤ 1 ∀k ∈ K (1.10)
i∈S 0
X
x0jk ≤ 1 ∀k ∈ K (1.11)
j∈S 0

uik − ujk + (n − 1)xijk ≤ n − 2 ∀i ∈ S 0 , j ∈ S 0 , k ∈ K (1.12)

xjik = {0, 1} (1.13)

La fonction objectif (1.6) minimise la somme des distances parcourues. Les équations (1.7)
et (1.8) assurent que chaque sommet n’est servi qu’une seule fois par un et un seul véhicule.
L’équation (1.9) assure la continuité d’une tournée par un véhicule : le sommet visité doit im-
pérativement être quitté. Les équations (1.10) et (1.11) assurent qu’un véhicule part d’un dépôt
et ne revient qu’une seule fois au même dépôt. L’équation (1.12) assure l’élimination des sous-
cycles.

[Link] Quelques variantes du VRP

Durant les cinq dernières décennies, de nombreuses variantes de VRP ont été proposées [65]. En
effet, l’apparition d’une nouvelle variante est due essentiellement à l’ajout d’une contrainte, une
caractéristique ou un nouvel élément au problème (l’ajout, la modification ou l’élimination d’une
ou de plusieurs contraintes du VRP peut nous mener vers d’autres variantes). Dans cette partie
nous essayons de présenter les variantes les plus connus du VRP [35, 46, 55, 50, 87, 61] :

1. Problème de tournées de véhicules avec contrainte de capacité (Capacitated Vehicle Routing

Problem (CVRP)):
Le CVRP est un VRP où la contrainte de capacité de véhicules est imposée, c’est-à-dire
que la somme des demandes des clients servis par chaque véhicule ne doit pas dépasser sa
capacité. Dans le CVRP la flotte de véhicules est supposée homogène.

2. Problème de tournées de véhicules dynamique (Dynamic Vehicle Routing Problem (DVRP))

Le DVRP est une variante du VRP où les données nécessaires pour résoudre le prob-
lème dépendent du temps, c-à-dire, soit elles ne sont pas connues à l’avance (manque
d’information avant la résolution de problème) ou bien elles peuvent être changées après le
commencement des tournées comme par exemple l’ajout d’une nouvelle demande pour un
nouveau client ou l’annulation d’une demande d’un client.

3. Problème de tournées de véhicules avec fenêtres de temps (Vehicle Routing Problem with
Time Windows (VRPTW))
Le VRPTW est un VRP où une contrainte temporelle est imposée. En effet, dans le VRP
un véhicule peut visiter un client à n’importe quel moment. Cependant, dans le VRPTW
un véhicule ne peut visiter un client que dans un intervalle de temps bien précis, c’est ce
que l’on appelle une fenêtre de temps.

10
 1.3. Le transport et la distribution dans la chaîne logistique

4. Problème de tournées de véhicules multi-périodes (Periodic Vehicle Routing Problem

(PVRP))
Dans le PVRP, nous avons un ensemble de périodes P = {1, ..., M } qui représente l’horizon
de planification, et pour chaque client, nous avons un nombre de visites k (1 ≤ k ≤ M ) qui
doivent être effectuées. Donc, pour résoudre le PVRP nous devons, pour chaque période,
déterminer les clients à visiter et construire les tournées de véhicules pour satisfaire ces
clients.

5. Problème de tournées de véhicules multi-dépôts (Multi-Depots Vehicle Routing Problem

(MDVRP))
Dans le VRP, la tournée de chaque véhicule commence et se termine à partir d’un dépôt
central. Cependant, dans le MDVRP nous disposons de plusieurs dépôts et dans chaque
dépôt nous disposons d’un ensemble de véhicules. Comme dans le VRP, la tournée de
chaque véhicule commence et se termine à partir de son dépôt et chaque client doit être
servi exactement une seule fois.

6. Problème de tournées de véhicules ouvert (Open Vehicle Routing Problem (OVRP))

Contrairement au VRP où la tournée de chaque véhicule doit se terminer au dépôt central,
dans le problème OVRP les véhicules ne sont pas obligés de retourner au dépôt central. En
effet, cette caractéristique est importante parce qu’elle change complètement la structure
de VRP.

7. Problème de tournées de véhicules avec multi-tournées pour chaque véhicule (Le Vehicle
Routing Problem with Multiple Trips (VRPMT))
La différence entre le VRP et le VRPMT réside dans le fait que dans le VRPMT un
véhicule peut faire plusieurs tournées, c’est-à-dire, dans un horizon de planification avec
plusieurs périodes et lorsque nous disposons d’une flotte de véhicules limitée, un véhicule
peut faire, dans une même période, plusieurs tournées en tenant compte d’une durée max-
imale d’utilisation par période.

8. Problème de tournées de véhicules stochastique (Stochastic Vehicle Routing Problem

(SVRP))
Un VRP est stochastique si un des éléments du problème est aléatoire, comme par exemple
la représentation des demandes des clients, du temps de transport sur un arc ou bien du
coût d’un arc par une variable aléatoire.

9. Problème de tournées de véhicules multi-compartiments (Multi-Compartment Vehicle Rout-

ing Problem (MCVRP))
Le MCVRP est utilisé pour modéliser les cas où les demandes des clients concernent
plusieurs produits incompatibles. Ces produits doivent être transportés sur un même
véhicule mais dans des compartiments indépendants.

10. Problème de tournées de véhicules avec une flotte hétérogène (Heterogeneous Fleet Vehicle
Routing Problem (HVRP))
Dans le VRP nous disposons d’une flotte de véhicules homogènes. Cependant dans le
HVRP, nous disposons d’une flotte de véhicules ayant des caractéristiques différentes. Les
véhicules peuvent être différenciés par : leurs capacités, leurs coûts de routage, leurs coûts
d’utilisation, etc.

11
 1.3. Le transport et la distribution dans la chaîne logistique

11. Problème de tournées de véhicules avec sélection (Selective Vehicle Routing Problem
(SVRP))
On rencontre le SVRP lorsque nous disposons d’une flotte de véhicules avec une capacité qui
n’est pas suffisante pour satisfaire toutes les demandes des clients. Donc, nous ne pouvons
servir qu’un sous-ensemble de clients sélectionnés à partir de l’ensemble des clients.

12. Problème de tournées de véhicules avec livraison et ramassage (Vehicle Routing Problem
with Pickup and Delivery (VRPPD))
Comme pour le VRP, le problème VRPPD consiste à élaborer un ensemble de tournées
pour satisfaire les demandes de clients. Cependant dans le VRPPD, nous distinguons deux
types de demande : la livraison d’un produit et le ramassage d’un produit.

13. Problème de tournées de véhicules avec retours (Vehicle Routing Problem with backhauls
(VRPB))
Comme pour le VRPPD, dans cette variante nous distinguons deux types de clients : des
livreurs où le véhicule doit faire un ramassage et des receveurs où le véhicule doit faire
une livraison. Cependant la différence entre les deux variantes est que dans le VRPB nous
visitons tous les receveurs avant de visiter les livreurs.

14. Problème de tournées de véhicules avec distribution partagée (Split Delivery Vehicle Routing
Problem (SDVRP))
On rencontre le SDVRP lorsqu’on a des demandes de clients qui sont supérieures à la
capacité du véhicule. Dans ce cas, chaque client peut être servi une ou plusieurs fois selon
le besoin, c’est-à-dire, le client peut être affecté à une ou plusieurs tournées.

1.3.3 La gestion de stock

La gestion de stock est une fonction importante qui reste au coeur des préoccupations des dé-
cideurs afin de piloter leurs entreprises de manière performante. La gestion de stock consiste à
appliquer un ensemble de techniques nécessaires pour contrôler et réguler les flux d’entrée et de
sortie en maintenant un stock suffisant pour satisfaire les clients avec un coût minimal. Autrement
dit, la gestion de stock consiste à déterminer le bon niveau de stock de chaque produit afin de
satisfaire les demandes des clients avec un coût réduit [96, 74, 10].
En effet, pour assurer la disponibilité des produits on doit avoir des niveaux de stocks élevés,
d’un autre côté, afin de minimiser les coûts de stockage, on doit avoir des niveaux de stocks
réduits. Donc, l’objectif de la gestion de stock est de trouver un bon compromis entre la satis-
faction des clients et les coûts de stockage, c’est-à-dire, assurer la disponibilité des produits afin
d’éviter tout problème de pertes de ventes (en cas de rupture de stocks) en minimisant le coût.
Enfin, la gestion de stock dépend fortement de deux facteurs principaux :

• Le type de produit : par exemple dans le cas des produits périssables, nous devons assurer
un acheminement rapide et un stockage dans les bonnes conditions de conservation.

• L’incertitude : l’incertitude des demandes de clients et des délais de livraison et de produc-

tion et enfin le prix des matières premières au niveau des cours de la bourse.

En tenant compte de ces deux facteurs, nous devons assurer une bonne gestion de stock.

12
 1.3. Le transport et la distribution dans la chaîne logistique

1.3.4 Intégration entre les problèmes

A cause de la complexité des problèmes d’optimisation, les trois problèmes décrits ci-dessus sont
traités de manière séparée [85]. Cependant, à cause de l’interdépendance entre les décisions liées à
ces problèmes, il est important de tenir compte de l’impact de chaque décision sur les autres. En
effet, durant ces 10 dernières années, les chercheurs ont montré que la conception d’un système de
distribution robuste nécessite l’intégration de ces décisions dans un même modèle d’optimisation
[86, 57, 24]. Par la suite, nous présentons deux problèmes en intégrant, dans le premier, le
problème d’élaboration de tournées avec le problème de localisation et dans le deuxième, le
problème d’élaboration de tournées avec le problème de gestion de stock.

[Link] Problème de localisation-routage (Location Routing Problem (LRP))

Le problème de localisation-routage combine deux fonctions principales de la chaîne logistique, à
savoir la localisation des dépôts et l’élaboration des tournées de véhicules [85]. Dans ce problème
le but est de choisir certains dépôts à ouvrir à partir d’un ensemble de dépôts candidats et
de planifier des tournées partantes de ces dépôts afin de satisfaire les demandes des clients.
Formellement, nous définissons les paramètres suivants:

• I : un ensemble de dépôts candidats, chaque dépôt i a un coût d’ouverture Oi .

• J : un ensemble de clients, chaque client j a une demande dj

• V = I ∪ J : l’ensemble de sommets

• cij : le coût du trajet entre le site i ∈ V et le site j ∈ V .

• K : une flotte de véhicules.

Les variables de décisions:

• yi : une variable binaire qui est égale 1 si le dépôt i est ouvert.

• fij : une variable binaire qui est égale 1 si le client j est servi à partir du dépôt i.

• xijk : une variable binaire qui est égale 1 si le véhicule k va directement du site i au site j.

Le problème LRP peut être modélisé par le programme linéaire en nombres entiers suivant:
La fonction objectif:
X XX X
min z = Oi yi + cij xijk (1.14)
i∈I i∈V j∈V k∈K

Sous les contraintes:

X X
xijk = 1 ∀j ∈ J (1.15)
k∈K i∈V
X X
xijk − xjik = 0 ∀i ∈ V, k ∈ K (1.16)
j∈V j∈V
XX
xijk ≤ 1 ∀k ∈ K (1.17)
i∈I j∈J

13
 1.3. Le transport et la distribution dans la chaîne logistique
XX
xijk ≤ |S| − 1 ∀S ⊆ J, ∀k ∈ K (1.18)
i∈S j∈S
X X
xiuk + xujk ≤ 1 + fij ∀i ∈ I, ∀j ∈ J, ∀k ∈ K (1.19)
u∈J u∈V −(j)

xijk ∈ {0, 1} ∀i ∈ V, ∀j ∈ V, ∀k ∈ K (1.20)

yi ∈ {0, 1} ∀i ∈ I (1.21)
fij ∈ {0, 1} ∀i ∈ I, ∀j ∈ V (1.22)
La fonction-objectif (1.14) minimise la somme des coûts d’ouverture des dépôts et de trans-
port respectivement. La contrainte (1.15) assure que chaque client est visité par exactement un
seul véhicule et possède un seul prédécesseur dans la route. Les contraintes (1.16) et (1.17) im-
posent la continuité de chaque route et que chaque route commence et se termine au même dépôt
ouvert. La contrainte (1.18) élimine les sous-cycles. La contrainte (1.19) impose qu’un client doit
être affecté à un dépôt s’il y a une route qui les relie. Enfin, l’intégrité des variables de décision
est assurée par les contraintes (1.20), (1.21) et (1.22).

[Link] Problème de tournées avec gestion de stock (Inventory Routing Problem

(IRP))
Le problème de tournées avec gestion de stock intègre deux fonctions principales de la chaîne
logistique, à savoir l’élaboration des tournées de véhicules et la gestion de stock [74]. Dans ce
cas, un fournisseur doit assurer, en utilisant une flotte de véhicules homogènes, la distribution
de certains produits à un ensemble de clients sur un horizon de temps, sachant que chaque client
ayant une capacité de stockage limitée. En plus, chaque client consomme les produits avec un
taux connu dans chaque période de l’horizon. L’objectif est de minimiser la somme des coûts de
stockage et de transport. Dans cette partie, nous présentons un modèle mathématique de l’IRP
en prenant le cas standard de la littérature [24], c’est-à-dire, un IRP avec un seul produit, un
seul véhicule, multi-périodes.
Formellement, nous définissons un graphe G(V, A) où :

• V = {0, ..., n} est l’ensemble des sommets. Le sommet 0 représente le fournisseur et

l’ensemble V 0 = V /{0} représente les clients.

• hi : Le coût de stockage dans le site i, i ∈ V .

• T = {1, ..., p} est l’ensemble des périodes, avec p la longueur de l’horizon de temps.

• rt est la quantité de produit disponible chez le fournisseur à chaque période t ∈ T .

• Iit et I0t sont les niveaux de stocks des clients et du fournisseur, respectivement; à la fin de
la période t ∈ T .

• dti est la demande à la période t ∈ T effectuée par le client i ∈ V 0 .

• Q : La capacité du véhicule.

• Ci : La capacité de stockage du client i.

• cij est le coût du trajet du site i vers le site j.

14
 1.3. Le transport et la distribution dans la chaîne logistique

Les variables de décision

• qit est la quantité de produit livrée au client i durant la période t.

• xtij est le nombre de fois où l’arc (i, j) (avec i ∈ j) est traversé par le véhicule dans la
période t.

• yit = 1 si i ∈ V est visité pendant la période t.

Le problème IRP peut être modélisé par le programme linéaire en nombres entiers suivant:
La fonction objectif:
XX X X X
min hi Iit + cij xtij (1.23)
i∈V t∈T i∈V j∈V,i<j t∈T

Sous les contraintes:

X
I0t = I0t−1 + rt − qit t∈T (1.24)
i∈V 0

Iit = Iit−1 + qit − dti i∈V0 t∈T (1.25)

Iit ≥ 0 i∈V t∈T (1.26)

qit ≥ Ci yit − Iit−1 i∈V0 t∈T (1.27)

qit ≤ Ci − Iit−1 i∈V0 t∈T (1.28)

qit ≤ Ci yit i∈V0 t∈T (1.29)

X
qit ≤ Q t∈T (1.30)
i∈V 0

X
qit ≤ Qy0t t∈T (1.31)
i∈V
X X
xtij + xtji = 2yit i∈V0 t∈T (1.32)
j∈V 0 ,i<j j∈V 0 ,i>j
X X X
xtij ≤ yit − ygt S⊆V t∈T g∈S (1.33)
i∈S j∈S,i<j i∈S

qit ≥ 0 i∈V t∈T (1.34)

xtij ∈ {0, 1} i, j ∈ V, i 6= j t∈T (1.35)

xti0 ∈ {0, 1, 2} i∈V t∈T (1.36)

15
 1.4. Les outils pour l’optimisation de la chaîne logistique

yit ∈ {0, 1} i∈V t∈T (1.37)

La fonction objectif (1.23) minimise la somme des coûts de stockage et de transport. Les
contraintes (1.24) et (1.25) définissent les niveaux des stocks chez le fournisseur et les clients re-
spectivement. La contrainte (1.26) assure la non-négativité des niveaux de stocks. Les contraintes
(1.27, 1.28 et 1.29) définissent la quantitée livrée pour chaque client. La contrainte (1.30) impose
la contrainte de capacité du véhicule. En plus, les contraintes (1.31, 1.32 et 1.33) assurent la
faisabilité de la route de chaque periode. Enfin, les contraintes de (1.34) à (1.37) assurent la
non-négativité et l’intégrité des variables de décision.

1.4 Les outils pour l’optimisation de la chaîne logistique

Un problème d’optimisation consiste à trouver une solution d’un problème donné en minimisant
ou bien en maximisant une fonction objectif donnée. En outre, une technique d’optimisation est
la méthode qu’on l’utilise pour trouver une solution pour un problème de minimisation ou de
maximisation. Au fil des années, de nombreuses techniques (méthodes) de résolution de problèmes
d’optimisation ont été proposées [46, 51, 62, 61, 70, 13]. En effet, nous pouvons regrouper ces
méthodes en deux grandes classes : la classe de méthodes approchées et la classe de méthodes
exactes. Dans cette partie nous donnons une vue générale sur ces deux classes de méthodes. La
figure 1.2 résume les différentes méthodes des deux classes.

Figure 1.2: Classification de méthodes d’optimisation

1.4.1 Méthodes exactes

Les méthodes exactes sont des méthodes qui cherchent la solution optimale d’un problème en
explorant exhaustivement toutes les solutions possibles dans l’espace de recherche. Cependant,
l’inconvénient majeur de ces méthodes est le temps d’exécution, car toutes les solutions sont
évaluées une à une et le temps d’exécution augmente exponentiellement avec la taille du problème

16
 1.4. Les outils pour l’optimisation de la chaîne logistique

considéré. Donc, ces techniques restent inappropriées aux problèmes combinatoires de grandes
tailles [42]. Comme exemple de ces méthodes, nous pouvons citer : la programmation dynamique,
la génération de colonne, l’algorithme A*, les algorithmes de type : branch & bound, branch &
cut, branch & price, etc.

1.4.2 Méthodes approchées

Les problèmes d’optimisation du monde industriel sont généralement de grandes tailles et dis-
posent de nombreuses contraintes, donc les méthodes exactes ne sont pas utilisables. Dans ce
cas, on doit chercher une bonne solution en un temps raisonnable au lieu d’attendre l’obtention
d’une solution optimale après des années de calcul ! [42]. Contrairement aux méthodes exactes,
les méthodes approchées ne garantissent pas l’optimalité de la solution mais, elles permettent de
trouver des solutions de très bonne qualité en un temps d’exécution raisonnable, c-à-dire, elles
cherchent un bon compromis entre la qualité de la solution et le temps de calcul. Dans la littéra-
ture, de nombreuses méthodes approchées ont été proposées. Nous pouvons diviser ces méthodes
en 4 catégories: des heuristiques, des méta-heuristiques, des algorithmes à performance garantie
et des algorithmes hybrides. Par la suite nous présentons chaque catégorie.

[Link] Heuristiques
Dans la littérature, il existe plusieurs définitions d’une heuristique, ici nous présentons celle de
Feigenbaum et Feldman (1963) [38] : "Une heuristique (règle heuristique, méthode heuristique)
est une règle d’estimation, une stratégie, une astuce, une simplification, ou tout autre type de
dispositif qui limite considérablement la recherche de solutions dans des espaces problématiques
importants. Les heuristiques ne garantissent pas des solutions optimales. En fait, elles ne garan-
tissent pas une solution du tout. Tout ce qui peut être dit d’une heuristique utile, c’est qu’elle
propose des solutions qui sont assez bonnes la plupart du temps".
En outre, dans le domaine de l’optimisation combinatoire on peut dire qu’une heuristique est
une méthode approchée développée pour résoudre un problème particulier et elle nécessite des
connaissances approfondies sur le problème traité. Le but d’une heuristique est de trouver de
bonnes solutions (pas forcement optimales) pour un problème donné dans un temps d’exécution
très réduit. Les méthodes constructives représentent un bon exemple des heuristiques.

[Link] Metaheuristiques
Selon Osman et Laporte (1996) [79]: "une métaheuristique est un processus itératif qui subor-
donne et guide une heuristique, en combinant intelligemment plusieurs concepts pour explorer et
exploiter tout l’espace de recherche. Des stratégies d’apprentissage sont utilisées pour structurer
l’information afin de trouver efficacement des solutions optimales, ou presque-optimales".
Généralement, une heuristique est un algorithme développé pour résoudre un problème spé-
cifique. Cependant, une métaheuristique est une stratégie générale qu’on peut appliquer pour
résoudre un grand nombre de problèmes d’optimisation. Comme par exemple : l’heuristique de
saving est une heuristique développée que pour résoudre le VRP. Cependant, on peut utiliser la
recherche Tabou (metaheuristique) pour résoudre le VRP comme on peut l’utiliser pour résoudre
d’autres problèmes. Dans la littérature, de nombreuses métaheuristiques ont été proposées qui
peuvent être subdivisées en deux grandes familles : les méthodes de recherche locale (à base de
solution unique) et les méthodes de recherche globale (à base d’une population de solutions). Ces
deux familles sont décrites ci-dessous.

17
 1.5. Conclusion

1. Les méthodes de recherche locale (Local Search Methods)

Les méthodes de recherche locale sont des algorithmes à base de solution unique qui se
basent généralement sur la notion de voisinage. Elles commencent à partir d’une solution
initiale, ensuite à chaque itération elles essayent d’améliorer la solution courante en ex-
ploitant son voisinage. De nombreuses méthodes de recherche locale ont été proposées dans
la littérature, ici nous citons les plus connues : la méthode de descente, la méthode du
recuit simulé, la recherche Tabou, la recherche à voisinage variable, la méthode GRASP,
etc.

2. Les méthodes de recherche globale (Global Search Methods)

Les méthodes de recherche globale, appelées aussi les algorithmes évolutionnaires [61], sont
des méthodes à base de population de solutions et qui sont en général inspirées de la
nature. Ces méthodes utilisent un ensemble de solutions appelé population. Elles commen-
cent avec une population initiale et, à chaque itération, elles essayent de construire une
nouvelle population meilleure basée sur la précédente afin de converger vers de bonne(s)
solution(s). Comme exemples de ces méthodes nous pouvons citer: les algorithmes géné-
tiques, l’algorithme d’optimisation par essaim de particules, l’algorithme de colonies de
fourmis, etc.

[Link] Algorithmes à performance garantie

Les algorithmes à performance garantie sont des méthodes approchées basées plutôt sur des
principes mathématiques. En se basant généralement sur des théorèmes prouvés mathématique-
ment, ces algorithmes nous permettent d’assurer que, dans le pire des cas, l’écart entre la solution
trouvée et la solution optimale sera au plus d’un facteur donné p.

[Link] Approches hybrides

Les méthodes approchées sont des méthodes puissantes, mais la combinaison entre ces méthodes
augmente encore leur puissance. En outre, les approches hybrides sont des méthodes qui visent à
combiner deux ou plusieurs algorithmes afin d’exploiter leurs points forts et de compenser leurs
faiblesses. Dans la littérature nous trouvons généralement deux types d’hybridations:

• L’hybridation entre les méthodes approchées, par exemple : l’hybridation entre les méta-
heuristiques basées population et les méthodes de recherche locale.

• L’hybridation entre les méthodes approchées et les méthodes exactes, soit en utilisant une
méthode approchée pour calculer une borne inferieure et/ou supérieure pour un algorithme
exact ou bien en utilisant un algorithme exact pour résoudre un sous-problème au sein d’une
méthode approchée (Mat-heuristiques).

1.5 Conclusion
Dans ce chapitre nous avons présenté les problèmes d’optimisation liés à la logistique de distribu-
tion et de transport et qui constituent le noyau des problèmes étudiés dans cette thèse. D’abord
nous avons présenté un aperçu sur les chaînes logistiques, ensuite nous avons décrit en détail
les trois problèmes de base de la logistique de distribution et de transport logistique, à savoir le
problème de localisation, le problème d’élaboration des tournées de véhicules et le problème de

18
 1.5. Conclusion

gestion de stock. Ainsi, nous avons donné un aperçu sur les deux problèmes résultant en com-
binant deux problèmes de base, à savoir le problème de localisation-routage et le problème de
routage avec gestion de stock. Enfin, nous avons consacré la dernière partie de ce chapitre pour
donner une vue générale sur les outils d’optimisation des chaînes logistiques.
Dans le chapitre suivant nous allons étudier le problème de localisation-routage avec con-
trainte de capacité en proposant une heuristique de résolution.

19
Chapitre 2

Algorithme en deux phases pour le

problème de localisation-routage avec
contrainte de capacité

Sommaire
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Un état de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Modèle mathématique pour le CLRP . . . . . . . . . . . . . . . . . . 23
2.4 Méthodologie de la solution . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4.1 La première phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 La deuxième phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.3 Algorithme complet (2-SH) . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.1 Réglage des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.2 Le jeu de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5.3 Résultats et discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.1 Introduction
Le problème de localisation-routage (Location Routing Problem (LRP)) combine deux problèmes,
à savoir le problème de localisation et le problème d’élaboration des tournées. Ce problème
consiste à choisir un sous-ensemble de dépôts à ouvrir parmi un ensemble de dépôts candidats,
et à élaborer des tournées de véhicules afin de satisfaire les demandes des clients avec comme
objectif d’optimiser un ou plusieurs critères tout en respectant certaines contraintes. Dans la
littérature, de nombreuses variantes du problème de localisation-routage ont été étudiées. Dans
notre étude nous traitons le problème de localisation-routage avec contrainte de capacité sur les
véhicules (Capacitated Location Routing Problem (CLRP)).
Dans ce chapitre, nous allons présenter un nouvel algorithme pour résoudre le problème
CLRP à grande échelle. Notre objectif est de trouver des solutions de bonne qualité pour des
instances de grande taille et avec un temps de calcul raisonnable. Pour cela, nous proposons une

20
 2.2. Un état de l’art

méthode composée de deux grandes phases. Dans la première phase, une heuristique d’insertion
est appliquée pour trouver une tournée géante non-fermée, puis nous divisons cette tournée en
plusieurs routes tout en respectant la contrainte de capacité du véhicule. Le coût de chaque route
est amélioré en utilisant la recherche Tabou (Tabu Search (TS)) afin de construire un ensemble
de routes avec des coûts minimaux. Dans la seconde phase, notre objectif est de déterminer un
ensemble de dépôts à ouvrir, et d’affecter chaque route à un de ces dépôts. Pour cela, nous allons
utiliser une procédure de recuit simulé [49].
Dans ce qui suit, nous donnons un aperçu global de la littérature sur le problème CLRP
et nous présentons la formulation mathématique du problème. Puis, l’algorithme proposé est
présenté. Ensuite, l’évaluation numérique et les résultats obtenus par l’algorithme proposé sont
présentées.

2.2 Un état de l’art

Au cours des quatre dernières décennies, un nombre considérable de méthodes ont été développées
pour le problème CLRP. En général, nous pouvons classer ces méthodes en trois catégories : des
algorithmes exacts, des méta-heuristiques et des math-heuristiques [34]. La plupart des méta-
heuristiques proposées sont des algorithmes en deux phases. Dans la première phase, le sous-
problème de localisation est résolu, avec comme but la détermination de certains dépôts à ouvrir
et l’affectation des clients à ces dépôts. Ensuite, dans la deuxième phase, le sous-problème de
routage est traité pour chaque dépôt ouvert. En plus, certaines méthodes proposées permettent la
résolution des deux sous-problèmes dans la même phase (généralement la deuxième phase) [37].
Dans plusieurs approches proposées, les deux sous-problèmes sont résolus au sein d’une boucle
itérative.
Les méthodes exactes proposées pour résoudre le CLRP sont en général des méthodes de
type : branch & price, branch & cut et génération de colonnes. Bien que ces algorithmes soient
appliqués, avec succès, avec différentes manières d’implémentation, il reste beaucoup de pistes
qui ne sont pas encore exploitées [34]. Les mat-heuristiques sont des algorithmes hybrides qui
combinent la programmation mathématique avec les méta-heuristiques. Pour le CLRP, les méta-
heuristiques sont souvent combinées avec la relaxation lagrangienne et/ou les solveurs (comme
CPLEX). En général, ces solveurs utilisent des algorithmes exacts de type branch & cut [24].
Dans le tableau 2.1, nous résumons les travaux de recherche traitant le CLRP. Parce que ce
travail porte sur le CLRP à grande échelle, par la suite, les travaux liés à notre cas d’étude
seront présentés en détail.
Harks et al. (2013) [52] ont proposé un algorithme à performance garantie (Approximation
Algorithm « Approx ») pour résoudre le CLRP. Tout d’abord, l’algorithme cherche une bonne
solution pour le problème de localisation en résolvant un cas spécial du problème de localisation
sans contrainte de capacité (Uncapacitated Location Problem). Puis, un arbre couvrant minimal
sur un graphe modifié est construit. L’algorithme divise cet arbre en sous-arbres tel que la somme
des demandes des clients dans chaque sous-arbre est entre 50% et 100% de la capacité du véhicule.
Ensuite, l’heuristique construit une tournée à partir de chaque sous-arbre en dupliquant ses arcs.
Chaque route est affectée à un dépôt ouvert dans l’étape précédente. Enfin, pour renforcer leur
approche, les auteurs utilisent l’heuristique de Lin-Kernighan-Helsgaun (LKH) (Helsgaun(2000))
[53] pour améliorer le coût des routes de la solution retournée par l’algorithme Approx. Les deux
méthodes proposées (Approx et Approx-LKH) ont été utilisées avec succès pour résoudre des
instances de CLRP de grande taille.
Alvim et Taillard (2013) [6] ont développé une heuristique pour le problème CLRP à grande

21
 2.2. Un état de l’art

Tableau 2.1: Méthodes proposées pour le CLRP

Référence Categorié Méthode
Chan and Baker (2005) [17] Métaheuristique Méthode de type Clustering et Saving
Bouhafs et al. (2006) [15] Métaheuristique Hybridation entre recuit simulé
et l’algorithme de colonies de fourmis
Prins et al. (2006a) [84] Métaheuristique Méthode de type GRASP
avec Path Relinking
Prins et al. (2006b) [83] Métaheuristique Algorithme mémétique avec
gestion de la population
Duhamel et al. (2010)[36] Métaheuristique Hybridation entre GRASP
et la recherche locale évolutionnaire
Marinakis and Marinaki (2008a)[72] Métaheuristique Hybridation entre l’algorithme
d’optimisation par essaim de particules,
la méthode GRASP et une recherche locale
Marinakis and Marinaki (2008b) [71] Métaheuristique Algorithme génétique
Jokar and Sahraeian (2012) [59] Métaheuristique Recuit simulé
Yu et al. (2010) [104] Métaheuristique Recuit simulé
Derbel et al. (2011) [31] Métaheuristique Recherche à voisinage variable
Jabal-Amelia et al. (2011) [56] Métaheuristique Descente à voisinage variable .
Stenger et al. (2011) [93] Métaheuristique Hybridation entre la méthode GRASP et
la recherche à voisinage variable
Ting and Chen (2013) [98] Métaheuristique Algorithme de colonies de fourmis
Akca et al. (2009) [5] Algorithme exact Algorithme de type branch & price
Belenguer et al. (2011) [14] Algorithme exact Algorithme de type branch & cut
Contardo (2011) [25] Algorithme exact Algorithme de coupe & génération de colonnes
Prins et al. (2007) [82] Matheuristique La relaxation lagrangienne
avec une recherche tabou granulaire
Chen and Ting (2007) [18] Matheuristique La relaxation lagrangienne avec
recuit simulé
Contardo et al. (2014) [26] Matheuristique Génération de colonnes + GRASP +
procedures de recherche locale
Escobar et al. (2014) [37] Matheuristique Un solveur de MIP
avec une recherche tabou granulaire

22
 2.3. Modèle mathématique pour le CLRP

échelle. La méthode proposée est basée sur la méta-heuristique d’optimisation partielle en con-
ditions d’intensifications spéciales (POP-MUSIC). Au début, l’algorithme cherche un ensemble
de dépôts à ouvrir en résolvant le problème p-médian (p-median problem) pour un échantillon
de clients. Tous ces clients sont alors affectés à ces centres en construisant des clusters. Ensuite,
l’algorithme utilise la méthode du gradient pour diviser chaque super-cluster, de la première
étape, tout en respectant la capacité du véhicule. Afin de réduire la violation de la capacité du
véhicule, la méthode du gradient est renforcée par une recherche locale. Enfin, après la construc-
tion de la solution initiale, les auteurs ont proposé une méthode de recherche Tabou, qui est
similaire à celle présentée par Taillard (1993) [95], comme une procédure d’amélioration dans le
Framework de POPMUSIC.
Dans l’état de l’art de Nagy et Salhi (2007) [78], les auteurs ont résumé les travaux pour
de nombreuses variantes de CLRP. Enfin, plus récemment, Drexl et Schneider (2013) [34] et
Prodhon et Prins (2014) [86] présentent un état de l’art des travaux récemment proposés pour
le LRP.

2.3 Modèle mathématique pour le CLRP

Dans cette section nous présentons le modèle mathématique de CLRP proposé par Prins et
al. (2007) [82]. L’objectif est d’ouvrir un ensemble de dépôts et de déterminer l’ensemble de
routes provenant de chaque dépôt ouvert dans le but de satisfaire les demandes des clients en
minimisant le coût total, y compris le coût d’ouverture des dépôts et le coût de transport. Les
deux hypothèses importantes dans notre cas sont les suivantes :

• Chaque client doit être servi par un seul véhicule lorsque sa demande est inférieure à la
capacité du véhicule et servi par deux véhicules, sinon [52].

• Chaque route doit commencer et se terminer au même dépôt ouvert et sa charge doit être
inférieure ou égale à la capacité du véhicule.

Le CLRP est défini sur un graphe complet G = (V, E), où V est l’ensemble des sommets
représentant les dépôts candidats I et les clients J (V = J ∪ I), et E est l’ensemble des arcs
reliant tous les sommets. En outre, à chaque arc (i, j) ∈ E, un coût de transport symétrique
cij est associé. La flotte K est composée d’un nombre illimité de véhicules homogènes et chaque
véhicule possède une capacité Q et un coût fixe d’utilisation F . Ainsi, à chaque dépôt candidat
i ∈ I est associé une capacité Pi et un coût d’ouverture Oi . En plus, chaque client j ∈ J possède
une demande dj connue à l’avance. Les variables de décisions sont des variables binaires où :
yi = 1 si le dépôt i est ouvert, fij = 1 si le client j est servi à partir du dépôt i et xijk = 1 si le
véhicule k va directement du sommet i au sommet j. Enfin, le CLRP considéré peut être formulé
comme suit:
X XX X X XX
min z = Oi yi + cij xijk + F xijk (2.1)
i∈I i∈V j∈V k∈K k∈K i∈I j∈J

Sous les contraintes: X X

xijk = 1 ∀j ∈ J (2.2)
k∈K i∈V
XX
dj xijk ≤ Q ∀k ∈ K (2.3)
j∈J i∈V

23
 2.4. Méthodologie de la solution
X
dj fij ≤ Pi yi ∀i ∈ I (2.4)
j∈J
X X
xijk − xjik = 0 ∀i ∈ V, ∀k ∈ K (2.5)
j∈V j∈V
XX
xijk ≤ 1 ∀k ∈ K (2.6)
i∈I j∈J
XX
xijk ≤ |S| − 1 ∀S ⊆ J, ∀k ∈ K (2.7)
i∈S j∈S
X X
xiuk + xujk ≤ 1 + fij ∀i ∈ I, ∀j ∈ J, ∀k ∈ K (2.8)
u∈J u∈V −(j)

xijk ∈ {0, 1} ∀i ∈ V, ∀j ∈ V, ∀k ∈ K (2.9)

yi ∈ {0, 1} ∀i ∈ I (2.10)
fij ∈ {0, 1} ∀i ∈ I, ∀j ∈ V (2.11)
La fonction-objectif (2.1) minimise la somme des coûts définis auparavant. La contrainte
(2.2) assure que chaque client possède un seul prédécesseur dans la route et qu’il est visité par
exactement un seul véhicule. Les équations (2.3) et (2.4) assurent respectivement le respect de
la contrainte de capacité de véhicules et de dépôts. Les contraintes (2.5) et (2.6) assurent la
continuité de chaque route et que chaque route commence et se termine au même dépôt ouvert.
L’élimination des sous-cycles est assurée par la contrainte (2.7). La contrainte (2.8) indique
qu’un client j est affecté à un dépôt i si et seulement s’il y a une route qui relie i et j. Enfin, les
contraintes (2.9), (2.10) et (2.11) imposent l’intégrité des variables de décisions.

2.4 Méthodologie de la solution

Récemment, dans la plus part des méthodes proposées pour le CLRP, le problème initial est
souvent décomposé en deux sous-problèmes et résolu en utilisant des algorithmes à deux phases.
Initialement, le sous-problème de localisation est traité et, ensuite le sous-problème de routage
est résolu pour chaque dépôt ouvert. Dans plusieurs cas, avec le but d’améliorer la qualité de la
solution obtenue, les deux phases sont répétées dans une boucle itérative [34]. Cependant, ces
techniques peuvent augmenter la complexité algorithmique de ces méthodes, ainsi que l’utilisation
des différentes mat-heuristiques et/ou algorithmes exacts; par conséquent, ces méthodes ont une
difficulté à résoudre les instances de grande taille (lorsque nous avons de nombreux clients et
dépôts) [26, 52]. En d’autres termes, ces méthodes utilisent des solveurs, des méthodes exactes et
des opérateurs semi-exhaustifs pour améliorer la qualité de la solution; et parce que ces techniques
sont très coûteuses en termes de temps d’exécution notamment pour les instances de grande taille,
leur efficacité n’est pas garantie. Donc, pour traiter des instances de grande taille, nous devons
choisir des procédures et des outils pour chercher le meilleur compromis entre la qualité de la
solution et le temps d’exécution. Pour atteindre cet objectif, nous proposons l’heuristique à deux
phases suivante (Two Stage Heuristic (2-SH)).
Dans cette section, l’algorithme 2-SH est présenté. Comme mentionné ci-dessus, notre objectif
est de proposer un algorithme pour traiter le CLRP à grande échelle et de trouver des solutions de
bonne qualité dans un temps d’exécution raisonnable, afin d’être compétitif avec les méthodes de
la littérature [52]. Dans notre approche, contrairement aux heuristiques de la littérature, le sous-
problème de routage est résolu d’abord et ensuite, le sous-problème de localisation est traité sans

24
 2.4. Méthodologie de la solution

aucune boucle itérative, de même que les méthodes exactes et les solveurs ne sont pas utilisés.
L’algorithme proposé se compose de deux grandes phases qui sont exécutées séquentiellement.
La première phase est une heuristique d’insertion suivie par une procédure de recherche Tabou
(Tabu Search (TS)) dans laquelle un ensemble de routes de coût minimal est construit. Dans la
deuxième phase, le recuit simulé est utilisé pour déterminer un sous-ensemble de dépôts à ouvrir
et pour affecter chaque route à un de ces dépôts. Dans ce qui suit, toutes ces procédures sont
décrites en détail.

2.4.1 La première phase

Dans cette phase, l’objectif est de construire un ensemble de routes faisables avec un coût mini-
mal. D’abord, une heuristique d’insertion est utilisée pour créer une tournée géante non-fermée
(pas de retour au sommet de départ). Ensuite, la tournée géante est divisée en plusieurs routes
de manière à satisfaire, pour chaque route, la capacité du véhicule. Enfin, la recherche Tabou
est appliquée pour améliorer la qualité des routes créées. Ces procédures sont décrites en détail
dans les paragraphes suivants.

[Link] L’Heuristique d’Insertion (HI)

Dans Prins et al. (2007) [82] et Escobar et al. (2014) [37], un schéma d’initialisation a été proposé
en construisant une tournée géante à l’aide des algorithmes connus, ensuite cette tournée est
divisée. Cependant, dans notre schéma d’initialisation proposé, l’heuristique d’insertion (HI)
construit une tournée non-fermée et pas une tournée fermée (TSP-tour). En effet, dans une
tournée fermée deux contraintes doivent être respectées. La première contrainte est : la tournée
doit commencer et se termine au même sommet (client). La seconde contrainte est que : chaque
sommet doit avoir une seule visite. Cependant, dans la tournée non-fermée, seulement la seconde
contrainte est imposée. Par conséquent, la construction d’une tournée fermée est plus difficile
et demande plus de temps d’exécution qu’une tournée non-fermée. En outre, une heuristique
d’insertion est suffisante pour construire une bonne tournée géante non-fermée qui recouvre tous
les clients. Enfin, nous estimons que cette technique est plus bénéfique en termes de temps
d’exécution et de la qualité de solution notamment pour les instances de grande taille.
Les heuristiques d’insertion sont des méthodes constructives simples et efficaces. Chaque
heuristique d’insertion commence avec un sous-ensemble de sommets (clients), puis elle construit
une solution en ajoutant progressivement le reste des clients un par un. Ici, nous exposons le
fonctionnement de HI.
Tout d’abord nous définissons les structures suivantes:

• I_L : une liste contenant tous les clients;

• I_G : une séquence de clients (liste) qui construit une tournée non-fermée, initialement
vide;

• L_R : l’ensemble de routes qui respectent la contrainte de capacité de véhicule;

Au début, deux clients sont sélectionnés aléatoirement à partir de I_L. Ils sont retirés de I_L
et insérés dans I_G. Ensuite, à chaque itération, nous cherchons la meilleure insertion possible,
c’est-à-dire, nous évaluons le coût généré par l’insertion de chaque client non servi (les clients
dans la liste I_L) dans toutes les positions possibles dans I_G. Le candidat qui donne le coût
minimal est sélectionné et est inséré dans I_G. Ce processus est répété jusqu’à ce que tous les

25
 2.4. Méthodologie de la solution

clients soient insérés dans I_G. En outre, la procédure de séparation est appliquée à I_G pour
construire un ensemble de routes faisables (L_R). Dans la procédure de séparation, la séquence
des clients dans I_G est respectée, et la somme des demandes des clients dans chaque route doit
être inférieure ou égale à la capacité du véhicule. En plus, chaque client avec une demande qui
dépasse la capacité du véhicule est servi par deux véhicules; dans le premièr véhicule, le client
est servi par la capacité totale du véhicule, et le reste de la demande est servi avec les autres
clients dans la séquence de I_G [52]. HI est décrite en détail dans l’algorithme 1.

Algorithme 1 Heuristique d’insertion

1: entrée : I_L, l’ensemble de clients;
2: sortie : R_L, un ensemble de routes;
3: c1, c2, c3 : client;
4: c1, c2 ← clients d’un arc ∈ I_L;
5: ajouter c1, c2 dans I_G et les supprimer de I_L;
6: calculer le fitness de chaque c ∈ I_L;
7: tant que (I_L n’est pas vide) faire
8: c3 ← meilleur_client c ∈ I_L;
9: supprimer c3 de I_L;
10: ajouter c3 dans I_G dans la bonne position;
11: faire la mise à jour du fitness de chaque c ∈ I_L;
12: fin tant que
13: R_L ←découper(I_G);
14: retourner R_L;

[Link] La recherche Tabou (TS)

Pour améliorer la qualité des routes générées dans l’étape précédente, nous utilisons la recherche
Tabou. La recherche Tabou est une méta-heuristique très utilisée, avec succès, pour résoudre
différents problèmes d’optimisations combinatoires [43, 68]. Formellement, la TS commence avec
une solution initiale T _Sc et choisit, à chaque itération, la meilleure solution T _S1 non-Tabou
dans sa structure de voisinage T _N (T _Sc). Ensuite, la solution T _Sc est remplacée par la
nouvelle solution T _S1 et T _Sc est déclarée interdite ou Tabou. Cette procédure se termine
quand un certain nombre d’itérations est atteint.
Dans la littérature, plusieurs variantes de TS ont été développées essentiellement pour le
problème du voyageur de commerce (TSP). Cependant, ces méthodes utilisent des techniques
qui consomment beaucoup de temps de calcul [11]. Alors, nous pensons que ces techniques ne
seront pas efficaces dans l’heuristique 2-SH parce que, dans notre cas, le but de la procédure
TS est de converger rapidement vers des solutions de bonne qualité, donc de faire le meilleur
compromis entre la qualité de la solution et le temps d’exécution. Par conséquent, pour faire face
à ce problème, nous proposons la méthode décrite par la suite.
Les principales composantes de la méthode TS sont : la solution initiale, la structure de
voisinage, les stratégies d’intensification et de diversification, et la mémoire à court terme (liste
Tabou). Nous présentons ces composantes dans les paragraphes suivants. Enfin, la structure
générale de notre méthode est présentée dans l’algorithme 2.

1. La solution initiale. La procédure de séparation génère des tournées (routes) non-fermées,

c’est-à-dire, chaque tournée commence par un client et se termine par un autre en visitant

26
 2.4. Méthodologie de la solution

un certain nombre de clients. Ici notre but est de créer, à partir d’une tournée non-fermée,
une tournée fermée ou bien un TSP-tour pour qu’elle puisse être utilisée comme une solution
initiale par la TS. Dans la littérature, plusieurs heuristiques ont été utilisées pour fournir
une solution initiale pour la TS [11]. Dans le 2-SH, nous utilisons l’heuristique du Plus
Proche Voisin (PPV). A partir d’une tournée initiale qui contient un seul client, à chaque
itération, la procédure PPV trouve le client non servi le plus proche et l’insère dans la
tournée. Ces étapes sont répétées jusqu’à ce que tous les clients concernés soient insérés.

2. La structure de voisinage. Nous utilisons trois mouvements pour construire la structure

de voisinage: le déplacement (Shift), l’échange (swap) et le déplacement aléatoire (random-
shift). Ces mouvements sont basés sur la notion de pires clients. P I_CL est le sous-
ensemble des T _K pires clients dans la tournée. Le pire client est celui qui possède les
deux arcs les plus longs dans la tournée.

• Le déplacement (Shift) : ce mouvement consiste à enlever un pire client sélectionné au

hasard à partir de sa position, et à l’insérer dans la meilleure position dans la route.
• L’echange (Swap) : ce mouvement consiste à échanger les positions de deux clients. Le
premier est un pire client sélectionné au hasard, mais le second est le meilleur client
qui minimise le coût du mouvement.
• Le déplacement aléatoire (Random-shift) : ce mouvement est un cas particulier du
Shift décrit précédemment. Il consiste à insérer le client sélectionné dans une position
aléatoire.

La méthode TS proposée exécute les trois mouvements ci-dessus comme suit : la structure
de voisinage est construite par le shift et le swap si le coût de la meilleure solution est
amélioré dans les T _N I dernières itérations, sinon le Random-shift est appliqué.

3. Les stratégies d’intensification et de diversification. Deux techniques

d’intensification sont utilisées : le choix de la meilleure solution dans la structure
de voisinage pour être la solution courante et le déplacement des clients vers les meilleures
positions dans les tournées pendant la recherche. Pour diversifier la recherche, le mouve-
ment random-shift, décrit ci-dessus, est utilisé. En plus, si la meilleure solution dans la
structure le voisinage dégrade la fonction objectif, cette solution est acceptée pour être la
nouvelle solution courante.

4. Mémoire à court terme. La mémoire à court terme, appelée aussi la liste Tabou
(T _List), est une liste qui contient les solutions interdites dans l’itération courante.
L’objectif de la liste Tabou est d’empêcher l’heuristique de tomber dans des cycles à court
terme. La longueur de cette liste est T _L. Dans notre cas, nous utilisons la technique la
plus simple, après la construction de la structure de voisinage, toutes les solutions Tabous
sont supprimées et ensuite la meilleure parmi le reste est choisie pour être la nouvelle
solution courante.

L’heuristique Tabou proposée ci-dessus est un peu moins performante que les méthodes de
la littérature (en terme de la qualité de solutions) mais elle est plus rapide. En effet, cette
caractéristique est importante pour réduire les temps de calcul de la méthode 2-SH, car la TS
va être exécutée plusieurs fois.

27
 2.4. Méthodologie de la solution

Algorithme 2 Recherche Tabou

1: entrée: r une route non-fermée;
2: sortie: r une route fermée (TSP-tour);
3: T 1 : entier;
4: r ←PPV(r);
5: T _Sc ← r; T _Sbest ← r;
6: T 1 ← T _N I;
7: ajouter T _Sc à T _list;
8: tant que (le critère d’arrêt non satisfait) faire
9: créer T _N (T _Sc) selon T 1;
10: T _Sc ← meilleur { T _S1 ∈ T _N (T _Sc) et T _S1 ∈
/ T _list };
11: ajouter T _Sc à T _list;
12: Si (coût(T _Sc) <coût(T _Sbest))
13: T _Sbest ← T _Sc;
14: T 1 ← T _N I + 1;
15: fin si
16: T 1 ← T 1 − 1;
17: fin tant que
18: r ← T _Sbest;
19: retourner r

2.4.2 La deuxième phase

Dans cette phase, le sous-problème de localisation, appelé le problème de localisation des dépôts
sans la contrainte de capacité (Uncapacitated Facility Location Problem (UFLP)), est résolu en
utilisant la méthode de recuit simulé. Le problème de localisation des dépôts sans la contrainte
de capacité consiste à ouvrir certains dépôts (à partir d’un ensemble de dépôts candidats) pour
servir un ensemble de clients, tout cela en minimisant le coût total (coût d’ouverture des dépôts
et le coût d’affectation des clients à ces dépôt) [12]. Le nombre de dépôts à ouvrir n’est pas fixé
à l’avance. Similaire à Escobar et al. (2014) [37] et Prins et al. (2007) [82], chaque route est
considérée comme un super-client. Le coût d’affectation de la route r (super-client) au dépôt i,
noté Lri , est la distance minimale entre i et r (L est une matrice de coûts d’affectation). Donc,
chaque route r sera servie par le dépôt ouvert le plus proche dans la solution. Bien que, Escobar
et al. (2014) [37] et Prins et al. (2007) [82] utilisent la même idée en considérant chaque route
comme un super-client, le UFLP a été abordé en utilisant des solveurs. Pour les petites instances,
les solveurs sont toujours efficaces avec environ 20 dépôts candidats et 20 à 25 routes. Cependant,
pour les instances de grande taille, jusqu’à 1000 dépôts candidats et environ 7.200 routes, les
méthodes proposées, dans [37, 82], ne peuvent pas être appliquées. Pour faire face à ce problème,
la méthode de recuit simulé suivante est proposée.

[Link] Recuit simulé (Simulated Annealing (SA))

La méthode de recuit simulé est une méta-heuristique inspirée d’un phénomène physique, utilisée
souvent pour résoudre de nombreux problèmes combinatoires NP-difficiles. Cette méthode a
été utilisée également avec succès pour résoudre certains problèmes de localisation [60]. Afin
d’éviter les minima locaux, la SA accepte (avec une certaine probabilité) de passer à des solutions
qui dégrade la fonction objectif. Ce principe est la principale caractéristique de la méthode.
Formellement, notre SA commence avec une solution initiale L_S, et à chaque itération, la

28
 2.4. Méthodologie de la solution

différence θ est calculée entre le coût de la solution courante L_Sc et le coût de la meilleure
solution dans la structure de voisinage L_Sc1 (θ ←Cost(L_Sc1 )−Cost(L_Sc)). Si le coût de la
meilleure solution du voisinage (L_Sc1) est meilleur que le coût la solution courante (L_Sc),
alors la solution courante est remplacée par L_Sc1; sinon la solution L_Sc1 est acceptée avec
une probabilité égale à e−θ/pr (pr est un nombre entier, représentant la température dans le
phénomène physique). Ces étapes sont répétées jusqu’à ce qu’un critère d’arrêt est atteint. En
plus, lorsque l’algorithme progresse, le pr est réduit en utilisant un facteur ρ (ρ < 1), appelé
fonction de refroidissement, pr ← pr × ρ. En outre, afin de renforcer la convergence de SA, une
procédure d’insertion est utilisée pour générer une solution initiale de bonne qualité.
Dans ce qui suit, les parties principales de la SA sont décrites, à savoir : l’heuristique
d’insertion, la représentation de la solution, l’évaluation des voisins et l’exploration du voisi-
nage. Enfin, la SA est décrite en détail dans l’algorithme 3.

1. L’Heuristique d’Insertion pour UFLP (HIU). Dans la littérature, plusieurs méthodes

ont été développées pour le problème UFLP. Dans les heuristiques gloutonnes les plus
connues proposées pour le problème UFLP, tous les dépôts candidats sont réévalués à
chaque itération [94]. En effet, ces heuristiques consomment beaucoup de temps de calcul
et elles ne sont pas efficaces dans notre cas. D’un autre côté, la génération d’une solution
initiale aléatoirement n’est pas souhaitable. Pour faire face à ce problème nous proposons
une heuristique d’insertion basée sur une fonction d’évaluation constante H (voir la formule
2.12). Les dépôts sont évalués une seule fois au début et ils gardent leurs fitness jusqu’à
la fin de l’algorithme. En utilisant cette technique, nous évitons de générer une solution
initiale aléatoire d’un côté et, d’un autre côté, le temps d’exécution de la procédure sera
très réduit (beaucoup mieux que ceux des heuristiques gloutonnes de la littérature). Tout
d’abord, nous définissons la fonction d’évaluation H:
X
Hi ← Oi − Lri (2.12)
r∈R1

Dans (2.12), R1 est un sous-ensemble de clients où le dépôt i est le plus proche parmi tous
les dépôts candidats. Donc, le meilleur dépôt est celui qui a la plus faible valeur de H. Les
étapes de l’heuristique IHU sont les suivantes:

• Etape 1 : évaluer tous les dépôts en utilisant la fonction H.

• Etape 2 : ajouter tous les dépôts dans une liste L_List dans un ordre croissant selon
la valeur de H.
• Etape 3 : choisir au hasard le dépôt i à ouvrir parmi les L_K meilleurs dépôts dans
la liste L_List.
• Etape 4 : ajouter i à la solution L_S.
• Etape 5 : évaluer la nouvelle solution L_S. Si le coût est diminué, alors aller à l’étape
3, sinon arrêter la procédure.

En outre, pour assurer la diversification et la flexibilité de la méthode, les dépôts à ouvrir

sont choisis au hasard parmi les L_K meilleurs (voir l’étape 3).

2. La représentation de la solution. L’efficacité d’un algorithme dépend fortement de

la structure de données utilisée, en particulier la représentation de la solution joue un
rôle important. Dans notre implémentation, trois structures de données sont utilisées : un

29
 2.4. Méthodologie de la solution

vecteur V S et deux matrices (AS, SM ). Dans ce qui suit nous expliquons comment elles
sont utilisées.
Rappelons d’abord que m est le nombre de clients, et n est le nombre des dépôts. La solution
est représentée comme un vecteur V S = {vs1 , ..., vsn } de variables binaires, vsi égale à 1
si le dépôt i est ouvert. Parce qu’il n’y a pas de contrainte de capacité sur les dépôts, il
est évident que chaque client j est affecté au dépôt le plus proche i (évidement parmi les
dépôts ouverts) et le coût de cette affectation est égal à Lij . Pour améliorer l’efficacité
de l’algorithme, une matrice d’affectation AS est proposée. Cette matrice contient, pour
chaque client, le dépôt auquel le client est affecté et le coût de cette affectation. Par ailleurs,
la matrice statique SM contient, pour chaque client i, la liste de tous les dépôts candidats
dans l’ordre croissant du coût d’affectation Lij . La figure 2.1 montre un exemple d’une
solution d’UFLP avec 4 dépôts candidats et 6 clients, et sa représentation.

Figure 2.1: Exemple d’une solution pour l’UFLP.

La solution dans la figure 2.1 est présentée comme suite:

• V S = {0, 1, 0, 1}
client dépôt coût
1 2 8
2 2 7.6
• AS = 3 2 8.3
4 2 7.5
5 4 8
6 4 6
client dépôts
1 1 2 3 4
2 1 2 3 4
• SM = 3 3 2 1 4
4 3 2 4 1
5 3 4 2 1
6 4 3 2 1

3. L’évaluation des solutions voisines. A chaque itération de l’algorithme SA, un ensemble

de nouvelles solutions est généré. Chaque nouvelle solution est le résultat de l’application
d’un opérateur sur la solution courante. D’une manière générale, le coût de chaque nou-
velle solution est calculé indépendamment de la solution courante, mais, cette procédure
consomme beaucoup de temps de calcul, notamment pour des instances de grande de taille.
Afin d’éviter cela, en utilisant AS et SM , le coût de chaque nouvelle solution est recalculé

30
 2.5. Expérimentation

d’une manière incrémentale à partir du coût de la solution courante, c’est-à-dire, juste une
mise à jour des coûts est faite comme suit :

• Si un nouveau dépôt i est ouvert, alors vsi ← 1 et le coût de la solution sera augmenté
par Oi . La complexité de cette procédure de mise à jour est en O (1). Ensuite, pour
chaque client j, si son coût d’affectation ASj,3 est supérieure à Lij , alors j sera affecté
à i, son nouveau coût d’affectation sera Lij et le coût de la solution sera diminué de
ASj,3 − Lij . Il est clair que la complexité de cette boucle est en O(m). Finalement, la
complexité algorithmique de cette procédure de mise à jour est en O(m).
• Dans l’autre cas, si un dépôt i0 est fermé, alors vsi0 ← 0 et le coût de la solution sera
diminué de Oi0 . La complexité de cette mise à jour est en O (1). En plus, pour chaque
client j affecté à i0 , nous cherchons dans SM le premier dépôt ouvert i00 . Donc, j sera
affecté à i00 et le coût de la solution sera augmenté par la valeur Li00 j − ASj,3 . En
effet, il est difficile d’estimer exactement la complexité de cette procédure, mais dans
le meilleur des cas cette procédure est en O (1), lorsque le dépôt fermé n’a qu’un seul
client et le dépôt suivant dans SM [j] est ouvert. Le pire des cas est celui où tous les
clients sont affectés au dépôt fermé et un seul autre dépôt est ouvert, et ce dépôt est
le plus loin de tous les clients, à savoir le dernier à SM pour tous les clients. Dans ce
cas, la complexité de la procédure est O (m × n). Expérimentalement, cette procédure
est très proche de son meilleur des cas.

Contrairement à tout cela, la complexité de la procédure classique qui recalcule la valeur

de chaque nouvelle solution est en O(m × n).

4. La structure de voisinage. Dans le problème UFLP, un voisin de la solution courante

L_Sc peut être obtenu par le changement de statut d’un dépôt (ouverture ou fermeture)
ou de deux dépôts (échange de statuts). Nous avons donc trois mouvements possibles:

• Le mouvement ajouter (ADD), qui ouvre un dépôt fermé.

• Le mouvement supprimer (DROP), qui ferme un dépôt ouvert.
• Le mouvement echanger (SWAP), qui remplace un dépôt ouvert par un autre fermé.

En effet, le SWAP est un mouvement qui consomme beaucoup de temps de calcul [94]. Par
conséquence, à chaque itération seulement les mouvements ADD et DROP sont utilisés
pour créer la structure de voisinage L_N (L_Sc).

2.4.3 Algorithme complet (2-SH)

Enfin, la méthode 2-SH est décrite dans l’algorithme 4. La solution finale (f inal_solution) est
obtenue en attribuant chaque route à son dépôt approprié, c’est-à-dire, à insérer le sommet de
dépôt dans la route. Dans l’algorithme 4, il est clairement indiqué que la procédure TS est
appliquée lorsque le nombre de clients dans la route est supérieur à 7.

2.5 Expérimentation
Dans cette section, nous allons présenter les résultats obtenus par l’algorithme proposé 2-SH.
Dans la littérature, plusieurs jeux d’essai ont été proposés pour le CLRP avec des instances de

31
 2.5. Expérimentation

Algorithme 3 Recuit simulé

1: entrée: L la matrice de coûts d’affectation;
2: sortie: L_S l’ensemble des dépôts ouverts;
3: M in1, M in2 : nombre réel;
4: pour (chaque depôt i)
5: evaluer i en utilisant H;
6: ajouter i à L_List en respectant l’ordre croissant selon H;
7: fin pour
8: M in1 ← ∞;
9: M in2 ← ∞ − 1;
10: tant que (Min2 ≤ Min1)
11: M in1 ← M in2;
12: i1 ←un dépôt parmi les L_K meilleur dans L_List;
13: ajouter i1 à L_S;
14: supprimer i1 de L_List;
15: M in2 ←coût(L_S);
16: fin tant que
17: L_Sc ← L_S;
18: L_Sbest ← L_S;
19: tant que (le critère d’arrêt non satisfait) faire
20: créer L_N (L_Sc);
21: L_Sc1 ← meilleur { L_S ∈ L_N (L_Sc) };
22: θ ←coût(L_Sc1 )−coût(L_Sc);
23: pp ←random(0, 1); /*générer un nombre aléatoire entre 0 et 1*/
24: si((θ < 0) ou (pp ≤ e−θ/pr )) alors
25: L_Sc ← L_Sc1 ;
26: fin si
27: si(coût(L_Sc1 ) <coût(L_Sbest )) alors
28: L_Sbest ← L_Sc1 ;
29: fin si
30: fin tant que
31: retourner L_Sbest ;

32
 2.5. Expérimentation

Algorithme 4 Heuristique en deux phases (2-SH)

1: entrée : instance de CLRP;
2: sortie : solution de CLRP (F inal_solution);
3: R_L ←heuristique_insertion();
4: pour (chaque r ∈ R_L) faire
5: si (|r| ≥ 7) alors
6: r ←Recherche_Tabou(r);
7: fin si
8: fin pour
9: pour (chaque route r ∈ R_L) faire
10: pour (chaque depôt i) faire
11: calculer Lri ;
12: fin pour
13: fin pour
14: L_S ← Recuit_Simulé(L);
15: F inal_solution ← construction(L_S,R_L);
16: retourner F inal_Solution;

petites et moyennes taille (un maximum de 20 dépôts candidats et 200 clients). En effet, ces
instances ne sont pas considérées comme des problèmes de grande taille [52, 86].
Pour le CLRP à grande échelle, nous avons le jeu de d’essai de Harks et al. (2013) [52] avec un
maximum de 1.000 dépôts candidats et 10.000 clients. Parce que l’approche 2-SH est développée
particulièrement pour résoudre le CLRP à grande échelle, nous avons choisi ces instances pour
tester notre algorithme.
L’algorithme 2-SH a été implémenté en Java. Toutes les expériences ont été réalisées sur un
PC équipé d’un processeur Intel i7 à 2.5 GHz et dispose d’une mémoire de 32Go. Pour tester
les performances de notre approche 2-SH, le jeu de d’essai standard de Harks et al. (2013) [52]
est utilisé, et les résultats obtenus sont comparés avec les meilleurs solutions connues et fournies
par les méthodes proposées de la littérature. Ces instances et les meilleurs solutions connues sont
téléchargeables sur le site [1]. Dans ce qui suit, nous allons tout d’abord présenter les paramètres
utilisés pour l’algorithme, ensuite le jeu de d’essai est exposé. Enfin, les résultats obtenus par
l’approche 2-SH sont présentés, comparés et discutés.

2.5.1 Réglage des paramètres

Dans notre expérimentation, les paramètres suivants sont utilisés:
Les critères d’arrêt pour les procédures TS et SA sont fixés comme étant le nombre de clients
dans la route et le nombre de dépôts candidats respectivement. Tout d’abord, les paramètres
pour la métaheuristique TS sont : T _N I = 15, T _K = 10, T _L = 15, la taille de la structure
de voisinage (| T _N (T _S)|) est fixée à 20. Ensuite, pour les paramètres de recuit simulé on a:
L_K = 10, ρ = 0.98, pr = 1500 et la taille de la structure de voisinage (| L_N (LS ) |) est fixée
à 50.

2.5.2 Le jeu de données

De la même façon de Tuzun et Burke (1999) [100], Harks et al. (2013) [52] ont généré un jeu
d’essai de 27 instances de grande taille. Les instances sont divisées en trois groupes : le groupe
M (1000 clients, 100 dépôts), le groupe L (5000 clients, 500 dépôts) et le groupe XL (10.000

33
 2.5. Expérimentation

Tableau 2.2: Le jeu de données de Harks et al. (2013) [52]

inst #dep #cl avg dem avg [Link]ût [Link] BKS borne inférieure
M 1,1 1000 100 5.04 47.938 9 13478.9 8800.8
M 1,2 1000 100 5.04 47.938 100 3499.05 2096.7
M 1,3 1000 100 5.04 47.938 1000 2478.9 2096.3
M 2,1 1000 100 5.04 147.937 9 17997 12166.6
M 2,2 1000 100 5.04 147.937 100 4468.74 2288.8
M 2,3 1000 100 5.04 147.937 1000 2620.84 2151.6
M 3,1 1000 100 5.04 343.814 9 22926.8 15432.2
M 3,2 1000 100 5.04 343.814 100 5345.92 2938.7
M 3,3 1000 100 5.04 343.814 1000 2779.25 2203.4
L 1,1 5000 500 4.97 49.136 9 32325.9 17502
L 1,2 5000 500 4.97 49.136 100 8106.1 4607
L 1,3 5000 500 4.97 49.136 1000 5463.71 4607
L 2,1 5000 500 4.97 149.136 9 50229.7 29519.6
L 2,2 5000 500 4.97 149.136 100 12059.5 5946.5
L 2,3 5000 500 4.97 149.136 1000 6624.78 4659.4
L 3,1 5000 500 4.97 347.409 9 63905.1 38728.3
L 3,2 5000 500 4.97 347.409 100 14372.4 7515.9
L 3,3 5000 500 4.97 347.409 1000 6966.54 4709.4
XL 1,1 10000 1000 5.024 49.36 9 48677.1 25449.7
XL 1,2 10000 1000 5.024 49.36 100 11872 6494.6
XL 1,3 10000 1000 5.024 49.36 1000 7754.66 6494.6
XL 2,1 10000 1000 5.024 149.36 9 77580.6 46601.8
XL 2,2 10000 1000 5.024 149.36 100 18159.1 9253.7
XL 2,3 10000 1000 5.024 149.36 1000 9296.1 6550.3
XL 3,1 10000 1000 5.024 348.09 9 101454 60461.3
XL 3,2 10000 1000 5.024 348.09 100 21341.5 11838.1
XL 3,3 10000 1000 5.024 348.09 1000 10389.9 6600.5

clients, 1.000 dépôts) avec 9 instances dans chaque groupe. Les instances de même groupe sont
divisées en trois types, à savoir le type 1, 2 et 3 avec trois instances pour chaque type. Dans
les instances de type 1 (respectivement 2 et 3), le coût d’ouverture de chaque dépôt est choisi
uniformément dans l’intervalle [0; 100] (respectivement [100; 200] et [200; 500]). De plus, pour les
trois instances de même groupe et de même type, la capacité de véhicule est fixée à 9, 100, 1000
respectivement. Pour toutes les instances, les demandes des clients ont été choisies uniformément
dans l’intervalle [0; 10]. Le tableau 2.2 décrit ces instances. La première colonne présente le nom
de l’instance (inst), les colonnes deux et trois indiquent le nombre de dépôts candidats et le
nombre de clients respectivement (#dep et #cl respectivement). Les colonnes quatre et cinq
représentent la moyenne des demandes de tous les clients et la moyenne des coûts de tous les
dépôts (avg dem et avg [Link]ût respectivement), la colonne six indique la capacité des véhicules
([Link]). Enfin, les colonnes sept et huit représentent, respectivement, la valeur de la meilleure
solution connue (Best Known Solution (BKS)) et la borne inférieure.

34
 2.5. Expérimentation

Tableau 2.3: Les résultats de 2-SH

2-SH
inst #[Link] [Link]ût #route coût gap temps CPU
M 1,1 54 1739.94 723 12014.16 0.365 1.029
M 1,2 17 250.22 53 3470.34 0.655 0.921
M 1,3 5 24.62 6 2814.54 0.343 10.687
M 2,1 29 3854.43 728 15760.49 0.295 1.123
M 2,2 6 721.83 53 4494.11 0.964 0.981
M 2,3 1 113.571 6 3010.64 0.399 10.563
M 3,1 20 5597.3 728 19839.45 0.286 1.029
M 3,2 5 1164.54 53 5207.41 0.436 0.937
M 3,3 1 208.04 6 3156.59 0.433 10.546
L 1,1 201 5684.61 3592 29538.07 0.688 64.758
L 1,2 63 693.83 256 8176.03 0.775 19.626
L 1,3 16 46.67 25 6228.35 0.352 66.52
L 2,1 102 13181.188 3599 43496.52 0.474 64.305
L 2,2 20 2296.34 258 11551.58 0.943 19.392
L 2,3 5 552.973 25 7058.20 0.515 68.579
L 3,1 66 17422.29 3578 54976.58 0.420 63.76
L 3,2 13 2890.25 257 13426.15 0.786 19.689
L 3,3 3 638.934 25 7467.20 0.586 65.927
XL 1,1 353 8359.69 7227 43939.78 0.727 179.044
XL 1,2 119 1010.42 520 11867.27 0.827 88.969
XL 1,3 40 120.38 51 8823.95 0.359 160.744
XL 2,1 168 21270.64 7215 68118.70 0.462 170.62
XL 2,2 34 3757.45 520 17638.79 0.906 88.985
XL 2,3 9 910.40 51 10172.31 0.553 162.522
XL 3,1 106 26572.69 7232 85509.48 0.414 177.562
XL 3,2 23 5231.12 519 20659.67 0.745 89.093
XL 3,3 6 1291.62 51 10897.51 0.651 167.126
Moyenne 19853.59 0.569 65.74

2.5.3 Résultats et discussion

Dans le tableau 2.3, nous exposons les résultats de l’heuristique 2-SH. La première colonne indique
le nom de l’instance (inst). Les colonnes deux, trois et quatre présentent le nombre des dépôts
ouverts (#[Link]), leurs coûts ([Link]ût) et le nombre de routes dans la solution respectivement
(#route). Les colonnes cinq et six indiquent le coût de la solution (coût) et l’écart entre le coût
solution_cout−borne_inf rieure
de la solution de la borne inférieure (gap) calculé comme suit : borne_inf rieure . La
dernière colonne présente le temps d’exécution qui est indiqué en secondes (temps CPU).
Le tableau 2.4 présente les résultats de Harks et al. (2013) [52]. L’implémentation de leurs
méthodes a été faite en C ++ en utilisant le compilateur GCC 4.5 sous SUSE Linux [Link]
leurs expérimentations ont été effectuées sur un PC équipé d’un processeur Intel Core 2 Duo
E8400 à 3.0 GHz avec 4 Go de RAM. On note ici que, Harks et al. (2013) [52] ont proposé un
algorithme à performance garantie (Approximation Algorithm) pour le CLRP. Nous référons à

35
 2.5. Expérimentation

Tableau 2.4: Les résultats de Approx et Approx-LKH [52]

Approx Approx-LKH
Inst #[Link] [Link]ût #route coût gap CPU coût gap CPU
M 1,1 33 779.4 757 13563.4 0.541 0.47 13478.9 0.532 0.55
M 1,2 13 82 58 4111.6 0.961 0.95 3499.05 0.669 1.00
M 1,3 8 31.8 10 3343.6 0.595 1.59 2478.9 0.183 1.65
M 2,1 18 2157.9 756 18086.2 0.487 0.53 17997 0.479 0.62
M 2,2 5 528.2 55 5098.9 1.228 0.92 4468.74 0.952 0.98
M 2,3 1 205.2 6 3520.2 0.636 1.62 2620.84 0.218 1.67
M 3,1 10 2370.3 756 23008.8 0.491 0.68 22926.8 0.486 0.76
M 3,2 3 869.1 55 6012 1.046 1.27 5345.92 0.819 1.32
M 3,3 1 414.3 6 3656.8 0.66 0.83 2779.25 0.261 0.88
L 1,1 128 2426.4 3695 32473 0.855 23.39 32325.9 0.847 35.90
L 1,2 47 337.3 272 9433.5 1.048 50.84 8106.1 0.76 59.29
L 1,3 16 42.1 31 7344.7 0.594 120.12 5463.71 0.186 121.95
L 2,1 50 6000.5 3694 50380.6 0.707 28.89 50229.7 0.702 41.35
L 2,2 10 1163.8 271 13435.5 1.259 65.79 12059.5 1.028 73.81
L 2,3 2 306 29 8477 0.819 162.99 6624.78 0.422 165.08
L 3,1 31 7293.4 3694 64058.9 0.654 38.3 63905.1 0.65 50.94
L 3,2 6 1473 271 15694.9 1.088 89.8 14372.4 0.912 97.81
L 3,3 1 409.3 29 8835.3 0.876 210.71 6966.54 0.479 213.44
XL 1,1 229 3394.8 7480 48879.5 0.921 136.48 48677.1 0.913 214.23
XL 1,2 78 405.1 554 13752.3 1.117 314.81 11872 0.828 369.47
XL 1,3 33 52.7 69 10400 0.601 741.08 7754.66 0.194 749.91
XL 2,1 82 9264.9 7473 77796.3 0.669 165.57 77580.6 0.665 243.40
XL 2,2 17 1752.7 547 20133.7 1.176 383.13 18159.1 0.962 434.58
XL 2,3 4 507.8 57 12018.2 0.835 879.48 9296.1 0.419 886.83
XL 3,1 48 10593.1 7473 101676 0.682 228.14 101454 0.678 307.12
XL 3,2 11 2255.2 547 23304.5 0.969 518.15 21341.5 0.803 570.46
XL 3,3 2 610.2 57 13091.1 0.983 1314.86 10389.9 0.574 1322.69
moyenne 22651.35 0.833 203.01 21562 0.616 221.03

cet algorithme par Approx. Approx a été amélioré par l’algorithme LKH de [53] et nous notons
ce nouvel algorithme Approx-LKH.
Le tableau 2.5 compare les résultats de notre approche 2-SH par rapport aux résultats des
deux algorithmes de Harks et al. (2013) [52] à savoir Approx et Approx-LKH. Nous indiquons
le nom de l’instance, le coût de la solution obtenue par chaque algorithme (coût) et son gap par
rapport à la borne inférieure (gap). Dans chaque ligne du tableau, nous soulignons le meilleur
résultat et son gap.
En comparant les résultats de 2-SH avec ceux de Approx et de Approx -LKH, la 2-SH
donne toujours de meilleurs résultats par rapport à Approx. Nous constatons, que 2-SH est
meilleure que l’algorithme Approx dans toutes les instances avec un pourcentage moyen de 26.4
% (gap × 100)). En outre, d’après le tableau 2.5, la 2-SH améliore les résultats de 16 instances
parmi les 27 instances par rapport aux résultats de Approx-LKH. Néanmoins, les résultats ne
subissent, malheureusement, pas une nette amélioration, la 2-SH ayant des résultats meilleurs
que le Approx-LKH avec un pourcentage moyen de 4.7%. De plus, nous observons que le 2-SH
améliore la moyenne de la fonction objectif (en comparant 19853.59 à 21562). Ainsi, nous obser-
vons que la 2-SH donne de meilleurs résultats et fonctionne de façon plus efficace sur les instances
où la capacité du véhicule est égale à 9. Dans ces instances, nous avons un nombre important de
routes par rapport aux autres (voir le tableau 2.3), par conséquent, nous avons un problème de
localisation de plus en plus difficile. Ces dernières constatations montrent l’efficacité du recuit
simulé et sa contribution dans 2-SH.
Dans le tableau 2.5, le temps d’exécution n’a pas été rapporté. Il est clair que 2-SH, Approx

36
 2.5. Expérimentation

Tableau 2.5: 2-SH vs. Approx et Approx-LKH

borne Approx Approx-LKH 2-SH

inst inférieure coût gap coût gap coût gap
M 1,1 8800.8 13563.4 0.541 13478.9 0.532 12014.16 0.365
M 1,2 2096.7 4111.6 0.961 3499.05 0.669 3470.34 0.655
M 1,3 2096.3 3343.6 0.595 2478.9 0.183 2814.54 0.343
M 2,1 12166.6 18086.2 0.487 17997 0.479 15760.49 0.295
M 2,2 2288.8 5098.9 1.228 4468.74 0.952 4494.11 0.964
M 2,3 2151.6 3520.2 0.636 2620.84 0.218 3010.64 0.399
M 3,1 15432.2 23008.8 0.491 22926.8 0.486 19839.45 0.286
M 3,2 2938.7 6012 1.046 5345.92 0.819 5207.41 0.436
M 3,3 2203.4 3656.8 0.66 2779.25 0.261 3156.59 0.433
L 1,1 17502 32473 0.855 32325.9 0.847 29538.07 0.688
L 1,2 4607 9433.5 1.048 8106.1 0.76 8176.03 0.775
L 1,3 4607 7344.7 0.594 5463.71 0.186 6228.35 0.352
L 2,1 29519.6 50380.6 0.707 50229.7 0.702 50229.7 0.474
L 2,2 5946.5 13435.5 1.259 12059.5 1.028 11551.58 0.943
L 2,3 4659.4 8477 0.819 6624.78 0.422 7058.20 0.515
L 3,1 38728.3 64058.9 0.654 63905.1 0.65 54976.58 0.420
L 3,2 7515.9 15694.9 1.088 14372.4 0.912 13426.15 0.786
L 3,3 4709.4 8835.3 0.876 6966.54 0.479 7467.20 0.586
XL 1,1 25449.7 48879.5 0.921 48677.1 0.913 43939.78 0.727
XL 1,2 6494.6 13752.3 1.117 11872 0.828 11867.27 0.827
XL 1,3 6494.6 10400 0.601 7754.66 0.194 8823.95 0.359
XL 2,1 46601.8 77796.3 0.669 77580.6 0.665 68118.70 0.462
XL 2,2 9253.7 20133.7 1.176 18159.1 0.962 17638.79 0.906
XL 2,3 6550.3 12018.2 0.835 9296.1 0.419 10172.31 0.553
XL 3,1 60461.3 101676 0.682 101454 0.678 85509.48 0.414
XL 3,2 11838.1 23304.5 0.969 21341.5 0.803 20659.67 0.745
XL 3,3 6600.5 13091.1 0.983 10389.9 0.574 10897.51 0.651
moyenne 11506.83 22651.35 0.833 21562 0.616 19853.59 0.569

37
 2.6. Conclusion

et Approx-LKH ont été développés sur des environnements différents et testés sur des machines
différentes. Par conséquent, nous évitons de comparer directement les temps d’exécution de
ces méthodes. Bien que la comparaison directe soit difficile, nous pouvons dire que les trois
algorithmes ont en général, des temps de calculs très proches en comparant la différence entre
les moyennes des temps de calcul et la taille des instances (avec un maximum de 10.000 clients
et 1.000 dépôts candidats). C’est-à-dire que, si un algorithme est considérablement meilleur
qu’un autre, la différence entre les temps d’exécution sera très importante parce que la taille de
l’instance est suffisamment grande pour clarifier cette différence.

2.6 Conclusion
Dans ce chapitre, une nouvelle heuristique à deux phases a été proposée pour le problème de
localisation-routage avec contrainte de capacité. Notre objectif est de faire face à un besoin à
des algorithmes efficaces pour des instances de grande taille et qui sont en mesure de trouver des
solutions de bonne qualité dans un temps de calcul raisonnable. Par conséquent, contrairement à
la plupart des algorithmes de la littérature, les solveurs et les méthodes exactes ne sont pas utilisés
en raison de leurs consommations élevées en temps d’exécution. Dans la méthode proposée, la
première phase consiste à construire un ensemble de routes de coût minimal en utilisant une
heuristique d’insertion suivie par une heuristique de recherche Tabou. Dans la seconde phase,
une procédure de recuit simulé a été utilisée pour résoudre le sous-problème de localisation.
Le rôle de la procédure est de déterminer certains dépôts à ouvrir (à partir d’un ensemble
de dépôts candidats) et d’affecter chaque route à un dépôt ouvert. La performance de notre
algorithme a été comparée, avec succès, avec deux algorithmes de la littérature en utilisant un
jeu de données standard de grande taille. L’expérimentation montre que, notre approche 2-SH est
plus performante que ces deux algorithmes et de nouvelles meilleures solutions pour 16 instances
(parmi 27 instances de jeu de données) ont été trouvés. En outre, les résultats ont montré que le
point-clé de succès de 2-SH a été la localisation des bons dépôts dans la deuxième phase grâce à
la méthode du recuit simulé.

38
Chapitre 3

Résolution de problème de routage avec

gestion de stock à base de la méthode
GRASP

Sommaire
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2 Revue de la littérature . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Hypothèses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.3 Le modèle mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4 Méthodologie de solution . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.1 Vue générale sur l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4.2 Prétraitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.3 Solution initiale pour GBH . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.4 Procédure gloutonne randomisée (GRP) . . . . . . . . . . . . . . . . . . 45
3.4.5 Recherche Tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4.6 La gestion de stock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.5.1 Réglage des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.2 Jeu de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.3 Résultats et comparaison avec B&C . . . . . . . . . . . . . . . . . . . . 53
3.5.4 L’analyse du comportement de GBH . . . . . . . . . . . . . . . . . . . . 58
3.5.5 Les résultats de GBH sur les instances de MMIRP-SD . . . . . . . . . . 60
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.1 Introduction
Dans ce chapitre nous étudions le problème de routage avec gestion de stock (en anglais Inven-
tory Routing Problem, IRP). Le problème IRP intègre deux activités importantes de la chaîne

39
 3.2. Revue de la littérature

logistique à savoir : l’élaboration des tournées de véhicules et la gestion de stock. Dans ce prob-
lème, un fournisseur est chargé de distribuer certains produits à un ensemble de clients sur un
horizon de temps donné en utilisant une flotte de véhicules homogènes. Chaque client possède
une capacité de stockage limitée et consomme à chaque période de l’horizon, les produits avec
un taux bien déterminé. L’objectif est de minimiser le coût total, y compris les coûts de stockage
(chez le fournisseur et les clients) et le coût de transport tout en satisfaisant certaines contraintes,
telles que : la capacité des véhicules, la capacité de stockage des clients et la non rupture des
stocks chez le fournisseur et chez les clients, etc.
Dans la littérature, plusieurs variantes de l’IRP ont été proposées. Dans ce chapitre, nous
nous intéressons au problème de routage avec gestion de stock multi-périodes, multi-produits,
multi-véhicules (en anglais Multi-Product Multi-vehicle Inventory Routing Problem (MMIRP)),
en prenant la même définition de Coelho et Laporte (2013b) [22]. Dans leur définition, les auteurs
ont considéré des hypothèses plus réalistes par rapport à ce qui est proposé dans la littérature,
telles que le taux de consommation variable chez les clients.
Pour faire face à ce problème, nous développons une heuristique de type GRASP (Greedy
Randomized Adaptive Search Procedure) qui utilise la recherche Tabou comme une procédure
de recherche locale [48]. Dans ce qui suite, d’abord, nous donnons un aperçu sur la littérature
de l’IRP et nous présentons la formulation mathématique du problème. Ensuite, nous exposons
la méthode proposée pour résoudre le problème MMIRP. En plus, l’algorithme est évalué et des
expérimentations sur des jeux de données standards sont présentées.

3.2 Revue de la littérature

Dans la littérature, plusieurs variantes du problème de routage avec gestion de stock ont été
étudiées et de nombreux algorithmes ont été proposés pour résoudre ces variantes y compris les
heuristiques, les méta-heuristiques, les méthodes exactes et les matheuristics [24]. Archetti et al.
(2007) [8] ont traité l’IRP avec un seul produit et un seul véhicule en utilisant un algorithme
exact de type branch & cut. En outre, plusieurs heuristiques ont été proposées pour cette variante
comme l’heuristique hybride d’Archetti et al. (2012) [7] et l’heuristique de type ALNS (Adaptive
Large Neighborhood Search) de Coelho et al. (2012a) [21]. Ainsi, pour les algorithmes exacts, on
peut citer le branch & cut de Solyali et al. (2011) [92] et récemment, un algorithme de type branch-
price & cut a été proposé par Desaulniers et al. (2014) [32]. Archetti et al. (2014) [9] ont présenté
et comparé plusieurs formulations mathématiques de l’IRP. Dans Coelho et Laporte (2013a) [23]
et Adulyasak et al. (2012) [4], les auteurs ont abordé l’IRP multi-véhicules et un algorithme exact
a été proposé dans chaque travail. Pour résoudre le problème avec des heuristiques, Coelho et
al. (2012b) [20] ont proposé une recherche locale à grand voisinage combinée avec un algorithme
exact. En plus, des heuristiques de construction ont été développées par Abdelmaguid (2004)
[2]. Dans le but d’améliorer la qualité de ces heuristiques, Abdelmaguid et Dessouky (2006) [3]
ont introduit un algorithme génétique. En outre, Yu et al. (2008) [105] ont étudié l’IRP multi-
véhicules avec une flotte de véhicules de taille limitée et le problème a été résolu en utilisant une
méthode hybride basée sur la relaxation lagrangienne. Par ailleurs, de nombreuses variantes de
l’IRP ont été proposées en prenant en compte le cas du multi-produits [76, 74, 81]. Dans toutes
ces contributions, des méthodes approchées ont été proposées. Dans Coelho et Laporte (2013b)
[22], les auteurs ont adressé, pour la première fois, l’IRP standard en considérant à la fois le cas
de multi-produits et multi-véhicules, ce qui est différent de ceux précédemment cités. D’abord,
ils ont présenté une formulation mathématique pour ce problème, et puis pour la résolution du
MMIRP, un algorithme exact de type branch & cut a été utilisé. Plus récemment, Cordeau et al.

40
 3.3. Définition du problème

(2015) [27] ont étudié l’IRP avec multi-produits et multi-véhicules en prenant la même définition
de Coelho et Laporte (2013b) [22] mais en ignorant les données sur le fournisseur (le coût de
stockage chez le fournisseur et la disponibilité des produits). Pour résoudre le problème, ils ont
proposé une heuristique de décomposition en trois phases. Un état de l’art résumant les travaux
proposés pour l’IRP et ses variantes est donné par Coelho et al. (2014) [24].

3.3 Définition du problème

Dans cette section, nous présentons la formulation mathématique du problème MMIRP proposé
par Coelho et Laporte (2013b) [22]. Tout d’abord, nous présentons les hypothèses considérées
dans ce travail, nous donnons les notations utilisées et enfin le modèle mathématique est exposé.

3.3.1 Hypothèses
Les hypothèses prises en compte dans le présent chapitre sont les suivantes:

1. Chaque véhicule doit effectuer une seule tournée par période. Son parcours commence et
se termine au niveau du fournisseur et sa charge totale ne doit pas dépasser sa capacité.

2. Il n’y a pas de capacité limitée spécifique pour chaque produit, mais la somme totale de
tous les produits ne doit pas dépasser la capacité du stockage du client.

3. Le coût de stockage est considéré à la fois pour le fournisseur et pour les clients.

4. Les demandes des clients sont déterministes et elles varient d’une période à une autre.
C’est-à-dire le taux de consommation de chaque client n’est pas fixé sur tout l’horizon.

5. Pour chaque client, au maximum une seule visite est effectuée provenant du fournisseur
dans une période donnée.

3.3.2 Notations
Pour formuler le MMIRP, nous utilisons les notations suivantes :
Le MMIRP est défini sur un graphe complet G(V, A) où :

• V = {0, ..., n} est l’ensemble des sommets et A est l’ensemble des arcs. V 0 = V /{0}
représente l’ensemble des clients et le sommet 0 représente le fournisseur.

• M = {1, ..., m} est l’ensemble des produits à distribuer.

• hm
i est le coût de stockage unitaire du produit m. m ∈ M , i ∈ V .

• p est la longueur de l’horizon de temps.

• T = {1, ..., p} est l’ensemble des périodes.

• rmt est la quantité de produit m disponible chez le fournisseur à chaque période t ∈ T .

• I0mt et Iimt sont les niveaux de stocks chez le fournisseur et les clients, respectivement; pour
chaque produit m ∈ M à la fin de la période t ∈ T .

• dmt 0
i est la demande du produit m ∈ M à la période t ∈ T effectuée par le client i ∈ V .

41
 3.3. Définition du problème

• K = {1, ..., z} est une flotte de véhicules homogènes.

• Qk est la capacité du véhicule k ∈ K.

• Ci est la capacité de stockage du client i ∈ V 0 .

• cij est le coût de déplacement du sommet i ∈ V vers le sommet j ∈ V .

Les variables de décision

• qimkt est la quantité de produit m livrée au client i durant la période t en utilisant le

véhicule k.

• xkt
ij est le nombre de fois que l’arc (i, j) avec i < j est traversé par le véhicule k dans la
période t.
(
1 si i ∈ V est visité par le véhicule k dans la période t.
• yikt =
0 sinon.

3.3.3 Le modèle mathématique

La fonction objectif :
X X X X X XX
min hm mt
i Ii + cij xkt
ij (3.1)
i∈V m∈M t∈T i∈V j∈V,i<j k∈K t∈T

Les contraintes:
X X
I0mt = I0m,t−1 + rmt − qimkt m∈M t∈T (3.2)
k∈K i∈V 0
X
Iimt = Iim,t−1 + qimkt − dmt
i m∈M i∈V0 t∈T (3.3)
k∈K

Iimt ≥ 0 i∈V m∈M t∈T (3.4)

X
Iimt ≤ Ci i∈V0 t∈T (3.5)
m∈M
X X X
qimkt ≤ Ci − Iim,t−1 i∈V0 t∈T (3.6)
m∈M k∈K m∈M

qimkt ≤ Ci yikt i∈V0 k∈K m∈M t∈T (3.7)

X X
qimkt ≤ Qk y0kt k∈K t∈T (3.8)
0
i∈V m∈M
X X
xkt
ij + xkt kt
ji = 2yi i∈V k∈K t∈T (3.9)
j∈V,i<j j∈V,j<i
X X X
xkt
ij ≤ yikt − ygkt S ⊆V0 k∈K t∈T g∈S (3.10)
i∈S j∈S,i<j i∈S

42
 3.4. Méthodologie de solution

qimkt ≥ 0 i∈V0 k∈K t∈T (3.11)

xkt
i0 ∈ {0, 1, 2} i∈V0 k∈K t∈T (3.12)

xkt
ij ∈ {0, 1} i, j ∈ V 0 k∈K t∈T (3.13)

yikt ∈ {0, 1} i∈V k∈K t∈T (3.14)

La fonction objectif (3.1) minimise à la fois les coûts de stockage et les coûts de transport.
Les niveaux de stocks du fournisseur et des clients sont définis par les contraintes (3.2) et (3.3)
respectivement. La contrainte (3.4) garantit la non rupture des stocks. La contrainte (3.5) impose
que la capacité de stockage maximale des clients soit respectée. En outre, le lien entre les quantités
livrées et les variables de routage est assuré par les contraintes (3.6) et (3.7). Les contraintes (3.8,
3.9 et 3.10) assurent la faisabilité des routes. Enfin, les contraintes de (3.11) à (3.14) imposent
la non-négativité et l’intégrité des variables de décision.

3.4 Méthodologie de solution

Dans cette section, nous présentons l’heuristique développée pour résoudre le problème MMIRP.
En effet, notre algorithme combine deux méta-heuristiques dans lequel nous essayons d’exploiter
les avantages de chacune. La méta-heuristique de base est la méthode GRASP (Greedy Ran-
domized Adaptive Search Procedure). La méthode GRASP est une méthode itérative où chaque
itération se compose de deux grandes phases successives. La première est la phase de construc-
tion, où une solution réalisable est construite par une procédure gloutonne randomisée (Greedy
Randomized Procedure (GRP)); la deuxième phase est une recherche locale qui améliore la so-
lution construite dans la phase précédente [39]. La méthode GRASP répète ces deux phases
jusqu’à ce qu’un critère d’arrêt soit atteint et la meilleure solution trouvée est retournée comme
résultat à la fin. Afin d’améliorer la procédure GRASP classique, la recherche locale que nous
utilisons est la recherche Tabou (Tabu Search (TS)). Dans notre algorithme (GRASP Based
Heuristic (GBH)), contrairement à la plupart des algorithmes proposés dans la littérature, nous
n’utilisons pas de solveurs et/ou des algorithmes exacts [24]. En effet, cette caractéristique est
très importante car elle permet au GBH d’être efficace et rapide pour les instances de grande
taille. Dans le reste de ce chapitre, d’abord nous donnons un aperçu général sur l’algorithme.
Ensuite, nous présentons les principales composantes de GBH, y compris les composantes de la
procédure gloutonne randomisée et les composantes de la recherche Tabou. Enfin, nous montrons
la stratégie de gestion de stock utilisée. Dans ce qui suit, lorsque nous parlons de termes dans
chaque équation, nous nous référons aux termes des fonctions min et/ou max.

3.4.1 Vue générale sur l’algorithme

Au début, l’algorithme GBH génère une solution initiale S en utilisant le nombre minimum de
visites pour chaque client. Cette solution est améliorée en utilisant la TS. En effet, dans cette
étape, la TS est consacrée à améliorer la solution initiale générée de façon aléatoire afin de la
préparer pour appliquer la procedure GRP. Ensuite, à chaque itération, l’algorithme continue
d’ajouter, par le biais de la procédure GRP, les meilleures visites de clients jusqu’à ce qu’un bon
compromis entre le coût de routage et le coût de stockage soit atteint. Dans l’étape suivante,

43
 3.4. Méthodologie de solution

le GBH améliore cette nouvelle solution en utilisant la méthode TS. Le GBH est décrit dans
l’algorithme 5, et ses composants sont explicités ci-dessous.

Algorithme 5 Heuristique de type GRASP

1: faire le prétraitement;
2: S ← Solution_initiale();
3: Sts ← Recherche_Tabou(S);
4: S ← Sts ;
5: Sbest ← S;
6: tant que (le critère d’arrêt n’est pas satisfait) faire
7: Sg ← Procédure_gloutonne_randomisée(S);
8: Sts ← Recherche_Tabou(Sg );
9: si (coût(Sts ) < coût(Sbest )) alors
10: Sbest ← Sts ;
11: fin si
12: fin tant que
13: retourner Sbest ;

3.4.2 Prétraitement
Dans une étape de prétraitement, le GBH calcule le nombre minimum (NBmini ) de visites pour
chaque client i comme suit :
Tout d’abord, nous calculons la quantité des produits que le client i a besoin sur l’horizon de
planification N Ei comme suit (voir l’équation (3.15)):
X X X
N Ei = dm,t
i − Iim,0 ∀i ∈ V 0 (3.15)
t∈T m∈M m∈M

» ¼ » ¼
N Ei N Ei
NBmini = max( , , 0) ∀i ∈ V 0 (3.16)
Ci Qk

Le calcul du nombre minimum de visites pour chaque client doit prendre en considération le
besoin du client qui doit être livré N Ei , sa capacité de stockage et la capacité du véhicule qui
ne doit pas être dépassée (voir équation (3.16)). Donc, nous avons mis le nombre minimum de
visites comme étant le maximum entre le besoin du client divisé par sa capacité de stockage, le
besoin de client divisé sur la capacité du véhicule et le zéro.
En outre, si aucune visite n’est effectuée pour le client i, alors son niveau de stock initial va
diminuer au cours du temps, et à une période donnée, une rupture de stock se produira. On note
cette période par maxi .

3.4.3 Solution initiale pour GBH

Une première solution initiale de base S pour le GBH est générée de manière aléatoire en utilisant
le nombre minimum de visites pour chaque client i (NBmini ) comme suit :

44
 3.4. Méthodologie de solution

1. La première visite de chaque client i est affectée à une période choisie aléatoirement dans
l’intervalle [1, maxi ].

2. Le reste des visites sont attribués aléatoirement, c’est-à-dire le choix de la période, de la

route et de la position dans la route se fait aléatoirement.

3.4.4 Procédure gloutonne randomisée (GRP)

Dans la procédure GRP (phase 1) de la métaheuristique GRASP, une solution faisable est con-
struite en introduisant progressivement un élément à la fois. A chaque étape, tous les éléments
candidats sont évalués en utilisant une fonction gloutonne et une liste des meilleurs candidats
(RCL) est formée par les Wr meilleurs éléments (Wr est un nombre entier). Ensuite, un élément
sélectionné aléatoirement à partir de RCL est retourné. L’élément est inséré dans la solution
partielle courante générant une nouvelle solution. Les étapes précitées sont répétées jusqu’à
l’insertion de tous les éléments [39].
Dans notre cas, après la génération d’une solution initiale de base S, le GBH l’améliore
en utilisant la méthode TS. Par conséquent, nous avons une solution avec un coût de routage
minimal, un coût de stockage maximal et un ensemble de contraintes qui peuvent être violées.
Donc, l’objectif est de diminuer le coût de stockage d’une valeur supérieure à l’augmentation
dans le coût de routage tout en maintenant la faisabilité de la solution. En plus, le but de la
procédure GRP est de chercher le meilleur compromis entre le coût de stockage et le coût de
routage en recherchant le meilleur nombre de visites à ajouter pour chaque client. Pour atteindre
cet objectif, nous proposons une procédure simple et efficace en trois étapes. Dans ce qui suit,
nous présentons d’abord les variables et les notations utilisées dans la procédure GRP, nous
exposons ses étapes, et enfin la procedure GRP est décrite dans l’algorithme 6.

[Link] Notations
Dans notre GRP nous utilisons les notations présentées dans le tableau 3.1. Donc, en tenant
compte la politique de la gestion de stock, l’insertion d’une visite de client i dans une tournée de
la période t signifie que son besoin de produits de la période t à la période ts,i , déjà livré dans
tp,i , sera livré dans la période t. On note cette quantité GSQSi,t,m et elle est calculée comme
suit:
ts,i
X m,t1
X m,k,tp,i
GSQSi,t,m = min( di , qi ) (3.17)
t1 =t k∈K

Dans l’équation (3.17), le premier terme représente le besoin du client (la somme des deman-
des) entre la période t et la période ts,i et le second terme est la quantité du produit livrée à i
dans la période tp,i qui est à l’origine le besoin de client i entre les périodes tp,i et ts,i en tenant
compte du niveau de stock à la période tp,i . En outre, après l’insertion de i dans la période t, ces
quantités de produits resteront chez le fournisseur de la période tp,i à t donc, le coût de stockage
du client i va diminuer et le coût de stockage du fournisseur va augmenter. Nous calculons ce
changement dans les coûts des stocks GSICi,t comme suit (voir l’équation (3.18)):
X
GSICi,t = GSQSi,t,m × (t − tp,i ) × (hm m
i − h0 ) (3.18)
m∈M

45
 3.4. Méthodologie de solution

Tableau 3.1: Les notations utilisées dans la Procédure gloutonne randomisée

Nom Description
tp,i La période de la précédente visite au client i en considérant
la période actuelle t, s’il y a pas de visite alors tp,i = 0.
ts,i La période de la suivante visite au client i en considérant
la période actuelle t, s’il y a pas de visite alors ts,i = p.
Sg La solution retournée par GRP.
N IM Le nombre maximal de fois que les propositions d’insertion des visites
qui dégradent la fonction objectif sont autorisées
Pro_List La liste de toutes les propositions d’insertion, chaque
proposition contient : le client qui sera visité,
la route, la période et le coût de l’insertion
GSCVi,t La diminution dans les valeurs des violations des contraintes, obtenues
lorsque nous ajoutons une visite de client i dans la période t.
GRCOi,k,t (the increase in the Routing COst). L’augmentation du coût de routage
lorsque nous ajoutons une visite de client i dans
la meilleure position dans k (k ∈ t).
GSQSi,t,m (The Save Quantity of a Single product). La quantité de produit m
expédiée de la période tp,i à la période t, si nous
ajoutons une visite de client i en t.
GSICi,t (The Save in the Inventory Cost). La diminution ou l’augmentation du coût
de stockage si nous ajoutons une visite de client i en t.
GGSCi,t (The General Save Cost). Le gain global engendré si nous ajoutons une
visite de client i en t, y compris le GSICi,t et GSCVi,t .

Enfin, nous calculons GGSCi,t comme suit (voir l’équation (3.19)):

GGSCi,t = GSICi,t + GSCVi,t (3.19)

[Link] Les phases de GRP

Chaque itération de GRP consiste en trois étapes, qui sont exécutées jusqu’à ce qu’aucune propo-
sition d’insertion ne soit disponible. Ces étapes sont les suivantes :

1. Etape de sauvegarde (Saving). Si une visite d’un client i est insérée dans une période t,
le coût de stockage et les violations des contraintes vont diminuer. Dans cette étape, pour
chaque client i et pour chaque période t, nous calculons le gain généré si une visite au client
i est insérée en t, comprenant le gain dans les coûts de stockage (GSICi,t ) et le gain dans
les violations des contraintes (GSCVi,t ).

2. Etape de routage (Routing). Pour chaque client i, chaque période t et chaque route k ∈ t,
nous calculons l’augmentation dans le coût de routage engendrée si nous ajoutons une
visite du client i en k. Cela se fait en examinant toutes les positions d’insertion possibles
et la meilleure position est retournée. En plus, si le gain de l’ajout (calculé dans l’étape

46
 3.4. Méthodologie de solution

Algorithme 6 Procédure gloutonne randomisée (S, N IM )

1: Sg ← S;
2: N I ← N IM ;
3: stop ← faut;
4: tant que (non stop) faire
5: /*** l’étape de sauvegarde ***/
6: pour (chaque client i ∈ V 0 et chaque periode t ∈ T ) faire
7: si (i n’est pas visité dans t) alors
8: calculer GGSCi,t ;
9: fin si
10: fin pour
11: /*** l’étape de routage ***/
12: pour (chaque client i ∈ V 0 ) faire
13: pour (chaque periode t ∈ T et chaque route k ∈ t) faire
14: GRCOi,k,t ← le coût de la meilleure insertion de i dans k;
15: si ((GGSCi,t > GRCOi,k,t ) ou ( N I > 0 )) alors
16: ajouter une proposition d’insertion à Pro_List;
17: fin si
18: fin pour
19: fin pour
20: /*** l’etape de selection ***/
21: si (Pro_List est vide) alors
22: stop ← vrai;
23: fin si
24: si (non stop) alors
25: construire RCL et choisir aléatoirement un élément à partir de RCL;
26: insérer le client de la proposition dans Sg ;
27: si (le coût de Sg n’est pas amélioré) alors
28: N I ← N I − 1;
29: fin si
30: fin si
31: fin tant que
32: retourner Sg

47
 3.4. Méthodologie de solution

de Saving) est supérieur à l’augmentation dans le coût de routage ou si les insertions qui
dégradent la fonction objectif sont autorisées dans l’itération courante, une proposition pour
ajouter une visite du client i dans t est insérée dans la liste des propositions (Pro_List).

3. Etape de sélection (Selection). Dans cette étape, si la liste Pro_List est vide, alors la
procédure est arrêtée; sinon, nous construisons la liste RCL par les Wr meilleurs éléments
dans Pro_List, et une proposition est sélectionnée aléatoirement. Ensuite, la visite est
insérée dans Sg , et enfin nous revenons à la phase de Saving. Après chaque insertion,
si l’opération de l’ajout de cette itération n’améliore pas le coût de Sg , alors le N I est
décrémenté.

3.4.5 Recherche Tabou

Dans GBH, afin d’améliorer la méthode GRASP classique, nous utilisons la recherche Tabou
comme une méthode de recherche locale. La recherche Tabou est une métaheuristique très utilisée
pour résoudre les problèmes d’optimisation combinatoire [43]. Dans notre algorithme, la TS
commence à partir de la solution retournée par GRP (Sg ) et, à chaque itération, elle choisit la
meilleure solution non Tabou (Sc0 ) dans la structure de voisinage T N (Sc ) de la solution courante
Sc . Ensuite, la solution courante Sc est remplacée par Sc0 et Sc est déclarée interdite ou Tabou,
c’est-à-dire nous ajoutons cette solution à la liste Tabou (T _list). Ces étapes sont répétées
jusqu’à ce qu’un critère d’arrêt soit atteint. Dans les paragraphes suivants, nous présentons les
trois principales composantes de TS : la structure de voisinage, le moteur de sélection et la liste
Tabou. Enfin, notre TS est présentée dans l’algorithme 7.

Algorithme 7 Recherche Tabou (Sg )

1: Sbest ← Sg ;
2: Sc ← Sg ;
3: insérer Sc dans T _list;
4: tant que (le critère d’arrêt n’est pas satisfait) faire
5: créer T N (Sc );
6: Sc ← meilleur {Sc0 ∈ T N (Sc ) et Sc0 ∈
/ T _list};
7: insérer Sc dans T _list;
8: si (coût(Sc ) < coût(Sbest )) alors
9: Sbest ← Sc ;
10: fin si
11: fin tant que
12: retourner Sbest

[Link] Structure de voisinage

Afin d’assurer une meilleure exploration de l’espace de recherche, nous utilisons 9 mouvements
pour construire la structure de voisinage de TS. Ces mouvements peuvent être divisés en cinq
groupes. En outre, pour assurer l’intensification et la diversification lors de la recherche, nous
utilisons un moteur pour sélectionner les groupes de mouvements appropriés à appliquer pour
créer les voisins de la solution courante. Dans ce qui suit, chaque groupe de mouvements est
décrit.

• Le groupe G1 :

48
 3.4. Méthodologie de solution

Le déplacement aléatoire intra-route (RB-shift-intra-route) : ce mouvement consiste à en-

lever une visite de sa position et de l’insérer dans une autre position choisie au hasard dans
la même route.
Le déplacement aléatoire inter-route (RB-shift-inter-route) : ce mouvement est similaire à
RB-shift-intra-route, mais la visite sélectionnée est insérée dans une autre route.
Le déplacement aléatoire entre-période (RB-shift-inter-period) : ce mouvement consiste à
enlever une visite et de l’insérer dans une route et dans une autre période.
Si le groupe G1 est choisi par le moteur de sélection, un mouvement aléatoire parmi ces
trois mouvements est appliqué.

• Le groupe G2 :
Le déplacement intra-route (BP-shift-intra-route) : ce mouvement supprime une visite de
sa position et l’insère dans la meilleure position dans la même route.
Le déplacement entre-route (BP-shift-inter-route) : ce mouvement est similaire à BP-shift-
intra-route, mais la visite du client est insérée dans une autre route.
Si le groupe G2 est choisi, une recherche exhaustive est faite en examinant toutes les
positions d’insertion possibles (intra et inter route) et la meilleure position est retournée.

• Le groupe G3 :
Le déplacement entre-période (BP-shift-inter-period) : ce mouvement consiste à supprimer
une visite de sa position, et de l’insérer dans la meilleure position dans une autre route
appartenant à une autre période rh. La période rh est choisie de façon aléatoire. Enfin,
comme pour le groupe G2, une recherche exhaustive est faite en examinant toutes les
positions d’insertion possibles (dans toutes les routes de rh), et évidemment, la visite est
insérée dans la meilleure position.

• Le groupe G4 :
L’échange intra-route (BP-swap-intra-route) : ce mouvement consiste à échanger deux vis-
ites (de deux clients) appartenant à la même route. La première visite est choisie aléatoire-
ment. Cependant, la deuxième visite est choisie par une recherche exhaustive en examinant
toutes les autres visites de la route.
L’échange entre-route (BP-swap-inter-route) : ce mouvement est similaire à BP-swap-intra-
route. Mais les deux visites appartenant à deux routes différentes de la même période.
De la même manière que G2, si le groupe G4 est choisi, une recherche exhaustive est faite
en examinant toutes les autres visites de la periode (intra et inter route) et la meilleure est
retournée.

• Le groupe G5 :
L’échange entre-période (BP-swap-inter-period) : ce mouvement consiste à échanger deux
visites appartenant à deux périodes différentes.

[Link] Le moteur de sélection

Afin de sélectionner les mouvements les plus appropriés pour générer la structure de voisinage de
la solution courante, nous utilisons un moteur de sélection. D’abord, un score scrgh est attribué
à chaque groupe de mouvements décrits ci-dessus, gh = 1...5. Au début, tous les scores sont

49
 3.4. Méthodologie de solution

initialisés à 1. Ensuite, à chaque itération de TS, nous supposons que l’operateur qui a généré
la meilleure solution dans la structure de voisinage est gh0 . Premièrement le score de gh0 est
augmenté par p1 (scrgh0 ← scrgh0 + p1). Ensuite, si l’operateur gh0 améliore la solution courante,
alors nous augmentons son score par p2 (scrgh0 ← scrgh0 + p2). En plus, si gh0 améliore la valeur
de la meilleure solution trouvée, alors nous augmentons son score par p3 (scrgh0 ← scrgh0 + p3),
avec p1 < p2 < p3. De plus, à chaque RT itérations, les scores sont réinitialisés. Dans Coelho
et al. (2012) [21], les auteurs ont utilisé la même technique de sélection, mais ils ont utilisé les
poids pour donner la priorité à certains opérateurs efficaces. En revanche, dans notre approche les
poids ne sont pas utilisés, et pour assurer la diversification, le score de groupe G1 est augmenté
avec p1 à chaque itération. Finalement, la probabilité de sélection spgh de chaque groupe gh, à
chaque itération, est calculée comme suit (voir 3.20) :
scrgh
spgh = P5 (3.20)
gh=1 scrgh

[Link] La liste Tabou

L’idée de base de la liste Tabou consiste à mémoriser les solutions visitées pour nous permettre
d’éviter de revenir vers les mêmes solutions. Le GBH applique ce principe de manière très simple,
c’est-à-dire, à chaque itération la solution courante est ajoutée à la liste Tabou, et les solutions
appartenant à cette liste ne peuvent pas être des candidates pour remplacer la solution courante.

3.4.6 La gestion de stock

Dans cette sous-section nous expliquons la technique que nous utilisons pour déterminer les
meilleures quantités de produits à livrer, lors de chaque visite, pour chaque client. Tout d’abord,
pour chaque client i, la quantité à livrer qim,t du produit m lors d’une visite effectuée à la période t,
est égale exactement à son besoin en tenant compte du niveau de stock actuel et de ses demandes
[7]. Cette quantité est calculée de la manière suivante (voir l’équation (3.21)) :
ts,i
X
qim,t = max(0, m,t1
di − Iim,t ) (3.21)
t1 =t

En outre, le coût de stockage peut être diminué, et cela se fait en expédiant des quantités de
produits du fournisseur aux clients lorsque le coût de stockage de ces clients est inférieur au coût
de stockage du fournisseur. Cela se fait en utilisant la procédure de réparation (Repair Procedure
(RP)) décrite dans l’algorithme 8.
Dans la procédure RP, pour chaque période t et pour chaque véhicule k, si la charge du
véhicule est inférieure à sa capacité, alors chaque pair (client i visité par le véhicule k, produit
m) avec Iim < I0m est ajouté dans une liste (LIST ) dans un ordre croissant de Iim . Ensuite, si
la liste n’est pas vide et la charge du véhicule est inférieure à sa capacité, alors le premier pair
(i0 , m0 ) dans LIST est choisi et la quantité à expédier Sh_Quai0 ,m0 ,k,t est calculée. Ensuite, si
Sh_Quai0 ,m0 ,k,t > 0 alors l’expédition est effectuée. Après chaque expédition, toutes les informa-
tions sur la solution sont mises à jour, y compris les niveaux de stock et la charge du véhicule.
Enfin le pair sélectionné est retiré de LIST . Ces étapes sont répétées jusqu’à ce que la liste soit

50
 3.5. Expérimentation

vide ou la charge du véhicule soit égale à sa capacité. A la fin, pour chaque paire (i,m) nous
calculons la quantité à expédier Sh_Quai,m,k,t comme suit (voir l’équation (3.22)) :
X 00 X X
Sh_Quai,m,k,t = min(I0m,t , (Ci − Iim,t )+ , (Qk − qim,k,t )+ ) (3.22)
m∈M 0
i∈V m∈M

Pour chaque client, nous appelons t00 la période où la somme des niveaux de stocks de pro-
duits est au maximum parmi toutes les périodes (de la période t jusqu’à la fin de l’horizon de
planification P ).

Algorithme 8 Procedure de réparation (Sx )

1: pour (chaque periode t ∈ T et route k ∈ t) faire
2: si (la charge de k < Qk ) alors
3: pour (chaque client i visité par k et chaque produit m ∈ M ) faire
4: si (hm m
i < h0 ) alors
5: ajouter (i,m) à LIST dans un ordre croissant selon hm
i ;
6: fin si
7: fin pour
8: tant que (LIST n’est pas vide et la charge de k < Qk ) faire
9: sélectionner le premier pair (i0 ,m0 ) ∈ LIST ;
10: calculer Sh_Quai0 ,m0 ,k,t ;
11: si (Sh_Quai0 ,m0 ,k,t > 0) alors
12: mettre à jour Sx ;
13: fin si
14: supprimer (i0 ,m0 ) de LIST;
15: fin tant que
16: fin si
17: fin pour
18: retourner Sx ;

Dans l’équation (3.22), pour le premier terme, la quantité expédiée de produit ne doit pas
dépasser la quantité disponible chez le fournisseur. Ensuite, le second terme assure la contrainte
de capacité de stockage du client sur l’horizon de planification. Le troisième terme est consacré
à maintenir la contrainte de capacité du véhicule : la quantité expédiée ne doit pas excéder le
volume disponible dans le véhicule.

3.5 Expérimentation
Dans cette section, nous présentons les résultats d’expérimentation de l’algorithme GBH. Notre
algorithme a été codé en JAVA, toutes les expériences ont été menées sur un PC équipé d’un
processeur Intel i7 avec 3.40 GHz et dispose d’une mémoire de 32Go. Dans la littérature de l’IRP,
Coelho et Laporte (2013b) [22] ont abordé la version de MMIRP considérée dans ce chapitre
[24]. Par conséquent, pour tester la performance de GBH, nous utilisons leur jeu de données et
nous comparons les résultats obtenus avec les meilleures solutions données par leur algorithme
de type Branch & Cut (B&C). En outre, afin de montrer l’efficacité de GBH, nous l’adaptons
pour résoudre la variante de MMIRP considérée dans le papier de Cordeau et al. (2015) [27]
et nous appelons cette variante par MMIRP-SD. Dans cette étude, les auteurs ont abordé le

51
 3.5. Expérimentation

même problème que Coelho et Laporte (2013b) [22], mais en ignorant les données du fournisseur
(le coût de stockage et la disponibilité de produits). Dans ce qui suit, d’abord, nous détaillons
les paramètres utilisés dans notre l’algorithme et nous exposons le jeu de données. Ensuite, les
résultats de GBH sont comparés à ceux de B&C et une analyse du comportement de l’algorithme
est effectuée sur un échantillon d’instances. Enfin, nous présentons les résultats de GBH sur les
instances de MMIRP-SD et nous les comparons avec les résultats de B&C et de l’heuristique de
décomposition (DH) de Cordeau et al. (2015) [27].

3.5.1 Réglage des paramètres

Dans notre expérimentation, les paramètres suivants sont utilisés : Le nombre d’itérations de
GBH est fixé à 10. Ensuite, pour la procédure GRP, nous avons : N IM = 7 et W r = 5. En
outre, pour la méthode TS, la taille de la structure du voisinage (|T N (Sc )|) est fixée à 50, la
taille de la liste Tabou (|T _list|) est fixée à 20. Ensuite, p1, p2, p3, RT sont fixés à 0.25, 1, 2,
200 respectivement. Enfin, le nombre d’itérations de TS est fixé à n × 30, où n est le nombre de
clients de l’instance.

3.5.2 Jeu de données

Dans [22], les auteurs ont généré 675 instances pour le MMIRP comme suit :

• Le nombre de clients n : égal à 10 × c où c = 1, 2, 3, 4, 5;

• Le nombre de produits M : égal à 1, 3 ou 5 produits;

• Le nombre de véhicules K : égal à 1, 3 ou 5 véhicules;

P
• Le niveau de stock initial chez le fournisseur I0m0 : égal à m0
i Ii , i ∈ V 0;

• Le niveau de stock initial chez le client i : choisi uniformément dans l’intervalle [100; 150];

• Le coût de stockage chez le client i, hm

i : choisi uniformément dans l’intervalle [0.02; 0.2];

• Le coût de stockage chez le fournisseur, hm

0 : est fixé à 0.01;

• La taille de l’horizon p : égale à 3, 5 ou 7 périodes;

• La quantité de produits envoyée au fournisseur rmt : égale à f mt × n, où f mt est généré

uniformément dans l’intervalle [50; 140];

• La capacité de stockage Ci du client i : égale à m × gi × fi où gi est tiré au hasard à partir

de l’ensemble {2, 3, 4} et fi est choisi uniformément dans l’intervalle [150; 200];

• La demande dmt
i du client i : est choisie uniformément dans l’intervalle [10; 100];
¥P P P mt
¦
• La capacité du véhicule Q est : réglée pour être 2 × i m t di /pK

En outre, en générant 5 instances pour chaque combinaison de n, M, K, p, nous obtenons au

total 675 instances. Mais, dans ce qui suit et en utilisant la même présentation que Coelho et
Laporte (2013b) [22], la moyenne des 5 instances de chaque combinaison est considérée comme
une seule instance.

52
 3.5. Expérimentation

Tableau 3.2: GBH Vs. B&C sur les instances avec K = 1 & M = 1

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 0.00 0.48 4.15
20 0.00 1.60 0.67 13.81
30 0.00 13.20 1.68 28.80
40 0.00 101.80 1.25 48.62
50 0.00 299.60 2.28 78.11
5 10 0.00 1 1.16 5.45
20 0.00 20.40 1.33 18.57
30 0.00 182.20 1.1 38.52
40 0.00 9464.60 1.12 67.26
50 0.56 20712.60 2.23 106.06
7 10 0.00 27.80 3.37 6.521
20 0.00 3335.60 2.68 21.984
30 3.06 28529.00 5.07 46.77
40 6.03 43200.00 7.34 79.73
50 9.97 43187.80 9.40 123.07

3.5.3 Résultats et comparaison avec B&C

Le B&C a été implémenté en C++ en utilisant IBM Concert Technology et CPLEX 12.4 comme
solveur de programme linéaire mixte. Tous les tests de Coelho et Laporte (2013b) [22] ont été
réalisés sur une grille de calcul doté d’un ensemble de processeurs Intel Xeon avec 2.66 GHz
et avec une mémoire de 48 Go par noeud. Le jeu d’essai utilisé pour tester l’algorithme et
les meilleures solutions obtenues sont téléchargeables à partir du site suivant ([Link]-
[Link]/instances). Par la suite, dans les tableaux de 3.2 jusqu’à 3.10 : la première colonne
indique le nombre de périodes (périodes). Ensuite, la deuxième colonne présente le nombre de
clients (clients). Les colonnes trois et quatre présentent le gap entre le coût de la solution obtenue
par B&C et la borne inférieure (gap), et le temps d’exécution de B&C (temps CPU) respective-
ment. Enfin, les colonnes cinq et six indiquent le gap entre la valeur de la solution obtenue par
GBH et la borne inférieure (gap), et le temps de calcul de GBH (temps CPU) respectivement.
Ainsi, pour calculer les gaps nous utilisons la formule (z 0 − z)/z 0 , où z est la borne inférieure,
z 0 est le coût de la solution obtenue pour chaque algorithme. Enfin, pour chaque instance, les
meilleurs résultats de GBH sont soulignés (quand GBH est meilleur que B&C).
En effet, il est difficile de faire une comparaison entre les deux algorithmes proposés (GBH et
B&C) à cause du grand nombre d’instances et leurs variétés. Par conséquent, pour obtenir une
bonne comparaison et dans le but de faciliter la tâche, nous divisons l’ensemble d’instances en
trois groupes : le premier groupe GS1 contient les instances où le B&C a prouvé l’optimalité. Le
deuxième groupe GS2 contient des instances où le B&C est meilleur que GBH mais l’optimalité
n’est pas prouvée; le troisième groupe GS3, contient les instances où les résultats de GBH sont
meilleurs que les résultats de B&C. Il est évident que la taille et la complexité des instances de
GS3 sont plus importantes que les instances de GS2 et GS1.
Le tableau 3.11 montre la comparaison entre le GBH et le B&C. La première colonne présente
les groupes d’instances (groupe) et la deuxième colonne représente le nombre d’instances dans

53
 3.5. Expérimentation

Tableau 3.3: GBH Vs. B&C sur les instances avec K = 3 & M = 1

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 6.60 0.16 4.706
20 0.00 184.00 0.42 14.75
30 0.00 5113.40 0.59 29.85
40 2.92 28221.60 3.62 49.51
50 19.44 43200.00 12.10 76.53
5 10 0.22 12555.40 4.79 5.84
20 17.04 41683.20 18.17 19.39
30 31.16 43181.00 28.44 39.99
40 42.11 43188.80 32.94 69.60
50 48.12 43197.20 30.70 104.73
7 10 14.40 28173.20 20.81 7.20
20 27.67 41297.40 30.836 23.475
30 33.60 43171.40 32.98 49.04
40 61.12 43200.00 42.00 84.30
50 62.17 43200.00 43.81 130.39

Tableau 3.4: GBH Vs. B&C sur les instances avec K = 5 & M = 1

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 120.20 0.86 4.89
20 4.09 29770.40 4.59 15.21
30 15.53 43200.00 15.18 31.48
40 16.20 43189.80 14.56 54.15
50 32.22 43189.00 20.73 81.19
5 10 12.82 35353.80 18.19 6.39
20 43.33 43200.00 44.15 19.94
30 43.84 43197.40 40.98 41.44
40 51.82 43197.60 36.02 72.53
50 65.98 43200.00 45.85 110.08
7 10 27.67 40106.40 35.37 8.07
20 46.27 43175.40 49.82 24.91
30 61.35 43191.20 51.77 50.79
40 71.09 43200.00 50.43 87.50
50 71.61 40688.40 54.83 134.62

54
 3.5. Expérimentation

Tableau 3.5: GBH Vs. B&C sur les instances avec K = 1 & M = 3

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 1.60 0.42 6.53
20 0.00 0.80 0.83 22.95
30 0.00 1.00 3.72 51.01
40 0.00 5.20 3.29 89.23
50 0.00 11.40 1.47 141.51
5 10 0.00 3.40 2.81 8.73
20 0.00 45.80 2.22 30.75
30 0.00 506.20 1.48 66.79
40 0.00 6967.80 2.52 118.89
50 2.72 40242.60 5.21 237.53
7 10 0.00 23.80 2.16 11.11
20 0.00 6173.40 4.78 40.35
30 5.41 43200.00 14.03 88.92
40 11.04 43200.00 17.54 162.33
50 15.15 43199.80 20.58 273.54

Tableau 3.6: GBH Vs. B&C sur les instances avec K = 3 & M = 3

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 5.80 0.462 6.89
20 0.00 322.60 1.29 23.69
30 0.00 3574.60 1.91 52.35
40 0.26 12952.60 6.14 88.62
50 2.27 35501.60 4.21 150.41
5 10 0.00 8008.20 2.94 9.29
20 17.05 42202.40 18.94 32.48
30 20.67 43196.00 22.86 69.91
40 23.57 43188.60 22.56 120.77
50 45.54 18555.20 24.10 191.59
7 10 21.94 27184.00 30.08 11.79
20 29.36 43197.60 34.43 41.49
30 30.89 43197.80 36.09 88.30
40 38.35 43200.00 36.16 155.08
50 54.69 43200.00 38.57 248.14

55
 3.5. Expérimentation

Tableau 3.7: GBH Vs. B&C sur les instances avec K = 5 & M = 3

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 102.40 0.13 7.349
20 2.46 21424.00 3.186 25.29
30 3.81 36036.80 4.95 52.29
40 2.36 42241.80 3.32 97.13
50 9.46 43200.00 7.58 145.85
5 10 19.39 41231.80 29.68 9.55
20 26.03 43200.00 28.70 33.47
30 37.85 43181.00 35.13 72.42
40 51.09 37037.80 32.34 124.18
50 47.08 21927.60 33.05 196.69
7 10 30.18 42541.20 34.48 13.03
20 41.00 43195.20 45.95 43.29
30 60.65 43190.00 47.41 90.67
40 61.09 34766.60 48.34 157.05
50 56.43 43200.00 42.47 247.97

Tableau 3.8: GBH Vs. B&C sur les instances avec K = 1 & M = 5

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 4.60 1.48 8.75
20 0.00 1.00 1.52 31.59
30 0.00 2.00 1.46 68.50
40 0.00 6.40 1.91 121.03
50 0.00 19.00 3.99 192.41
5 10 0.00 7.40 3.91 12.32
20 0.00 95.20 2.78 45.06
30 0.00 5670.40 3.39 99.17
40 2.11 32088.60 6.13 178.50
50 7.49 43194.00 10.60 277.39
7 10 0.00 53.60 4.43 16.20
20 0.33 18773.60 6.33 62.27
30 9.39 43195.00 15.97 139.08
40 12.30 43200.00 20.14 253.59
50 17.64 43194.80 22.33 401.10

56
 3.5. Expérimentation

Tableau 3.9: GBH Vs. B&C sur les instances avec K = 3 & M = 5

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 5.00 1.70 9.37
20 0.00 520.00 0.74 32.48
30 0.81 17738.80 3.89 70.36
40 0.71 14205.40 3.30 123.11
50 1.14 33966.20 1.99 199.91
5 10 5.10 16428.00 9.33 12.84
20 15.28 43200.00 20.02 45.97
30 22.49 43188.60 21.89 100.30
40 30.40 43194.60 25.71 176.74
50 45.56 42173.00 21.62 283.91
7 10 22.77 26783.20 28.98 17.22
20 30.34 43200.00 37.56 60.70
30 30.84 43200.00 34.35 136.35
40 62.96 43192.00 39.98 239.80
50 55.65 43200.00 34.78 390.54

Tableau 3.10: GBH Vs. B&C sur les instances avec K = 5 & M = 5

B&C GBH
périodes clients gap temps CPU gap temps CPU
3 10 0.00 64.00 0.39 9.753
20 0.60 9813.20 2.00 34.25
30 3.13 37412.20 2.88 72.08
40 5.55 43199.40 7.97 128.18
50 12.14 41009.60 8.57 195.65
5 10 17.73 43122.00 30.19 13.42
20 30.16 43200.00 32.64 46.97
30 39.07 43200.00 33.71 101.14
40 54.65 43200.00 30.91 181.18
50 54.34 41344.60 31.27 280.77
7 10 29.57 42114.00 35.46 18.51
20 40.03 43200.00 44.76 63.18
30 44.05 43185.40 45.40 134.45
40 54.70 43200.00 43.19 239.64
50 55.06 43200.00 47.45 375.68

57
 3.5. Expérimentation

Tableau 3.11: GBH Vs. B&C en regroupant les instances

GBH B&C
groupe #instance gap temps CPU gap temps CPU gapGBH -gapB&C
GS1 43 01.84 39.63 00.00 1187.78 01.84
GS2 52 19.71 83.64 15.62 35640.88 04.09
GS3 40 31.81 143.23 42.83 41348.53 −11.02

chaque groupe (#instance). Ensuite, les colonnes trois et quatre (cinq et six respectivement) sont
la moyenne des gaps et la moyenne des temps d’exécution de GBH (de B&C respectivement)
pour chaque groupe. Enfin, la dernière colonne est la différence entre la moyenne des gaps de
GBH et la moyenne des gaps de B&C (gapGBH -gapB&C ).
En comparant GBH à B&C lorsque l’optimalité est prouvée, GBH a un petit gap de, seule-
ment, 01.84% au-dessus des solutions optimales. En outre, bien que les instances de GS2 montrent
clairement la performance et l’efficacité de B&C, nous constatons que le GBH est toujours com-
pétitive et il a un gap de 04.09% au-dessus de la borne supérieure du B&C. Ici, il est important
de noter que, dans GS2 la différence entre les gaps est plus importante de celle de GS1 parce
que la qualité des gaps de GS2 dépend de la qualité des bornes inférieures trouvées par CPLEX,
contrairement au GS1 où la qualité des gaps dépend de la qualité des solutions optimales. Dans
GS1 et GS2, l’efficacité du B&C est clairement montrée et au même temps, il semble raisonnable
de dire que les gaps de GBH sont relativement faibles. Pour les instances du groupe GS3, la taille
des instances augmente et le problème devient de plus en plus complexe. Dans ces instances, le
GBH donne des meilleurs résultats par rapport au B&C avec un pourcentage moyen de 11.02%.
Néanmoins les deux algorithmes ont été implémentés dans des environnements différents et
testés sur des machines différentes, la comparaison des grandeurs des temps d’exécution reste
possible [52]. En effet, parce que le GBH n’utilise pas les solveurs et/ou les méthodes exactes, le
temps d’exécution de GBH est considérablement inférieur à celui de B&C, en comparant 143.23
à 41348.5 secondes bien que la machine utilisée pour tester le GBH est moins performante que
la machine utilisée pour tester B&C. Ces temps de calcul intéressants ont été obtenus grâce
à la non-utilisation des solveurs et/ou des algorithmes exacts. En outre, à la lumière de notre
temps d’exécution considérablement faible, nous constatons que GBH est efficace et rapide en
comparant avec la plupart des algorithmes de la littérature [24].
Pour conclure cette partie, bien que le B&C est meilleur que le GBH dans les petites et
moyennes instances, le GBH donne des résultats, pour ces instances, très proches de l’optimalité
avec un temps d’exécution très faible. Pour les instances de grande taille, le GBH se montre plus
performant que B&C avec un gap moyen de 11.02 % avec un temps d’exécution beaucoup moins
important. Enfin, GBH est capable de trouver de nouvelles solutions pour 40 instances de grande
taille sur un total de 135 instances.

3.5.4 L’analyse du comportement de GBH

Dans cette section, nous analysons le comportement de GBH en testant sa flexibilité, sa stabilité
et son efficacité. Nous entendons par la flexibilité de GBH, sa capacité à faire face à différentes
instances ayant des caractéristiques différentes (en faisant varier le nombre de véhicules, de
produits et les périodes), et nous entendons par la stabilité de GBH, sa capacité à converger
vers la même qualité de solution même si nous l’exécutons plusieurs fois. Ainsi, pour bien tester

58
 3.5. Expérimentation

Tableau 3.12: Résultats d’analyse de comportement de GBH

GBH ×10 GBH-LT gapbest gapavg

Inst moyenne meilleur CPU gapavg,best coût CPU
mmirp-50-1-1-3 6868.61 6781.32 74.23 1.27 6816.416 772.29 0.51 −0.77
mmirp-50-1-1-5 9912.66 9725.96 100.2 1.88 9651.658 990.38 −0.77 −2.7
mmirp-50-1-1-7 13313.68 13247.54 118.89 0.5 13159.43 1149.63 −0.67 −1.17
mmirp-50-1-3-3 7663.53 7589.76 78.23 0.96 7559.13 748.78 −0.41 −1.38
mmirp-50-1-3-5 12115.98 12030.28 101.63 0.71 11921.26 987.22 −0.91 −1.63
mmirp-50-1-3-7 17972.78 17874.88 123.4 0.54 17774.31 1188.91 −0.57 −1.12
mmirp-50-1-5-3 7893.34 7789.87 78.32 1.31 7770.43 783.24 −0.25 −1.58
mmirp-50-1-5-5 14907.15 14776.25 103.31 0.88 14714.73 1011.17 −0.42 −1.31
mmirp-50-1-5-7 25358.58 25250.64 127.77 0.43 24893.86 1233.4 −1.43 −1.87
mmirp-50-3-1-3 11375.11 11117.68 130.4 2.26 11143.97 1257.89 0.24 −2.07
mmirp-50-3-1-5 17175.37 17102.34 175.15 0.43 17071.82 1694.34 −0.18 −0.61
mmirp-50-3-1-7 25328.76 25185.91 238.45 0.56 25300.86 2303.43 0.45 −0.11
mmirp-50-3-3-3 11867.21 11610.2 135.92 2.17 11742.31 1356.89 1.13 −1.06
mmirp-50-3-3-5 19691.3 19545.27 181.11 0.74 19286.7 1735.52 −1.34 −2.1
mmirp-50-3-3-7 30726.6 30494.93 234.89 0.75 30476.14 2255.03 −0.06 −0.82
mmirp-50-3-5-3 12231.67 12106.89 138.97 1.02 12002.99 1426.15 −0.87 −1.91
mmirp-50-3-5-5 22608.47 22407.0 187.11 0.89 22330.58 1817.73 −0.34 −1.24
mmirp-50-3-5-7 34615.42 34381.33 235.73 0.68 33991.91 2274.91 −1.15 −1.83
mmirp-50-5-1-3 14497.11 14235.65 180.47 1.80 14548.68 1732.54 2.15 0.35
mmirp-50-5-1-5 23313.7 23166.74 270.06 0.63 23066.43 2587.44 −0.43 −1.07
mmirp-50-5-1-7 33942.77 33757.14 390.02 0.55 33379.77 3721.54 −1.13 −1.69
mmirp-50-5-3-3 15465.83 15045.28 186.89 2.72 15049.55 1845.25 0.03 −2.77
mmirp-50-5-3-5 25785.45 25444.48 273.63 1.32 25320.31 2560.61 −0.49 −1.84
mmirp-50-5-3-7 40357.87 40038.97 382.81 0.79 39896.84 3544.13 −0.36 −1.16
mmirp-50-5-5-3 16007.15 15652.81 190.99 2.21 15463.16 1817.52 −1.23 −3.52
mmirp-50-5-5-5 29146.77 28675.88 275.44 1.62 28530.26 2555.25 −0.51 −2.16
mmirp-50-5-5-7 49967.91 49661.83 366.36 0.61 48806.4 3381.84 −1.75 −2.38
moyenne 188.16 1.12 1804.93 −0.40 −1.54

l’algorithme, nous utilisons toutes les instances de 50 clients, qui sont les plus difficiles et avec
lesquelles les caractéristiques de GBH seront clairement montrées.
Tout d’abord, nous exécutons le GBH sur ces instances 10 fois (GBH×10) en utilisant les
mêmes critères d’arrêt présentés dans le paragraphe de réglage des paramètres. La meilleure
solution et le gap entre la solution moyenne et la meilleure sont présentés. Ces résultats nous
permettent de tester la flexibilité et la stabilité de GBH. Deuxièmement, nous lançons le GBH
juste une fois sur les mêmes instances, mais avec plus de temps d’exécution, c’est-à-dire, les
critères d’arrêt seront multipliés par 10 (GBH with Long Time, GBH-LT), et les résultats obtenus
nous aident à montrer l’efficacité et la stabilité de GBH. Dans le tableau 3.12, les éléments
suivants figurent : la première colonne indique le nom de l’instance (Inst). Ensuite, les colonnes
de deux à cinq présentent les résultats d’exécution de GBH×10. Les colonnes deux et trois
indiquent la moyenne (moyenne) et le meilleur (meilleur) coût obtenus pour chaque instance
respectivement, la colonne quatre présente le temps de calcul moyen des 10 exécutions (CPU), et
la cinquième colonne contient le gap (gapavg,best ) entre le meilleur coût et la moyenne des coûts
((avg − best)/avg). En plus, les colonnes six et sept indiquent le coût de la solution (coût) et le
temps de calcul de GBH-LT (CPU). Enfin, les colonnes huit et neuf présentent le gap entre la
moyenne des coûts de GBH×10 et le coût de la solution de GBH-LT, et le gap entre le meilleur
coût de GBH×10 et le coût de la solution de GBH-LT, respectivement.

59
 3.5. Expérimentation

A partir du tableau 3.12, nous pouvons remarquer que la moyenne des gaps entre les moyennes
et les meilleures solutions de GBH×10 est égale à 1.12%. En effet, ce gap, qui varie de 0.43% à
2.72%, montre clairement la stabilité de l’algorithme, car il peut toujours converger vers la même
qualité de solution sur des instances complexes. En plus, avec plus du temps de calcul et pour
chaque instance, le GBH-LT est en mesure d’améliorer la qualité de la moyenne et la meilleure
solution obtenues par GBH×10 avec un pourcentage moyen de 1.54% et 0.40% respectivement.
Pour la moyenne de GBH×10, GBH-LT améliore la qualité des solutions de toutes les instances.
En plus, bien que le GBH×10 dépense environ le même temps d’exécution de GBH-LT pour
obtenir les meilleures solutions, GBH-LT se montre plus performant que GBH×10 dans 21 sur 27
instances. Ces résultats expliquent clairement à la fois l’efficacité et la stabilité de convergence de
GBH. Dans cette étape de l’expérimentation, le GBH est exécuté sur des instances où les nombres
de produits, de véhicules et de périodes varient de 1, 1, 3 à 5, 5, 7 respectivement. (C’est-à-dire
de l’instance 50-1-1-3 à l’instance 50-5-5-7). Même avec une grande différence entre les instances
en entrée de l’algorithme, le GBH est en mesure de traiter tous les cas et de fournir des résultats
très prometteurs ce qui montre sa flexibilité.

3.5.5 Les résultats de GBH sur les instances de MMIRP-SD

Dans cette sous-section, notre objectif est de comparer le GBH à une autre heuristique de la
littérature. Donc, nous avons adapté le GBH pour résoudre la variante de MMIRP abordée
dans Cordeau et al. (2015) [27] (MMIRP-SD). Dans Cordeau et al. (2015) [27], les auteurs ont
considéré la même définition de MMIRP de Coelho et Laporte (2013b) [22], mais en ignorant
les données du le fournisseur. En effet, le B&C a déjà été adapté à cette variante, et cela a
permis à Cordeau et al. (2015) [27] de comparer leur Heuristique de Décomposition (DH) avec
B&C. Cette comparaison a été faite sur des instances de MMIRP-SD, qui sont dérivées du jeu
d’essai de Coelho et Laporte (2013b) [22]. Par conséquent, nous avons la possibilité, d’une part,
de comparer GBH avec une heuristique de la littérature, et d’autre part, de comparer GBH
avec B&C avec un temps de calcul limité. Dans Coelho et Laporte (2013b) [22], pour chaque
combinaison de n, M, K, p, les cinq instances ont été considérées comme une seule instance en
prenant la moyenne des coûts des solutions mais, dans Cordeau et al. (2015) [27], chaque instance
de la même combinaison est considérée comme une seule instance. En outre, dans Cordeau et al.
(2015) [27], seules les instances de 3 périodes, 3 véhicules et {3, 5} produits ont été utilisées. La
DH a été implémentée en JAVA, toutes les expériences ont été menées sur un PC équipé d’un
processeur Intel i7 avec 2.40 GHz et disposant d’une mémoire de 32Go de RAM.
Le tableau 3.13 compare les résultats de GBH avec ceux de B&C et DH. La première et la
dernière colonne indiquent le nom de l’instance (inst) et la meilleure solution trouvée (meilleure)
par tous les algorithmes respectivement. En plus, pour chaque algorithme, nous présentons le
coût de la solution (coût), le temps d’exécution (CPU, en secondes) et le pourcentage du gap
(gap) entre le coût de la solution obtenue et le coût de la meilleure solution trouvée. Ici, il faut
noter que les résultats de B&C sont obtenus avec un temps de calcul limité à 3600 secondes.
En comparant GBH à DH, le GBH donne de meilleurs résultats dans 42 sur 50 instances
par rapport au DH, les deux algorithmes donnent les mêmes résultats pour 7 instances et pour
une seule instance la DH est meilleure que GBH. Ainsi, malgré que les résultats ne subissent
pas une nette amélioration, le GBH se montre plus performant que DH avec un pourcentage
moyen de 4.72%. En outre, les deux algorithmes ont été implémentés en JAVA et les expériences
ont été réalisées sur un PC avec un processeur i7 et avec 32 Go de RAM, mais la fréquence de
notre processeur est plus élevée que le processeur de Cordeau et al. (2015) [27] (En comparant
03.40 GHz à 2.40 GHz). Donc, en prenant ces caractéristiques en considération et en comparant

60
 3.5. Expérimentation

Tableau 3.13: GBH Vs. B&C et DH

DH B&C GBH meilleure
inst coût gap CPU coût gap CPU coût gap CPU
mmirp-10-3-1 4159.86 0.0 3.36 4159.86 0.0 13.08 4159.86 0.0 12.71 4159.86*
mmirp-10-3-2 4411.81 10.62 1.3 3988.34 0.0 1.43 3988.34 0.0 11.72 3988.34*
mmirp-10-3-3 4130.03 0.0 3.34 4130.03 0.0 19.49 4130.03 0.0 11.67 4130.03*
mmirp-10-3-4 3932.27 0.0 2.59 3932.27 0.0 5.5 3932.27 0.0 11.73 3932.27*
mmirp-10-3-5 4373.71 3.38 1.42 4230.71 0.0 9.09 4230.71 0.0 11.46 4230.71*
mmirp-20-3-1 6696.39 6.9 5.0 6264.39 0.0 1921.76 6367.36 1.64 38.25 6264.39*
mmirp-20-3-2 6884.72 5.31 7.91 6537.72 0.0 165.43 6537.72 0.0 40.51 6537.72*
mmirp-20-3-3 5797.23 2.36 20.66 5663.52 0.0 33.58 5694.23 0.54 39.96 5663.52*
mmirp-20-3-4 6241.56 3.62 16.92 6023.56 0.0 49.69 6023.56 0.0 41.09 6023.56*
mmirp-20-3-5 5961.5 5.04 77.44 5675.68 0.0 1114.74 5675.68 0.0 38.33 5675.68*
mmirp-30-3-1 7225.53 0.18 17.05 7212.53 0.0 2470.93 7497.27 3.95 81.63 7212.53*
mmirp-30-3-2 8357.41 9.89 68.87 7605.41 0.0 3600.0 7605.41 0.0 81.87 7605.41*
mmirp-30-3-3 7198.66 3.98 33.98 6922.94 0.0 369.42 6922.94 0.0 85.77 6922.94*
mmirp-30-3-4 8058.41 7.96 51.09 7464.14 0.0 3600.0 7464.14 0.0 83.23 7464.14*
mmirp-30-3-5 7907.68 1.59 207.89 7783.68 0.0 330.03 7783.68 0.0 92.92 7783.68*
mmirp-40-3-1 9034.73 0.0 415.89 9034.73 0.0 3600.0 9034.73 0.0 146.575 9034.73*
mmirp-40-3-2 8861.96 12.91 402.13 7848.96 0.0 3450.45 7848.96 0.0 173.33 7848.96*
mmirp-40-3-3 9298.3 10.45 424.16 8576.3 1.88 3600.0 8418.3 0.0 174.84 8418.3*
mmirp-40-3-4 8501.82 0.0 317.62 8501.82 0.0 1943.75 8501.82 0.0 146.42 8501.82*
mmirp-40-3-5 10263.51 13.78 559.18 10363.7 14.89 3600.0 9020.7 0.0 166.353 9020.7*
mmirp-50-3-1 10561.95 6.12 276.55 9953.25 0.0 3600.0 9953.25 0.0 272.86 9953.25
mmirp-50-3-2 10714.03 4.73 920.25 11457.03 11.99 3600.0 10230.03 0.0 261.273 10230.03**
mmirp-50-3-3 10654.04 6.26 774.47 10026.04 0.0 3600.0 10026.04 0.0 260.06 10026.04*
mmirp-50-3-4 11111.64 10.08 531.8 11539.72 14.33 3600.0 10093.72 0.0 223.83 10093.72
mmirp-50-3-5 11154.42 11.54 904.58 10406.99 4.07 3600.0 9999.99 0.0 261.23 9999.99
mmirp-10-5-1 4747.34 7.19 2.31 4428.96 0.0 12.54 4428.96 0.0 15.1 4428.96*
mmirp-10-5-2 5572.91 1.24 2.83 5504.91 0.0 4.97 5504.91 0.0 15.13 5504.91*
mmirp-10-5-3 3648.88 0.0 0.91 3648.88 0.0 20.47 3648.88 0.0 15.44 3648.88*
mmirp-10-5-4 4807.03 2.23 1.7 4702.09 0.0 2.95 4702.09 0.0 15.27 4702.09*
mmirp-10-5-5 4862.73 0.0 1.78 4862.73 0.0 44.38 4862.73 0.0 15.16 4862.73*
mmirp-20-5-1 6211.68 1.43 9.94 6124.38 0.0 295.08 6124.38 0.0 53.96 6124.38*
mmirp-20-5-2 6356.61 7.14 15.36 5933.0 0.0 164.94 5933.0 0.0 53.93 5933.0*
mmirp-20-5-3 7615.51 0.74 18.19 7559.51 0.0 1725.7 7559.51 0.0 53.36 7559.51*
mmirp-20-5-4 7814.61 4.89 47.49 7450.61 0.0 50.11 7450.61 0.0 55.34 7450.61*
mmirp-20-5-5 7631.96 10.08 71.58 6932.96 0.0 102.4 6932.96 0.0 53.52 6932.96*
mmirp-30-5-1 8617.34 1.69 318.3 8474.34 0.0 1234.0 8474.34 0.0 125.19 8474.34*
mmirp-30-5-2 9525.27 4.18 214.2 9143.27 0.0 441.73 9143.27 0.0 127.82 9143.27*
mmirp-30-5-3 10017.6 2.95 105.98 9730.94 0.0 3600.0 9730.94 0.0 131.21 9730.94*
mmirp-30-5-4 10424.66 5.19 7.08 10511.66 6.06 3600.0 9910.66 0.0 120.6 9910.66*
mmirp-30-5-5 9347.05 3.65 53.02 9018.05 0.0 259.85 9018.05 0.0 126.01 9018.05*
mmirp-40-5-1 12000.1 4.52 507.97 11889.99 3.56 3600.0 11481.1 0.0 214.38 11481.1
mmirp-40-5-2 11303.19 5.83 591.95 10680.19 0.0 3600.0 10711.19 0.29 209.44 10680.19*
mmirp-40-5-3 11755.3 13.63 306.63 10732.9 3.75 3600.0 10344.9 0.0 230.48 10344.9*
mmirp-40-5-4 11034.9 1.71 220.08 10849.9 0.0 3600.0 10849.9 0.0 225.96 10849.9*
mmirp-40-5-5 10743.4 4.36 126.41 10294.64 0.0 3600.0 10294.64 0.0 215.37 10294.64*
mmirp-50-5-1 12849.23 3.23 489.17 12883.23 3.5 3600.0 12447.23 0.0 304.85 12447.23
mmirp-50-5-2 13782.47 6.29 568.81 12966.47 0.0 3600.0 12966.47 0.0 350.33 12966.47*
mmirp-50-5-3 12783.93 4.27 671.53 12260.93 0.0 3600.0 12270.93 0.08 326.84 12260.93
mmirp-50-5-4 13072.92 5.52 230.41 12500.92 0.9 3600.0 12388.92 0.0 299.26 12388.92*
mmirp-50-5-5 12869.29 3.94 105.53 13585.29 9.72 3600.0 12381.29 0.0 300.09 12381.29
moyenne 4.85 214.69 1.49 1909.15 0.13 128.47
∗ solution optimale
∗∗ nouvelle solution trouvée

61
 3.6. Conclusion

214.69s de DH à 128.47s de GBH, nous pouvons constater que les deux algorithmes ont à peu
près le même temps d’exécution.
A partir du tableau 3.13 nous pouvons remarquer que le GBH donne de meilleurs résultats
que le B&C dans 11 instances, tandis que le B&C reste meilleur dans 5 instances et dans 34
instances le GBH et B&C donnent les mêmes résultats. Bien que dans la plupart des instances,
les deux algorithmes donnent les mêmes résultats, le GBH se montre plus performant que B&C
avec un pourcentage moyen de 1.36% et avec un temps de calcul moyen considérablement faible
en comparant 128.47s avec 1909.15s. Dans Cordeau et al. (2015) [27], les auteurs donnent les
résultats obtenus par le B&C lorsque le temps de calcul est limité à 12 heures (43200 secondes).
En tenant compte de ces résultats, le GBH a pu trouver une nouvelle meilleure solution pour
l’instance mmirp-50-3-2, et des solutions optimales ont été rapportées pour 38 instances.

3.6 Conclusion
Dans ce chapitre, nous avons abordé le problème des tournées de véhicules avec gestion de
stock multi-périodes, multi-véhicules et multi-produits, appelé le MMIRP. Pour faire face à ce
problème, un nouvel algorithme a été introduit. Notre algorithme (GBH) est basé sur la méta-
heuristique GRASP (Greedy Randomized Adaptive Search Procedure). Le GBH est composé de
deux grandes phases. La première est une procédure gloutonne randomisée (GRP) qui construit
une solution réalisable de bonne qualité. La deuxième phase est une recherche locale qui se
consacre à améliorer la solution obtenue à partir de la phase précédente. Dans notre cas, la
première phase cherche à trouver le meilleur compromis entre le coût de stockage et le coût de
routage. Ensuite, comme méthode de recherche locale, nous avons utilisé la recherche Tabou.
Tout d’abord, la performance de GBH a été testée sur le jeu de données standard de Coelho
et Laporte (2013b) [22] avec 135 instances et les résultats obtenus ont été comparés avec les
résultats de leur algorithme de type Branch & Cut (B&C). Bien que le B&C ait été meilleur
que le GBH dans les petites et moyennes instances, nous avons obtenu de nouvelles meilleures
solutions pour 40 instances de grande taille. En plus, le GBH a un temps de calcul largement
inférieur par rapport au temps de calcul de B&C. Deuxièmement, afin de montrer encore son
efficacité, le GBH a été adapté pour résoudre la variante de MMIRP abordé dans Cordeau et al.
(2015) [27] et ses résultats ont été comparés avec les résultats de l’heuristique de décomposition
et de B&C. Les résultats présentés montrent que le GBH est meilleur que les deux algorithmes
proposés.

62
Chapitre 4

Algorithmes pour le problème de

routage de navettes et de taxis

Sommaire
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Définition du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.1 Contraintes & fonction objectif . . . . . . . . . . . . . . . . . . . . . . . 65
4.3 Méthodologie de la solution . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.1 L’idée principale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.3.2 Algorithmes pour le CTSSP . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.1 Réglage des paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.4.2 La procédure de génération de jeu de données . . . . . . . . . . . . . . . 73
4.4.3 Les résultats de TS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.4.4 La comparaison entre TS, GRASP et GRASP-LP . . . . . . . . . . . . 76
4.4.5 La méthode GRASP-LP sur les instances de VRP et d’OVRP . . . . . . 76
4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.1 Introduction
Le problème d’élaboration des tournées (Vehicle Routing Problem (VRP)) est l’un des problèmes
les plus importants dans le domaine de transport et de la logistique. Le VRP a été défini à la
fin des années 1950 [29]. A cause de leurs nombreuses applications dans l’industrie et le monde
réel, un nombre très important d’études ont été publiées portant sur le VRP et ses variantes [65].
En outre, le problème des tournées de véhicules ouvert (Open VRP (OVRP)) est une variante
importante de VRP où le véhicule n’a pas besoin de revenir au dépôt après avoir visité le dernier
client [106]. L’OVRP a été utilisé pour concevoir de nombreux problèmes de la vie quotidienne
tels que le problème d’élaboration de tournées de bus scolaire [89]. Il est souvent utilisé pour
modéliser des situations où l’entreprise a besoin de véhicules externes pour accomplir certaines
tâches.
Dans ce chapitre, nous présentons une contribution à un challenge international, à savoir
VeRoLog Solver Challenge 2015 (VSC2015) [33]. En collaboration avec le PTV-groupe (entreprise

63
 4.2. Définition du problème

logistique), le groupe de travail EWGVRLO (the EURO Working Group on Vehicle Routing and
Logistics Optimization) a défini une nouvelle variante du VRP (peut également être considérée
comme une nouvelle variante d’OVRP) que l’on appelle le problème de routage de navettes et
de taxis (Coach Trip with Shuttle Service Problem (CTSSP)). Cette nouvelle variante a été le
sujet du VSC2015 Doerner et al. (2015) [33]. Le CTSSP est un problème industriel qui concerne
le transport de personnel, dont le but est de transporter un ensemble de passagers depuis leurs
origines arrêts de bus à un dépôt central en utilisant une flotte de véhicules hétérogène. En effet, le
CTSSP possède certaines caractéristiques qui lui permettent non seulement d’être une nouvelle
variante du VRP mais, une variante qui est très compliquée en comparant avec les variantes
de VRP précédemment proposées dans la littérature, y compris celles de l’OVRP. Parmi ces
caractéristiques : les distances et les temps de transport entre les sommets sont asymétriques,
l’hétérogénéité de véhicules, l’utilisation des points de transfert, etc.
Pour résoudre le CTSSP, nous proposons deux méthodes, à savoir une recherche Tabou (Tabu
Search (TS)) et une méthode de type GRASP (Greedy Randomized Adaptive Search Procédure
(GRASP)). Après la construction d’une solution réalisable de bonne qualité en utilisant une
heuristique d’insertion, la méthode TS proposée utilise, à chaque itération, sept mouvements
pour créer la structure de voisinage [47]. Ainsi, afin de faciliter l’exploration de l’espace de
recherche, un mécanisme de relaxation est utilisé. En outre, nous proposons une méthode de
type GRASP qui utilise la méthode TS comme une recherche locale. Enfin, la méthode GRASP
est améliorée en utilisant une technique d’apprentissage. Dans ce qui suit, tout d’abord, nous
présentons la définition de CTSSP. Ensuite, nous présentons en détail les méthodes proposées,
et après cela, des expériences sur plusieurs jeux de test sont exposées.

4.2 Définition du problème

Le problème de routage de navettes et de taxis consiste à transporter un ensemble de passagers
depuis leurs arrêts de bus vers un dépôt central (HUB) en utilisant une flotte de véhicules
hétérogènes. Dans le CTSSP nous définissons :

• Un ensemble d’arrêts de bus bi (i = 1, ..., n).

• Chaque arrêt de bus bi possède un ensemble de qi passagers (qi ≥ 0).

• Une flotte de véhicule F V = (CO ∪ T X) où CO est un ensemble de m navettes et T X est

un ensemble de K taxis.

• Chaque véhicule j ∈ F V a une capacité spécifique.

• Chaque véhicule j ∈ F V a un coût d’utilisation et un coût de routage.

• Chaque navette commence sa route de son propre emplacement et se termine au HUB en

visitant un ensemble d’arrêts de bus.

• Chaque taxi commence sa route de son propre emplacement et se termine soit au HUB soit
à un arrêt de bus visité par une navette (un point de transfert).

• Les véhicules ne doivent pas revenir à leurs emplacements de départ.

• Les distances et les temps de conduite entre tous les sommets sont donnés dans des matrices
carrées. En effet, on a trois matrices: une matrice de distance, une matrice de temps pour

64
 4.3. Méthodologie de la solution

les navettes et une matrice de temps pour les taxis (parce que les taxis sont plus rapides
que les navettes).

• Toutes les matrices (de temps et de distance) sont asymétriques.

Dans la figure 4.1, nous présentons un exemple d’une solution pour le CTSSP avec 2 navettes
(c1 et c2), 4 taxis (s1, s2, s3 et s4) et 10 arrêts de bus (de b1 jusqu’a b10). Dans cette solution,
s1 et s2 utilisent b7 et b4 comme points de transfert respectivement.

4.2.1 Contraintes & fonction objectif

Comme contraintes dans le CTSSP nous avons:

• Le temps de transport de chaque passager p depuis son arrêt de bus jusqu’au HUB ne doit
pas dépasser une durée maximale Dpmax .

• Le nombre d’arrêts de bus dans une route de navette ne doit pas dépasser un nombre
maximal Smax .

• Les capacités des véhicules ne doivent pas être dépassées.

Dans le CTSSP le but (fonction objectif) est de minimiser le coût total, y compris le coût
d’utilisation de véhicules et le coût de transport.

Figure 4.1: Un exemple d’une solution pour le CTSSP

4.3 Méthodologie de la solution

Dans cette section, nous exposons les algorithmes proposés pour résoudre le CTSSP. Tout
d’abord, nous exposons l’idée principale en rapport avec les algorithmes proposés, puis les prin-
cipales composantes de la procédure TS et la méthode GRASP.

4.3.1 L’idée principale

[Link] Difficultés
L’utilisation des points de transfert dans le CTSSP est une nouvelle caractéristique qui augmente
sa difficulté en comparant avec toutes les variantes de VRP ou d’OVRP dans la littérature. En

65
 4.3. Méthodologie de la solution

effet, cette utilisation des points de transfert génère deux difficultés principales. La première est
: comment peut-on représenter une solution de CTSSP ? C’est-à-dire le choix de structures de
données pour représenter les points de transfert. La seconde difficulté est : comment peut-on
développer des opérateurs afin d’exploiter le voisinage dans une méthode de recherche locale ?
Dans les figures suivantes, nous montrons quelques exemples de ces difficultés (Figure 4.2- 4.4):

Figure 4.2: Difficultés de résolution de CTSSP : exemple 1

Dans la figure 4.2, le déplacement de l’arrêt de bus b1 de la navette c2 à la navette c1 peut

violer la contrainte de capacité de c1, parce que tous les passagers de s1 et s2 seront servis par
c1, et on note ici que c1 et c2 n’ont pas la même capacité.
Dans la figure 4.3, le déplacement de b1 du taxi s1 vers la navette c1 peut violer la contrainte
de temps de transport des passagers de b2 servis par s2.
Dans la figure 4.4, nous supposons que le déplacement de b1 de s2 vers s1 ne conduit pas à
l’infaisabilité. Cependant, il est clair que les routes de s1 et s2, générées après le déplacement,
nécessitent d’autres modifications pour améliorer leur qualité, c’est-à-dire nous devons trouver,
pour chaque route, un nouveau point de transfert. En plus, nous voulons montrer avec cet exemple
que le meilleur nouveau point de transfert peut appartenir à une autre route d’une autre navette,
qui n’a pas été pris en compte dans le mouvement.
Par conséquent, le développement des opérateurs pour passer d’une solution à une autre
nécessite plusieurs autres procédures afin de contrôler la faisabilité et la qualité de la solution.
Après chaque mouvement, on doit exécuter ces procédures, qui consomment beaucoup de temps
de calcul, pour maintenir la faisabilité et la qualité de chaque nouvelle solution. Ainsi, chaque
situation nécessite certaines procédures. Pour faire face à ces difficultés, dans le paragraphe
suivant, nous proposons une technique efficace.

[Link] L’approche proposée

Tout d’abord, nous définissons deux types de solution pour le CTSSP, à savoir Base et Amélioré:

66
 4.3. Méthodologie de la solution

Figure 4.3: Difficultés de résolution de CTSSP : exemple 2

Figure 4.4: Difficultés de résolution de CTSSP : exemple 3

• Une solution de type Base (Ba) est une solution pour le CTSSP où toutes les routes des
taxis se terminent au HUB, de sorte que les points de transfert ne sont pas considérés.

• Une solution de type Amélioré (Am) est une solution pour le CTSSP où les points de
transfert sont utilisés, donc certaines routes de taxis ne se terminent pas au HUB.

67
 4.3. Méthodologie de la solution

La différence entre une solution Ba et une solution Am est : la solution de type Am exploite
la caractéristique de points de transfert, et donc la qualité d’une solution Am est beaucoup mieux
qu’une solution de type Ba. Cependant, les deux types de solutions sont considérés comme des
solutions faisables pour le CTSSP [33]. Maintenant, nous considérons une solution Sb de type Ba.
En effet, nous pouvons obtenir une solution Sf de type Am à partir de Sb en supprimant quelques
arcs et en ajoutant quelques autres et vice-versa, c-à-dire que nous pouvons obtenir une solution
de type Am à partir d’une solution de type Ba en recherchant pour chaque taxi, le meilleur point
de transfert. Notre idée principale est basée sur qu’au lieu de considérer des solutions de type
Am au cours du processus de recherche, nous considérons des solutions de type Ba seulement et
pour chaque solution Ba, nous calculons le coût de la solution Am correspondante à l’aide d’une
procédure de réparation (Repair Procedure). Donc, pendant la recherche, les mouvements sont
appliqués à des solutions de type Ba.

[Link] Motivation
Notre choix, pour utiliser cette technique, a été motivé parce que :

1. Il est considérablement plus facile de développer des opérateurs pour exploiter le voisinage
si nous considérons des solutions de type Ba que des solutions de type Am.

2. Le contrôle de faisabilité des solutions est plus facile, c’est-à-dire, on n’a pas besoin de
procédures qui consomment beaucoup de temps de calcul pour maintenir la faisabilité de
la solution.

3. Pendant la recherche, pour chaque solution Ba, nous calculons le coût amélioré de sa
solution Am correspondante, et dans ce cas là, la fonction objectif va guider la recherche
vers des solutions Am de bonne qualité [28].

4. En utilisant cette technique, une seule procédure (procédure de réparation) sera appliquée
à toutes les solutions pour améliorer sa qualité en maintenant toutes les contraintes.

[Link] Procédure de réparation

La procédure de réparation (Repair Procedure) est un algorithme qui assure le passage d’une
solution Ba à une solution Am en cherchant pour chaque route de taxi le meilleur point de
transfert, tout en maintenant la faisabilité de la solution.
Tout d’abord, en prenant la définition de CTSSP, que les arrêts de bus visités par les navettes
peuvent être utilisés comme des points de transfert. Donc, pour chaque taxi, nous recherchons
le meilleur point de transfert dans ce sous-ensemble d’arrêts de bus. Ensuite, s’il existe un arrêt
de bus qui peut être utilisé comme un point de transfert en réduisant le coût de transport, alors
cet arrêt de bus remplace le HUB en fin de la route (en tant que dernier point visité). En outre,
pendant la recherche, la capacité de la navette et le temps de transport des passagers visités par
les taxis doivent être respectés.

4.3.2 Algorithmes pour le CTSSP

Dans cette partie, nous exposons les algorithmes développés pour résoudre le CTSSP, à savoir la
méthode TS et la méthode GRASP.

68
 4.3. Méthodologie de la solution

Algorithme 9 Procédure de réparation

1: entrée : S, une solution de type Base;
2: sortie : S, une solution de type Amélioré;
3: pour (chaque route de taxi Shi = {bi,1 , bi,2 ,..,bi,n }, Shi ∈ T X ) faire
4: bv ← meilleur {bj,k ∈ CAj , ∀CAj ∈ CO};
5: si (bv 6= NULL) alors
6: remplacer bi,n par bv dans Shi ;
7: fin si
8: fin pour

[Link] Recherche Tabou

La recherche Tabou (TS) est une méta-heuristique largement utilisée, avec succès, pour résoudre
les problèmes d’optimisation combinatoire [44, 49]. En prenant sa définition, la TS commence à
partir d’une solution initiale S0 . A chaque itération, elle choisit, la meilleure solution non-Tabou
Sm dans la structure de voisinage T N (Sc ) de la solution courante Sc . La solution Sm est devenue
la solution courante et l’ancienne solution courante Sc est déclarée interdite ou Tabou. Ces
étapes sont répétées jusqu’à ce qu’un critère d’arrêt soit atteint. Dans ce qui suit, les principales
composantes de la méthode TS sont exposées : l’heuristique d’insertion, la structure de voisinage,
le mécanisme de relaxation, la liste Tabou et enfin la méthode TS est décrite dans l’algorithme
11. On note ici que la procédure changer_vers_base() dans l’algorithme 11 est la procédure
inverse de la procédure de réparation.

1. Solution initiale : dans chaque solution de type Ba, le taxi commence à partir de son
propre emplacement et se termine au HUB. Par conséquent, afin de générer une solution
Ba réalisable de bonne qualité, nous utilisons l’heuristique d’insertion suivante (Insertion
Technique (IT)). L’IT nous présentons peut être classée comme une nouvelle heuristique
constructive pour le problème CTSSP. Tout d’abord, la procédure commence par une solu-
tion S vide et nous définissons une liste de candidats (CL) initialement formée par tous les
arrêts de bus. Ensuite, nous construisons, pour chaque véhicule (taxi ou navette), une route
vide entre son emplacement et le HUB. Après cela, à chaque itération, l’IT évalue tous les
arrêts dans la CL, puis le meilleur est retourné. L’arrêt de bus est inséré dans la route
appropriée et retiré du CL. L’IT se termine lorsque tous les arrêts de bus sont ajoutés à la
solution S. En effet, l’IT évalue chaque arrêt de bus en recherchant sa meilleure position
d’insertion dans la solution partielle actuelle et la fitness de cet arrêt est égale exactement
au coût de cette insertion. En outre, dans notre cas, chaque véhicule possède son propre
coût fixe (le coût de l’utilisation), son propre coût variable (coût de routage ou de trans-
port) et la matrice de coût/distance est asymétrique. Par conséquence, tous ces critères
doivent être pris en compte dans le processus d’évaluation. Enfin, l’IT est décrite dans
l’Algorithme10.

2. La structure de voisinage : la TS explore l’espace de recherche en utilisant sept mou-

vements pour créer la structure de voisinage. Tous ces mouvements sont principalement
basés sur le mouvement de déplacement (shift), où trois sont des mouvements gloutons,
trois sont des mouvements gloutons randomisés et un mouvement aléatoire. Dans ce qui
suit, nous donnons une description pour chaque mouvement.

• Le déplacement aléatoire (OpR) : ce mouvement consiste à déplacer un arrêt de sa

route vers une autre route choisie aléatoirement, de même que la position dans cette

69
 4.3. Méthodologie de la solution

Algorithme 10 Heuristique d’insertion

1: S: solution vide;
2: pour (chaque vehicle v ∈ S) faire
3: créer une route vide pour v;
4: fin pour
5: créer CL;
6: tant que (CL n’est pas vide) faire
7: évaluer chaque b ∈ CL;
8: b0 ← meilleur {b ∈ CL};
9: ajouter b0 dans S;
10: supprimer b0 de CL;
11: fin tant que
12: retourner S;

route.
• Le déplacement glouton 1 (G-OP1) : ce mouvement supprime un arrêt de sa route
et l’insère dans la meilleure position dans une autre route. G-OP1 respecte toutes les
contraintes.
• Le déplacement glouton 2 (G-OP2) : ce mouvement est similaire à G-OP1, mais il
peut violer la contrainte de temps de transport maximal de passagers.
• Le déplacement glouton 3 (G-OP3) : ce mouvement est similaire à G-OP1, mais il
peut violer la contrainte de capacité du véhicule.
• Le déplacement glouton-randomisé 1 (GR-OP1) : en utilisant ce mouvement, un arrêt
de bus b est retiré de sa route, puis une liste de candidats (RCL) est formée. RCL
contient les Kg meilleures positions d’insertion de b dans la solution. Après cela, une
position est choisie aléatoirement à partir de RCL et b est inséré dans cette position.
GR-OP1 respecte toutes les contraintes.
• Le déplacement glouton-randomisé 2 (GR-OP2) : ce mouvement est similaire à GR-
OP1, mais il peut violer la contrainte de temps de transport maximal de passagers.
• Le déplacement glouton-randomisé 3 (GR-OP3) : ce mouvement est similaire à GR-
OP1, mais il peut violer la contrainte de capacité du véhicule.

En outre, sauf OpR, tous les mouvements décrits ci-dessus sont effectués de façon exhaus-
tive, c’est-à-dire, après la suppression de l’arrêt de bus, toutes les positions dans toutes les
routes de la solution sont examinées.

3. Mécanisme de relaxation : dans notre heuristique TS, au cours du processus de

recherche, l’exploration de l’espace de recherche des solutions infaisables est autorisée. En
effet, cette technique, que l’on appelle le mécanisme de relaxation (en englais Relaxation
mechanism), souvent utilisée lorsque nous avons des problèmes avec plusieurs contraintes
difficiles [28], car elle facilite l’exploration de l’espace de recherche, et améliore considérable-
ment la puissance de convergence de l’algorithme [68]. En outre, afin de gérer l’infaisabilité,
ces violations sont pénalisées dans la fonction objectif.
Formellement, pour une solution S, nous définissons la variable Coût (S) qui représente le
coût total la solution, y compris le coût fixe d’utilisation de véhicules et le coût de transport.
De plus, nous définissons Cus (S), Veh (S) et Coa (S) qui représentent respectivement, la

70
 4.3. Méthodologie de la solution

violation du temps de transport de passagers, la violation de la capacité des véhicules et

la violation de contrainte du nombre maximum d’arrêts dans les routes de navettes. Donc,
la fonction objectif F(S) à minimiser sera F(S) = Coût(S) + Cus(S) × α + Veh(S) ×
β + Coa(S) × γ; où α, β et γ sont des paramètres positifs auto-réglés et leurs valeurs sont
réglées dynamiquement pendant le processus de recherche comme suit:
Similaire à Cordeau et Laporte (2003) [28], initialement, ces paramètres sont fixés a :
α = 1, β = 1 etγ = 1. Ensuite, à chaque itération, si la nouvelle solution courante Sc viole
une contrainte, le paramètre correspondant sera multiplié par φ, sinon le paramètre sera
divisé par φ (φ = 1.025). On note ici que, la meilleure solution trouvée Stbest doit satisfaire
toutes les contraintes.

4. La liste Tabou : l’objectif principal de la liste Tabou est d’éviter de retourner vers les
mêmes solutions en mémorisant les solutions visitées dans les dernières itérations. La TS
applique ce principe de manière très simple, c’est-à-dire, à chaque itération nous ajoutons
la solution courante à la liste Tabou et chaque solution appartenant à la liste ne peut être
une solution courante, même si cette solution est la meilleure dans la structure de voisinage.

Algorithme 11 Recherche Tabou

1: S0 ← Heuristique_insertion();
2: Sc ← S0 ;
3: tant que (le critère d’arrêt n’est pas satisfait) faire
4: créer T N (Sc );
5: pour (chaque Si ∈ T N (Sc )) faire
6: Si ← Procedure_réparation(Si );
7: fin pour
8: Sm ← meilleur { Si ∈ T N (Sc ) et Si ∈ / T _list};
9: si (coût(Sm ) < coût(Stbest )) alors
10: Stbest ← Sm ;
11: fin si
12: insérer Sm à T _list;
13: Sc ← changer_vers_base(Sm );
14: fin tant que
15: retourner Stbest

[Link] GRASP
La méthode GRASP (Greedy Randomized Adaptive Search Procedure) est une métaheuristique
itérative utilisée pour résoudre les problèmes d’optimisation combinatoire. Chaque itération de
GRASP se compose de deux phases, une procédure gloutonne randomisée (Greedy Randomized
Procedure (GRP)) et une recherche locale (Local Search (LS)) [39]. Dans la procédure gloutonne
randomisée, une solution réalisable de bonne qualité est construite en ajoutant progressivement
un élément à la fois. En commençant à partir d’une solution partielle vide, à chaque itération, les
éléments qui ne sont pas déjà insérés sont évalués en utilisant une fonction gloutonne, puis une
liste restreinte de candidats (RCL) est formée par les Kg meilleurs éléments. Ensuite, un élément
de RCL est choisi aléatoirement et est inséré dans la solution. Ces étapes sont répétées jusqu’à
ce que tous les éléments soient insérés. Dans la deuxième phase, la méthode GRASP utilise une

71
 4.3. Méthodologie de la solution

recherche locale pour améliorer la qualité de la solution retournée par la phase précédente. Ces
deux phases sont répétées jusqu’à ce qu’un critère d’arrêt soit atteint, et finalement la meilleure
solution globale trouvée est retournée.
L’une de façon pour améliorer la méthode GRASP classique est d’ajouter un proces-
sus d’apprentissage (Learning Process LP). Le LP est un mécanisme qui permet au GRASP
d’exploiter les informations recueillies dans les itérations précédentes pour améliorer la qual-
ité de la solution. Dans ce qui suit, nous présentons les principales composantes du GRASP :
la procédure gloutonne randomisée, la recherche locale, le processus d’apprentissage et enfin la
méthode GRASP est décrite dans l’algorithme 12.

1. La procédure gloutonne randomisée : comme procédure gloutonne randomisée au sein

de la méthode GRASP, nous utilisons une version modifiée de l’heuristique d’insertion (IT)
decrite ci-dessus. En effet, dans IT, à chaque itération, le meilleur arrêt de bus est inséré
dans la solution. Donc, au lieu d’utiliser cette technique, une liste de Kg meilleurs arrêts
est construite, et ensuite un arrêt sélectionné aléatoirement est inséré.

2. La recherche locale : comme recherche locale au sein de la méthode GRASP, nous

utilisons la recherche Tabou décrite ci-dessus. Cependant, dans ce cas, la recherche Tabou
commence à partir de la solution retournée par la procedure GRP.

3. Le processus d’apprentissage : le LP est une partie très importante dans les algorithmes
itératifs parce qu’il conduit à des améliorations en terme de qualité de la solution. En outre,
la construction d’une solution initiale de haute qualité pour une recherche locale joue un rôle
très important dans le but de parvenir à de meilleures solutions [66, 84]. Par conséquent,
dans notre cas, l’objectif de LP est d’améliorer la convergence de GRASP en améliorant la
procedure GRP avec une méthode simple et efficace.
D’abord, la construction d’une solution de haute qualité consiste à insérer chaque arrêt
de bus dans la route appropriée. Sur la base de cette idée, le LP essaie de trouver, pour
chaque arrêt, une liste de routes dans lesquelles, l’insertion de cet arrêt dans une route
de cette liste conduite à une solution de bonne qualité. Pendant la recherche, le LP crée,
pour chaque arrêt de bus b, une liste Lb des routes dans lesquelles b a été affecté quand
une nouvelle meilleure solution est trouvée. Donc, à chaque itération GRP, chaque arrêt b
sera inséré dans une route choisie à partir de la liste Lb qui est formée dans les itérations
précédentes de GRASP, et donc une bonne solution de qualité sera construite.

Algorithme 12 GRASP
1: tant que (le critère d’arrêt non satisfait) faire
2: Sg ← Procédure_gloutonne_randomisée();
3: Sts ← Recherche_Tabou(Sg );
4: si (coût(Sts ) < coût(Sgbest )) alors
5: Sgbest ← Sts ;
6: fin si
7: fin tant que
8: retourner Sgbest ;

72
 4.4. Expérimentation

Tableau 4.1: Liste des acronymes

Acronyme description

TS-OP La recherche Tabou en utilisant que l’operateur G-OP1, c-à-dire

sans mécanisme de relaxation et
sans procédure de réparation

TS-OP-RP La recherche Tabou en utlisant que l’operateur G-OP1

avec la procédure de réparation mais sans
mécanisme de relaxation

TS-OP-RP-RX La méthode TS-OP-RP mais en rajoutant le

mécanisme de relaxation avec les opérateurs
G-OP2, G-OP3 et OpR

TS-Full La méthode TS-OP-RP-RX en rajoutant les opérateurs

glouton-randomisés GR-OP1, GR-OP2 et GR-OP3

4.4 Expérimentation
Dans cette section, nous présentons les résultats obtenus par les algorithmes proposés. Les deux
algorithmes ont été codées en JAVA; toutes les expériences ont été menées sur un PC équipé
par un processeur Intel i7 avec 3.40 GHz et disposant d’une mémoire de 32Go. Pour tester les
performances des algorithmes proposés, nous générons un jeu de données avec 24 instances basés
sur les instances utilisées dans les étapes de VSC2015. Dans ce qui suit, d’abord, nous présentons
le réglage des paramètres et la procédure de génération de jeu de test, puis nous présentons les
résultats de la méthode TS et la contribution de chaque composant dans les résultats finaux.
Ensuite, une comparaison entre les méthodes TS, GRASP et GRASP-LP (GRASP avec LP) est
présentée. Enfin, pour valider notre approches avec la littérature, nous présentons les résultats
de la méthode GRASP-LP sur des jeux de données de VRP et d’OVRP. Dans le tableau 4.1,
nous donnons une liste des acronymes utilisés dans les expériences.

4.4.1 Réglage des paramètres

Dans notre expérimentation, les paramètres suivants sont utilisés : le temps d’exécution des
algorithmes est fixé à 10 minites. Ensuite, pour la procédure GRP, nous avons : Kg égal au
minimum entre le nombre de véhicules utilisés dans la solution courante et 10. En outre, pour
la méthode TS, la taille de la structure du voisinage est fixée à 30, la taille de la liste Tabou est
fixée à 20.

4.4.2 La procédure de génération de jeu de données

Pendant les étapes de VSC2015, trois instances de test ont été utilisés par le jury. Au début,
deux instances publiques de présélection ont été fournies aux participants, puis une instance
privée a été ajoutée après l’étape de qualification. Enfin, une autre instance privée est utilisée,
conjointement avec les instances utilisées précédemment, pour déterminer les vainqueurs. En
effet, les deux instances publiques de présélection ont la même configuration de réseau, à savoir
la même flotte de véhicules, les mêmes matrices de temps et de distance, etc. La différence est

73
 4.4. Expérimentation

Tableau 4.2: La contribution de chaque composant de TS

TS-OP TS-OP-RP TS-OP-RP-RX TS-FULL
inst coût gap coût gap coût gap coût gap meilleur
A1 1440170.57 41.03% 927296.91 8.41% 849322.0 0.0% 857870.64 1.0% 849322.0
A2 1404235.88 39.59% 890022.54 4.69% 858722.5 1.21% 848317.34 0.0% 848317.34
A3 1379994.22 39.26% 899990.92 6.86% 845306.74 0.83% 838253.64 0.0% 838253.64
A4 1362559.54 38.07% 898092.6 6.04% 843886.51 0.0% 845698.37 0.21% 843886.51
A5 1039446.18 38.45% 675239.71 5.25% 640365.32 0.09% 639782.74 0.0% 639782.74
A6 1021703.16 39.67% 644601.8 4.38% 616365.55 0.0% 622508.12 0.99% 616365.55
A7 1256095.52 42.43% 785575.66 7.96% 739019.34 2.16% 723079.2 0.0% 723079.2
A8 1112382.04 39.79% 717636.96 6.68% 671588.67 0.28% 669724.7 0.0% 669724.7
A9 737488.41 25.97% 593819.05 8.06% 545969.09 0.0% 551457.25 1.0% 545969.09
A10 597730.7 26.02% 454828.34 2.77% 444545.1 0.52% 442228.54 0.0% 442228.54
A11 670116.73 24.04% 557675.43 8.72% 513797.31 0.92% 509050.33 0.0% 509050.33
A12 884113.17 46.9% 591969.19 20.69% 469492.74 0.0% 471524.27 0.43% 469492.74
B1 2450523.4 44.54% 2006697.1 32.28% 1359019.84 0.0% 1382659.42 1.71% 1359019.84
B2 2542153.92 48.06% 1979996.65 33.32% 1348057.02 2.06% 1320335.68 0.0% 1320335.68
B3 2479758.71 45.2% 1985983.38 31.57% 1375628.22 1.21% 1358917.61 0.0% 1358917.61
B4 2621523.55 47.86% 2083452.23 34.4% 1380040.08 0.96% 1366801.39 0.0% 1366801.39
B5 2080947.86 46.34% 1600260.07 30.22% 1117823.43 0.1% 1116693.7 0.0% 1116693.7
B6 1863304.87 46.14% 1615243.83 37.87% 1017803.39 1.4% 1003511.98 0.0% 1003511.98
B7 1890909.68 43.16% 1731545.34 37.93% 1074767.6 0.0% 1087502.4 1.17% 1074767.6
B8 1717898.74 43.05% 1334916.28 26.71% 1024945.7 4.54% 978376.75 0.0% 978376.75
B9 968812.82 38.14% 751543.01 20.26% 599307.36 0.0% 602149.2 0.47% 599307.36
B10 922927.08 39.25% 687132.25 18.4% 560707.0 0.0% 563001.24 0.41% 560707.0
B11 1333861.18 46.36% 1104643.8 35.23% 736637.2 2.87% 715512.33 0.0% 715512.33
B12 1095074.69 41.59% 876721.14 27.04% 640996.81 0.21% 639636.91 0.0% 639636.91
moyenne 40.45 % 18.99 % 0.81 % 0.31 %

seulement dans le nombre de passagers dans les arrêts de bus. En outre, les instances privées
ont un autre réseau, qui est diffèrent de celui des instances publiques. Donc, sur la base de ces
deux configurations, nous générons pour chaque réseau 12 instances en variant le nombre de
passagers dans chaque arrêt de bus. Tout d’abord, nous appelons le premier réseau par A et le
second par B. Par la suite, les instances de chaque réseau sont divisées en trois catégories 1,
2 et 3, et chaque catégorie dispose de 4 instances. Dans les instances de catégorie 1, tous les
arrêts de bus contiennent des passagers, et le nombre de passagers dans chaque arrêt est choisi
aléatoirement à partir de l’ensemble {1, 2, 3, 4} (en nous basant toujours nous basons sur la
méthode de génération du jury de VSC2015). Pour la catégorie 2, le pourcentage des arrêts de
bus qui ont des passagers est égal approximativement à 75%. Le nombre de passagers dans ces
arrêts est choisi aléatoirement à partir de l’ensemble {1, 2, 3, 4} et le nombre de passagers dans
les autres arrêts est égal à 0. Ainsi, nous utilisons la même méthode pour la catégorie 3, mais le
pourcentage des arrêts qui possèdent des passagers est égal approximativement à 40%. Au total,
nous obtenons 24 instances (8 petites, 8 moyennes et 8 grandes instances).

4.4.3 Les résultats de TS

Dans le tableau 4.2, nous montrons les résultats de TS-OP, TS-OP-RP, TS-OP-RP-RX et TS-
FULL. Nous exécutons chaque méthode 10 fois et nous présentons la meilleure solution obtenue.
La première colonne indique le nom de l’instance, puis pour chaque méthode, nous présentons
la valeur de la meilleure solution obtenue et le pourcentage du gap entre cette solution et la
meilleure solution trouvée par toutes les méthodes. Le temps de calcul est fixé à 10 minutes (soit
600 secondes) pour une seule exécution sur chaque instance, en gardant la même valeur fixée par
le jury de VSC2015.
A partir du tableau 4.2, on peut facilement constater l’importance et la contribution de

74
 4.4. Expérimentation

Tableau 4.3: TS Vs. GRASP Vs. GRASP-LP

TS GRASP GRASP-LP
Inst coût m-gap coût m-gap coût m-gap
A1 857870.64 02.1% 871199.33 02.05% 844280.79 04.5%
A2 848317.34 02.56% 866863.58 01.73% 859915.94 01.92%
A3 838253.64 01.9% 844017.15 01.7% 851466.3 01.07%
A4 845698.37 01.92% 851182.62 01.61% 839531.07 02.41%
A5 639782.74 02.26% 644979.09 01.84% 648085.96 01.51%
A6 622508.12 01.35% 621739.32 01.65% 623912.75 01.32%
A7 723079.2 02.35% 727536.41 01.6% 721780.68 02.38%
A8 669724.7 02.71% 683662.32 01.2% 680075.24 02.32%
A9 551457.25 01.7% 547694.45 02.62% 545857.19 01.92%
A10 442228.54 00.9% 442677.86 00.51% 440685.38 01.26%
A11 509050.33 01.01% 512539.93 00.85% 510144.63 00.94%
A12 471524.27 02.16% 474265.55 00.71% 472394.24 01.33%
B1 1382659.42 02.03% 1392157.41 02.8% 1397837.54 01.94%
B2 1320335.68 04.31% 1348925.74 03.97% 1351861.22 03.58%
B3 1358917.61 05.11% 1374003.66 04.74% 1383143.96 02.96%
B4 1366801.39 03.97% 1428376.87 02.55% 1417691.36 02.99%
B5 1116693.7 02.55% 1117308.25 03.34% 1121762.38 03.07%
B6 1003511.98 04.47% 1025229.82 02.94% 1015944.32 02.38%
B7 1087502.4 05.07% 1095053.35 04.4% 1102104.26 03.45%
B8 978376.75 04.75% 1007798.72 02.84% 1010840.14 02.19%
B9 602149.2 03.42% 599154.77 01.61% 598572.47 01.67%
B10 563001.24 02.32% 567894.57 01.1% 566122.36 01.23%
B11 715512.34 04.04% 717795.67 03.74% 729532.87 01.82%
B12 639636.91 04.35% 651911.74 02.63% 651905.84 03.9%
Moyenne 839774.74 02.89% 850582.01 02.28% 849393.70 02.25%

chaque composante de la TS. D’abord, la procédure de réparation est la composante la plus

efficace de la TS et son utilisation améliore, en moyenne, de 21.46% la qualité de la solution,
parce que cette procédure réduit considérablement le coût du transport des taxis en recherchant,
pour chaque taxi, le meilleur point de transfert. En outre, les opérateurs infaisables avec le
mécanisme de relaxation contribuent pour, en moyenne, 18.18% dans la qualité de la solution.
Cette caractéristique améliore la convergence et permet de mieux explorer l’espace de recherche.
Enfin, grâce à l’utilisation des opérateurs glouton-randomisés, nous pouvons améliorer la qualité
de la solution avec un pourcentage de 0.50%. En effet, l’utilisation de ces opérateurs obéit à deux
raisons : la première est d’assurer la diversification. Le seconde est : la sélection de la meilleure
position d’insertion pour une solution de type Ba ne conduit pas nécessairement à une meilleure
solution Am, et en randomisant cet opérateur, nous avons plus de chance d’avoir une meilleure
solution.

75
 4.4. Expérimentation

4.4.4 La comparaison entre TS, GRASP et GRASP-LP

Dans le tableau 4.3, nous présentons une comparaison entre les méthodes TS, GRASP et GRASP-
LP. Dans cette comparaison, nous nous intéressons à deux critères : l’efficacité de l’algorithme
exprimé par la qualité de la meilleure solution obtenue, et la stabilité de la méthode en regardant
le pourcentage du gap entre la moyenne de 10 exécutions et la meilleure solution pour chaque
instance (m-gap).
Tout d’abord, en comparant TS au GRASP, dans 23 instances, la méthode TS est plus efficace
que la méthode GRASP, elle peut trouver de meilleures solutions que la méthode GRASP avec
un pourcentage moyen de 1.27%. Cependant, la méthode GRASP se montre plus stable que la
TS, parce que son m-gap est inférieur à celle de TS, avec un pourcentage moyen de 0.61%.
Deuxièmement, en comparant TS au GRASP-LP, bien que la méthode TS est plus efficace
que la méthode GRASP-LP avec un pourcentage moyen de 1.13% et elle donne de meilleures
solutions dans 18 instances, la méthode GRASP-LP se montre plus stable que TS, et elle a m-
gap plus faible que la TS, avec un pourcentage moyen de 0.64%. Enfin, nous constatons que la
méthode GRASP-LP est plus efficace et plus stable que la méthode GRASP.

4.4.5 La méthode GRASP-LP sur les instances de VRP et d’OVRP

A notre connaissance, dans la littérature du VRP, il n’existe pas de variante (avec ou sans jeu de
donnée) similaire ou relativement proche au problème CTSSP traité dans ce chapitre. Donc, afin
de valider nos approches proposées avec la littérature, nous exécutons la méthode GRASP-LP,
qui représente le bon compromis entre la stabilité et l’efficacité, sur deux jeux de données, à
savoir celui de Christofides et al. (1979) [19] pour le VRP et celui de Li et al. (2007) [69] pour
l’OVRP. Dans les tableaux 4.4 et 4.5, nous présentons les résultats de la méthode GRASP-LP.
Pour chaque tableau, la première colonne indique le nom de l’instance, la deuxième et la troisième
colonne présentent la solution obtenue par la GRASP-LP et le pourcentage du gap entre cette
solution et la meilleure solution connue respectivement. Enfin, la dernière colonne indique la
meilleure solution connue pour chaque instance.

[Link] La méthode GRASP-LP sur les instances de VRP

Pour le VRP, nous utilisons les instances de Christofides et al. (1979) [19] et nous comparons
nos résultats avec les solutions optimales et les meilleures solutions connues, prélevées de Uchoa
et al. (2014) [101]. Le temps d’exécution de GRASP-LP a été fixé à 10 minutes (600 secondes)
pour chaque instance.
Comme il est montré dans le tableau 4.4, d’abord, notre approche proposée a un gap très
faible de 0.74% (en moyenne) par rapport aux meilleures solutions connues. En plus, la méth-
ode GRASP-LP fonctionne bien et trouve les meilleures solutions connues pour 6 parmi les 14
instances. En effet, les meilleures solutions connues ont été trouvées par des méthodes de haut
niveau proposées durant les trois dernières décennies et ces méthodes ont été développées spéci-
fiquement pour résoudre ce problème [65]. Par conséquent, malgré que la méthode GRASP-LP
n’est pas développée spécifiquement pour résoudre ce problème, elle a pu trouver des solutions
avec un gap moyen de seulement 0.74% au-dessus des meilleures solutions connues, ce qui explique
clairement son efficacité.

76
 4.5. Conclusion

Tableau 4.4: Les résultats de GRASP-LP sur les instances de VRP

GRASP-LP
Inst coût gap BKS
C1 524.61 0.00 % 524.61∗
C2 838.20 00.35% 835.26∗
C3 828.34 00.27% 826.14∗
C4 1045.70 01.65% 1028.42∗
C5 1317.35 01.98% 1291.29∗
C6 555.43 0.00 % 555.43
C7 909.68 0.00 % 909.68
C8 865.95 0.00 % 865.94
C9 1168.50 00.51% 1162.55
C10 1414.55 01.32% 1395.85
C11 1072.90 02.87% 1042.11∗
C12 819.56 0.00 % 819.56∗
C13 1562.85 01.39% 1541.14
C14 866.37 0.00 % 866.37
moyenne 0.74 %

[Link] La méthode GRASP-LP sur les instances d’OVRP

Pour l’OVRP, nous utilisons deux jeux de test standard [106], le premier a été dérivé et adapté
du jeu de donnée de Christofides et al. (1979) [19] pour le VRP. Le second est un jeu de test avec
des instances de grande taille qui a été proposé par Li et al. (2007) [69]. Pour le premier jeu de
donnée, le temps de calcul de GRASP-LP a été fixé à 10 minutes, contrairement au second, qui
à cause de la grande taille des instances, le temps de calcul a été fixé selon la taille de l’instance,
à savoir cus-nbr×3 minutes. Dont cus-nbr est le nombre de clients dans l’instance.
D’après le tableau 4.5, la méthode GRASP-LP est en mesure de trouver des solutions de
haute qualité, même pour les instances de grande taille. Tout d’abord, des meilleures solutions
connues ont été trouvées pour 2 instances. En outre, bien que les gaps de 3 instances soient
supérieur de 2%, la moyenne des gaps est égale seulement à 01.13%. Comme le cas de VRP, tous
ces résultats expliquent l’efficacité de l’approche proposée.

4.5 Conclusion
Dans ce chapitre nous avons présenté une contribution au VSC2015 dont une nouvelle variante du
VRP appelée CTSSP (Coach Trip with Shuttle Service Problem, CTSSP) a été définie comme
étant le sujet de ce challenge. Pour résoudre le problème CTSSP, Nous avons proposé deux
algorithmes, une recherche Tabou (TS) et une heuristique de type GRASP (Greedy Randomized
Adaptive Search Procédure (GRASP)). La TS a été soumis au cours des étapes de qualification
du VSC2015 et elle a été déclarée comme vainqueur du deuxième prix parmi 16 participants. En
outre, pour encore tester et évaluer les algorithmes proposés, nous avons généré un nouveau jeu
de données en nous basant sur les instances utilisés dans VSC2015. D’abord, la méthode TS a été
expérimentée en montrant la contribution de chaque composant dans la méthode. Ensuite, la TS
a été comparée avec les méthodes GRASP et GRASP-LP. Bien que, ces méthodes ont été plus
stable que TS, la TS a été en mesure de trouver de meilleures solutions. Enfin, pour valider nos
approches proposées avec la littérature, la méthode GRASP-LP a été exécutée sur des instances
de VRP et d’OVRP. Les bons résultats obtenus ont montré l’efficacité de la méthode proposée.

77
 4.5. Conclusion

Tableau 4.5: Les résultats de GRASP-LP sur les instances d’OVRP

GRASP-LP
Inst coût gap BKS
C1 412.96 0.00 % 412.96
C2 564.06 0.00 % 564.06
C3 639.74 00.08% 639.26
C4 737.14 00.54% 733.13
C5 872.95 00.45% 869.00
O1 6149.77 02.62% 5988.35
O2 4560.87 00.30% 4549.46
O3 7822.19 01.63% 7731.00
O4 7263.68 00.484% 7251.30
O5 9334.9643 01.96% 9152.47
O6 9893.9921 01.01% 9793.72
O7 10584.73 02.24% 10347.70
O8 12842.044 03.35% 12412.26
moyenne 01.13%

78
 Conclusion générale

La conception des systèmes de transport et de distribution est l’une des tâches les plus im-
portantes dans la chaîne logistique. En effet, pour les entreprises cette tâche est devenue in-
dispensable dont le but est d’améliorer sa productivité, sa performance et, par conséquent, sa
compétitivité. Cependant, cette conception nécessite d’importants efforts afin de modéliser et de
résoudre de nombreux problèmes liés à ces systèmes. Dans le cadre de cette thèse, nous avons
proposé et validé des méthodes pour résoudre trois problèmes liés à la logistique de transport et
de distribution, à savoir le problème de localisation-routage à grande échelle avec contrainte de
capacité, le problème d’élaboration des tournées avec gestion de stock multi-véhicules et multi-
produits et une variante du problème d’élaboration des tournées qui représente un cas réel de
transport de passagers.

Dans le premier chapitre, nous avons présenté un état de l’art sur les chaînes logistiques en
nous concentrant sur les problèmes d’optimisation de base qui constituent le noyau des prob-
lèmes étudiés dans cette thèse. Nous avons décrit en détail ces problèmes liés principalement à
la logistique de distribution et de transport, à savoir le problème de localisation, le problème
d’élaboration des tournées de véhicules et le problème de gestion de stock. En outre, nous avons
présenté les deux problèmes résultants en intégrant deux problèmes de base, à savoir le problème
de localisation-routage et le problème de routage avec gestion de stock. Enfin, nous avons donné
un aperçu sur les outils d’optimisation des chaînes logistiques.

Notre première contribution a été présentée dans le deuxième chapitre où une nouvelle heuris-
tique en deux phases pour le problème de localisation-routage avec contrainte de capacité a été
introduite. Notre objectif a été de développer des algorithmes qui sont en mesure de trouver des
solutions de bonne qualité dans un temps de calcul réduit pour des instances de grande taille.
L’algorithme proposé combine la recherche Tabou et le recuit simulé. La recherche Tabou est
utilisée pour la résolution du sous-problème de routage et le recuit simulé est utilisé pour résoudre
le sous-problème de localisation. Les résultats de notre algorithme ont été comparés, avec succès,
avec les résultats de deux algorithmes de la littérature en utilisant un jeu de données standard.
L’expérimentation a montré que notre algorithme est plus performant que ces deux méthodes
dans la mesure où des meilleures solutions pour 16 instances (à partir des 27 instances de jeu
d’essai) ont été trouvées. En outre, l’expérimentation a montré que, grâce au recuit simulé, le
point-clé du succès de la méthode a été le choix des bons dépôts dans la deuxième phase.

Notre deuxième contribution a été présentée dans le troisième chapitre où nous avons abordé
le problème de l’élaboration des tournées avec gestion de stock multi-périodes multi-véhicules

79
multi-produits en utilisant une heuristique basée sur la métaheuristique GRASP (appelée GBH).
En effet, la GBH se compose de deux grandes phases. La première est une heuristique gloutonne
randomisée qui construit une solution réalisable de bonne qualité en cherchant un compromis
entre le coût de routage et le coût de stockage. La deuxième phase est une recherche locale
utilisée pour améliorer la solution obtenue dans la phase précédente. En plus, comme recherche
locale, nous avons utilisé la recherche Tabou. D’abord, la performance du GBH a été testée sur
le jeu de données standard de Coelho et Laporte (2013b) [22] avec 135 instances et les résultats
obtenus ont été comparés avec les résultats de leur algorithme de type Branch-&-Cut (B&C).
Les résultats ont été satisfaisants et la GBH a été plus performante que le B&C. Nous avons
obtenu 40 nouvelles meilleures solutions pour des instances de grande taille. En plus, le temps de
calcul du GBH a été largement inférieur par rapport au temps de calcul du B&C. En outre, afin
de montrer encore l’efficacité de GBH, elle a été adaptée pour résoudre la variante de MMIRP
abordée dans Cordeau et al. (2015) [27] et ses résultats ont été comparés, avec succès, avec les
résultats de l’heuristique de décomposition et de B&C. Les résultats ont montré que, la GBH est
meilleure que les deux algorithmes proposés.

Dans le quatrième chapitre, nous avons présenté une contribution au VSC2015 (Verolog Solver
Challenge 2015) dont une nouvelle variante du VRP appelée CTSSP (Coach Trip with Shuttle
Service Problem, CTSSP) a été définie comme étant le sujet de ce challenge. En fait, nous avons
proposé deux algorithmes de résolution : une recherche Tabou, avec laquelle nous avons participé
au VSC2015, et une heuristique de type GRASP. Pour évaluer et tester les algorithmes proposés,
nous avons généré un nouveau jeu de données en se basant sur les instances (qui représentent des
cas réel) utilisées dans VSC2015. D’abord, la TS a été expérimentée en montrant la contribution
de chaque composant de la méthode. Ensuite, la TS a été comparée avec la méthode GRASP.
Enfin, pour valider nos approches proposées avec la littérature, la méthode GRASP a été exécutée
sur des instances de VRP et de OVRP. Bien que, la méthode GRASP a été développée pour une
variante qui est différente du VRP et d’OVRP (en comparant les caractéristiques de CTSSP avec
les caractéristiques du VRP et d’OVRP), les bons résultats trouvés ont montré son efficacité. En
plus, la TS a été déclarée vainqueur du deuxième prix parmi 16 participants au VSC2015.

Enfin, comme perspectives nous pouvons proposer:

1. Des méthodes pour résoudre le problème localisation-routage avec gestion de stock en

combinant les caractéristiques des deux problèmes étudiés dans les chapitres deux et trois.

2. Une autre méthode pour le problème de localisation-routage étudié dans le chapitre deux,
en améliorant la phase d’élaboration des tournées dans l’algorithme proposé.

3. D’étudier d’autres variantes du problème de localisation-routage comme le problème de

localisation-routage avec distribution partagée.

4. D’autres heuristiques pour le problème de routage avec gestion de stock étudié dans le
troisième chapitre.

5. D’étudier d’autres variantes du problème de routage avec gestion de stock multi-véhicules

et multi-produits en considérant d’autres caractéristiques importantes comme le cas où les
produits sont périssables.

80
6. D’autres heuristiques pour le problème étudié dans le chapitre quatre, comme par exemple
la recherche à grand voisinage (en anglais, Large Neighborhood Search)

7. De combiner la méthode de recherche Tabou proposée dans le chapitre quatre avec une
méthode évolutionnaire afin d’améliorer les résultats obtenus.

81
 Bibliographie

[1] Clrlib. [Link]

[2] T. F Abdelmaguid. Heuristic approaches for the integrated inventory distribution problem.
PhD thesis, University of Southern California, Los Angeles, USA, 2004.

[3] T. F Abdelmaguid and M. M Dessouky. A genetic algorithm approach to the inte-

grated inventory-distribution problem. International Journal of Production Research,
44(21):4445–4464, 2006.

[4] Y. Adulyasak, J. F Cordeau, and R. Jans. Formulations and branch-and-cut algorithms

for multi-vehicle production and inventory routing problems. Technical report, GERAD,
Ref. G-2012-14, Canada, 2012.

[5] Z. Akca, R. T Berger, and T. K Ralphs. Operations Research and Cyber-Infrastructure, vol-
ume 47, chapter A branch-and-price algorithm for combined location and routing problems
under capacity restrictions, pages 309–330. Springer, 2009.

[6] A. C F Alvim and E. D Taillard. POPMUSIC for the world location-routing problem.
EURO Journal on Transportation and Logistics, 2(3):231–254, 2013.

[7] C. Archetti, L. Bertazzi, A. Hertz, and M. G Speranza. A hybrid heuristic for an inventory
routing problem. INFORMS Journal on Computing, 24(1):101–116, 2012.

[8] C. Archetti, L. Bertazzi, G. Laporte, and M. G Speranza. A branch-and-cut algorithm

for a vendor-managed inventory-routing problem. Transportation Science, 41(3):382–391,
2007.

[9] C. Archetti, N. Bianchessi, S. Irnich, and M. G Speranza. Formulations for an inventory

routing problem. International Transactions in Operational Research, 21(3):353–374, 2014.

[10] K. Bahloul. Optimisation combinée des coûts de transport et de stockage dans un réseau
logistique dyadique, multi-produits avec demande probabiliste. Thèse de doctorat, INSA
de Lyon, France, 2011.

[11] S. Basu and D. Ghosh. A review of the tabu search literature on traveling salesman
problems. Technical report, No. 2008-10-01, Indian Institute of Management Ahmedabad,
India, 2008.

[12] S. Basu, M. Sharma, and P. S. Ghosh. Metaheuristic applications on discrete facility

location problems: A survey. OPSEARCH, 52(3):530–561, 2015.

82
[13] A. Bekrar. Résolution du problème de placement en deux dimensions : heuristiques, bornes
inférieures et méthodes exactes. Thèse de doctorat, Université de Technologie de Troyes,
France, 2007.
[14] J. M Belenguer, E. Benavent, C. Prins, C. Prodhon, and R. Wolfler Calvo. A branch-
and-cut method for the capacitated location-routing problem. Computers and Operations
Research, 38(6):931–941, 2011.
[15] L. Bouhafs, A. Hajjam, and A. Koukam. Knowledge-Based Intelligent Information and
Engineering Systems, volume 4251, chapter A combination of simulated annealing and ant
colony system for the capacitated location-routing problem, pages 409–416. Springer, 2006.
[16] A. M Campbell and M. W P Savelsbergh. A decomposition approach for the inventory-
routing problem. Transportation Science, 38(4):488–502, 2004.
[17] Y. Chan and S. F Baker. The multiple depot, multiple traveling salesmen facility-location
problem: Vehicle range, service frequency, and heuristic implementations. Mathematical
and Computer Modelling, 41(8 - 9):1035–1053, 2005.
[18] C. H Chen and C. J Ting. A hybrid lagrangian heuristic/simulated annealing algorithm
for the multi-depot location routing problem. Journal of the Eastern Asia Society for
Transportation Studies, 7:961–974, 2007.
[19] N. Christofides, A. Mingozzi, and P. Toth. Combinatorial Optimization, chapter The vehicle
routing problem, pages 315–338. Wiley, 1979.
[20] L. C Coelho, J. F Cordeau, and G. Laporte. Consistency in multi-vehicle inventory-routing.
Transportation research part c: emerging technologies, 24:270–287, 2012.
[21] L. C Coelho, J. F Cordeau, and G. Laporte. The inventory-routing problem with trans-
shipment. Computers & Operations Research, 39(11):2537–2548, 2012.
[22] L. C Coelho and G. Laporte. A branch-and-cut algorithm for the multi-product multi-
vehicle inventory-routing problem. International Journal of Production Research, 51(23-
24):7156–7169, 2013.
[23] L. C Coelho and G. Laporte. The exact solution of several classes of inventory-routing
problems. Computers & operations research, 40(2):558–565, 2013.
[24] L. C Coelho and G. Laporte. Thirty years of inventory-routing. Transportation Science,
48(1):001–019, 2014.
[25] C. Contardo. Models and algorithms for the capacitated location-routing problem. PhD
thesis, University of Montreal, Canada, 2011.
[26] C. Contardo, J. F Cordeau, and B. Gendron. A GRASP + ILP-based metaheuristic for
the capacitated location-routing problem. Journal of Heuristics, 20(1):1–38, 2014.
[27] J. F Cordeau, D. Laganà, R. Musmanno, and F. Vocaturo. A decomposition-based heuristic
for the multiple-product inventory-routing problem. Computers & Operations Research,
55:153–166, 2015.
[28] J. F Cordeau and G. Laporte. A tabu search heuristic for the static multi-vehicle dial-a-ride
problem. Transportation Research Part B, 37(06):579–594, 2003.

83
[29] G. B Dantzig and J. H Ramser. The truck dispatching problem. Management Sciences,
6(1):80–91, 1959.
[30] M. S Daskin, L. V Snyder, and R. T Berger. Facility Location in Supply Chain Design.
Working Paper No. 03-010, Department of Industrial Engineering and Management Sci-
ences, Northwestern University, Evanston, Illinois, USA, 2003.
[31] H. Derbel, B. Jarboui, H. Chabchoub, S. Hanafi, and N. Mladenovic. A variable neighbor-
hood search for the capacitated location-routing problem. In LOGISTIQUA, 4th interna-
tional conference on logistics, pages 514–519, 2011.
[32] G. Desaulniers, J. G Rakke, and L. C Coelho. A branch-price-and-cut algorithm for
the inventory-routing problem. Technical report, GERAD, Technical report G-2014-12,
Canada, 2014.
[33] K. Doerner, W. Heid, and D. Vigo. Verolog solver challenge 2015: prob-
lem description. [Link]
verolog-solver-challenge-2015, 2015.
[34] M. Drexl and M. Schneider. A survey of location-routing problems. Technical report, No.
LM-2013-03, Johannes Gutenberg University, Mainz, 2013.
[35] I. Harbaoui Dridi. Optimisation heuristique pour la résolution du m-PDPTW statique
et dynamique. Thèse de doctorat, l’école Centrale de Lille, France et l’école Nationale
d’Ingénieurs de Tunis, Tunisie, 2010.
[36] C. Duhamel, P. Lacomme, C. Prins, and C. Prodhon. A GRASP × ELS approach for the
capacitated location routing problem. Computers and Operations Research, 37(11):1912–
1923, 2010.
[37] J. W Escobar, R. Linfati, and P. Toth. A two-phase hybrid heuristic algorithm for the
capacitated location-routing problem. Computers and Operations Research, 40(1):70–79,
2013.
[38] E. A Feigenbaum and j. Feldman. Computers and thought. McGraw-Hill, Inc. New York,
NY, USA, 1963.
[39] T. A Feo and M. G C Resende. Greedy randomized adaptive search procedures. Journal
of Global Optimization, 6(2):109–133, 1995.
[40] F. Galasso. Aide à la planification dans les chaînes logistiques en présence de demande
flexible. Thèse de doctorat, l’Institut National Polytechnique de Toulouse, France, 2007.
[41] R. Ganeshan and T. P Harrison. An introduction to supply chain management. Department
of Management Sciences and Information Systems, Penn State University, University Park,
PA, USA, 1995.
[42] A. Gherboudj. Méthodes de résolution de problèmes difficiles académiques. Thèse de doc-
torat, Université de Constantine 2, Algérie, 2013.
[43] F. Glover. Tabu search - part I. ORSA Journal on Computing, 1(3):190–206, 1989.
[44] F. Glover, E. Taillard, and D. D Werra. A user’s guide to tabu search. Annals of Operations
Research, 41(1):3–28, 1993.

84
[45] M. G Granada and C. W Silva. Inventory location routing problem: A column generation
approach. In Proceedings of the International Conference on Industrial Engineering and
Operations Management, Istanbul, Turkey, pages 482–491, 2012.

[46] E. Grellier. Optimisation des tournées de véhicules dans le cadre de la logistique inverse
: modélisation et résolution par des méthodes hybrides. Thèse de doctorat, Université de
Nantes, France, 2008.

[47] O. Guemri and A. Bekrar. An improved tabu search heuristic algorithm for the coach
trip with shuttle service problem. In 4th Meeting of the EURO Working Group on Vehicle
Routing and Logistics Optimization, Vienne. Invited talk as finalist of the VeRoLog Solver
challenge, 2015.

[48] O. Guemri, A. Bekrar, B. Beldjilali, and D. Trentesaux. GRASP-based heuristic algorithm

for the multi-product multi-vehicle inventory routing problem. 4OR: quarterly journal of
Operations Research, 14(4):377–404, 2016.

[49] O. Guemri, B. Beldjilali, A. Bekrar, and G. Belalem. Two-stage heuristic algorithm for the
large-scale capacitated location routing problem. International Journal of Mathematical
Modeling and Numerical Optimizations, 7(1):97–119, 2016.

[50] A. Hammami. Modélisation technico-économique d’une chaîne logistique dans une en-
treprise réseau. Thèse de doctorat en cotutelle, l’ école Nationale Supérieure des Mines de
Saint-Etienne, France et l’Université de Laval, Canada, 2003.

[51] J. K Hao, P. Galinier, and M. Habib. Métaheuristiques pour l’optimisation combinatoire

et l’affectation sous contraintes. Revue d’Intelligence Artificielle, 13(2):283–324, 1999.

[52] T. Harks, F. G Konig, and J. Matuschke. Approximation algorithms for capacitated loca-
tion routing. Transportation Science, 47(1):3–22, 2013.

[53] K. Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic.

European Journal of Operations Research, 126(1):106–130, 2000.

[54] M. H Hugos. Essentials of supply chain management. John Wiley and Sons, 2003.

[55] S. Ben Ismail, F. Legras, and G. Coppin. Synthèse du problème de routage de véhicules.
Technical report, Collection des rapports de recherche de Télécom Bretagne, RR-2011-03-
LUSSI, France, 2011.

[56] M. S Jabal-Ameli, M. B Aryanezhad, and N. Ghaffari-Nasab. A variable neighborhood

descent based heuristic to solve the capacitated location-routing problem. International
Journal of Industrial Engineering Computations, 2(1):141–154, 2011.

[57] A. A Javid and N. Azad. Incorporating location, routing and inventory decisions in sup-
ply chain network design. Transportation Research Part E: Logistics and Transportation
Review, 46(5):582–597, 2010.

[58] A. Jokar and R. Sahraeian. An iterative two phase search based heuristic to solve the
capacitated location-routing problem. Australian Journal of Basic and Applied Sciences,
5(12):1613–1621, 2011.

85
[59] A. Jokar and R. Sahraeian. A heuristic based approach to solve a capacitated location-
routing problem. Journal of Management and Sustainability, 2(2):219–226, 2012.

[60] M. A Arostegui Jr., S. N Kadipasaoglu, and B. M Khumawala. An empirical comparison

of tabu search, simulated annealing, and genetic algorithms for facilities location problems.
International Journal of Production Economics, 103(2):742–754, 2006.

[61] R. Kammarti. Approches évolutionnistes pour la résolution du 1-PDPTW statique et

dynamique. Thèse de doctorat, l’Ecole Centrale de Lille, France, 2006.

[62] S. Kande. Etude et résolution de problèmes de planification dans des réseaux logistiques
multi-échelons. Thèse de doctorat, l’Université de Technologie de Troyes, France, 2015.

[63] S. kirkpatrick, C. D Gelatt, and P. N Vecchi. Optimization by simulated annealing. Science,

220(4598):671–680, 1983.

[64] O. Labarthe. Modélisation et simulation orientées agents de chaînes logistiques dans un

contexte de personnalisation de masse : modèles et cadre méthodologique. Thèse de doc-
torat en cotutelle, Université de Laval, Canada et Université Paul Cézanne Marseille,
France, 2006.

[65] G. Laporte. Fifty years of vehicle routing. Transportation Science, 43(4):408–416, 2009.

[66] A. Layeb, M. Ammi, and S. Chikhi. A GRASP algorithm based on new randomized
heuristic for vehicle routing problem. Journal of Computing and Information Technology,
21(1):35–46, 2013.

[67] H. L Lee and C. Billington. Material management in decentralized supply chain. Operations
Research, 41(5):835–847, 1993.

[68] A. Lemouari and O. Guemri. A two-phase scheduling method combined to the tabu search
for the DARP. International Journal of Applied Metaheuristic Computing, 5(2):1–21, 2014.

[69] F. Li, B. Golden, and E. Wasil. The open vehicle routing problem: algorithms, large scale
test problems, and computational results. Computers & Operations Research, 34(10):2918–
2930, 2007.

[70] C. Mancel. Modélisation et résolution de problèmes d’optimisation combinatoire issus

d’applications spatiales. Thèse de doctorat, INSA de Toulouse, France, 2004.

[71] Y. Marinakis and M. Marinaki. A bilevel genetic algorithm for a real life location routing
problem. International Journal of Logistics Research and Applications, 11(1):49–65, 2008.

[72] Y. Marinakis and M. Marinaki. A particle swarm optimization algorithm with path relink-
ing for the location routing problem. Journal of Mathematical Modelling and Algorithms,
7(1):59–78, 2008.

[73] J. T Mentzer, W. Dewitt, J. S Keebler, S. Min, N. W Nix, C. D Smith, and Z. G Zacharia.

Defining supply chain management. Journal of business logistics, 22(2):1–25, 2001.

[74] A. Mjirda. Recherche à voisinage variable pour des problèmes de routage avec ou sans
gestion de stock. Thèse de doctorat, Université de Valenciennes et du Hainaut-Cambrésis,
France, 2014.

86
[75] A. Mjirda, B. Jarboui, R. Macedo, S. Hanafi, and N. Mladenovic. A two phase variable
neighborhood search for the multi-product inventory routing problem. Computers & Op-
erations Research, 52:291–299, 2014.

[76] N. H Moin, S. Salhi, and N. A B Aziz. An efficient hybrid genetic algorithm for the
multi-product multi-period inventory routing problem. International Journal of Production
Economics, 133(1):334–343, 2011.

[77] Z. Mouloua. Ordonnancements coopératifs pour les chaînes logistiques. Thèse de doctorat,
l’Institut National Polytechnique de Lorraine, France, 2007.

[78] G. Nagy and S. Salhi. Location-routing: Issues, models and methods. European Journal
of Operational Research, 177(2):649–672, 2007.

[79] I. H Osman and G. Laporte. Metaheuristics: A bibliography. Annals of Operations Re-

search, 63(5):511–623, 1996.

[80] J. Pons and P. Chevalier. La logistique intégrée. Hermes Science Publications, 1993.

[81] D. Popovic, M. Vidovic, and G. Radivojevic. Variable neighborhood search heuristic for the
inventory routing problem in fuel delivery. Expert Systems with Applications, 39(18):13390–
13398, 2012.

[82] C. Prins, C. Prodhon, A. Ruiz, P. Soriano, and R. Wolfler-Calvo. Solving the capaci-
tated location-routing problem by a cooperative lagrangian relaxation-granular tabu search
heuristic. Transportation Science, 41(4):470–483, 2007.

[83] C. Prins, C. Prodhon, and R. Wolfler-Calvo. Evolutionary computation in combinatorial

optimization, volume 3906, chapter A memetic algorithm with population management
(MA|PM) for the capacitated location-routing problem, pages 183–194. Springer Berlin
Heidelberg, 2006.

[84] C. Prins, C. Prodhon, and R. Wolfler-Calvo. Solving the capacitated location routing
problem by a GRASP complemented by a learning process and a path relinking. 4OR: A
Quarterly Journal of Operations Research, 4(3):221–238, 2006.

[85] C. Prodhon. Le problème de localisation-routage. Thèse de doctorat, Université de

Technologie de Troyes, France, 2006.

[86] C. Prodhon and C. Prins. A survey of recent research on location-routing problems. Eu-
ropean Journal of Operational Research, 238(1):01–17, 2014.

[87] M. Haj Rachid. Les problèmes de tournées de véhicules en planification industrielle :

classification et comparaison d’opérateurs évolutionnaires. Thèse de doctorat, Université
de Franche-Comté, France, 2010.

[88] S. Salhi and G. K Rand. The effect of ignoring routes when locating depots. European
Journal of Operational Research, 39(2):150–156, 1989.

[89] P. Schittekat, J. Kinable, K. Sorensen, M. Sevaux, F. Spieksma, and J. Springael. A

metaheuristic for the school bus routing problem with bus stop selection. European Journal
of Operational Research, 229(2):518–528, 2013.

87
 [90] P. Schittekat and K. Sorensen. Or practice-supporting 3PL decisions in the automotive in-
dustry by generating diverse solutions to a large-scale location-routing problem. Operations
Research, 57(5):1058–1067, 2009.
[91] J. M Segura. Localisation et affectation : application aux réseaux de contenus. Thèse de
doctorat, Université Pierre et Marie Curie (Paris 6), Paris, France, 2011.
[92] O. Solyali and H. Sural. A branch-and-cut algorithm using a strong formulation and an
a priori tour based heuristic for an inventory-routing problem. Transportation Science,
45(3):335–345, 2011.
[93] A. Stenger, M. Schneider, and S. Enz. A hybrid GRASP × VNS algorithm with effective
depot reduction mechanism for the capacitated location routing problem. Technical report,
No. 01/2011, IT-based Logistics, Goethe University Frankfurt, 2011.
[94] M. Sun. Solving the uncapacitated facility location problem using tabu search. Computers
& Operations Research, 33(9):2563–2589, 2006.
[95] E. Taillard. Parallel iterative search methods for vehicle routing problems. Networks,
23(8):661–673, 1993.
[96] G. A Tanonkou. Une approche par relaxation lagrangienne pour l’optimisation d’un réseau
de distribution : modèles stochastiques et fiables. Thèse de doctorat, Université Paul
Verlaine, Metz, France, 2007.
[97] R. Teigen and M. Barbuceanu. The Supply Chain Demonstrator. Enterprise Integration
Laboratory, University of Toronto, Canada, 1996.
[98] C. J Ting and C. H Chen. A multiple ant colony optimization algorithm for the capacitated
location routing problem. International Journal of Production Economics, 141(1):34–44,
2013.
[99] P. Toth and D. Vigo. The vehicle routing problem. Society for Industrial and Applied
Mathematics, Philadelphia, PA, USA, 2001.
[100] D. Tuzun and L. I Burke. A two-phase tabu search approach to the location routing
problem. European Journal of Operational Research, 116(1):87–99, 1999.
[101] E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, A. Subramanian, and T. Vidal. New benchmark
instances for the capacitated vehicle routing problem. Optimization Online: an eprint for
the optimization community, [Link]
[Link], 2014.
[102] P. Vallin. La logistique : modèles et méthodes du pilotage des flux. Economica, 2003.
[103] NEVEN WORKGROUP. Performance Indicators in Logistics. IFS Publications, Springer-
Verlag, 1989.
[104] V. F Yu, S. W Lin, W. Lee, and C. J Ting. A simulated annealing heuristic for the
capacitated location routing problem. Computers & Industrial Engineering, 58(2):288–
299, 2010.
[105] Y. Yu, H. Chen, and F. Chu. A new model and hybrid approach for large-scale inventory
routing problems. European Journal of Operational Research, 189(3):1022–1040, 2008.

88
[106] E. E Zachariadis and C. T Kiranoudis. An open vehicle routing problem metaheuristic for
examining wide solution neighborhoods. Computers & Operations Research, 37(4):712–723,
2010.

89
 Résumé
Dans le cadre de cette thèse nous présentons des algorithmes pour résoudre des
problèmes liés à la logistique de distribution et de transport. Premièrement, nous
développons un algorithme en deux phases pour résoudre le problème de localisation-
routage avec contrainte de capacité en utilisant la recherche Tabou et le recuit simulé.
Ensuite, nous traitons le problème d’élaboration de tournées avec gestion de stock
multi-périodes, multi-produits et multi-véhicules en proposant un algorithme (appelé
GBH) basé sur la métaheuristique GRASP (Greedy Randomized Adaptive Search
Procedure). Pour améliorer la méthode GRASP classique, nous utilisons la recherche
Tabou comme recherche locale dans le GBH. Dans notre troisième contribution, nous
développons deux algorithmes pour faire face à une nouvelle variante du problème
d’élaboration de tournées des véhicules appelée le problème de routage de navettes et
de taxis (Coach Trip with Shuttle Service Problem, CTSSP).Le premier algorithme est
une recherche Tabou et le second est une méthode GRASP. Les expériences montrent
que les algorithmes proposés et comparés avec succès avec plusieurs méthodes de la
littérature donnent de meilleurs résultats.

Mots-clés :

Optimisation combinatoire; Métaheuristiques; Recherche Tabou; GRASP; Recuit

simulé; Chaînes logistique; Problèmes de transport; Routage des véhicules;
Localisation-routage; Routage avec gestion de stock.