‫ﺍلجمهوﺭ ية ﺍلجزﺍئر ية ﺍلديمقرﺍطية ﺍلشعبية‬

République Algérienne Démocratique et Populaire

‫وﺯﺍﺭﺓ ﺍلتعليم ﺍلعالي و ﺍلبحث ﺍلعلمي‬
Ministère de l’Enseignement Supérieur et de la
Recherche Scientifique
‫ﺍﺍلمدﺭسة ﺍلوطنية ﺍلعليا للتكنولوجياﺕ ﺍلمتقدمة‬
École Nationale Supérieure des Technologies Avancées
Département Génie Logistique et Transport

Mémoire de fin d’étude En vue de l’obtention du diplôme

d’Ingénieur d’État
­ Filière ­
Ingénierie De la chaîne Logistique et du Transport ­
Spécialité ­
Ingénierie Des Transports
­ Thème ­
Optimisation de tournées de véhicules en présence
des contraintes temporelles de types fenêtres de
temps et délais :
Application au domaine de livraison agricole

Réalisé par :
BOULMERDJ Wassim
BOUSSAHOUL Haithem

Les membres du jury :

[Link] Nafissa Présidente : Maitre de conférence B
[Link] Zhor Promotrice : Maitre de conférence B
[Link] Chafik Examinateur : Maitre de conférence B

Alger, le 20/06/2025

Année universitaire 2024­2025

 Dédicace

Cette œuvre est dédiée à :

À mes chers parents : Monsieur mon père et Madame ma mère,
En reconnaissance de leur abnégation exemplaire, de leurs renoncements tacites, leur
confiance en mes capacités. Ce travail constitue l'aboutissement de leur accompagnement
bienveillant. Immense appréciation pour vous.

À mes chers membres de famille,

Mon frère Oussama et mes sœurs Chahrazed et Oumaima pour leur solidarité constante
et les liens fraternels indissolubles qui façonnent notre unité familiale.

À ma famille élargie et à mes proches,

Pour leurs encouragements soutenus et l'émulation qu'ils ont su insuffler tout au long de
mon parcours.

À mon binôme El-Haba,

Pour son investissement personnel et la synergie qui a caractérisé notre partenariat dans
l'élaboration de ce projet. Bravo, l'ami !
À tous ceux que j'aime et tous ceux qui m'aiment,
Je vous dédie ce travail en gage de ma profonde gratitude et de mon attachement sincère.

BOUSSAHOUL Haithem
 Dédicace

Je dédié ce travail à :

À mes grands parents

À mon père et ma mère bien aimés
Pour leur dévouement sans limite, leurs sacrifices silencieux, leur patience,
leur amour infini, et pour avoir toujours cru en moi même dans les
moments les plus incertains.
Ce travail est le fruit de leur foi et de leur présence constante.

À mes frères Imad, Chouaib et Abderrahim

Et à leurs épouses : Ahlem et Hafidha ,
ainsi qu’à ma chère petite Ilyne, rayon de lumière de la famille.

À mon oncle Lounis, que Dieu ait pitié de lui,

ainsi qu’à Sihem, Yakoub et Slimane.

À ma famille, mes proches

Pour leur amour, leurs encouragements et leur présence constante.

À mon binôme Haithem Le D

Pour sa collaboration, sa patience et son amitié.

À tous mes amis :

Anis, Oussama 315, Dhayaa, Abdou, Aymen, El Bedri, Ihab,
Youssef, Amine L'art, Djamal, Rayane, Dorindo, Fouad, Anis, Zaki et
Yacine
Pour les moments partagés, les rires et l’amitié sincère.

À ma promo 2025 ingénierie de chaîne logistique et transport

À tous ceux que j’aime.
Wassim Boulmerdj
 Remerciement

En tout premier lieu, nous remercions le bon Dieu, tout puissant, de

nous avoir donné la force pour avancer, ainsi que le courage pour
surmonter toutes les difficultés.
Nous exprimons nos sincères remerciements et notre profonde
gratitude à notre encadrante Mme. CHERGUI Zhor, pour ses
conseils précieux, sa patience et le temps qu'il nous a consacré tout
au long de ce projet.
Nos vifs remerciements vont également au PDG de l'entreprise
DJE-AGRO, M. DJEBABLIA Ihab, qui nous a permis d'intégrer la
structure et de mener à bien notre travail dans les meilleures
conditions.
Nous adressons aussi nos remerciements à l'ensemble des membres
du jury pour l'honneur qu'ils nous ont fait en acceptant d'évaluer
notre travail et pour leurs remarques enrichissantes.
Enfin, nous remercions chaleureusement toutes les personnes, de
près ou de loin, ayant contribué à la réalisation de ce travail.
Résumé

Résumé
Dans ce projet de fin d’étude, nous analysons l’optimisation de tournée de véhicules au
sein de l’entreprise DJE­AGRO, dont l’activité consiste à distribuer des produits avicoles
frais, à partir du dépôt central implanté dans la wilaya de Batna vers 38 clients répartis dans
cette localité ainsi qu’aux sept wilayas avoisinantes de l’Est algérien.
L’objectif principal s’articule sur l’optimisation des coûts de transport tout en assurant un
haut niveau de qualité de service à travers le respect des engagements temporels de livraison
ainsi que les quantités journalières commandées.
Ce système de distribution agricole repose sur une flotte hétérogène de véhicules de ca­
pacités distinctes, prenant en compte des contraintes de délais de livraison et de fenêtres
temporelles imposées par les clients.
Mots clés : Optimisation des tournées de véhicules, optimisation des coûts, optimisation
des distances, distribution agricole, fenêtres temporelles, flotte hétérogène.

Abstract
This final­year project analyzes vehicle route optimization in a company DJE­AGRO
whose activity consists of distributing fresh poultry products from the central depot located
in the Batna province to 38 clients located within the province and in seven neighboring
provinces of eastern Algeria.
The main objective is to optimize transportation costs while ensuring a high level of service
quality by meeting delivery time commitments and the daily ordered quantities.
This agricultural distribution system relies on a heterogeneous fleet of vehicles with dif­
ferent capacities, taking into account delivery deadlines and customer­defined time win­
dows.
Keywords : Vehicle routing optimization, cost optimization, distance optimization, agri­
cultural distribution, time windows, heterogeneous fleet.
‫ﺍلملخص‬
‫في هذﺍ ﺍلمشروﻉ ﺍلنهائي‪ ،‬نقوم بتحليل تحسين جولاﺕ ﺍلمركباﺕ ﺩﺍخل شركة ‪ DJE-AGRO‬ﺍلتي تنشط في توﺯ يع‬
‫ﺍلمنتجاﺕ ﺍلدوﺍجن ﺍلطاﺯجة ﺍنطلاقا ً من ﺍلمستوﺩﻉ ﺍلمركزي ﺍلوﺍقع في ولاية باتنة نحو ‪ 38‬ﺯ بونا ً موﺯعين ﺩﺍخل ﺍلولاية‬
‫وسبع ولاياﺕ مجاوﺭﺓ في شرق ﺍلجزﺍئر‪.‬‬
‫ل من جوﺩﺓ ﺍلخدمة من خلال ﺍحترﺍم ﺍلموﺍعيد‬ ‫يتمثل ﺍلهدف ﺍلرئيسي في تحسين تكاليف ﺍلنقل مع ضمان مستوى عا ٍ‬
‫ﺍلزمنية للتوصيل وﺍلكمياﺕ ﺍليومية ﺍلمطلو بة‪.‬‬
‫يعتمد نظام ﺍلتوﺯ يع ﺍلزﺭﺍعي هذﺍ على ﺃسطول غير متجانس من ﺍلمركباﺕ ﺫﺍﺕ قدﺭﺍﺕ مختلفة‪ ،‬مع ﺃخذ قيوﺩ موﺍعيد‬
‫ﺍلتسليم وﺍلنوﺍفذ ﺍلزمنية ﺍلتي يفرضها ﺍلز بائن بعين ﺍلاعتباﺭ‪.‬‬
‫ﺍلكلماﺕ ﺍلمفتاحية‪ :‬تحسين جولاﺕ ﺍلمركباﺕ‪ ،‬تحسين ﺍلتكاليف‪ ،‬تحسين ﺍلمسافاﺕ‪ ،‬ﺍلتوﺯ يع ﺍلزﺭﺍعي‪ ،‬ﺍلنوﺍفذ ﺍلزمنية‪،‬‬
‫ﺍلأسطول غير ﺍلمتجانس‪.‬‬
Table des matières

Table des figures ii

Liste des Tableaux iii

Liste des acronymes iv

Introduction Générale 1

1 Présentation générale du contexte : La distribution agricole fraîche et l’entre­

prise d’accueil 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Généralité sur la distribution agricole fraîche . . . . . . . . . . . . . . . . . . . 4
1.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Les paramètres critiques du champ d’activité . . . . . . . . . . . . . . . 5
1.2.3 Les modes de transport adaptés . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 Les défis du secteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.5 Les stratégies logistiques pour une distribution efficiente . . . . . . . . 8
1.3 Entreprise d’accueil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Présentation de l’entreprise . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Historique et contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.3 Activités principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.4 Structure organisationnelle . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.5 Typologie de la clientèle . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.6 La logistique de distribution . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.7 Réseau de la distribution . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.8 Flotte de distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.9 Défis de la distribution chez DJE­Agro . . . . . . . . . . . . . . . . . . 16
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 L’État de l’art 18
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Optimisation combinatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Problèmes classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.3 Classe de complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Présentation du VRP (Vehicle Routing Problem) . . . . . . . . . . . . . . . . . 23
2.3.1 Définition et caractéristiques fondamentales . . . . . . . . . . . . . . . 23
2.3.2 Évolution historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.3 La configuration fondamentale du VRP . . . . . . . . . . . . . . . . . 25
2.3.4 Les variantes du VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
 2.4 Synthèse et positionnement de notre travail par rapport à l’état de l’art . . . . . 31
2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3 Les approches de résolution 32

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Taxonomie des méthodes de résolution du VRP . . . . . . . . . . . . . . . . . 33
3.2.1 Méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.2 Méthodes approximatives . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4 Résolution, Implémentation et Interprétation des résultats expérimentaux 43

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 La démarche méthodologique de résolution . . . . . . . . . . . . . . . . . . . 44
4.2.1 Modélisation Formelle du Problème . . . . . . . . . . . . . . . . . . . 44
4.2.2 Justification du choix de l’Approche Algorithmique . . . . . . . . . . . 47
4.3 Environnement d’Implémentation et Données . . . . . . . . . . . . . . . . . . 47
4.3.1 Outils et Langages de Programmation . . . . . . . . . . . . . . . . . . 47
4.3.2 Description de Données . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.3.3 Série d’expérimentations . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4 Déploiement de l’approche algorithmique . . . . . . . . . . . . . . . . . . . . 50
4.4.1 Phase 1 : Construction d’une Solution Initiale . . . . . . . . . . . . . . 50
4.4.2 Phase 2 : Amélioration par Recherche Locale . . . . . . . . . . . . . . 51
4.4.3 Phase 3 : Affinement par Métaheuristique (Recuit Simulé) . . . . . . . 52
4.5 Interprétation des Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5.1 Analyse Séquentielle des Résultats . . . . . . . . . . . . . . . . . . . . 54
4.5.2 Discussion et Interprétation Opérationnelle . . . . . . . . . . . . . . . . 62
4.5.3 Les contributions réelles apportées à DJE AGRO : . . . . . . . . . . . . 64
4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

Conclusion générale 66

Annexes 67

Bibliographie 77
Table des figures

1.1 Logo de l’entreprise (Source : DJE­AGRO) . . . . . . . . . . . . . . . . . . . 10

1.2 Plumeuse et Finisseuse de poulet (Source : DJE­AGRO) . . . . . . . . . . . . 11
1.3 Poulets emballer (Source : DJE­AGRO) . . . . . . . . . . . . . . . . . . . . . 11
1.4 Chambre froid négatif (Source : DJE­AGRO) . . . . . . . . . . . . . . . . . . 12
1.5 Organigramme de l’entreprise (Source : DJE­AGRO) . . . . . . . . . . . . . . 13
1.6 Réseau de la distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.7 Véhicule frigorifique de 400 Kg.[29] . . . . . . . . . . . . . . . . . . . . . . . 15
1.8 Véhicule frigorifique de 900 Kg. [30]. . . . . . . . . . . . . . . . . . . . . . . 16
1.9 Véhicule frigorifique de 3500 Kg.[31] . . . . . . . . . . . . . . . . . . . . . . 16

2.1 Illustration d’une solution TSP.[41] . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2 Illustration des inclusions des classes de complexité.[46] . . . . . . . . . . . . 22
2.3 Illustration d’une solution VRP.[50] . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Le processus de croissance du VRP.[51] . . . . . . . . . . . . . . . . . . . . . 24

3.1 Les Méthodes de résolution du VRP.[67] . . . . . . . . . . . . . . . . . . . . . 34

3.2 Illustration de l’algorithme séquentiel de séparation et évaluation.[68] . . . . . 35
3.3 Principe de la recherche locale.[73] . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Représentation simplifiée d’une approche métaheuristique.[74] . . . . . . . . . 39
3.5 Principe de fonctionnement d’un algorithme génétique.[73] . . . . . . . . . . . 41
3.6 Effet de la coupure d’une piste de phéromone.[76] . . . . . . . . . . . . . . . . 42

4.1 Schéma conceptuel de l’algorithme de construction par insertion (Phase 1). . . 51

4.2 Schéma conceptuel de l’algorithme de recherche locale (Phase 2). . . . . . . . 52
4.3 Schéma conceptuel de l’algorithme de Recuit Simulé (Phase 3). . . . . . . . . 53
4.4 Visualisation des tournées générées par l’heuristique d’insertion (Phase 1). . . . 54
4.5 Tournée 9 avec le véhicule 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.6 Tournée 15 avec le véhicule 17. . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.7 Tournée 18 par la deuxième rotation du véhicule 9. . . . . . . . . . . . . . . . 56
4.8 Visualisation des tournées après amélioration par Recherche Locale (Phase 2). . 57
4.9 Illustration de deux nouvelles tournées. . . . . . . . . . . . . . . . . . . . . . 58
4.10 Tournées 12 avec le véhicule 18. . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.11 Visualisation de la solution finale obtenue par Recuit Simulé (Phase 3) : vue
d’ensemble et vue rapprochée. . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.12 Tournée 9 avec le véhicule 15. . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.13 Tournée 11 avec le véhicule 17. . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.14 Évolution des indicateurs de performance à chaque phase d’optimisation. . . . 62
4.15 Amélioration du Taux de Satisfaction Client. . . . . . . . . . . . . . . . . . . . 63
16 Détails de la tournée 1 et 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
17 Détails de la tournée 3 et 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
18 Détails de la tournée 5, 6 et 7. . . . . . . . . . . . . . . . . . . . . . . . . . . 69

i
19 Détails de la tournée 8 et 9. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
20 Détails de la tournée 10 et 11. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
21 Détails de la tournée 12 et 13. . . . . . . . . . . . . . . . . . . . . . . . . . . 71
22 Résumé final du cas optimisé. . . . . . . . . . . . . . . . . . . . . . . . . . . 71

ii
Liste des tableaux

1.1 Missions et responsabilités des départements de DJE­AGRO . . . . . . . . . . 13

4.1 Résultats des différentes configurations de recuit simulé . . . . . . . . . . . . 49

4.2 Tableau Comparatif des Gains : Réel vs Optimisé . . . . . . . . . . . . . . . . 63
3 Liste des clients avec leurs fenêtres de temps . . . . . . . . . . . . . . . . . . 72

iii
Liste des acronymes

AIE Agence Internationale de l’Énergie

ATP Accord relatif aux Transport internationaux de denrées Périssables
CVRP Capacitated Vehicle Routing Problem
DLC Date Limite de Consommation
DDM Date de Durabilité Minimale
HACCP Hazard Analysis Critical Control Points
HVRP Heterogeneous Vehicle Routing Problem
IOT Internet of Things
MTVRP Multi­Trip Vehicle Routing Problem
NP Non­deterministic Polynomial­time
OMI Organisation Maritime Internationale
TSP Traveling Salesman Problem
UE Union Européenne
URGENCI Urban­Rural Generator of New Partnerships Cooperatives Initiative
VRP Vehicle Routing Problem
VRPTW Vehicle Routing Problem with Time Windows

iv
Introduction Générale

Dans un contexte économique marqué par une concurrence accrue et une exigence croissante
en matière de qualité de service, l’optimisation des systèmes logistiques constitue un enjeu stra­
tégique majeur pour le secteur de distribution. Cette problématique prend une dimension critique
dans le domaine agricole frais, où la qualité et la périssabilité des produits imposent une coor­
dination précise des opérations de transport et de livraison.

Le présent projet de fin d’étude vise à optimiser un système de distribution des produits agri­
coles frais par la résolution du problème des tournées de véhicules avec contraintes temporelles
par la manière suivante :

Le premier chapitre sera dédié à la présentation du contexte général de la distribution agricole

fraîche et de l’entreprise d’accueil. La SARL DJE AGRO est spécialisée dans la distribution de
produits avicoles frais dans la région Est de l’Algérie. Opérant à partir de son dépôt central situé
dans la wilaya de Batna, l’entreprise dessert quotidiennement 38 clients répartis sur un territoire
étendu couvrant sept wilayas. Cette configuration géographique, associée à la nature périssable
des produits et aux exigences temporelles des clients à formuler la problématique centrale de
notre travail : Comment peut­on optimiser l’utilisation de la flotte et le séquencement des livrai­
sons de DJE­AGRO pour réduire les coûts de distribution, tout en garantissant un respect strict
des contraintes temporelles imposées par les clients ?

Le deuxième chapitre établira le cadre théorique de notre étude, en explorant l’état de l’art du
problème de tournées de véhicules. Ce problème d’optimisation VRP (Vehicle Routing Problem)
représente l’un des défis de la recherche opérationnelle notamment avec la prise en compte si­
multanée de multiples contraintes qui étendent le problème classique de VRP . Cette classe
des problèmes combinatoires, reconnue comme NP­difficile, consiste à déterminer un ensemble
optimal de routes pour une flotte de véhicules afin de desservir un ensemble de clients géogra­
phiquement dispersés, tout en respectant diverses contraintes opérationnelles et en minimisant
les coûts totaux de transport.

Le troisième chapitre présentera une revue des différentes méthodes de résolution existantes.
Cette méthodologie est fondée sur l’étude des principales approches de résolution du problème
de tournées de véhicules (VRP) en s’intéressant à leur classification, à leurs fondements théo­
riques, ainsi qu’à leurs performances sur le plan computationnel. Cette analyse permettra de
mieux comprendre les avantages et les limites de chaque méthode en vue d’orienter le choix de
la solution la plus adaptée au contexte du problème étudié.

1
 Le quatrième chapitre consiste à développer une stratégie algorithmique hybride en trois
phases : une heuristique de construction pour générer une solution initiale, une phase de re­
cherche locale pour l’améliorer, et une métaheuristique de type recuit simulé pour affiner le
résultat et explorer plus largement l’espace des solutions. Puis, on a procédé à une analyse ap­
profondie des résultats obtenus, afin de quantifier les gains potentiels pour l’entreprise et de
valider la pertinence de notre approche.

Cette démarche s’inscrit dans une perspective d’amélioration continue des performances
logistiques et de renforcement de la compétitivité de l’entreprise sur son marché. Elle vise éga­
lement à contribuer à l’enrichissement des connaissances scientifiques dans le domaine de l’op­
timisation des systèmes de distribution agricole fraîche.

2
Chapitre 1

Présentation générale du contexte : La

distribution agricole fraîche et l’entreprise
d’accueil

3
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

1.1 Introduction
La distribution agricole s’érige en pilier fondamental de la chaîne de valeur agroalimentaire,
jouant le rôle d’interface névralgique entre les concepteurs d’intrants et les exploitants agricoles.
Ce secteur évolue dans un écosystème d’une complexité remarquable, confronté à des enjeux
économiques, environnementaux et sociétaux dont l’ampleur ne cesse de s’accentuer.
Comme le souligne Bertrand Valiorgue,La distribution agricole se trouve au carrefour des
tensions qui traversent notre système alimentaire contemporain. Elle n’est plus un simple inter­
médiaire commercial, mais devient un acteur de la transition agroécologique, porteur de savoirs
et d’innovations [1].
En outre, la distribution agricole des produits frais constitue un maillon stratégique d’une
remarquable complexité dans l’architecture des filières agroalimentaires contemporaines, or­
chestrant le flux logistique entre les producteurs et les consommateurs finaux. Cette branche
singulière de la distribution agricole se distingue par des exigences spécifiques liées à la péris­
sabilité intrinsèque des denrées qu’elle manipule.
En 2024, le segment des produits frais affiche un taux de croissance mondial de 4,8 %, tandis
qu’en France, il représente 26 % de la grande distribution alimentaire [2], [3]. Cette dynamique
s’accompagne de l’essor des circuits courts, privilégiés par 76 % des consommateurs français
pour l’achat de produits frais en raison de la qualité et du goût perçus, engendrant de nouveaux
paradigmes de distribution [4].
Ce chapitre vise ainsi à contextualiser ces enjeux logistiques de la distribution dans le secteur
agricole frais, en soulignant leurs spécificités, et leurs défis actuels, et à introduire l’entreprise
d’accueil qui fera l’objet de notre étude de cas dans les prochains chapitres.

1.2 Généralité sur la distribution agricole fraîche

1.2.1 Définitions
La distribution de marchandises fraîches : définie comme l’ensemble des activités logistiques
comprenant la planification stratégique des itinéraires de livraison, la sélection de véhicules
techniques appropriés et la gestion rigoureuse des délais d’acheminement. Cette orchestration
logistique vise à préserver l’intégrité qualitative des produits périssables tout en optimisant les
ressources déployées. Le règlement (UE) 𝑛∘ 931/2011 relatif aux exigences de traçabilité établit
que « les exploitants du secteur alimentaire doivent être en mesure d’identifier toute personne
leur ayant fourni des denrées alimentaires et toute entreprise à laquelle leurs produits ont été
livrés », renforçant ainsi l’exigence d’une distribution rigoureusement maîtrisée [5].

La chaîne du froid : désigne le maintien ininterrompu de produits alimentaires à des tempé­

ratures spécifiquement prescrites, tout au long des phases successives de manutention, d’en­
treposage, de distribution et de transport. Cette continuité thermique représente l’élément sine
qua non de la préservation des qualités organoleptiques, nutritionnelles et sanitaires des produits
frais. Comme le précise l’article 𝑅.231 − 59 − 1 qui encadre la législation française : « Les tem­
pératures des denrées alimentaires réfrigérées, congelées ou surgelées, doivent être maintenues
en tous points des produits à des températures conformes aux prescriptions réglementaires ou,
en l’absence de celles­ci, aux températures fixées par le conditionneur sous sa responsabilité »
[6].

4
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

Le transport de marchandises fraîches : constitue un ensemble complexe d’opérations d’ache­

minement de denrées périssables sous régime thermique contrôlé, depuis leur lieu d’élaboration
ou de récolte jusqu’aux différents maillons de la chaîne de valeur agroalimentaire. Ce processus
s’inscrit dans un cadre normatif rigoureux, notamment régi par l’Accord ATP et les règlements
(𝐶𝐸) 𝑛∘ 852/2004 et 𝑛∘ 853/2004 relatifs à l’hygiène des denrées alimentaires [7]­[9]. L’ar­
ticle 𝐿.3222 − 9 du Code des transports stipule d’ailleurs que « le transporteur doit justifier, par
tout moyen de preuve, du respect de ses obligations en matière de préservation de l’intégrité des
denrées périssables transportées » [10].

1.2.2 Les paramètres critiques du champ d’activité

Le système de distribution des denrées périssables se définit par un ensemble de caractéris­
tiques distinctives qui en font un domaine d’activité aux mécanismes singuliers :

Les contraintes liées à la périssabilité : la durée de vie limitée des produits frais impose une
gestion temporelle rigoureuse. Selon leur nature, les denrées présentent des durées de conserva­
tion variables. Cette contrainte exige une rotation optimale des stocks et des livraisons. De plus,
les conditions de conservation nécessitent un suivi rigoureux des équipements frigorifiques ainsi
qu’une surveillance continue des paramètres de stockage et de transport (température, humidité,
atmosphère contrôlée) [11].

La réglementation stricte et normes sanitaires : le cadre réglementaire du secteur se carac­

térise par sa rigueur. Les normes HACCP imposent une analyse systématique des risques et la
définition de points de contrôle critiques. Le paquet hygiène européen renforce ces obligations
avec des contrôles sanitaires réguliers et des sanctions dissuasives. L’étiquetage précis constitue
une obligation légale essentielle. Les mentions des dates limites (DLC/DDM), de l’origine, des
conditions de conservation et des allergènes sont strictement encadrées. Cette exigence d’infor­
mation renforce la responsabilité des distributeurs à l’égard des consommateurs [12],[13].

La logistique complexe et onéreuse : le transport des produits frais nécessite une infrastructure
spécialisée. Les véhicules frigorifiques, conteneurs isothermes et équipements de suivi des tem­
pératures représentent des investissements significatifs qui impactent la structure des coûts. La
fréquence élevée des livraisons, souvent quotidiennes, distingue ce secteur des autres activités de
distribution. Cette cadence soutenue, nécessaire pour maintenir la fraîcheur, engendre des coûts
logistiques importants mais constitue un impératif de qualité. En parallèle, la traçabilité impose
un suivi rigoureux de chaque lot depuis la production jusqu’à la vente. Cette exigence, renfor­
cée par la réglementation, permet d’assurer la sécurité sanitaire et de faciliter les procédures de
rappel en cas de problème [11],[13].

La vulnérabilité aux aléas externes : les risques climatiques constituent une source majeure
d’incertitude. Ils peuvent perturber brutalement les approvisionnements et provoquer des ten­
sions sur les prix. Cette vulnérabilité s’accentue avec l’intensification des phénomènes météo­
rologiques extrêmes. À ces aléas naturels s’inscrivent les crises sanitaires comme un facteur de
risque systémique. Des épizooties, contaminations microbiologiques ou scandales alimentaires
peuvent effondrer certains marchés et nécessiter des adaptations rapides des circuits de distribu­
tion. En outre, la fluctuation de la demande ajoute une dimension d’incertitude supplémentaire,
contraignant les distributeurs à ajuster constamment leur offre[13].

5
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

1.2.3 Les modes de transport adaptés

La gestion des flux logistiques dans le secteur agricole frais constitue un défi majeur qui
nécessite un arsenal de solutions de transport spécifiquement adaptées à la nature hautement
périssable des produits concernés. Ces modalités s’inscrivent dans un équilibre délicat entre
préservation qualitative, optimisation temporelle et considérations environnementales :

Le transport routier frigorifique (colonne vertébrale du système) : le transport routier de­

meure incontestablement la modalité dominante dans la distribution des produits agricoles frais,
représentant près de 47% des flux en 2023. Sa flexibilité intrinsèque et sa capacité d’adapta­
tion aux contraintes territoriales en font un vecteur privilégié malgré son empreinte carbone
conséquente. Bernard Pecqueur met en avant que le camion frigorifique s’est imposé comme le
prolongement mobile des espaces de stockage, permettant une continuité parfaite de la chaîne
du froid, élément indispensable de la distribution moderne des produits périssables [14]. Selon
le rapport de l’ADEME, les unités de réfrigération fonctionnant à l’azote liquide ou au CO2
cryogénique permettent désormais de réduire jusqu’à 90% les émissions sonores et polluantes
par rapport aux groupes diesel conventionnels, tout en garantissant une stabilité thermique su­
périeure [15].

Le transport ferroviaire réfrigéré (renaissance d’une modalité ancestrale) : le rail connaît

une résurrection remarquable dans le secteur des produits frais, particulièrement pour les trajets
longue distance. Selon l’analyse de Catherine Morency, le wagon frigorifique de nouvelle gé­
nération équipé de systèmes de refroidissement autonomes et de capteurs connectés réconcilie
la massification propre au ferroviaire avec les exigences de traçabilité et de contrôle thermique
inhérentes aux produits frais. Les corridors ferroviaires dédiés aux produits périssables se mul­
tiplient, notamment dans l’axe Nord­Sud européen, avec des fréquences de rotation optimisées
pour les produits saisonniers. D’après l’étude de Backcarbone, les trains sont les moyens de
transport les moins émetteurs de CO2 , représentant seulement 1,2% des émissions de GES liées
au transport mondial, et 9% du fret international, tout en maintenant une durée de transit com­
parable [16].

Le transport maritime à température dirigée (vecteur de globalisation contrôlée) : pour les

échanges intercontinentaux, le transport maritime spécialisé s’avère incontournable malgré ses
contraintes temporelles. Une étude sur les porte­conteneurs équipés d’unités frigorifiques à at­
mosphère contrôlée révèle leur contribution décisive à la révolution du commerce mondial des
denrées périssables, transformant des produits jadis strictement locaux en commodités globali­
sées disponibles en permanence [17]. L’émergence de navires spécialisés dans le transport de
produits ultra­frais, capables de maintenir des conditions optimales pendant plusieurs semaines,
remodèle la géographie des approvisionnements. Parallèlement, l’OMI concentre ses efforts sur
la réduction des impacts environnementaux liés aux émissions de gaz à effet de serre de ce mode
[18].

Le fret aérien (solution d’exception pour l’ultra­fraîcheur) : malgré son coût écologique et
économique considérable, le transport aérien conserve une place stratégique pour certaines den­
rées à très haute qualité ou à durée de conservation extrêmement limitée ainsi que des contraintes
techniques de manutention exigeantes. Selon l’analyse de Jean­Paul Rodrigue, ce mode remplit
une mission logistique spécifique qui privilégie la valeur ajoutée et la célérité plutôt que les

6
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

volumes transportés [19]. En revanche, selon l’Agence Internationale de l’Énergie (AIE), l’em­
preinte environnementale globale du transport aérien est évaluée à 24 % des émissions totales,
dont 40 % pour le fret aérien [20].

La multimodalité intégrée (vers une optimisation systémique) : la complexification des chaînes

d’approvisionnement et la diversification des exigences qualitatives ont favorisé l’émergence de
solutions hybrides combinant différents modes de transport. Comme l’explicite Florence Béné­
teau : « Tous les facteurs sont réunis pour permettre Pôle Béarn­Mont de Marsan­Dax de devenir
un ” hub logistique nouvelle génération ” interconnecté, intermodal et intelligent, maillant lo­
gistique endogène et logistique exogène pour lui assurer les retombées économiques attendues.
Un des facteurs de réussite sera la capacité du pôle à rendre effectif l’intermodalité de ses es­
paces et une meilleure interconnexion avec les autres pôles aquitains et notamment celui de
Bordeaux mais également avec Tarbes, Toulouse et les territoires espagnols (Pays Basque, Na­
varre et Aragon) ». François Fulconis explique que l’intelligence des systèmes de distribution
des produits frais réside désormais dans leur capacité à orchestrer des transferts intermodaux
fluides, où chaque mode de transport intervient précisément là où son efficience comparative
est maximale. Ces architectures logistiques prospères s’appuient sur des plateformes d’échange
multimodales spécifiquement conçues pour les produits périssables[21].

1.2.4 Les défis du secteur

La tyrannie temporelle (une course contre la dégradation biologique) : la dimension tem­
porelle représente indéniablement la contrainte primordiale structurant l’ensemble de la chaîne
logistique. Selon Pierre Feillet, chaque produit agricole frais possède sa propre horloge biolo­
gique interne, sa propre cinétique de dégradation qualitative qui impose un tempo spécifique à
sa distribution. La logistique des produits frais s’apparente ainsi à une véritable chorégraphie
temporelle où chaque retard se traduit inexorablement par une destruction de valeur[22].

La fragilité infrastructurelle de la chaîne du froid (un maillon critique) : le maintien de

l’intégrité thermique constitue un défi technique considérable dont la complexité est souvent
sous­estimée. Les points de rupture de charge représentent des zones de vulnérabilité particu­
lière. L’Institut International du Froid révèle que les incidents de rupture de la chaîne du froid
surviennent lors des opérations de transbordement entre différents modes de transport ou lors
des phases de chargement/déchargement, engendrant des variations thermiques critiques qui
compromettent l’intégrité des produits thermosensibles [23].

L’hétérogénéité qualitative (le défi de la standardisation) : contrairement aux produits ma­

nufacturés, les denrées agricoles fraîches présentent une variabilité qualitative intrinsèque qui
complexifie considérablement leur gestion logistique. Comme le soulignent François Valceschi­
ni que La distribution des produits agricoles périssables ne peut jamais totalement s’affranchir
d’une certaine imprévisibilité qualitative qui exige des processus logistiques dotés d’une capa­
cité d’adaptation et de tri dynamique incompatible avec une standardisation excessive.

La fragmentation géographique (l’atomisation des points de livraison) : La dispersion spa­

tiale des lieux de production et de consommation génère des défis considérables d’optimisation
des tournées et des chargements. Bernard Pecqueur corrobore que la capillarité extrême de la
distribution finale des produits frais, notamment dans les systèmes alimentaires territorialisés,

7
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

induit une complexité combinatoire qui défie les algorithmes d’optimisation [24]. Cette ato­
misation s’accentue par l’essor des circuits courts, entraîne une augmentation significative des
distances parcourues et des fréquences des cycles de tournées, mettant à l’épreuve les modèles
logistiques traditionnels. Selon le réseau URGENCI, la multiplication des points de livraison di­
recte au consommateur a entraîné une augmentation du kilométrage parcouru par tonne de pro­
duits frais distribuée au cours de la dernière décennie, exacerbant ainsi la tension entre proximité
relationnelle et efficience logistique [25].

La transition écologique (concilier performance environnementale et intégrité des pro­

duits) : l’impératif de décarbonation des activités logistiques se heurte aux contraintes spéci­
fiques de la distribution des produits périssables. Corinne Blanquart constate que ce système
distributif cristallise la tension entre impératif de rapidité et objectif de sobriété énergétique.
Cette transition nécessite des innovations de rupture. Les travaux de Wageningen établissent
que les technologies de réfrigération passive avancée, combinées à une optimisation topolo­
gique des réseaux logistiques, permettent désormais d’envisager une réduction significative de
l’empreinte carbone du réseau distributif sans compromettre leur intégrité qualitative, à condi­
tion d’accepter une reconfiguration profonde des schémas logistiques traditionnels [26].

1.2.5 Les stratégies logistiques pour une distribution efficiente

Confrontés aux défis posés par l’acheminement du vivrier. Les acteurs du secteur ont déve­
loppé des approches stratégiques afin de rationaliser leurs flux :

La segmentation différenciée : l’hétérogénéité des produits agricoles frais a conduit à l’aban­

don des approches logistiques uniformisées. Fabrizio Dallari souligne dans son analyse que la
segmentation physiologique des flux constitue désormais le principe architectural fondamen­
tal des systèmes logistiques contemporains, où chaque type de produit est orienté vers un cir­
cuit logistique spécifique. La tendance actuelle en logistique bascule vers des plateformes de
nouvelle génération, fondées sur des architectures modulaires comprenant des environnements
thermiques distincts[27].

La compression temporelle ciblée : a maîtrise du facteur temps s’articule autour d’une hié­
rarchisation des priorités d’acheminement. Selon Fabbe­Costes, l’approche contemporaine de
la gestion temporelle des flux périssables repose sur une discrimination dynamique des niveaux
d’urgence, permettant d’allouer les ressources logistiques indispensables en priorité aux produits
dont la valeur temporelle marginale est la plus élevée.

L’intégration verticale accentuée : le contrôle des zones de transition entre maillons de la

chaîne logistique s’est imposé comme un levier stratégique. Rizwan et al. démontrent que l’in­
tégration verticale dans la distribution des produits frais répond à un impératif de continuité
opérationnelle visant à éliminer les discontinuités aux interfaces entre acteurs, véritables points
de vulnérabilité de la chaîne de valeur [28].

La décentralisation coordonnée : la reconfiguration des réseaux et des canaux de distribution

s’oriente vers un modèle hybride alliant proximité territoriale et massification. Le paradigme
émergent de la centralisation distribuée repose sur un maillage territorial dense de hubs logis­
tiques de taille intermédiaire, suffisamment importants pour générer des économies d’échelle,
mais suffisamment décentralisés pour minimiser les distances terminales.

8
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

La mutualisation dynamique des ressources : le partage optimisé des infrastructures s’impose

comme une tendance structurante. Selon Fabbe­Costes, la mutualisation dans la distribution des
produits frais transcende le simple partage statique d’infrastructures pour atteindre une dimen­
sion dynamique où les ressources logistiques sont constamment réallouées en temps réel entre
acteurs concurrents.

Dans ce contexte, l’efficacité du transport et de la distribution impose un enjeu stratégique

majeur pour les entreprises du secteur agricole frais, avec des impacts directs sur la compétitivité,
la rentabilité et la durabilité des chaînes logistiques.

9
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

1.3 Entreprise d’accueil

1.3.1 Présentation de l’entreprise
Le secteur agricole, notamment dans les segments de la transformation des produits agricoles
frais tels que la viande blanche, occupe une position clé dans l’économie nationale. Il contribue
activement à la sécurité alimentaire en assurant un approvisionnement constant en produits de
volaille frais, tout en garantissant la conformité aux normes d’hygiène et sanitaires.

Dans ce contexte, la SARL DJE­AGRO se posi­

tionne comme un acteur clé. Cette société à responsabi­
lité limitée, fondée en 2005, est implantée à Aïn Tou­
ta dans la commune de Ouled Aouf (wilaya de Bat­
na). Elle se spécialise dans l’abattage industriel et la
transformation de volaille, et s’est distinguée par la
qualité de ses produits et la rigueur de ses processus.

Dotée d’une organisation souple, l’entreprise adapte

ses effectifs aux périodes de forte demande, comme
durant le mois de Ramadan. Ce mode de fonction­
nement lui permet de répondre rapidement aux be­
soins du marché tout en maintenant des standards éle­
vés. Fig. 1.1 : Logo de l’entreprise
(Source : DJE­AGRO)
Afin d’assurer une prestation fiable, DJE­AGRO
doit relever plusieurs défis, notamment en matière de
distribution et de gestion de la chaîne du froid. Ces enjeux sont au cœur de la réflexion logistique
présentée dans ce mémoire.

1.3.2 Historique et contexte

Depuis sa création en 2005, la SARL DJE­AGRO a su s’imposer dans le domaine de la
transformation de viande blanche grâce à une stratégie fondée sur la qualité, la fiabilité et la
modernisation de ses installations. Son implantation dans la région de Batna (Ouled Aouf – Aïn
Touta) lui confère un positionnement géographique stratégique pour desservir une large zone de
consommation.
L’entreprise a établi des partenariats solides avec des acteurs institutionnels et privés. L’un
des plus significatifs est celui mené avec le ministère de la Défense nationale, révélateur de
sa capacité à répondre à des exigences strictes en matière de sécurité alimentaire, de volumes
livrables et de ponctualité.
DJE­AGRO assure également une distribution régulière à travers un réseau de boucheries,
de grossistes et de restaurants, ce qui lui permet de consolider son ancrage local. Cette diversité
de débouchés implique une logistique maîtrisée et une gestion rigoureuse des flux pour garantir
la fraîcheur et la traçabilité des produits.
Animée par une volonté de développement, l’entreprise continue d’investir dans ses capaci­
tés de production et d’améliorer ses performances logistiques afin de renforcer sa compétitivité
sur le marché régional.

10
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

1.3.3 Activités principales

La SARL DJE­AGRO opère dans la transformation industrielle de volaille, avec des activités
allant de l’abattage, la découpe, le conditionnement jusqu’à la distribution :
Le processus de production s’articule autour de plusieurs étapes successives :

– Réception des poulets vifs : Les volailles sont réceptionnées dans des conditions contrôlées.
Cette étape inclut la vérification des documents d’accompagnement, l’inspection sanitaire et
le déchargement sécurisé des animaux.

– Préparation pré­abattage : Avant l’abattage proprement dit, il y a des processus de prépa­

ration tels que la mise en place des équipements nécessaires, la stérilisation des installations
et la mise en œuvre des procédures de sécurité.

– L’abattage : Réalisé selon des procédures encadrées par les autorités sanitaires, dans le res­
pect des normes d’hygiène et de bien­être animal.

– Échaudage, plumaison et finition : Après l’abattage, les carcasses passent dans un bac
d’échaudage pour faciliter l’enlèvement des plumes. Elles sont ensuite traitées par une plu­
meuse automatique 1.2a, puis par une finisseuse 1.2b, pour éliminer les plumes résiduelles.

(a) Plumeuse de poulet (b) Finisseuse de poulet

Fig. 1.2 : Plumeuse et Finisseuse de poulet (Source : DJE­AGRO)

– Conditionnement : Effectué dans des emballages adaptés, garantissant la traçabilité, la conser­

vation et la présentation commerciale des produits, en version fraîche ou surgelée.

Fig. 1.3 : Poulets emballer (Source : DJE­AGRO)

– Stockage en chambre froide : Permettant de maintenir la qualité microbiologique des pro­

duits jusqu’à leur expédition.

11
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

Fig. 1.4 : Chambre froid négatif (Source : DJE­AGRO)

– Distribution : Cette étape comprend l’organisation logistique nécessaire pour acheminer les
produits vers les différents points de vente (centres de distribution, supermarchés, etc.).

– Gestion des déchets : Les sous­produits et déchets sont collectés, triés et traités conformé­
ment aux normes environnementales et sanitaires.

– Maintenance des installations : Une maintenance régulière des équipements est assurée pour
garantir le bon déroulement de la production.

L’entreprise attache une attention particulière à la conformité sanitaire de ses produits, en

se dotant de protocoles stricts de contrôle qualité tout au long de la chaîne de transformation.
Elle vise à assurer aux consommateurs un produit sûr, savoureux et conforme aux attentes du
marché.
En parallèle, DJE­AGRO gère les aspects logistiques et commerciaux, en assurant la distri­
bution quotidienne de ses produits vers différents clients, ce qui complète son positionnement
comme acteur local de référence dans le secteur avicole.

1.3.4 Structure organisationnelle

Afin de soutenir efficacement ses activités principales et de garantir une qualité constante
des produits, la SARL DJE­AGRO s’est dotée d’une structure organisationnelle adaptée. Cette
organisation repose sur une mobilisation de personnel qualifié et sur l’utilisation d’équipements
de haute technologie, visant à optimiser à la fois le respect du bien­être animal et la sécurité
sanitaire des produits finis. La répartition des rôles et des responsabilités au sein de l’entreprise
est détaillée dans le tableau ci­dessous 1.1 :

12
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

Fig. 1.5 : Organigramme de l’entreprise (Source : DJE­AGRO)

Département Rôle principal

Direction Générale Supervise la gestion globale de l’entreprise, définit la stratégie et
prend les décisions majeures.
Ressources Humaines Gère le recrutement, la formation, la gestion des carrières, la paie
et le climat social.
Production Supervise l’ensemble des opérations de transformation de la vo­
laille, de l’abattage à l’emballage.
Qualité et Contrôle Contrôle la qualité sanitaire des produits et veille au respect des
normes HACCP et ATP.
Logistique Organise, coordonne et optimise les flux physiques de marchan­
dises dans l’entreprise.
–Gestion de Stock Assure le stockage des marchandises dans des conditions adaptées
(température contrôlée), la gestion des entrées/sorties et l’inven­
taire permanent.
–Transport et Distribu­ Planifie et exécute la livraison des produits frais vers les clients,
tion en garantissant le respect de la chaîne du froid et des délais.
Maintenance Assure l’entretien, la réparation préventive et curative des équipe­
ments de production et des véhicules frigorifiques.
Approvisionnement Sélectionne les fournisseurs, négocie les achats et assure le réap­
provisionnement des matières premières et emballages.
Administration et Fi­ Assure la gestion comptable, financière et administrative de l’en­
nances treprise.

Tab. 1.1 : Missions et responsabilités des départements de DJE­AGRO

13
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

1.3.5 Typologie de la clientèle

La clientèle de la SARL DJE­AGRO se répartit en plusieurs segments, chacun avec des
besoins d’approvisionnements spécifiques. Par conséquent, on distingue principalement trois
grandes catégories :

• Les clients commerciaux, tels que les boucheries, restaurants et grossistes, représentent
le noyau principal de la distribution quotidienne. Ces clients, répartis sur plusieurs wi­
layas, achètent pour la revente ou la consommation directe. Ils nécessitent des livraisons
fréquentes en fonction de la demande réelle du marché.
• Les institutions publiques, notamment les écoles, internats et universités, sont livrées
dans le cadre de contrats planifiés. Les commandes de ces clients ne sont pas journalières :
elles sont souvent programmées pour des périodes allant de vingt jours à un mois, selon
les besoins et les stocks disponibles.
• Les organismes gouvernementaux, en particulier le Ministère de la Défense nationale,
constituent des partenaires pour l’entreprise. Les volumes livrés sont importants, et les
commandes sont également effectuées sur des cycles périodiques, généralement non quo­
tidiens, et nécessitant une coordination logistique rigoureuse.

Il convient de souligner que le présent mémoire porte spécifiquement sur la distribution jour­
nalière, ciblant les besoins des clients commerciaux (Boucheries, Restaurants et Grossistes),
en raison de leur rythme d’activité élevé, imposent une logistique réactive et flexible, que ce
travail se propose d’analyser et d’optimiser.

1.3.6 La logistique de distribution

La SARL DJE­AGRO gère en propre sa distribution journalière de ses produits finis. Son
recentrage stratégique sur les poulets frais impose à l’entreprise de se concentrer sur un produit
à forte demande, nécessitant une maîtrise rigoureuse de la chaîne logistique, notamment en ma­
tière de respect de la chaîne du froid. L’entreprise dispose d’une flotte de véhicules réfrigérés
spécialement dédiés à cette activité. Ces camions assurent le maintien de la température adé­
quate tout au long du transport, garantissant la fraîcheur, la sécurité sanitaire et la qualité des
produits jusqu’à leur livraison aux clients. Le respect de la chaîne du froid est ainsi pleinement
assuré par l’entreprise, conformément aux exigences réglementaires.
La programmation des livraisons repose sur une organisation humaine expérimentée, sans
recours à des outils numériques ou mathématiques. Les responsables logistiques construisent les
tournées à partir de leur connaissance du terrain et de l’expérience accumulée.
La confirmation des commandes des clients s’effectue la veille de la livraison (𝐽 − 1).
Ce mode d’organisation impose une réactivité de la part des équipes logistiques, qui doivent
planifier les tournées du lendemain à partir des demandes validées.
En résumé, la SARL DJE­AGRO dispose d’un système agricole frais conforme aux exi­
gences sanitaires, et soutenu par une équipe expérimentée.

1.3.7 Réseau de la distribution

La SARL DJE­AGRO assure la distribution de ses produits à partir du dépôt central implan­
té dans la wilaya de Batna vers 38 points de livraison, répartis dans cette localité ainsi qu’aux
sept wilayas avoisinantes de l’Est algérien :

14
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

• Batna (siège de l’entreprise), Sétif, Constantine, Oum El Bouaghi, Khenchela, Biskra,

M’Sila, Mila, la ville d’Aïn M’lila (wilaya d’Oum El Bouaghi)

Fig. 1.6 : Réseau de la distribution

1.3.8 Flotte de distribution

La SARL DJE­AGRO dispose d’un parc logistique composé de 20 véhicules frigorifiques,
adaptés aux exigences du transport de denrées périssables, en particulier la viande blanche. Cette
flotte diversifiée permet à l’entreprise d’assurer une distribution quotidienne efficace, en fonc­
tion des profils de ses clients et des zones desservies.
On distingue trois catégories principales de véhicules :

• Petits camions de 400 kg : particulièrement adaptés aux livraisons en milieu urbain dense,
où l’accessibilité est limitée. Ils sont souvent utilisés pour approvisionner les boucheries
de quartier ou les petits détaillants ayant des volumes modestes.

Fig. 1.7 : Véhicule frigorifique de 400 Kg.[29]

15
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

• Camions de 900 kg : utilisés pour les commandes de taille moyenne, notamment pour
les clients situés dans des villes voisines ou sur des axes interurbains. Ils offrent un bon
compromis entre capacité de charge et flexibilité de déplacement.

Fig. 1.8 : Véhicule frigorifique de 900 Kg. [30].

• Camions lourds de 3500 kg : réservés aux livraisons en gros volumes, ces véhicules
desservent les grands supermarchés, les centres de distribution. Ils permettent de regrouper
plusieurs commandes et d’optimiser les trajets sur de longues distances.

Fig. 1.9 : Véhicule frigorifique de 3500 Kg.[31]

Tous les véhicules sont équipés de groupes frigorifiques conformes aux normes de transport
alimentaire, assurant le maintien strict de la chaîne du froid durant tout le cycle de livraison. Cette
configuration technique garantit la qualité, la sécurité sanitaire et la conformité réglementaire
des produits transportés.

1.3.9 Défis de la distribution chez DJE­Agro

L’organisation actuelle ne dispose d’aucun outil informatique de planification ni de suivi
des tournées de distribution. Reposant sur des processus manuels, basée sur les bons de com­
mande reçus, la connaissance du terrain par les responsables, la disponibilité des véhicules et une
estimation approximative des temps et des distances à parcourir. Cette méthode, bien que opé­
rationnellement fonctionnelle, présente certaines limites liées au temps, et à distance. En outre,

16
Chapitre 1. Présentation générale du contexte : La distribution agricole fraîche et l’entreprise
d’accueil

elle répond de manière expérimentée aux besoins de ses clients tout en mobilisant quasiment
l’ensemble de sa flotte, engendrant :

• Une utilisation quasiment totale de tous les véhicules, sans évaluation préalable des
besoins réels, peut conduire à une mobilisation inutile de la flotte impliquant des coûts
supplémentaires.

• Absence d’optimisation des itinéraires : les tournées sont établies sans algorithme d’aide
à la décision, ce qui peut entraîner des trajets sous­optimaux, des chevauchements ou des
détours inutiles.

• Manque de flexibilité : cette approche limite la capacité à réagir efficacement face aux
imprévus ou aux modifications de dernière minute.

• Impact nocif sur la rentabilité, et la performance globale de la distribution journalière.

Dans ce contexte, la question centrale que pose ce mémoire est la suivante :

Comment peut­on optimiser l’utilisation de la flotte en déterminant à la fois le

nombre de véhicules et de rotations journalières nécessaires pour répondre de ma­
nière efficiente aux besoins des clients, tout en respectant leurs plages temporelles ?
Et quel serait le meilleur séquencement de distribution à adopter dans ce cas ?

Cette problématique soulève des enjeux d’efficacité opérationnelle, de réduction des coûts
logistiques et d’amélioration du niveau de service. Elle appelle à la mise en place d’une démarche
rigoureuse d’optimisation, fondée sur les outils de la recherche opérationnelle, et notamment sur
la modélisation du problème des tournées de véhicules (VRP).

1.4 Conclusion
Ce chapitre a permis d’établir le cadre général de notre étude en présentant, d’une part,
les enjeux logistiques liés à la distribution des produits agricoles périssables, et d’autre part, le
contexte spécifique de l’entreprise d’accueil, la SARL DJE­AGRO, en mettant l’accent d’avan­
tage sur la distribution de poulets frais.
Le chapitre suivant explorera ainsi les fondements théoriques du problème d’optimisation
des tournées de véhicules (VRP), afin de poser les bases méthodologiques nécessaires à l’éla­
boration d’un modèle répondant aux spécificités du cas DJE­AGRO.

17
Chapitre 2

L’État de l’art

18
Chapitre 2. L’État de l’art

2.1 Introduction
Ce chapitre pose les fondations théoriques de notre projet, en se concentrant sur l’optimisa­
tion des itinéraires de véhicules. Le problème de tournées de véhicules (VRP) s’impose comme
un instrument stratégique décisif, susceptible de révolutionner l’efficience économique et l’em­
preinte environnementale des réseaux de distribution.[32]
Les outils de planification des itinéraires permettent d’optimiser de 70% à 85% du temps
alloué à la construction des tournées. Ce gain temporel se traduit en amont par la compression
des délais de conception et le contrôle préventif de la rentabilité, et en aval par une réactivité
quasi instantanée face aux ajustements d’ordres, de flotte ou de commandes.[33]
Selon les sources, une solution d’optimisation des tournées de véhicules dans la logistique
permet de réduire les coûts de transport de 10% à 25%. Cette réalité économique prend une
dimension encore plus critique dans les systèmes distributifs des produits périssables, où les
exigences de fraîcheur et la ponctualité de livraison sont extrêmement strictes.[34]
Selon Todorovic et al. [35], dans la filière de la distribution de denrées périssables, la com­
plexité inhérente à cette problématique d’optimisation s’est intensifiée par la tendance actuelle
privilégiant des livraisons fréquentes et de moindres volumes, engendrant par conséquent une
multiplication du nombre de points de desserte.
À cet égard, l’implémentation d’algorithmes d’optimisation appliqués au VRP, adaptés aux
contraintes spécifiques de la distribution agricole fraîche offre un potentiel considérable, tout en
permettant d’améliorer les taux de service des clients.[36]

2.2 Optimisation combinatoire

2.2.1 Définition
L’optimisation combinatoire (ou discrète) est une branche scientifique multidisciplinaire, à
l’interface de trois grands domaines scientifiques : la recherche opérationnelle, les mathéma­
tiques appliquées, l’informatique. Elle comprend un grand nombre de problèmes d’optimisation
combinatoire difficiles, issus d’applications réelles dans différents domaines tels que l’industrie,
la finance ou l’armée [37].
L’objectif de ces problèmes combinatoires consiste à trouver une meilleure solution dans un
espace dénombrable et discret de solutions réalisables, qui respectent un ensemble de conditions,
dites aussi contraintes. L’évaluation d’une solution est effectuée à l’aide d’une fonction dite
fonction objectif. Une meilleure alternative (solution optimale) est une solution réalisable qui
minimise ou maximise, selon le contexte, la fonction objectif [38].

2.2.2 Problèmes classiques

Le problème du voyageur de commerce
Le problème du voyageur de commerce (TSP) est l’un des problèmes les plus emblématiques
de l’optimisation combinatoire [39]. Il consiste à déterminer le circuit le plus court permettant
de visiter une série de villes en circuit unique avant de retourner au point de départ.

19
Chapitre 2. L’État de l’art

Selon Gutin et Punnen , le TSP peut être formalisé comme suit : étant donné un graphe
complet 𝐺 = (𝑉 , 𝐸) avec 𝑛 = |𝑉 | sommets et une fonction de coût 𝑐 ∶ 𝐸 → ℝ+ qui asso­
cie à chaque arête un coût non négatif, l’objectif est de trouver un cycle hamiltonien de coût
minimal.[40] Les travaux récents de Taillard et al. ont montré que, malgré sa simplicité concep­
tuelle, le TSP continue de jouer un rôle central dans l’élaboration de nouvelles heuristiques et
méta­heuristiques pour l’optimisation combinatoire.

Fig. 2.1 : Illustration d’une solution TSP.[41]

Le problème d’affectation
Le problème d’affectation consiste à affecter 𝑛 tâches à 𝑛 agents avec un coût total minimal,
où 𝑐𝑖𝑗 représente le coût d’affecter l’agent 𝑖 à la tâche 𝑗 [42] :

min ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗

𝑖 𝑗

s.c. ∑ 𝑥𝑖𝑗 = 1 ∀𝑖, ∑ 𝑥𝑖𝑗 = 1 ∀𝑗, 𝑥𝑖𝑗 ∈ {0, 1} ∀𝑖, 𝑗

𝑗 𝑖

Les variantes majeures incluent :

• Problème d’affectation généralisée (GAP) : Dans ce problème chaque agent possède des
capacités limitées et l’exécution de chaque tâche nécessite une consommation variable de
ressources selon l’agent qui l’effectue.

• Problème d’affectation quadratique (QAP) : Ce problème traite de l’emplacement opti­

mal d’installations en tenant compte des interactions entre elles. Il intègre les coûts générés
par les flux d’échanges entre les différentes installations selon leur localisation relative.

• Problème d’affectation tridimensionnelle : Il s’agit d’une généralisation qui implique

l’appariement simultané de trois ensembles distincts d’éléments, contrairement aux pro­
blèmes classiques qui ne considèrent que deux ensembles.

20
Chapitre 2. L’État de l’art

Le problème du sac à dos

Le problème du sac à dos est un autre problème fondamental de l’optimisation combinatoire
[43]. Dans sa forme la plus simple, il s’agit de sélectionner un sous­ensemble d’objets, chacun
ayant un poids et une valeur, de manière à maximiser la valeur totale sans dépasser une contrainte
de poids. Martello et Toth[44] ont formalisé ce problème comme suit :
𝑛
max ∑ 𝑣𝑖 𝑥𝑖
𝑖=1
𝑛
s.c. ∑ 𝑤𝑖 𝑥 𝑖 ≤ 𝑊 , 𝑥𝑖 ∈ {0, 1}, 𝑖 = 1, … , 𝑛
𝑖=1
où 𝑣𝑖 et 𝑤𝑖 représentent respectivement la valeur et le poids de l’objet 𝑖, 𝑊 est la capacité du
sac à dos, et 𝑥𝑖 est une variable binaire indiquant si l’objet 𝑖 est sélectionné (𝑥𝑖 = 1) ou non
(𝑥𝑖 = 0). Des extensions plus complexes de ce problème ont été étudiées par Puchinger et al.,
notamment le problème du sac à dos multidimensionnel où plusieurs contraintes de ressources
sont considérées simultanément.

Le problème de recouvrement d’ensemble

Ce problème consiste à identifier la collection de sous­ensembles la moins coûteuse capable
de couvrir intégralement un ensemble universel donné. Soit un ensemble 𝑈 = {1, … , 𝑛} et une
collection 𝑆 = {𝑆1 , … , 𝑆𝑚 } de sous­ensembles de 𝑈 avec des coûts 𝑐1 , … , 𝑐𝑚 , l’objectif est
de trouver une sous­collection de coût minimal qui couvre entièrement 𝑈 [45]. La formulation
PLNE est :
𝑣(SCP) = min ∑ 𝑐𝑗 𝑥𝑗
𝑗

s.c. ∑ 𝑎𝑖𝑗 𝑥𝑗 ≥ 1 ∀𝑖 ∈ 𝑀 , 𝑥𝑗 ∈ {0, 1} ∀𝑗 ∈ 𝑁

𝑗∈𝑁

Variables de décision : 𝑥𝑗 = 1 si la colonne 𝑗 est sélectionnée (𝑗 ∈ 𝑆), 𝑥𝑗 = 0 sinon. Pour

chaque ligne 𝑖 ∈ 𝑀, on définit : 𝐽𝑖 = {𝑗 ∈ 𝑁 ∶ 𝑎𝑖𝑗 = 1}, où 𝐽𝑖 représente l’ensemble des
colonnes qui couvrent la ligne 𝑖. De manière analogique, pour chaque colonne 𝑗 ∈ 𝑁, on définit :
𝐼𝑗 = {𝑖 ∈ 𝑀 ∶ 𝑎𝑖𝑗 = 1}, où 𝐼𝑗 est l’ensemble des lignes que la colonne 𝑗 peut couvrir. Les
variantes importantes incluent :

• Partitionnement d’ensemble : Les sous­ensembles sélectionnés doivent être disjoints où

chaque élément ne peut appartenir qu’à un seul sous­ensemble choisi.

• Couverture maximale : Maximiser le nombre d’éléments couverts avec une contrainte

budgétaire de sous­ensembles utilisables.

Ces problèmes apparaissent en localisation de services, planification de personnel, et conception

de réseaux.

21
Chapitre 2. L’État de l’art

2.2.3 Classe de complexité

La théorie de la complexité algorithmique réside dans la compréhension de la difficulté in­
hérente aux problèmes d’optimisation combinatoire, qui consiste à mesurer principalement le
temps de calcul et l’espace mémoire requis afin de trouver la solution optimale. Cette mesure
s’exprime généralement en fonction de la taille de l’instance du problème, notée 𝑛.

La classe P
La classe P représente l’ensemble des problèmes de décision que nous pouvons résoudre
efficacement. Plus précisément, un problème appartient à P s’il existe un algorithme déterministe
qui le résout en temps polynomial, c’est­à­dire en 𝑂(𝑛𝑘 ) pour une constante 𝑘, où 𝑛 représente
la taille de l’entrée.

La classe NP
Un problème est dans la classe NP (Non Deterministic Polynomial time) si, étant donnée
une solution candidate (appelée certificat), on peut vérifier sa validité en temps polynomial.

Les problèmes NP­complets

Un problème est NP­complet s’il possède simultanément ces deux propriétés : il appartient
à la classe NP car ses solutions peuvent être vérifiées rapidement en temps polynomial, et il est
au moins aussi difficile que tous les autres problèmes de NP puisque tout problème de NP peut
être transformé en lui via une réduction polynomiale.

Les problèmes NP­difficiles

Un problème est NP­difficile si tous les problèmes de NP peuvent être réduits à celui­ci en
temps polynomial. Cette notion de réduction, formalisée par Cook en 1971, est fondamentale :
si nous pouvions résoudre efficacement un problème NP­difficile, nous pourrions résoudre ef­
ficacement tous les problèmes de NP. Les problèmes NP­difficiles ne sont pas nécessairement
des problèmes de décision. Par exemple, la version optimisation du TSP est NP­difficile, mais
n’appartient pas à NP car ce n’est pas un problème de décision.

Fig. 2.2 : Illustration des inclusions des classes de complexité.[46]

22
Chapitre 2. L’État de l’art

2.3 Présentation du VRP (Vehicle Routing Problem)

2.3.1 Définition et caractéristiques fondamentales
Le problème de tournées de véhicules (Vehicle Routing Problem ­ VRP) constitue une ex­
tension naturelle du problème du voyageur de commerce (Traveling Salesman Problem – TSP)
et représente l’un des défis majeurs de l’optimisation combinatoire contemporaine. Il consiste à
déterminer un ensemble de tournées optimales pour une flotte de véhicules chargés de desservir
un ensemble de clients, tout en respectant diverses contraintes opérationnelles. [47]
Selon Laporte [48], le VRP classique peut être formellement défini sur un graphe 𝐺 =
(𝑉 , 𝐴) où 𝑉 = {0, 1, … , 𝑛} est l’ensemble des sommets et 𝐴 est l’ensemble des arcs. Le som­
met 0 représente le dépôt, tandis que les sommets restants correspondent aux clients. À chaque
client 𝑖 est associée une demande 𝑑𝑖 , et à chaque arc (𝑖, 𝑗) est associé un coût de déplacement
𝑐𝑖𝑗 . L’objectif est de déterminer un ensemble de tournées de coût minimal tel que :
• Chaque tournée commence et se termine au dépôt.
• Chaque client est visité exactement une fois par un seul véhicule.
• La demande totale servie sur chaque tournée ne dépasse pas la capacité maximale du
véhicule.
Comme le soulignent Braekers et al., le VRP se distingue par sa nature hautement combi­
natoire qui engendre une explosion exponentielle du nombre de solutions possibles avec l’aug­
mentation du nombre de clients, ce qui explique sa difficulté computationnelle intrinsèque.[49]

Les objectifs classiques dans le cadre du VRP incluent la minimisation de la distance totale
parcourue, du temps de service ou du nombre de véhicules utilisés. Les contraintes les plus
couramment prises en compte concernent la capacité des véhicules, l’unicité de la visite de
chaque client, et le retour obligatoire des véhicules au dépôt à la fin de chaque tournée.

Fig. 2.3 : Illustration d’une solution VRP.[50]

23
Chapitre 2. L’État de l’art

2.3.2 Évolution historique

L’évolution du VRP se structure en six grandes périodes, chacune marquée par des avancées
paradigmatiques et algorithmiques majeures.
La genèse (1959­1960) s’initie avec les travaux fondateurs de Dantzig et Ramser qui for­
malisent le « Truck Dispatching Problem » par programmation linéaire, établissant les bases
conceptuelles du routage de véhicules avec contraintes de capacité dans un contexte industriel
de distribution pétrolière.
La phase de développement algorithmique (1961­1970) se caractérise par l’émergence
d’heuristiques constructives, notamment l’algorithme des économies de Clarke et Wright et les
méthodes exactes de Christofides.
Durant la consolidation théorique (1971­1980), les contributions de Christofides, Mingoz­
zi et Toth (1973) ainsi que l’introduction de la relaxation lagrangienne par Fisher et Jaikumar
établissent un corpus théorique rigoureux du champ.
La diversification applicative (1981­1990) témoigne d’une explosion des variantes spécia­
lisées avec l’introduction du VRPTW par Solomon (1981), du VRP avec flotte hétérogène et
du VRP dynamique par , marquant la transition des modèles académiques vers les contraintes
opérationnelles réelles.
La révolution métaheuristique (1991­2000) constitue une rupture paradigmatique avec
l’adoption d’algorithmes génétiques, de recherche tabou et de recuit simulé, abandonnant l’opti­
malité au profit de l’efficacité computationnelle pour traiter des instances de grande dimension.
Enfin, l’ère contemporaine (2001­présent) est caractérisée par l’hybridation algorithmique
(métaheuristiques), l’intégration des dimensions temps réel et environnementales avec le VRP
dynamique et Green VRP, puis la révolution de l’intelligence artificielle incorporant appren­
tissage par renforcement, réseaux de neurones et approches end­to­end, ouvrant la voie vers
l’optimisation autonome et l’intégration IoT.

Fig. 2.4 : Le processus de croissance du VRP.[51]

24
Chapitre 2. L’État de l’art

2.3.3 La configuration fondamentale du VRP

La configuration géographiques et topologiques
Données de localisation

• Coordonnées : La géolocalisation précise des points constitue la base spatiale du VRP.

Chaque client et dépôt est défini par des coordonnées (𝑥𝑖 , 𝑦𝑖 ) dans un système de réfé­
rence bidimensionnel. La précision de ces coordonnées, généralement obtenue par GPS,
influence directement la qualité des solutions d’optimisation, notamment en environne­
ment urbain dense où de faibles écarts peuvent générer des différences significatives de
temps de parcours.

• Type d’espace : L’espace euclidien (métrique 𝐿2 ) facilite l’application d’heuristiques

géométriques et garantit l’inégalité triangulaire. L’espace de Manhattan (métrique 𝐿1 )
convient aux réseaux urbains orthogonaux. Le réseau routier réel, modélisé comme graphe
pondéré, capture fidèlement les contraintes opérationnelles mais nécessite des algorithmes
afin de calculer les plus courts chemins.

• Matrice de distances : Cette structure bidimensionnelle encapsule les coûts de déplace­

ment entre chaque paire de points. Elle peut être symétrique (𝑑𝑖𝑗 = 𝑑𝑗𝑖 ) ou asymétrique
selon les conditions de circulation.
Le choix de la métrique est crucial : distances euclidiennes pour une approximation simple,
distances de Manhattan pour les grilles urbaines, ou distances réelles via APIs pour une
fidélité optimale au terrain.

Topologie du réseau

• Structure : Les environnements urbains se caractérisent par une forte densité de points
et des temps de parcours variables, favorisant les tournées compactes mais complexi­
fiant l’optimisation. Les environnements ruraux présentent une faible densité avec des
distances importantes mais des temps plus prévisibles, privilégiant les stratégies globales.
Les réseaux mixtes nécessitent des approches hybrides adaptatives.

• Contraintes de circulation : Les sens uniques créent des asymétries dans la matrice de
distances et compliquent les opérations d’amélioration locale. Les restrictions temporelles
(zones piétonnes, livraisons nocturnes) introduisent une dimension spatio­temporelle. Les
limitations de tonnage ou gabarit génèrent des sous­réseaux différenciés selon les types
de véhicules.

• Variabilité temporelle : Les embouteillages introduisent une dépendance temporelle des

coûts de transport, transformant le problème statique en problème dynamique. Cette varia­
bilité peut être traitée par modélisation déterministe (temps moyens), stochastique (dis­
tributions de probabilité) ou robuste (optimisation du pire cas). Les conditions météo­
rologiques ajoutent une incertitude supplémentaire nécessitant souvent une planification
dynamique.

25
Chapitre 2. L’État de l’art

La configuration temporelle
Horizons de planification
• Horizon court : Cette perspective journalière permet une modélisation précise des contraintes
opérationnelles tout en maintenant une complexité calculatoire gérable pour les instances
de taille réaliste.
• Horizon moyen : L’horizon hebdomadaire introduit des considérations d’équilibrage des
charges de travail et de régularité de service. Cette échelle temporelle nécessite souvent
l’intégration de contraintes de fairness et de considérations stratégiques dans la fonction
objectif.
• Horizon long : L’horizon mensuel ou saisonnier relève davantage de la planification
stratégique et intègre des variations de demande cycliques. Ces modèles long terme né­
cessitent généralement des approches hiérarchiques décomposant le problème en sous­
problèmes de granularité temporelle différente.

Paramètres temporels
• Matrice des temps :constitue la structure fondamentale définissant les durées de dépla­
cement entre tous les points du réseau. Cette matrice symétrique ou asymétrique selon le
contexte (sens uniques, conditions de circulation différentielles) encapsule les contraintes
de connectivité temporelle du problème. Chaque élément 𝑡(𝑖, 𝑗) représente le temps re­
quis pour se déplacer du point 𝑖 vers le point 𝑗, intégrant potentiellement les conditions
de trafic, la topographie du réseau routier, et les restrictions de circulation spécifiques à
chaque arc du graphe sous­jacent.
• La durée maximale des tournées : Reflète les réglementations du travail et les contraintes
physiologiques des conducteurs. Cette contrainte impose une borne supérieure sur la du­
rée totale de chaque route, influençant directement le nombre minimal de véhicules né­
cessaires.
• Les fenêtres de service : Représentent les créneaux temporels durant lesquels le service
peut être effectué chez chaque client.
• Les temps de service : Correspondent aux durées opérationnelles nécessaires pour effec­
tuer les opérations de chargement, déchargement ou prestation de service à chaque client.
Ces paramètres déterministes ou stochastiques influencent la faisabilité temporelle des
séquences de visite.

La configuration de la flotte
Caractéristiques des véhicules
• La capacité des véhicules : Constitue la contrainte de ressource principale dans la plupart
des variantes du VRP. Cette limitation peut être unidimensionnelle (poids maximal) ou
multidimensionnelle (poids et volume simultanément).
• La structure de coûts : Comprend généralement une composante fixe (coût d’activation
du véhicule) et une composante variable proportionnelle à la distance parcourue. Cette
dichotomie influence l’arbitrage entre le nombre de véhicules utilisés et la longueur totale
des tournées.

26
Chapitre 2. L’État de l’art

• Les contraintes techniques : Incluent les restrictions d’accès dimensionnelles et les équi­
pements spécialisés requis. Ces paramètres peuvent créer des incompatibilités entre cer­
tains véhicules et certains clients.

Gestion de la flotte

• La disponibilité de la flotte : Détermine le nombre maximal de véhicules simultané­

ment utilisables. Cette contrainte de ressource influence directement la borne inférieure
du nombre de tournées nécessaires.

• Le type de la flotte : L’homogénéité de la flotte simplifie considérablement la modélisa­

tion mathématique en permettant l’utilisation de variables de décision symétriques. Les
flottes hétérogènes introduisent des dimensions supplémentaires dans l’espace de déci­
sion.

• La localisation initiale des véhicules : Influence les coûts de repositionnement et peut

justifier l’adoption de modèles multi­dépôts lorsque les véhicules sont géographiquement
dispersés en début de période.

La configuration des clients

• La nature des demandes : Détermine le type de flux logistique, les demandes de livrai­
son créent un flux sortant du dépôt, les demandes de collecte génèrent un flux entrant,
tandis que les demandes mixtes nécessitent une gestion simultanée des deux flux avec des
contraintes de compatibilité spatiale et temporelle.

• La quantification des demandes : Peut être déterministe ou stochastique. Les approches

stochastiques nécessitent des méthodes de programmation ou d’optimisation robuste pour
maintenir la faisabilité des solutions dans un environnement incertain.

• La priorisation des clients : Introduit une hiérarchisation dans la satisfaction des de­
mandes. Cette différenciation se traduira par des contraintes strictes de service pour les
clients prioritaires.

2.3.4 Les variantes du VRP

L’évolution du problème de tournées de véhicules reflète les besoins croissants et la com­
plexification des systèmes de distribution modernes :

CVRP : le VRP classique

Le VRP a été formellement introduit par Dantzig et Ramser dans leur article fondateur « Le
problème de la répartition des camions ». Ils y présentent ce qui est maintenant connu comme le
CVRP (Capacitated Vehicle Routing Problem)[52] :

• Objectif : Minimiser la distance totale parcourue par une flotte de véhicules identiques.

• Contraintes : Chaque client doit être visité exactement une fois et la capacité des vé­
hicules ne doit pas être dépassée. Tous les véhicules partent d’un dépôt central et y re­
viennent.

27
Chapitre 2. L’État de l’art

VRPTW : le VRP avec contraintes de temps

Le VRPTW Le VRPTW (Vehicle Routing Problem with Time Windows) a émergé avec les
travaux de Pullen et Webb , puis a été formalisé par Savelsbergh. Cette variante ajoute des
fenêtres temporelles pendant lesquelles chaque client doit être servi, reflétant les contraintes
réelles de livraison. Mathématiquement, pour chaque client 𝑖, on définit [𝑎𝑖 , 𝑏𝑖 ] comme la fenêtre
de temps durant laquelle le service doit commencer.

Le VRP avec temps de service Le VRP avec temps de service constitue une extension natu­
relle du VRPTW où l’on modélise explicitement le temps passé chez chaque client pour réaliser
le service demandé. Selon les travaux de Baker, ces temps étaient généralement traités comme
une constante et non comme une variable à optimiser. Bien que Solomon ait formalisé la prise en
compte des temps de service dans son benchmark fondateur sur le VRPTW. Dans sa formulation,
chaque client 𝑖 est associé à :

• Une fenêtre temporelle [𝑎𝑖 , 𝑏𝑖 ].

• Un temps de service 𝑠𝑖 .

Le temps de service 𝑠𝑖 représente la durée incompressible pendant laquelle le véhicule doit

rester chez le client 𝑖 pour effectuer la manutention des marchandises ou toute autre opération
requise.[53]

MDVRP : le VRP avec Multi­Depot

Le problème de tournées de véhicules à dépôts multiples (MDVRP) représente une exten­
sion naturelle et précoce du VRP classique. Il a été conceptualisé initialement par Tillman, puis
formalisé mathématiquement par Wren et Holliday.[54]
Dans cette variante, la flotte de véhicules est répartie entre plusieurs dépôts, et chaque tournée
doit commencer et se terminer au même dépôt. L’optimisation comporte alors deux niveaux de
décision interdépendants :

• L’affectation des clients aux dépôts.

• La construction des tournées pour chaque dépôt.

HVRP : le VRP avec flotte hétérogène

Le HVRP considère une flotte de véhicules aux caractéristiques différentes (capacité, vitesse,
coûts). Cette variante reflète la diversité des flottes dans les applications réelles et complexifie
considérablement la résolution.[55]

VRPSD : le VRP avec demandes stochastiques

Le VRPSD (Vehicle Routing Problem with Stochastic Demands) a été formalisé par Dror et
Trudeau, puis développé conceptuellement par Stewart et Golden. Dans cette variante, les de­
mandes des clients ne sont pas connues avec certitude au moment de la planification mais suivent
une distribution de probabilité. Cette incertitude reflète de nombreuses situations réelles : varia­
bilité des commandes, incertitude sur les quantités à collecter, ou fluctuations saisonnières.[56]

28
Chapitre 2. L’État de l’art

VRPPD : le VRP avec livraisons et collectes

Le VRPPD (Vehicle Routing Problem with Pickup and Delivery) a été formalisé par Psaraf­
tis. Il considère que certains clients requièrent une livraison tandis que d’autres nécessitent une
collecte, introduisant des contraintes de précédence.[57]

SDVRP : le VRP avec livraisons fractionnées

Le SDVRP (Split Delivery VRP), introduit par Dror et Trudeau, autorise la desserte d’un
client par plusieurs véhicules, permettant des économies significatives lorsque les demandes
sont proches de la capacité des véhicules.[58]

PVRP : le VRP avec période

Le PVRP (Periodic VRP), formalisé par Christofides et Beasley et développé par Russell,
Igo, Beltrami et Bodin, étend l’horizon de planification à plusieurs jours. Les clients doivent
être visités un certain nombre de fois durant cette période selon des schémas prédéfinis.[59]

VRPMT : le VRP avec tournées multiples

Le VRPMT (Vehicle Routing Problem with Multiple Trips), parfois appelé MTVRP, a été
introduit conceptuellement par Fleischmann puis formalisé par Taillard et al., Cette variante
considère qu’un même véhicule peut effectuer plusieurs tournées au cours d’une période de
planification (typiquement une journée).
Chaque tournée doit commencer et se terminer au dépôt pour permettre le rechargement du
véhicule, mais un même véhicule peut enchaîner plusieurs tournées sous réserve de respecter
ses contraintes de temps de travail.[60]

SVRP : le VRP avec stochastique

Le SVRP (Stochastic VRP), exploré par Gendreau et al. et théorisé dès (1991) par Stewart
et Golden, intègre l’incertitude dans différents paramètres du problème : demandes aléatoires,
temps de service variables ou temps de trajet stochastiques.

DVRP : le VRP avec dynamisme

Le DVRP (Dynamic VRP) a été formalisé par Psaraftis pour refléter les environnements où
l’information (nouveaux clients, modifications des demandes) est révélée en temps réel pendant
l’exécution des tournées.[61]

VRPB : le VRP avec contraintes de chargement

Le VRPB (VRP with Backhauls) distingue les clients de livraison (linehauls) des clients de
collecte (backhauls) avec la contrainte que toutes les livraisons doivent être effectuées avant les
collectes.[62]

GVRP : le VRP vert

Le GVRP (Green VRP), introduit conceptuellement par Palmer et développé par Bektas et
Laporte, intègre des objectifs environnementaux comme la minimisation des émissions de CO2
ou la consommation de carburant.[63]

29
Chapitre 2. L’État de l’art

EVRP : le VRP avec véhicules électriques

L’EVRP (Electric VRP), développé par Conrad et Figliozzi, prend en compte les contraintes
spécifiques aux véhicules électriques : autonomie limitée, temps de recharge, localisation des
stations de recharge.

VRPP : le VRP avec profits

Le VRPP (VRP with Profits), formalisé par Archetti et al., associe chaque client à un profit.
L’objectif consiste alors à maximiser le profit total collecté tout en minimisant les coûts de
transport.[64]

VRPD : le VRP avec drones

Le VRPD (VRP with Drones), conceptualisé par Murray et Chu, intègre l’utilisation com­
binée de véhicules traditionnels et de drones pour effectuer les livraisons, ouvrant de nouvelles
perspectives pour la livraison du dernier kilomètre.[65]

VRPCS : le VRP avec crowdsourcing

Le VRPCS, formalisé par Arslan et al., intègre l’utilisation de livreurs occasionnels (parti­
culiers) en complément d’une flotte dédiée, reflétant l’émergence de l’économie collaborative.

CVRP : le VRP avec livraison sans contact

Émergé durant la pandémie de COVID­19, le CVRP (Contactless VRP) intègre des contraintes
de distanciation sociale et de livraison sans contact, reflétant les adaptations logistiques néces­
saires en période de crise sanitaire.

AVRP : le VRP avec véhicules autonomes

L’AVRP (Autonomous VRP), développé par Bazzan et Cetin, considère l’utilisation de vé­
hicules autonomes avec leurs contraintes spécifiques : coordination entre véhicules, limitations
technologiques, et réglementations émergentes.

MEVRP : le VRP multi­échelon avec hubs mobiles

Le MEVRP (Multi­Echelon VRP) avec hubs mobiles, développé par Perboli et al., envisage
une logistique à plusieurs niveaux où des véhicules de grande capacité alimentent des hubs
mobiles qui, à leur tour, desservent les clients finaux via des véhicules légers ou des solutions
de micromobilité.

SRVRP : le VRP durable et résilient

Le SRVRP (Sustainable and Resilient VRP), exploré par Vidal et al., intègre simultanément
des objectifs de durabilité environnementale, de résilience face aux perturbations (catastrophes
naturelles, pannes) et d’optimisation économique.

30
Chapitre 2. L’État de l’art

2.4 Synthèse et positionnement de notre travail par rapport

à l’état de l’art
Le diagnostic réalisé, les limites identifiées couplées à l’identification des contraintes opé­
rationnelles et à la synthèse théorique du VRP incluant ses fondements, ses déclinaisons et les
méthodes de résolution, permet de caractériser les paramètres distinctifs du problème de distri­
bution de la SARL DJE­AGRO, telles que la diversité des véhicules (hétérogénéité de la flotte),
la multiplicité des tournées par véhicule, la limitation des quantités livrées par la capacité des
véhicules, les contraintes temporelles imposées par les clients, ainsi que le temps de service spé­
cifique à chaque client. Cette configuration relève d’une combinaison de variantes du VRP telle
que le HVRP , le MTVRP, le CVRP, le VRPTW avec fenêtres du temps et avec temps service.
L’implémentation d’un modèle VRP dans le contexte de DJE­AGRO s’inscrit dans une lo­
gique d’amélioration progressive et pragmatique de la performance du système de distribution.
L’objectif n’est pas de substituer brutalement l’expertise humaine par des outils technologiques,
mais bien de valoriser cette expertise en la structurant autour de modèles d’optimisation concrets
au fur et à mesure de la croissance de l’activité, des disparités dans la consommation accrue de
carburant, et une augmentation des coûts de transport associés aux tournées.

2.5 Conclusion
Ce chapitre a permis d’explorer le problème du VRP, en abordant ses définitions fondamen­
tales, son évolution historique, ses paramètres clés ainsi que ses principales variantes. L’analyse
a mis en lumière la nature intrinsèquement combinatoire de ce problème d’optimisation, dont
les ramifications pratiques et théoriques appellent des méthodologies de résolution adaptées.

Le chapitre suivant sera consacré à l’examen systématique des approches de résolution du

VRP. Structuré autour des deux grands paradigmes fondamentaux que sont les méthodes exactes,
les méthodes approchées.

31
Chapitre 3

Les approches de résolution

32
Chapitre 3. Les approches de résolution

3.1 Introduction
La résolution du Vehicle Routing Problem (VRP), caractérisé par sa complexité NP­difficile,
constitue un enjeu de la recherche opérationnelle, comme démontré par les travaux fondateurs
de Lenstra et Rinnooy Kan. L’explosion combinatoire inhérente à ce problème d’optimisation
impose le développement de stratégies méthodologiques, chacune présentant des compromis
entre qualité de solution, temps de calcul et faisabilité concrète.[66]
La méthodologie développée pour résoudre le VRP et ses variantes s’articule autour de deux
paradigmes fondamentaux :

• Méthodes exactes : ces méthodes garantissent l’obtention d’une solution optimale pour
une instance donnée du problème d’optimisation, en explorant systématiquement l’espace
des solutions possibles.

• Méthodes approchées : ces approches, qui visent à produire des solutions de bonne qua­
lité dans un temps acceptable, se subdivisent en deux sous­catégories :

– Heuristiques : méthodes basées sur des régles pour construire ou améliorer des so­
lutions rapidement, sans garantie d’optimalité.
– Métaheuristiques : approches plus élaborées, combinant des mécanismes de re­
cherche locale et globale pour explorer efficacement l’espace des solutions et trouver
des résultats proches de l’optimum.

Cette dualité méthodologique reflète le défi de concilier la rigueur théorique, visant l’opti­
malité, avec les besoins concrets du monde industriel, où l’efficacité computationnelle prime.
Ce chapitre propose une analyse structurée des principales approches de résolution du VRP,
examinant leurs classifications, leurs fondements théoriques et leurs performances computation­
nelles.

3.2 Taxonomie des méthodes de résolution du VRP

La présente taxonomie synthétise les principales stratégies de résolution en distinguant les
méthodes exactes et approchées.

33
Chapitre 3. Les approches de résolution

Fig. 3.1 : Les Méthodes de résolution du VRP.[67]

3.2.1 Méthodes exactes

Les méthodes exactes visent à garantir l’optimalité de la solution obtenue, cependant leur
application est souvent limitée. Cette complexité provient du fait que le nombre de combinai­
sons de tournées possibles augmente de manière exponentielle avec la dimension du problème.
Par conséquent, l’efficacité de ces algorithmes n’est garantie que pour les instances de petite
taille. En revanche, pour les problèmes de plus grande échelle, les méthodes exactes deviennent
rapidement impraticables en termes de temps de calcul.
Les approches exactes les plus notables incluent :

Les méthodes de recherche arborescentes

Cette méthode représente une technique d’exploration exhaustive de l’arbre de recherche
qui combine l’énumération complète avec des stratégies d’élagage. Cette méthode décompose
systématiquement le problème en sous­problèmes plus petits, créant ainsi une structure arbores­
cente où chaque nœud correspond à une solution partielle.
Le processus d’élagage s’appuie sur le calcul de bornes inférieures pour chaque nœud de
l’arbre. Lorsque la borne inférieure d’un nœud dépasse la valeur de la meilleure solution com­
plète trouvée jusqu’à présent, toute la branche correspondante peut être éliminée sans explora­
tion ultérieure. Les bornes inférieures sont généralement obtenues par la résolution de relaxa­
tions continues du problème original ou par l’application d’heuristiques. L’efficacité de cette
approche dépend fortement de la qualité des bornes calculées et des stratégies de branchement
employées. Des techniques de branchement, telles que le branchement sur les variables de flot
ou sur les ensembles de clients, permettent d’améliorer considérablement les performances.

34
Chapitre 3. Les approches de résolution

Fig. 3.2 : Illustration de l’algorithme séquentiel de séparation et évaluation.[68]

La programmation dynamique
La programmation dynamique offre une approche alternative pour certaines variantes du
VRP, particulièrement efficace pour les problèmes présentant une structure de sous­problèmes
optimaux. L’algorithme de Held­Karp, initialement développé pour le problème du voyageur de
commerce, peut être adapté au contexte du VRP.
Cette approche décompose le problème en sous­problèmes de taille réduite, résolus de ma­
nière récursive. L’état du système est caractérisé par l’ensemble des clients déjà visités et la
position actuelle du véhicule. Malgré sa garantie d’optimalité, la complexité exponentielle en
espace et en temps limite son applicabilité aux instances de petite taille.[69].

La programmation linéaire en nombres entiers (MILP)

La formulation du VRP sous forme de programme linéaire en nombres entiers (PLNE) per­
met l’utilisation d’algorithmes tels que la méthode de branch­and­bound et ses variantes. Plu­
sieurs formulations mathématiques ont été proposées dans la littérature, notamment :

• Formulation à deux indices : utilise des variables binaires 𝑥𝑖𝑗 indiquant si l’arc (𝑖, 𝑗) est
emprunté dans la solution optimale.

• Formulation à trois indices : introduit une dimension supplémentaire pour identifier

explicitement les véhicules 𝑥𝑖𝑗𝑘 .

L’efficacité de ces formulations dépend de la qualité de la relaxation linéaire et de la présence

de contraintes de coupes valides. Les algorithmes de branch­and­cut intègrent dynamiquement
des inégalités valides pour renforcer la formulation et accélérer la convergence.
Des solveurs commerciaux comme CPLEX, Gurobi ou FICO XPRESS peuvent résoudre ef­
ficacement ces formulations pour des instances comportant jusqu’à quelques dizaines de clients
[70].

35
Chapitre 3. Les approches de résolution

3.2.2 Méthodes approximatives

Face aux limitations des méthodes exactes, les approches heuristiques et métaheuristiques
constituent des alternatives pragmatiques pour traiter des instances de taille réelle dans des temps
de calcul raisonnables.

[Link] Heuristiques
Les heuristiques peuvent être classées deux paradigmes selon leur principe de construction
ou d’amélioration des solutions :

Heuristiques constructives : élaborent progressivement une solution admissible, et on catégo­

rise :
• Heuristiques des gains : proposée par Clarke et Wright, cette heuristique calcule pour
chaque paire de clients (𝑖, 𝑗) un gain 𝑠𝑖𝑗 = 𝑑0𝑖 + 𝑑0𝑗 − 𝑑𝑖𝑗 , où 𝑑𝑖𝑗 représente la distance
entre les clients 𝑖 et 𝑗, et 0 désigne le dépôt. Les gains sont triés par ordre décroissant,
et les fusions de routes sont effectuées selon cette priorité, sous réserve de respecter les
contraintes de capacité et autres restrictions opérationnelles.
• Heuristiques d’insertion : utilisées pour générer des solutions initiales dans les VRP et
leurs variantes. Elles procèdent en insérant les clients un à un dans des tournées partielle­
ment construites, tout en respectant les contraintes du problème.[71]
– Insertion séquentielle : consiste à compléter intégralement une tournée avant de com­
mencer la suivante. Elle est simple à implémenter et souvent efficace dans les cas
de faible densité de clients ou de contraintes serrées.
– Insertion parallèle : repose sur la construction des plusieurs tournées simultanément.
À chaque étape, le client à insérer est affecté à la tournée et à la position où son
insertion est la plus avantageuse selon un critère donné.
Les critères d’insertion peuvent être basés sur :
– Distance­Temps : l’optimisation spatio­temporelle.
– Coût­Faisabilité : l’intégration de la faisabilité des contraintes opérationnelles mul­
tiples, tout en optimisant l’objectif économique.
– Urgence­Distance : le compromis entre priorité et efficacité optimise le niveau de
service tout en contrôlant les coûts.
– Regret­Coût : la prise en compte du regret évite les décisions myopes.
Parmi les approches les plus reconnues figure l’heuristique d’insertion I1 développée par
Solomon. Elle s’inscrit dans la catégorie des insertions séquentielles et se fonde sur une
logique en deux étapes :
1. Initialisation : une première tournée est créée avec un client germe, souvent choisi
comme étant le plus éloigné du dépôt ou celui dont la fenêtre de temps commence
le plus tôt.
2. Insertion séquentielle : les clients restants sont insérés un par un à la position de la
tournée en cours qui minimise le coût d’insertion, tout en respectant les contraintes
de capacité et de fenêtres de temps. Lorsqu’aucune insertion n’est possible dans la
tournée actuelle, une nouvelle tournée est initiée.

36
Chapitre 3. Les approches de résolution

La variante I1 privilégie des insertions économes en distance et pénalise fortement les

violations temporelles. Elle est adaptée aux cas où le respect strict des contraintes tempo­
relles est prioritaire.

Solomon a également proposé des variantes de cette heuristique :

– I2 : partage le même mécanisme d’insertion séquentielle que I1, mais adopte une
fonction d’évaluation différente, centrée sur le coût marginal moyen introduit par
l’insertion du client. Plus précisément, pour chaque position d’insertion possible
entre les clients 𝑖 et 𝑗, le coût est défini comme suit :
𝑐𝑖𝑘 + 𝑐𝑘𝑗 − 𝑐𝑖𝑗
𝐶(𝑖, 𝑗, 𝑘) = (3.1)
1+𝑛
où :

* 𝑘 : le client candidat à l’insertion entre 𝑖 et 𝑗,

* 𝑛 : le nombre actuel de clients dans la tournée considérée.
Cette formulation met l’accent sur l’augmentation relative de la distance totale de
la tournée, en pénalisant davantage les insertions qui allongent fortement la tournée
existante. En ce sens, l’heuristique I2 tend à construire des tournées plus compactes
et équilibrées en distance, au détriment d’un respect strict des fenêtres de temps.

– I3 : repose sur le concept de regret, qui consiste à sélectionner le client ayant l’écart
le plus important entre sa meilleure et sa deuxième meilleure position d’insertion,
plutôt que de simplement choisir celui dont l’insertion est la moins coûteuse. For­
mellement, pour chaque client non inséré 𝑘, on évalue :

Regret(𝑘) = 𝐶2e meilleur (𝑘) − 𝐶meilleur (𝑘) (3.2)

Le client avec le regret le plus élevé est priorisé et inséré à sa position optimale (celle
correspondant à 𝐶meilleur (𝑘)).

Méthodes en deux phases : cette approche décompose le problème en deux sous­problèmes

traités séquentiellement :

• Phase de groupage (clustering) : affectation des clients aux véhicules sans considération
de l’ordre de visite.

• Phase de routage (routing) : détermination de l’ordre optimal de visite pour chaque clus­
ter.

Route en premier, Groupe en second : construit initialement une route géante visitant tous
les clients, puis la décompose en tournées respectant les contraintes de capacité.
Groupe en premier, Route en second : forme primitivement des groupes de clients respec­
tant les contraintes, puis optimise l’ordre de visite au sein de chaque groupe, typiquement par
résolution d’un problème des tournées de véhicules.

37
Chapitre 3. Les approches de résolution

Heuristiques d’amélioration : les heuristiques locales, ou méthodes de recherche locale, consti­

tuent une classe fondamentale d’algorithmes d’optimisation qui opèrent selon un paradigme ité­
ratif d’amélioration progressive. Elles partent d’une solution initiale complète et cherchent à
l’améliorer en explorant son voisinage. Cette approche garantit une convergence monotone vers
un optimum local, bien que l’optimum global ne soit pas nécessairement atteint [72].

• Principes Fondamentaux
Voisinage : le principe central des heuristiques d’amélioration repose sur la définition
formelle d’un voisinage 𝑁 (𝑠) pour toute solution 𝑠 de l’espace de recherche 𝑆. Le voisi­
nage 𝑁 (𝑠) ⊆ 𝑆 représente l’ensemble des solutions accessibles depuis 𝑠 par l’application
d’une transformation élémentaire, communément appelée mouvement ou opérateur de
voisinage.

Fig. 3.3 : Principe de la recherche locale.[73]

Exploration : l’exploration du voisinage peut suivre différentes stratégies, chacune pré­

sentant des caractéristiques distinctes en termes de qualité de solution et de complexité
computationnelle.

– Amélioration du Premier Type : consiste à accepter le premier mouvement rencon­

tré qui améliore strictement la valeur de la fonction objectif. L’algorithme parcourt
𝑁 (𝑠) selon un ordre prédéfini et s’arrête dès qu’une solution 𝑠′ ∈ 𝑁 (𝑠) vérifie
𝑓(𝑠′ ) < 𝑓(𝑠) pour un problème de minimisation.
– Amélioration du Meilleur Type : explore exhaustivement l’ensemble du voisinage
𝑁 (𝑠) pour identifier le mouvement optimal : 𝑠∗ = arg min{𝑓(𝑠′ ) ∶ 𝑠′ ∈ 𝑁 (𝑠)}.
Cette stratégie garantit la sélection du mouvement le plus prometteur à chaque ité­
ration.

• Les opérateurs essentiels :

Intra­tournées : Ces opérateurs modifient le séquencement des clients au sein d’une
même tournée :

– 2­opt : supprime deux arêtes non adjacentes et reconnecte le tour différemment pour
éliminer les croisements.
– 3­opt : supprime trois arêtes et explore les reconnexions possibles.
– Or­opt : déplace une chaîne de 1, 2 ou 3 clients consécutifs vers une nouvelle posi­
tion dans la tournée.
– k­opt : généralisation flexible des opérateurs précédents, supprimant 𝑘 arêtes simul­
tanément.

38
Chapitre 3. Les approches de résolution

Inter­tournées : Ces opérateurs déplacent des clients entre différentes tournées :

– Relocate : déplace un client d’une tournée à une autre.

– Exchange/Swap : échange la position de deux clients appartenant à des tournées
différentes.
– Cross : échange des segments terminaux entre deux tournées.
– GENI : insertion généralisée avec réoptimisation des tournées.

[Link]. Métaheuristiques
Les métaheuristiques constituent des stratégies algorithmiques de haut niveau conçues pour
dépasser les limites des heuristiques locales classiques, notamment leur tendance à se bloquer
dans des optima locaux. Elles adoptent des mécanismes de diversification et d’intensification
pour explorer efficacement l’espace de recherche, en combinant l’exploration globale et l’ex­
ploitation locale, afin de converger vers les optima globaux.

Fig. 3.4 : Représentation simplifiée d’une approche métaheuristique.[74]

Métaheuristiques à solution unique : cette classe d’algorithmes maintient et améliore itérati­

vement une solution unique à travers des voisinages successifs guidées par des mécanismes de
contrôle déterminés.

• Recuit simulé (Simulated Annealing) : inspiré du processus physique de recuit métal­

lurgique, le recuit simulé introduit un mécanisme probabiliste d’acceptation de solutions
dégradantes, contrôlé par un paramètre de température décroissant [75].

– La Température (𝑇) : c’est un paramètre de contrôle qui diminue au cours de la re­

cherche. Une température initiale 𝑇0 élevée autorise une forte probabilité d’accepter
de mauvaises solutions, favorisant une large exploration.
– Schéma de refroidissement : la température suit généralement une décroissance
𝑇0
géométrique 𝑇𝑘+1 = 𝛼 ⋅ 𝑇𝑘 avec 𝛼 ∈]0, 1[, ou logarithmique 𝑇𝑘 = log(1+𝑘) .
– Mécanisme d’acceptation (le critère d’acceptation) : une solution voisine 𝑆 ′ de
coût 𝐶 ′ est comparée à la solution actuelle 𝑆 de coût 𝐶. Si Δ = 𝐶 ′ − 𝐶 < 0, la
nouvelle solution est toujours acceptée. Sinon, elle est acceptée avec la probabilité
de Metropolis :
Δ
𝑃 (acceptation) = exp (− ) . (3.3)
𝑇
– Condition d’Arrêt : l’algorithme s’arrête lorsque la température atteint un seuil très
bas (”gel”) ou après un nombre défini d’itérations.

39
Chapitre 3. Les approches de résolution

– Propriétés théoriques : sous certaines conditions (refroidissement suffisamment

lent), convergence asymptotique garantie vers l’optimum global.

Algorithm 1 Pseudo­code du recuit simulé

(a) Phase d’initialisation
1 : Générer une solution initiale 𝑆0 et une température initiale 𝑇0
2 : Initialiser la meilleure solution trouvée 𝑆 ∗ ← 𝑆0

(b) Phase d’amélioration

3: répéter
4: répéter
5: 𝑆 ← solution courante
6: Générer un voisinage 𝑉 (𝑆)
7: Sélectionner aléatoirement un voisin 𝑆 ′ ∈ 𝑉 (𝑆)
8: Calculer Δ𝐸 ← 𝑓(𝑆 ′ ) − 𝑓(𝑆)
9: si Δ𝐸 ≤ 0 faire
10 : 𝑆 ← 𝑆′ ▷ Accepter la nouvelle solution qui est meilleure
11 : si 𝑓(𝑆 ′ ) ≤ 𝑓(𝑆 ∗ ) faire
12 : 𝑆∗ ← 𝑆′ ▷ Mettre à jour la meilleure solution globale
13 : fin si
14 : sinon
15 : 𝑆 ← 𝑆 ′ avec la probabilité exp(− Δ𝐸 𝑇 ) ▷ Accepter une moins bonne solution
16 : fin si
17 : jusqu’à Fin de Palier (nombre d’itérations à température constante)
18 : Modifier la température 𝑇 (refroidissement, e.g., 𝑇 ← 𝛼 ⋅ 𝑇)
19 : jusqu’à Critère d’arrêt satisfait (e.g., température finale atteinte)
20 : Renvoyer 𝑆 ∗

• Recherche tabou (Tabu Search) : utilise une mémoire adaptative pour échapper le retour
vers des solutions récemment visitées et guide l’exploration vers des régions inexplorées
de l’espace de recherche. Cette architecture algorithmique peut conduire à des résultats
supérieurs à ceux obtenus par des méthodes purement aléatoires ou déterministes.
Composants fondamentaux :

– Liste tabou : Structure mémorisant les attributs des mouvements interdits.

– Durée tabou : Paramètre contrôlant la durée d’interdiction.
– Critères d’aspiration : Règles permettant de lever l’interdiction sous certaines condi­
tions.

Stratégies de mémoire : le mécanisme central réside dans l’implémentation d’une struc­

ture mémoire multi­niveaux comprenant :

– Mémoire à court terme : liste tabou classique.

– Mémoire à moyen terme : stratégies d’intensification basées sur la fréquence.
– Mémoire à long terme : mécanismes de diversification et de redémarrage.

40
Chapitre 3. Les approches de résolution

Métaheuristiques basées sur la population : cette catégorie regroupe les algorithmes qui font
évoluer simultanément plusieurs solutions à travers des mécanismes inspirés de phénomènes
naturels. L’exploitation d’une population de solutions permet d’équilibrer exploration et exploi­
tation tout en maintenant la diversité nécessaire à l’évitement des optima locaux.

• Algorithmes génétiques : inspirés des mécanismes de l’évolution biologique. Ces al­

gorithmes s’appuient sur les principes darwiniens de sélection naturelle, de croisement
(recombinaison) et de mutation sur une population codée afin d’explorer l’espace des so­
lutions d’un problème d’optimisation donné.

Principe de Fonctionnement

– Population : ensemble de solutions candidates (individus)

– Chromosome : représentation codée d’une solution
– Fitness : qualité d’une solution
– Génération : itération de l’algorithme

Opérateurs Génétiques

– Sélection (proportionnelle à la fitness, par tournoi, par rang)

– Croisement (un point, deux points, uniforme, combine les caractéristiques de deux
parents)
– Mutation (modification aléatoire des gènes, maintient la diversité génétique)

Fig. 3.5 : Principe de fonctionnement d’un algorithme génétique.[73]

41
Chapitre 3. Les approches de résolution

• Optimisation par colonies de fourmis : l’optimisation par colonies de fourmis (Ant Co­
lony Optimization – ACO) est une métaheuristique inspirée du comportement collectif des
fourmis réelles dans leur recherche de nourriture. Cette approche exploite le principe de
stigmergie.

Principe de Fonctionnement :
Les fourmis déposent des phéromones sur leur passage, créant des pistes chimiques. Les
chemins les plus courts accumulent davantage de phéromones car ils sont parcourus plus
fréquemment, créant un mécanisme d’auto­renforcement positif qui guide la colonie vers
les solutions optimales.

Modélisation Algorithmique

– Initialisation : Placement des fourmis artificielles.

– Construction : Chaque fourmi construit une solution en suivant les probabilités
basées sur les phéromones.
– Mise à jour : Dépôt de phéromones proportionnel à la qualité des solutions.
– Évaporation : Réduction progressive des phéromones.
– Répétition : Jusqu’à convergence.

Fig. 3.6 : Effet de la coupure d’une piste de phéromone.[76]

3.3 Conclusion
Ce chapitre a détaillé la méthodologie de résolution des problématiques de tournées de véhi­
cules, fondée sur les méthodes étudiées précédemment. Le chapitre suivant se consacre à l’im­
plémentation de cette méthodologie en s’articulant autour de la modélisation mathématique et de
la mobilisation des outils d’optimisation les plus appropriés à notre cas concret de DJE­AGRO,
visant à atteindre l’objectif de notre étude.

42
Chapitre 4

Résolution, Implémentation et
Interprétation des résultats expérimentaux

43
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

4.1 Introduction
Ce chapitre constitue le pivot de notre travail, en faisant la liaison entre les fondements
théoriques développés précédemment et leur mise en œuvre concrète.

Initialement, nous présenterons la démarche méthodologique de résolution que nous avons

adoptée, fondée sur une stratégie hiérarchisée en trois phases (construction, amélioration locale,
et métaheuristique), justifiée par la nature du problème. Par la suite nous décrirons l’environ­
nement d’implémentation technique, les données opérationnelles et les paramètres qui ont servi
de base à nos expérimentations.

En conclusion de cette démarche, nous procéderons à l’interprétation et à l’analyse appro­

fondie des résultats obtenus. Des comparaisons rigoureuses entre l’état réel du système et celle
issue du processus d’optimisation, afin d’évaluer les gains en termes de coûts, de distance, d’ef­
ficacité de la flotte et de qualité de service.

4.2 La démarche méthodologique de résolution

La résolution du problème de la SARL DJE­AGRO, repose sur une approche structurée,
commençant par une modélisation formelle, suivie d’une heuristique de construction basée sur
l’insertion, puis d’une heuristique d’amélioration locale, et enfin une métaheuristique.

4.2.1 Modélisation Formelle du Problème

Afin de formaliser rigoureusement le problème de distribution de la SARL DJE­AGRO, un
modèle mathématique est présenté ci­dessous. Ce modèle définit les ensembles, les paramètres,
les variables de décision, la fonction objectif ainsi que l’ensemble des contraintes régissant le
problème.

Notations
Ensembles
• C = {1, 2, … , 38} : ensemble des 38 clients.

• N = {0} ∪ 𝐶 : ensemble de tous les nœuds, où le nœud 0 représente le dépôt.

• V = {0, 1, … , 19} : ensemble des 20 véhicules disponibles.

• M = {1, 2, 3} : ensemble des tournées possibles par véhicule (maximum 3).

Paramètres
• 𝑞𝑖 : demande du client 𝑖 ∈ 𝐶 en kg.

• [𝑒𝑖 , 𝑙𝑖 ] : fenêtre temporelle du nœud 𝑖 ∈ 𝑁 (heure de début et de fin de service, en minutes).

• 𝑠𝑖 : temps de service requis chez le client 𝑖 ∈ 𝐶 (en minutes).

• 𝑑𝑖𝑗 : distance en km entre le nœud 𝑖 et le nœud 𝑗.

• 𝑡𝑖𝑗 : temps de trajet en minutes entre le nœud 𝑖 et le nœud 𝑗.

44
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• 𝑄𝑣 : capacité de chargement du véhicule 𝑣 ∈ 𝑉 en kg.

• 𝑐𝑣 : coût par kilomètre du véhicule 𝑣 ∈ 𝑉 (en DA/km).

• 𝛼 : temps de chargement au dépôt, fixé à 0.03 minutes/kg.

• 𝑇max : durée maximale d’une tournée, fixée à 540 minutes.

• 𝜏 : taux de remplissage minimum, fixé à 0.6 (60%).

Variables de Décision

• 𝑥𝑖𝑗𝑣𝑚 ∈ {0, 1} : variable binaire qui vaut 1 si le véhicule 𝑣 parcourt l’arc (𝑖, 𝑗) dans sa
tournée 𝑚, et 0 sinon.

• 𝑎𝑖𝑣𝑚 ≥ 0 : temps d’arrivée du véhicule 𝑣 au nœud 𝑖 pour sa tournée 𝑚.

• 𝑑0𝑣𝑚 ≥ 0 : temps de départ du véhicule v depuis le dépôt pour une tournée m validée.

• 𝑦𝑣𝑚 ∈ {0, 1} : variable binaire qui vaut 1 si le véhicule 𝑣 effectue une tournée 𝑚, et 0
sinon.

Fonction Objectif
L’objectif principal est de minimiser le coût total de distribution, qui est la somme des coûts
de toutes les tournées effectuées, chaque coût étant fonction de la distance parcourue et du coût
kilométrique du véhicule assigné.

Minimiser 𝑍 = ∑ ∑ ∑ ∑ 𝑐𝑣 ⋅ 𝑑𝑖𝑗 ⋅ 𝑥𝑖𝑗𝑣𝑚 (4.1)

𝑣∈𝑉 𝑚∈𝑀 𝑖∈𝑁 𝑗∈𝑁

Contraintes Principales
La solution doit respecter un ensemble de contraintes pour être réalisable :

• Visite unique des clients : chaque client doit être visité exactement une fois par un seul
véhicule sur une seule tournée.

∑ ∑ ∑ 𝑥𝑖𝑗𝑣𝑚 = 1, ∀𝑖 ∈ 𝐶 (4.2)
𝑣∈𝑉 𝑚∈𝑀 𝑗∈𝑁

• Conservation du flux : pour chaque tournée validée, si un véhicule arrive à un nœud

(client), il doit en repartir.

∑ 𝑥𝑖𝑗𝑣𝑚 = ∑ 𝑥𝑗𝑖𝑣𝑚 , ∀𝑖 ∈ 𝑁 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.3)

𝑗∈𝑁 𝑗∈𝑁

• Départ et retour depuis dépôt : chaque tournée validée doit commencer et se terminer
au dépôt (0).
∑ 𝑥0𝑗𝑣𝑚 = ∑ 𝑥𝑖0𝑣𝑚 = 𝑦𝑣𝑚 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.4)
𝑗∈𝐶 𝑖∈𝐶

45
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Fenêtres temporelles : pour chaque client, l’heure effective de début de service doit être
comprise à l’intérieur des bornes de sa fenêtre de temps [𝑒𝑖 , 𝑙𝑖 ].

𝑒𝑖 ⋅ ∑ 𝑥𝑖𝑗𝑣𝑚 ≤ 𝑎𝑖𝑣𝑚 ≤ 𝑙𝑖 ⋅ ∑ 𝑥𝑖𝑗𝑣𝑚 , ∀𝑖 ∈ 𝑁 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.5)

𝑗∈𝑁 𝑗∈𝑁

• Temps de départ minimal au dépôt : tout départ actif évite les attentes chez les clients.

𝑑0𝑣𝑚 ≥ 𝑒0 ⋅ 𝑦𝑣𝑚 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.6)

• Capacité des véhicules : la somme des demandes des clients desservis au cours d’une
même tournée validée ne doit pas dépasser la capacité du véhicule qui y est assigné.

𝑞𝑖 ⋅ ∑ 𝑥𝑖𝑗𝑣𝑚 ≤ 𝑞𝑖𝑣𝑚 ≤ 𝑞𝑖 ⋅ ∑ 𝑥𝑖𝑗𝑣𝑚 , ∀𝑖 ∈ 𝐶, ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.7)

𝑗∈𝑁 𝑗∈𝑁

∑ 𝑞𝑖𝑣𝑚 ≤ 𝑄𝑣 ⋅ 𝑦𝑣𝑚 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.8)

𝑖∈𝐶

• Taux de remplissage : la charge totale transportée au cours d’une tournée validée doit
représenter au moins à 60% de la capacité du véhicule.

∑ 𝑞𝑖𝑣𝑚 ≥ 𝜏 ⋅ 𝑄𝑣 ⋅ 𝑦𝑣𝑚 , ∀𝑣 ∈ 𝑉 , ∀𝑚𝑀 (4.9)

𝑖∈𝐶

• Séquencement des temps : le temps d’arrivée à un nœud 𝑗 dépend du temps d’arrivée au

nœud précédent 𝑖, du temps de service en 𝑖, et du temps de trajet entre 𝑖 et 𝑗.

𝑎𝑗𝑣𝑚 ≥ (𝑎0𝑣𝑚 + ∑ 𝛼 ⋅ 𝑞𝑘𝑣𝑚 + 𝑡0𝑗 ) ⋅ 𝑥0𝑗𝑣𝑚 , ∀𝑗 ∈ 𝐶, ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.10)

𝑘∈𝐶

• Enchaînement des tournées : Assure que la tournée 𝑚 d’un véhicule commence après
la fin de la tournée précédente (𝑚 − 1), respectant l’ordre chronologique des tournées
multiples.

𝑎0𝑣𝑚 ≥ (𝑎0𝑣,𝑚−1 ⋅ ∑ 𝑥𝑖0𝑣,𝑚−1 ) ⋅ 𝑦𝑣𝑚 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ {2, 3} (4.11)

𝑖∈𝐶

• Durée maximale : la durée totale de chaque tournée (temps de trajet + temps de service)
ne doit pas dépasser 𝑇max .

𝑎0𝑣𝑚 ⋅ ∑ 𝑥𝑖0𝑣𝑚 − 𝑎0𝑣𝑚 ⋅ ∑ 𝑥0𝑗𝑣𝑚 ≤ 𝑇max ⋅ 𝑦𝑣𝑚 , ∀𝑣 ∈ 𝑉 , ∀𝑚 ∈ 𝑀 (4.12)

𝑖∈𝐶 𝑗∈𝐶

• Tournées multiples : chaque véhicule ne peut effectuer que trois tournées.

∑ 𝑦𝑣𝑚 ≤ 3, ∀𝑣 ∈ 𝑉 (4.13)
𝑚∈𝑀

46
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

4.2.2 Justification du choix de l’Approche Algorithmique

La configuration du problème de tournées de véhicules chez DJE­AGRO relève un VRPTW
enrichi de plusieurs variantes telle que : VRP avec flotte hétérogène (HVRP), VRP avec tournées
multiples (MTVRP), VRP avec capacité (CVRP), VRP avec fenêtres de temps (VRPTW) et VRP
avec temps de service. En raison de cette structure combinatoire, il est classé parmi les problèmes
NP­difficiles.
Une tentative initiale de résolution par des méthodes exactes à l’aide du solveur IBM CPLEX.
Les temps de calcul explosent au­delà de quelques dizaines de clients ont rendu les méthodes
exactes incompatibles avec les besoins d’une planification journalière. Ce constat est cohérent
avec les résultats de la littérature, qui soulignent que les méthodes exactes deviennent inappli­
cables dès que le problème dépasse une échelle modeste.
Face à ces limitations, nous avons orienté notre choix vers des méthodes approchées, com­
binant des heuristiques et des métaheuristiques. Ces approches ne garantissent pas l’optimalité
mathématique absolue mais visent à obtenir des solutions de très bonne qualité en un temps de
calcul maîtrisé. Ce choix est motivé par les avantages suivants :

• Efficacité computationnelle : elles permettent d’obtenir des solutions de qualité en des

temps très courts, essentiels pour une planification quotidienne.

• Souplesse d’adaptation : elles s’adaptent facilement à la nature spécifique des contraintes

opérationnelles de DJE­AGRO (absence de temps d’attente chez les clients, ajustement
du temps de départ depuis le dépôt).

• Expérience prouvée dans la littérature : de nombreuses études démontrent que ces mé­
thodes offrent un excellent compromis entre qualité de solution et temps de calcul, no­
tamment à des variantes étendues du VRPTW.

Ultimement notre démarche s’appuie sur la structure suivante :

• Construction initiale (I1) des tournées par heuristiques guidées.

• Amélioration locale (2­opt, ReLocate) pour raffiner les itinéraires .

• Optimisation globale via une métaheuristique (recuit simulé) pour explorer efficace­
ment l’espace des solutions.

Cette approche modulaire et itérative assure la rapidité, la robustesse et l’adaptabilité, trois qua­
lités primordiales pour une solution déployable en contexte réel.

4.3 Environnement d’Implémentation et Données

La concrétisation de l’approche algorithmique établie ci­dessus exige un environnement
d’implémentation opérationnel qui s’appuie par l’utilisation des données journalières fournies
par DJE­AGRO.

4.3.1 Outils et Langages de Programmation

Nous avons utilisé un ensemble d’outils modernes et adaptés à la recherche opérationnelle
et à l’analyse de données.

47
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Environnement de Développement : l’ensemble du projet a été développé dans l’en­

vironnement en ligne Google Colaboratory (Colab). Cette plateforme a été choisie pour
sa simplicité d’accès et d’utilisation, car elle ne nécessite aucune configuration logicielle
sur la machine locale et offre un accès gratuit à des ressources de calcul. Son format de
”notebook” a également facilité le développement itératif, l’analyse et la visualisation des
résultats au même endroit.

• Langage de Programmation : le langage Python (version 3.9) a été le pilier de notre

implémentation. Il a été retenu pour sa polyvalence, sa syntaxe claire, et surtout pour son
riche écosystème de bibliothèques scientifiques qui sont essentielles pour la manipulation
de données, l’implémentation d’algorithmes complexes et la visualisation.

– Bibliothèques Principales : Les bibliothèques suivantes ont été mobilisées :

* Pandas et NumPy : Pour la manipulation, la structuration des données et les

calculs numériques.
* Matplotlib & Seaborn : Pour la génération des graphiques statistiques et des
visualisations de performance.
* OpenRouteService : Pour interroger l’API et obtenir la matrice des distances
et des temps de trajet basés sur le réseau routier réel.
* Folium : Pour la création de cartes interactives permettant de visualiser les tour­
nées de véhicules.

4.3.2 Description de Données

Nos expérimentations se basent sur les données d’activité de la distribution chez SARL DJE­
AGRO :

• Données de localisation :

– Coordonnées : l’étude s’appuie sur des coordonnées géospatiales (xi, yi) acquises
par GPS.
– Espace de modélisation : le réseau routier réel a été retenu comme cadre spatial de
référence.
– Matrice de distances : bidimensionnelle symétrique (dij = dji). Les distances réelles,
obtenues via interfaces de programmation applicatives (APIs) cartographiques.

• Topologie du réseau :

– Structure du réseau : un environnement mixte combinant zones urbaines et rurales

(un dépôt central unique et 38 clients à livrer).
– Contraintes de circulation : La modélisation s’appuie sur une homogénéité des condi­
tions de circulation pour l’ensemble de la flotte.
– Variabilité temporelle : Le problème est traité dans un cadre statique, considérant
des conditions météorologiques printanières stables.

48
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Horizon de planification :

– Horizon journalier : retenu pour une modélisation précise des contraintes opération­
nelles.

• Paramètres temporels :

– Matrice des temps : Structure symétrique définissant les durées de déplacement entre
points, intégrant les conditions de trafic réelles.
– Fenêtres de service [𝑒𝑖 , 𝑙𝑖 ] : spécifiques à chaque catégorie clientèle (Boucherie,
Grossiste, Restaurant).
– Temps de service (𝑠𝑖 ) : calculé en fonction de la quantité si=qi*alpha.

• Caractéristiques des véhicules :

– La capacité des véhicules : la flotte disponible est hétérogène et se compose de 20

véhicules au total : 8 de 400 kg, 7 de 900 kg, et 5 de 3500 kg de capacité.
– La structure de coûts : chaque type de véhicule est associé à un coût kilométrique
distinct : 20 DA/km (400 kg), 30 DA/km (900 kg), et 60 DA/km (3500 kg).

• Gestion de la flotte :

– La disponibilité de la flotte : l’ensemble de la flotte composée de 20 véhicules est

totalement disponible.
– La localisation initiale des véhicules : l’ensemble de la flotte est localisé au dépôt
central, éliminant les coûts de repositionnement initial.

• La configuration des clients :

– La quantification des demandes : les demandes (qi) sont déterministes.

4.3.3 Série d’expérimentations

Le succès de la Phase 3 (Recuit Simulé) dépend du réglage fin de ses hyperparamètres (tem­
pérature initiale, taux de refroidissement, critères d’arrêt), voici un tableau récapitulatif des dif­
férents série de tests :

T Max Temps Coût Distance Nb

N° T_init 𝛼 Iter/T
final it (s) Total (DA) (km) Véhicules

1 75000 0,994 180 0,1 35 1211,43 137 334,86 3175,4 13

2 85000 0,995 300 0,03 40 2955,38 139 555,72 3300,49 13
3 100000 0,995 200 0,01 30 1973,19 138 950,29 3176,52 13
4 110000 0,997 280 0,01 55 5614,35 141 496,32 3407,75 14
5 130000 0,998 200 0,02 60 6550,62 141 534,89 3362,52 13

Tab. 4.1 : Résultats des différentes configurations de recuit simulé

49
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

4.4 Déploiement de l’approche algorithmique

4.4.1 Phase 1 : Construction d’une Solution Initiale
L’objectif de cette première phase est de générer rapidement une solution de base réalisable,
qui servira de point de départ pour les phases d’optimisation.

Méthode retenue : pour cela, nous avons implémenté un algorithme d’insertion séquentielle,
inspiré de l’heuristique I1 de Solomon. Le principe est d’initialiser les tournées une par une et
d’y insérer les clients non encore servis.

Processus :

• Initialisation d’une tournée : une nouvelle tournée est créé partant du dépôt et en sélec­
tionnant un véhicule disponible pour un client germe. Ce client est choisi en priorité parmi
ceux ayant les fenêtres de temps les plus contraignantes. La faisabilité de ce premier trajet
est vérifiée.

• Insertion itérative : l’algorithme tente ensuite d’insérer les autres clients, un par un, dans
la tournée en cours. Pour chaque client candidat, il évalue toutes les positions d’insertion
possibles et choisit celle qui minimise le coût additionnel (mesuré par l’augmentation de
la distance parcourue).

• Vérification des contraintes : à chaque tentative d’insertion, toutes les contraintes de

DJE­AGRO sont rigoureusement vérifiées : capacité maximale du véhicule, ponctualité
des livraisons (ni retard, ni attente), respect strict des plages horaires.

• Finalisation d’une tournée : lorsqu’aucun client ne peut plus être inséré, la tournée est
considérée comme complète. Si elle respecte le taux de remplissage minimum de 60%,
elle est validée et ajoutée à la solution. Sinon, elle est abandonnée et ses clients sont remis
dans la liste des clients à desservir.

Le processus recommence jusqu’à ce que tous les clients soient servis ou qu’aucun véhicule ne
puisse plus initier de tournée valide.

50
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Le schéma conceptuel de cette première phase est illustré dans la Figure 4.1 ci­dessous.

Fig. 4.1 : Schéma conceptuel de l’algorithme de construction par insertion (Phase 1).

4.4.2 Phase 2 : Amélioration par Recherche Locale

La solution obtenue en Phase 1, bien que réalisable, est généralement sous­optimale. Cette
deuxième phase vise à l’améliorer en explorant son voisinage, c’est­à­dire des solutions alter­
natives très proches.

Opérateurs de voisinage : Deux opérateurs classiques ont été implémentés :

• 2­Opt (intra­tournée) : cet opérateur améliore l’ordre des visites au sein d’une même
tournée. Consiste à choisir deux points dans la tournée et à inverser l’ordre des clients
entre eux, tandis que le reste de la séquence est conservé tel quel. Si cette modification
réduit la distance totale, l’arrangement est adopté.
• Relocate (inter­tournées) : Cet opérateur déplace un client d’une tournée vers une autre.
Son but est de rééquilibrer la charge entre les tournées et potentiellement de réduire le
nombre total de véhicules utilisés si une tournée devient vide.

51
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Processus de recherche : Nous avons adopté une stratégie de descente itérative. Les opéra­
teurs 2­Opt et Relocate sont appliqués en boucle sur la solution.
Ce cycle est répété jusqu’à ce qu’une passe complète des deux opérateurs n’apporte plus
aucune amélioration au coût global, signifiant qu’un optimum local a été atteint.
La logique de cette recherche locale est détaillée dans la Figure 4.2 ci­dessous.

Fig. 4.2 : Schéma conceptuel de l’algorithme de recherche locale (Phase 2).

4.4.3 Phase 3 : Affinement par Métaheuristique (Recuit Simulé)

La recherche locale peut rester piégée dans un optimum local qui n’est pas le meilleur pos­
sible. Pour surmonter cette limite, nous utilisons le Recuit Simulé, une métaheuristique capable
d’explorer plus largement l’espace des solutions.

Processus :

• L’algorithme part de la meilleure solution trouvée à l’issue de la Phase 2.

• À chaque itération, il génère une solution voisine de manière stochastique, en choisissant

aléatoirement un opérateur (2­Opt ou Relocate) et des paramètres (clients, tournées).

• Cette nouvelle solution est évaluée. Si elle est meilleure, elle est acceptée. Si elle est moins
bonne, elle est acceptée selon la probabilité de Metropolis (𝑃 = exp(−Δcoût/𝑇 )), qui
diminue à mesure que la température baisse.

52
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Ce processus est contrôlé par un schéma de refroidissement qui fait baisser la température
progressivement, d’une valeur initiale élevée jusqu’à un seuil final très bas. La meilleure
solution rencontrée durant tout le processus est mémorisée et restituée à la fin.

Le fonctionnement de l’algorithme de Recuit Simulé est présenté dans la Figure 4.3 ci­
dessous.

Fig. 4.3 : Schéma conceptuel de l’algorithme de Recuit Simulé (Phase 3).

53
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

4.5 Interprétation des Résultats

4.5.1 Analyse Séquentielle des Résultats
Cette section présente les résultats concrets obtenus suite à l’application de notre méthodo­
logie de résolution sur le jeu de données de la SARL DJE­AGRO. Nous analyserons d’abord
les performances de manière séquentielle, phase par phase, avant de conclure par une synthèse
comparative entre la situation réelle et la solution finale optimisée.

[Link] Phase 1 : Solution Initiale (Heuristique d’Insertion)

La première phase a généré une solution réalisable avec les performances suivantes :

• Coût Total : 176 133 DA

• Distance Totale : 4 529 km

• Nombre de Véhicules : 17

• Nombre de Tournées : 18

L’algorithme a généré rapidement une solution complète où tous les clients sont desservis
dans leurs fenêtres de temps. Comme le montre la Figure 4.4, les rotations sont fonctionnelles
mais visiblement peu optimisées, avec des itinéraires longs et des chevauchements. En revanche,
c’est un point de départ fonctionnel suggère que des améliorations substantielles sont possibles
dans les phases d’optimisation suivantes.

Fig. 4.4 : Visualisation des tournées générées par l’heuristique d’insertion (Phase 1).

54
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Points positifs :

• L’algorithme a accompli sa mission principale : générer une solution complète où 100%

des clients (38 clients) sont servis.

• Toutes les contraintes de fenêtres de temps sont respectées avec des arrivées précises.

• La capacité des véhicules est respectée pour chaque tournée (charges variant de 320 kg à
3 440 kg).

• Solution réalisable servant de base solide pour l’optimisation.

• Gestion correcte des horaires avec des départs échelonnés entre 6h05 et 7h43.

Points d’amélioration identifiés :

• Disparité de coûts importante : écart de 1 à 12 entre la tournée la moins chère (2 031 DA)
et la plus chère (25 227 DA).

• Inefficacité géographique : distance totale élevée (4 529 km) suggérant des itinéraires sous
optimisés avec possibles croisements.

• Utilisation de 17 véhicules sur 20 disponibles, laissant peu de marge de manœuvre

• Solution réalisable servant de base solide pour l’optimisation.

• Déséquilibre des charges de travail : durées variant de 2h07 à 8h13, créant une répartition
inéquitable.

Échantillon représentatif des tournées :

• Tournée 09 (Véhicule 11) :

Itinéraire : Dépôt → Client 35 → Client 9 → Dépôt

Fig. 4.5 : Tournée 9 avec le véhicule 11

Observation : Excellente utilisation de la capacité avec un ratio coût/poids très favorable.

55
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Tournées Problématiques :
Tournée 15 (Véhicule 17) :
Itinéraire : Dépôt→ Client 4 → Client 22 → Client 18 → Dépôt

Fig. 4.6 : Tournée 15 avec le véhicule 17.

Observation : tournée coûteuse avec une durée excessive.

• Tournées à Double Rotation :

Tournée 18 (Véhicule 9 ­ deuxième tour) :
Itinéraire : Dépôt→ Client 10 → Dépôt

Fig. 4.7 : Tournée 18 par la deuxième rotation du véhicule 9.

Observation : Utilisation d’un véhicule pour un second tour, indication d’une optimisation
possible.

[Link] Phase 2 : Amélioration par Recherche Locale

La recherche locale a amélioré la solution initiale :
• Coût Initial : 176 133,19 DA → Coût Final : 149 128,66 DA

• Réduction de Coût : 27 004,53 DA (­15,34%).

• Distance Initiale : 4 528,71 km → Distance Finale : 3 533,56 km.

• Réduction de Distance : 995,15 km (­21,97%).

• Véhicules Utilisés : 17 → 14 (­3 véhicules).

• Nombre de Tournées : 18 → 14 (­4 tournées).

56
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

L’impact de la recherche locale est significatif, avec une réduction du coût de 15,3% et de la
distance de 22% par rapport à la Phase 1. La Figure 4.8 montre des itinéraires plus cohérents et
géographiquement plus compacts, avec moins de croisements, illustrant l’efficacité des opéra­
teurs 2­Opt et Relocate.

Fig. 4.8 : Visualisation des tournées après amélioration par Recherche Locale (Phase 2).

Points positifs :

• Réduction significative des coûts (­15,34%) dépassant les objectifs initiaux.

• Optimisation géographique avec 22% de distance en moins.

• La capacité des véhicules est respectée pour chaque tournée (charges variant de 320 kg à
3 440 kg).

• Rationalisation de la flotte avec 3 véhicules économisés.

• Élimination des inefficacités majeures identifiées en phase 1.

Points d’amélioration identifiés :

• L’algorithme a convergé vers un optimum local après 10 itérations consécutives sans amé­
lioration du gain supplémentaire.

57
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Échantillon représentatif des tournées :

• Transformation des Tournées Problématiques :

Ancienne Tournée 15 (Véhicule 17) :
Dépôt → Client 4 → Client 22 → Client 18 → Dépôt.
Éclatée en 2 nouvelles tournées :
Tournée 11 : Dépôt→ Client 22 → Client 4 → Dépôt.
Tournée 13 :Dépôt→ Client 25 → Client 24 → Client 18→ Client 14 → Client 38 →
Dépôt.

(a) Tournées 11 avec le véhicule 17.

(b) Tournées 11 avec le véhicule 17.

Fig. 4.9 : Illustration de deux nouvelles tournées.

Observation : la réaffectation des trois clients 4, 22, 18 permet d’optimiser davantage les
performances, en réduisant à la fois le coût total et la distance parcourue, tout en desservant
d’autres clients.

58
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Tournée 12 (Véhicule 18) :

Dépôt→ Client 30 → Client 21 → Client 20 → Client 3 → Dépôt.

Fig. 4.10 : Tournées 12 avec le véhicule 18.

Observation : une consolidation optimisée, regroupant des clients géographiquement co­

hérents améliorant ainsi l’efficacité de la tournée.

[Link] Phase 3 : Affinement par Recuit Simulé

La métaheuristique a poli la solution pour atteindre les performances finales :

• Coût Initial : 149 128,66 DA → Coût Final : 137 334,86 DA.

• Réduction de Coût : 11 793,8 DA (­7,91%).

• Distance Initial : 3 533,56 km → Distance Finale : 3 175,40 km.

• Réduction de Distance : 358,16 km (­10,14%).

• Véhicules Utilisés : 14 → 13 (­1 véhicules)

• Nombre de Tournées : 14 → 13 (­1 tournées)

Le Recuit Simulé a permis une amélioration supplémentaire en explorant des configurations in­
accessibles pour la recherche locale, libérant ainsi un véhicule de plus. La carte de cette solution
finale (Figure 4.11) présente des tournées hautement optimisées, avec des clusters de clients très
nets.

59
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

(a) Vue globale de l’optimisation des tournées.

(b) Vue rapprochée sur une zone dense de la carte.

Fig. 4.11 : Visualisation de la solution finale obtenue par Recuit Simulé (Phase 3) : vue d’en­
semble et vue rapprochée.

Points positifs :

• Utilisation optimale des véhicules : 13 véhicules pour 38 clients.

• Taux de remplissage élevé : Plusieurs véhicules atteignent des charges transportées signi­
ficatives.

• Couverture géographique : Distribution équilibrée des tournées avec 10% de distance en

moins.

• Équilibre entre contraintes opérationnelles et optimisation économique.

60
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Points d’amélioration identifiés :

• Cette solution constitue une base solide mais perfectible qui pourrait bénéficier d’autres
méthodes d’optimisation pour atteindre de meilleures performances.

Échantillon représentatif des tournées :

• Tournée 9 (Véhicule 15) :

Itinéraire : Dépôt → Client 27 → Client 34 → Client 18 → Client 14 → Client 13 →
Dépôt.

Fig. 4.12 : Tournée 9 avec le véhicule 15.

Observations : Une tournée optimisée exploitant pleinement la capacité du véhicule sur

l’ensemble de la journée, desservant 5 clients.

• Tournée 11 (Véhicule 17) :

Itinéraire : Dépôt → Client 11 → Client 22 → Client 4 → Dépôt.

Fig. 4.13 : Tournée 11 avec le véhicule 17.

Observations :Une rotation présente un bon compromis entre Distance, coût et charge
équilibrés.

61
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

4.5.2 Discussion et Interprétation Opérationnelle

[Link] Analyse des diagrammes représentatifs de performance algorith­
mique
Au­delà de la performance algorithmique, les résultats obtenus ouvrent des perspectives
concrètes d’amélioration pour la SARL DJE­AGRO. Cette section vise à interpréter les gains
quantitatifs et qualitatifs en termes d’impacts opérationnels, économiques et stratégiques pour
l’entreprise.

(a) Évolution du coût totale de transport (b) Évolution de la distance parcourue

(c) Évolution du nombre de tournées (d) Évolution du nombre de Véhicules

effectuées utilisés

Fig. 4.14 : Évolution des indicateurs de performance à chaque phase d’optimisation.

La mise en place de la solution issue de la phase 3 (Recuit simulé) se traduit par des gains
directs et mesurables :

• Réduction des Coûts directs : La baisse incessante du coût total de transport tout au long
de processus d’optimisation (176 133 DA→ 149 128,66 DA→ 137 334,86 DA ) représente
22,03% d’économie substantielle sur le budget. Cette performance est principalement due
à la diminution successive de 29,89% de la distance totale parcourue ( 4 529 Km → 3
533,56 Km → 3 175,40 Km ), ce qui implique une réduction significative des coûts du
carburant.

62
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Optimisation de la Flotte : La satisfaction complète de la demande clientèle a été assurée

dès les premières phases du processus, tout en maintenant la ponctualité des livraisons.
Elle s’accompagne d’une optimisation significative du nombre de rotations, passant de 18
à 14, puis à 13 rotations, représentant une réduction de 27,78% des tournées. Cette amé­
lioration se traduit par la bonne cohérence du processus de distribution y compris l’éli­
mination des retards de livraison et les chevauchements. Parallèlement, la réduction du
parc de véhicules utilisés, de 17 à 14, puis à 13 véhicules (soit une diminution de 23,53%)
créant une réserve de capacité stratégique qui génère une baisse immédiate des coûts opé­
rationnels journaliers ainsi qu’une réduction des coûts fixes à moyen terme, notamment
en matière de maintenance corrective et d’amortissement des équipements.

[Link] Synthèse comparative entre le cas réel et optimisé :

La comparaison directe entre la situation réelle et la solution finale optimisée quantifie la
valeur ajoutée de notre travail. Le Tableau 4.2 ci­dessous synthétise les gains obtenus sur l’en­
semble des indicateurs de performance économiques et opérationnels.
Tab. 4.2 : Tableau Comparatif des Gains : Réel vs Optimisé
Indicateur de Performance Situation Réelle Solution Optimisée Amélioration
Coût Total de Transport 162 456.65 137 334.86 15.46%
Distance Totale Parcourue 4 824.39 3 175.40 34.18%
Nombre de Véhicules 16.00 13.00 18.75%
Nombre de Tournées 24.00 13.00 45.83%
Taux de Satisfaction Client 94.70% 100.00% +5.3%

Analyse : Le tableau 4.2 montre un succès du modèle optimisé sur tous les plans. Il permet de
réduire le coût total de 15.46% par rapport au cas concret, portée par une optimisation de la
distance totale de 34.18%. L’efficacité de la flotte est également remarquable : 18.75% de
véhicules en moins (13 contre 16) et 45.83% de tournées en moins (13 contre 24), ce qui
indique une planification rationaliste et un meilleur remplissage des camions.
Outre ces gains quantitatifs obtenus, l’amélioration de la qualité de service constitue un gain
qualitatif de ce projet comme le montre la Figure 4.15 ci­dessous :

Fig. 4.15 : Amélioration du Taux de Satisfaction Client.

63
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Analyse : comme l’illustre la figure, la solution optimisée atteint un service parfait de 100% de
satisfaction client, garantissant le respect de toutes les fenêtres temporelles. Contrairement à la
situation réelle où, comme l’indique la note sur le graphique, 2 des 38 clients n’étaient pas
servis dans leur créneau, résultant en un taux de 94.7%. Cette garantie de fiabilité représente
un avantage concurrentiel majeur pour DJE­AGRO.

[Link] Compromis entre Optimalité et Applicabilité Opérationnelle :

Il est essentiel de souligner que, par la nature des méthodes approchées (heuristiques et
métaheuristiques) utilisées, la solution finale obtenue n’est pas garantie d’être l’optimum
mathématique absolu. Il est théoriquement possible qu’une meilleure configuration de tournées
existe.
Concrètement notre solution apporte des optimisation importantes (distance, coûts,
satisfaction..etc ) au profit de DJE­AGRO. En mettant l’accent sur la puissance de notre
approche réside dans l’élaboration du plan de distribution de très haute qualité en quelques
minutes avec des ressources modestes, surpassant largement les performances manuelles
actuelles, tout en étant suffisamment rapide pour s’intégrer dans le cycle de planification
journalière (J­1) de l’entreprise.

4.5.3 Les contributions réelles apportées à DJE AGRO :

1. Fourniture d’un Outil d’Optimisation
Ce projet développé dépasse le processus de planification manuel. Notre modèle est
spécifiquement calibré pour gérer la complexité intensifié des opérations de l’entreprise en
éliminant les risques d’erreurs humaines, et en garantissant la cohérence des planifications et la
complémentarité des rotations. De plus, il permet de réaliser des simulations « what­if » pour
évaluer des scénarios futurs et prendre des décisions éclairées. La direction peut désormais
répondre à des questions complexes avec des données chiffrées :

• Stratégie commerciale : Quel est le coût logistique pour intégrer un nouveau groupe de
clients dans la wilaya de Sétif ? Est­il rentable de conquérir ce segment de clientèle ?

• Stratégie d’investissement : Faut­il investir dans un nouveau camion de 3500 kg ou

dans deux de 900 kg ? Le modèle peut simuler l’impact de chaque choix sur l’efficacité
globale des tournées et le coût total.

• Gestion des risques : Comment nos tournées et nos coûts seraient­ils affectés par une
hausse de 20% du prix du carburant ?

2. Gains Économiques et Opérationnels Quantifiés et Significatifs

Notre solution apporte des améliorations directes et chiffrables sur les indicateurs de
performance clés. La comparaison avec la situation réelle observée révèle :

• Réduction du coût total de transport de 15.46%.

• Respect total des fenêtres de temps (100%).

• Chute de la distance totale parcourue de 34.18%.

64
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Moindre des véhicules et des rotations de 18.75% et de 45.23% respectivement afin de

gérer avec souplesse les variations d’activité, notamment les commandes de dernière
minute et les fluctuations saisonnières.

• Meilleur remplissage des camions au moyen de 87.4%.

• Flotte disponible pour accompagner la croissance de son portefeuille client sans engager
de nouveaux investissements véhiculaires.

3. Amélioration de la Fiabilité et Avantage Concurrentiel

• Garantie de service : le passage à 100% de satisfaction client n’est pas un simple
chiffre. Il signifie que l’entreprise est désormais en mesure de garantir le respect de la
totalité de ses engagements de livraison. Cette fiabilité est un avantage concurrentiel
majeur, en particulier auprès des clients institutionnels et des grandes surfaces.

• Renforcement de l’image de marque : Une entreprise qui livre systématiquement à

l’heure renforce son image de professionnalisme et de partenaire de confiance. Cela
contribue à fidéliser la clientèle existante et constitue un argument de poids pour en
acquérir de nouvelles.

4.6 Conclusion
Ce chapitre présente l’ensemble de la démarche adoptée pour résoudre le problème de
distribution chez SARL DJE­AGRO, depuis la justification de la méthodologie et la
modélisation mathématique du problème, jusqu’à l’interprétation détaillée des résultats.
Nous avons démontré que notre approche approximative séquentielle en trois phases permet de
tirer une solution logistique qui surpasse largement les performances du système manuel
actuel. Les résultats ont mis en évidence des gains significatifs sur tous les indicateurs clés :
une réduction notable des coûts et des distances, une rationalisation de l’utilisation de la flotte,
et surtout, l’atteinte d’une qualité de service parfaite avec 100% de satisfaction client.
L’analyse finale a permis de traduire ces succès techniques en avantages opérationnels et
stratégiques concrets pour l’entreprise, validant ainsi la pertinence et la valeur ajoutée de notre
approche, non seulement comme un outil de planification journalière mais aussi comme un
levier d’aide à la décision stratégique.

65
Conclusion générale

Au terme de cette étude, nous avons abordé un défi central pour de nombreuses entreprises du
secteur agricole : l’optimisation de distribution des produits frais. Confrontée à la complexité
d’une planification manuelle pour ses livraisons quotidiennes, l’entreprise DJE­AGRO
représentait un cas d’étude pertinent pour démontrer la valeur ajoutée des outils de la
recherche opérationnelle. Elle permet de dégager des apports pertinents, tant sur le plan
théorique que pratique.
Sur le plan théorique, ce travail a permis de confirmer la complexité des problèmes de VRP
avec contraintes temporelles. L’analyse approfondie de la littérature scientifique a révélé la
diversité des approches méthodologiques développées pour traiter ces problèmes
d’optimisation, à l’instar des méthodes exactes, des heuristiques et des métaheuristiques.
L’étude de cas réalisée au sein de l’entreprise SARL DJE AGRO a constitué un terrain
d’application riche pour l’expérimentation des concepts théoriques étudiés. L’analyse détaillée
du système de distribution existant a permis d’identifier les principales sources d’inefficacité et
les opportunités d’amélioration. La modélisation mathématique du problème, prenant en
compte les contraintes opérationnelles de l’entreprise (flotte hétérogène, fenêtres temporelles,
capacités variables), a abouti à la formulation d’un modèle VRP qui combine plusieurs
variantes du VRP ( VRPTW, HVRP, MTVRP,CVRP ) ajusté aux spécificités du secteur avicole.
L’implémentation de notre chaîne algorithmique a démontré l’efficacité des approches
développées pour traiter le problème étudié. Les résultats obtenus révèlent des gains
significatifs en termes de réduction des coûts de transport (­15.46%), d’optimisation des
distances parcourues (­34.18%) et d’amélioration du taux de respect des contraintes
temporelles (+5,3%). Ces améliorations se traduisent concrètement par une utilisation
rationnelle des ressources de l’entreprise (13 véhicules en 13 tournées), et un renforcement de
la qualité de service offerte à la clientèle (100%) éradiquant les retards de livraison.
Néanmoins, notre étude présente certaines limites qui ouvrent la voie à des perspectives de
recherche et de développement futures. La nature déterministe du modèle développé ne prend
pas en compte les aléas pouvant survenir en temps réel (embouteillages, pannes, nouvelles
commandes urgentes). De plus, bien que la réduction de la distance induise une baisse des
émissions de CO2, l’optimisation environnementale n’était pas un objectif explicite du modèle.
En définitive, ce projet a démontré à travers un cas d’étude concret, le rapprochement des
aspects théoriques de la recherche opérationnelle et des besoins concrets des entreprises, en
créant de la valeur à la fois économique, opérationnelle et qualitative.

66
Annexes

Composition Détaillée des Tournées

Le séquencement des tournées du cas réel
• Camion 01 (400 kg) : Dépôt → Client 17 → Client 2 → Dépôt

• Camion 02 (400 kg) : Dépôt → Client 5 → Client 15 → Client 23 → Dépôt

• Camion 02 (400 kg) : Dépôt → Client 33 → Client 25 → Dépôt

• Camion 03 (400 kg) : Dépôt → Client 3 → Client 29 → Dépôt

• Camion 03 (400 kg) : Dépôt → Client 34 → Dépôt

• Camion 04 (400 kg) : Dépôt → Client 7 → Client 11 → Dépôt

• Camion 04 (400 kg) : Dépôt → Client 21 → Dépôt

• Camion 05 (400 kg) : Dépôt → Client 35 → Dépôt

• Camion 05 (400 kg) : Dépôt → Client 28 → Dépôt

• Camion 06 (400 kg) : Dépôt → Client 36 → Dépôt

• Camion 06 (400 kg) : Dépôt → Client 32 → Dépôt

• Camion 06 (400 kg) : Dépôt → Client 19 → Dépôt

• Camion 07 (900 kg) : Dépôt → Client 18 → Client 14 → Dépôt

• Camion 08 (900 kg) : Dépôt → Client 6 → Client 8 → Client 1 → Dépôt

• Camion 09 (900 kg) : Dépôt → Client 13 → Client 37 → Dépôt

• Camion 10 (900 kg) : Dépôt → Client 9 → Dépôt

• Camion 10 (900 kg) : Dépôt → Client 10 → Dépôt

• Camion 11 (900 kg) : Dépôt → Client 30 → Dépôt

• Camion 12 (3500 kg) : Dépôt → Client 38 → Client 26 → Client 12 →Client31 →

Dépôt

• Camion 13 (3500 kg) : Dépôt → Client 4 → Client 22 → Dépôt

67
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

• Camion 14 (3500 kg) : Dépôt → Client 24 → Dépôt

• Camion 15 (3500 kg) : Dépôt → Client 27 → Dépôt

• Camion 15 (3500 kg) : Dépôt → Client 20 → Dépôt

• Camion 16 (3500 kg) : Dépôt → Client 16 → Dépôt

Note : Les clients 25 et 21 (indiqués en rouge) sont desservis hors de leur fenêtre de temps.

Le séquencement des tournées du cas optimisé

Fig. 16 : Détails de la tournée 1 et 2.

68
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Fig. 17 : Détails de la tournée 3 et 4.

Fig. 18 : Détails de la tournée 5, 6 et 7.

69
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Fig. 19 : Détails de la tournée 8 et 9.

Fig. 20 : Détails de la tournée 10 et 11.

70
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Fig. 21 : Détails de la tournée 12 et 13.

Fig. 22 : Résumé final du cas optimisé.

71
Chapitre 4 : Résolution, Implémentation et Interprétation des résultats expérimentaux

Tab. 3 : Liste des clients avec leurs fenêtres de temps

id client fenêtre de temps id client fenêtre de temps

Client 1 6h­16h Client 20 8h­12h
Client 2 8h­10h Client 21 6h­16h
Client 3 6h­16h Client 22 8h­12h
Client 4 8h­12h Client 23 8h­10h
Client 5 8h­10h Client 24 8h­12h
Client 6 8h­10h Client 25 8h­10h
Client 7 8h­10h Client 26 6h­16h
Client 8 6h­16h Client 27 8h­12h
Client 9 6h­16h Client 28 6h­16h
Client 10 6h­16h Client 29 8h­10h
Client 11 8h­10h Client 30 8h­12h
Client 12 6h­16h Client 31 8h­12h
Client 13 6h­16h Client 32 6h­16h
Client 14 6h­16h Client 33 6h­16h
Client 15 8h­10h Client 34 6h­16h
Client 16 8h­12h Client 35 6h­16h
Client 17 6h­16h Client 36 6h­16h
Client 18 6h­16h Client 37 6h­16h
Client 19 6h­16h Client 38 6h­16h

72
Bibliographie

[1] R. Crézé. « Bertrand Valiorgue, Refonder l’agriculture à l’heure de l’Anthropocène ». (2021),

adresse : [Link] (visité le 15/05/2025).
[2] Yahoo Finance. « Fresh Produce Market Size to Capture USD 3,539.7 Billion by 2030, Growing
at a 4.8% CAGR ». (2024), adresse : [Link]
[Link] (visité le 15/05/2025).
[3] Interfel. « Bilan de la consommation 2024 ». (2024), (visité le 15/05/2025).
[4] La France Agricole. « En 2024, un engouement des consommateurs pour le circuit court ».
(2024), (visité le 15/05/2025).
[5] Commission Européenne. « Règlement (UE) n° 931/2011 concernant les exigences en matière de
traçabilité pour les denrées alimentaires d’origine animale ». (2011), adresse :
[Link] (visité le 16/05/2025).
[6] Legifrance. « Article R.231­59­1 du Code rural et de la pêche maritime ». (2025), adresse :
[Link]
LEGISCTA000017763457/#LEGISCTA000042397046 (visité le 16/05/2025).
[7] Nations Unies. « Accord ATP – Accord relatif aux transports internationaux de denrées
périssables et aux engins spéciaux à utiliser pour ces transports ». (1970), adresse :
[Link] (visité le
16/05/2025).
[8] Commission Européenne. « Règlement (CE) n° 852/2004 – Hygiène des denrées alimentaires ».
(2004), adresse : [Link] (visité le 16/05/2025).
[9] Commission Européenne. « Règlement (CE) n° 853/2004 – Hygiène des denrées alimentaires
d’origine animale ». (2004), adresse : [Link]
(visité le 16/05/2025).
[10] R. française, Article L.3222­9 du Code des transports, 2025. adresse :
[Link]
TRAN001138&FromId=CODES_SECS_CCOM (visité le 16/05/2025).
[11] M. F. M. S. Mustafa, N. Navaranjan et A. Demirovic, « Food cold chain logistics and
management : A review of current development and emerging trends », Journal of Agriculture
and Food Research, t. 18, p. 101 343, 2024.
[12] F. Caillavet, N. Darmon, C. Dubois et al. « Vers une sécurité alimentaire durable : enjeux,
initiatives et principes directeurs ». (2021), (visité le 17/05/2025).
[13] S. Dani, Food Supply Chain Management and Logistics : From Farm to Fork, 1re éd. Kogan
Page, 2015.
[14] Global Market Insights, Refrigerated Transport Market Size, 2023. adresse : https:
//[Link]/fr/industry-analysis/refrigerated-transport-market
(visité le 17/05/2025).
[15] ADEME, Fiche d’Actualité Transport Routier de Marchandises, 2022.

73
Bibliographie

[16] Backcarbone, L’empreinte carbone des trains, 2023. adresse : [Link]

[Link]/dossiers-experts/empreinte-carbone-trains (visité le
17/05/2025).
[17] A. Ikegaya, S. Yamazaki, I. Yamaga et al., « Controlled atmosphere maintains the quality of
certain fresh produce in mixed cargo shipments », Journal of Food Process Engineering, t. 46,
2023.
[18] International Maritime Organization (IMO). « 2023 IMO Strategy on Reduction of GHG
Emissions from Ships ». (2023), adresse :
[Link]
[Link] (visité le 17/05/2025).
[19] G. Baxter et K. Kourousis, « Temperature Controlled Aircraft Unit Load Devices : The
Technological Response to Growing Global Air Cargo Cool Chain Requirements », Journal of
Technology Management and Innovation, t. 10, no 1, p. 157­168, 2015.
[20] C. Compensation, L’empreinte carbone des avions, 2023. adresse : [Link]
[Link]/dossiers-experts/empreinte-carbone-avion (visité le
17/05/2025).
[21] Douze Point Cinq. « Hub logistique ». (2023), adresse :
[Link] (visité le 18/05/2025).
[22] Klarys. « Produits frais : les 6 grands défis de la supply chain ». (2023), adresse :
[Link]
supply-chain (visité le 18/05/2025).
[23] Institut International du Froid. « The Role of Refrigeration in Worldwide Nutrition ». (2020),
(visité le 18/05/2025).
[24] Ministère de l’Agriculture et de la Souveraineté alimentaire. « Géographie logistique du système
agro­alimentaire français, Analyse n°192 ». (2023), adresse :
[Link]
alimentaire-francais-analyse-ndeg192 (visité le 19/05/2025).
[25] InTerLUD. « Agir pour des solutions logistiques des circuits courts alimentaires de proximité ».
(2022), (visité le 19/05/2025).
[26] L. J. S. Lukasse, M. B. Baerentz et J. E. de Kramer, « Quest II : réduction des émissions de CO2
des conteneurs reefers », Wageningen UR Food & Biobased Research, rapp. tech., 2013.
[27] Banque des Territoires. « Transition alimentaire : les dynamiques territoriales, Volume 2 ».
(2021).
[28] D. Rizwan, S. B. R. Kirmani et F. A. Masoodi, « Circular Economy in the Food Systems : A
Review », Environmental Quality Management, t. 34, no 4, e70096, 2025.
[29] SGCarMart. « DFSK EC31 Refrigerated Electric ». (2025), adresse : https:
//[Link]/new-cars/info/21824/dfsk-ec31-refrigerated-electric
(visité le 19/05/2025).
[30] FavPNG. « Car Kia Bongo Kia Motors Hyundai Mega Truck Car Refrigeration ». (2025),
adresse : [Link]
truck-car-refrigeration-png/Zqjed39x (visité le 19/05/2025).
[31] Lamberet. « Gamme de véhicules frigorifiques ». (2025), adresse :
[Link] (visité le
19/05/2025).
[32] Kardinal. « Optimisation de tournées : répondre aux défis du transport de produits frais ». (2023),
(visité le 20/05/2025).

74
Bibliographie

[33] PTV Logistics. « Solutions : Optimisation des tournées ». (2023), adresse :

[Link] (visité
le 20/05/2025).
[34] PTV Groupe. « Qu’est­ce que l’optimisation de tournées ? » (2021), (visité le 20/05/2025).
[35] M. Todorovic, M. Simic et A. Kumar, « Managing risks in the supply chain of perishable goods
using advanced analytics », Sustainability, t. 10, no 10, p. 3481, 2018.
[36] L. Zhao, M. Li et Z. Song, « A Study of the Capacitated Vehicle Routing Problem with
Time­Window and Three­Dimensional Loading Constraints in Land­Sea Transport »,
ResearchGate, 2024.
[37] V. T. Paschos, Applications of Combinatorial Optimization, Volume 3. John Wiley & Sons, 2013.
[38] S. Diaby, « Optimisation combinatoire pour la gestion des flux de production : application à la
planification des ressources dans l’industrie », thèse de doct., Université de Toulouse, 2019.
[39] D. L. Applegate, R. E. Bixby, V. Chvátal et W. J. Cook, The Traveling Salesman Problem : A
Computational Study. Princeton University Press, 2011.
[40] G. Gutin et A. P. Punnen, éd., The Traveling Salesman Problem and Its Variations. Springer
Science & Business Media, 2006, t. 12.
[41] R. Belmont, Problème du voyageur de commerce, PDF document on personal webpage, 2025.
(visité le 21/05/2025).
[42] R. Burkard, M. Dell’Amico et S. Martello, Assignment Problems. SIAM, 2012.
[43] H. Kellerer, U. Pferschy et D. Pisinger, Knapsack Problems. Springer Berlin Heidelberg, 2004,
p. 235­283.
[44] S. Martello et P. Toth, Knapsack Problems : Algorithms and Computer Implementations. John
Wiley & Sons, Inc., 1990.
[45] A. Caprara, P. Toth et M. Fischetti, « Algorithms for the Set Covering Problem », Annals of
Operations Research, t. 98, p. 353­371, 2000.
[46] M. Bougeret, P.­F. Dutot, K. Jansen, C. Robenek et D. Trystram, « Scheduling under service
quality constraints in the clouds », ResearchGate, 2015. adresse :
[Link]
classes-de-complexite_fig12_278826950 (visité le 21/05/2025).
[47] P. Toth et D. Vigo, éd., Routage de véhicules : problèmes, méthodes et applications. Society for
Industrial et Applied Mathematics, 2014.
[48] G. Laporte, « Cinquante ans de routage de véhicules », Transportation Science, t. 43, no 4,
p. 408­416, 2009.
[49] K. Braekers, K. Ramaekers et I. Van Nieuwenhuyse, « The vehicle routing problem : state of the
art classification and review », Computers & Industrial Engineering, t. 99, p. 300­313, 2016.
[50] S. Belhaiza, Illustration d’une solution VRP, Figure in ResearchGate, 2019. adresse :
[Link]
VRP_fig3_337840545 (visité le 22/05/2025).
[51] J. Yang, Y. Zhang, X. Li, Z. Chen et Z. Wang, « A comprehensive review of explainable artificial
intelligence for smart grids », Energy and AI, t. 17, p. 100 394, 2024.
[52] G. B. Dantzig et J. H. Ramser, « Le problème de la répartition des camions », Management
Science, t. 6, no 1, p. 80­91, 1959.
[53] M. Desrochers, J. Desrosiers et M. Solomon, « A new optimization algorithm for the vehicle
routing problem with time windows », Operations Research, t. 40, no 2, p. 342­354, 1992.

75
Bibliographie

[54] A. Wren et A. Holliday, « Programmation informatique des véhicules d’un ou plusieurs dépôts
vers plusieurs points de livraison », Journal of the Operational Research Society, t. 23, no 3,
p. 333­344, 1972.
[55] É. D. Taillard, « Une méthode heuristique de génération de colonnes pour le VRP de flotte
hétérogène », RAIRO­Recherche opérationnelle, t. 33, no 1, p. 1­14, 1999.
[56] D. Bertsimas, P. Chervi et M. Peterson, « Approches computationnelles des problèmes
stochastiques de routage de véhicules », Transportation Science, t. 29, no 4, p. 342­352, 1995.
[57] H. Min, « Le problème des tournées de véhicules multiples avec points de livraison et de
ramassage simultanés », Transportation Research Part A : General, t. 23, no 5, p. 377­386, 1989.
[58] C. Archetti, M. G. Speranza et A. Hertz, « A tabu search algorithm for the split delivery vehicle
routing problem », Transportation Science, t. 40, no 1, p. 64­73, 2006.
[59] J.­F. Cordeau, M. Gendreau et G. Laporte, « Une heuristique de recherche tabou pour les
problèmes de tournées de véhicules périodiques et multi­dépôts », Networks, t. 30, no 2,
p. 105­119, 1997.
[60] D. Cattaruzza, N. Absi et D. Feillet, « Problèmes de tournées de véhicules avec trajets
multiples », 4OR, t. 14, no 3, p. 223­259, 2016.
[61] V. Pillar, M. Gendreau, C. Guéret et A. L. Medaglia, « A review of dynamic vehicle routing
problems », European Journal of Operational Research, t. 225, no 1, p. 1­11, 2013.
[62] P. Toth et D. Vigo, « VRP with backhauls », in The Vehicle Routing Problem, Society for
Industrial et Applied Mathematics, 2002, p. 195­224.
[63] S. Erdoğan et E. Miller­Hooks, « Un problème de routage de véhicules écologiques »,
Transportation Research Part E : Logistics and Transportation Review, t. 48, no 1, p. 100­114,
2012.
[64] T. Vidal, N. Maculan, L. S. Ochi et P. H. Vaz Penna, « Grands quartiers avec sélection implicite
des clients pour les problèmes de tournées de véhicules avec profits », Transportation Science,
t. 50, no 2, p. 720­734, 2016.
[65] N. Agatz, P. Bouman et M. Schmidt, « Approches d’optimisation pour le problème du voyageur
de commerce avec drone », Transportation Science, t. 52, no 4, p. 64­73, 2018.
[66] J. K. Lenstra et A. H. G. Rinnooy Kan, « Complexité des problèmes de tournées et
d’ordonnancement des véhicules », Networks, t. 11, no 2, p. 221­227, 1981.
[67] A. Benantar, « Optimisation pour des problèmes industriels de tournées de véhicules », thèse de
doct., Normandie Université, 2017.
[68] M. Mehdi, Illustration of the sequential branch and bound algorithm, Figure in ResearchGate,
2015. adresse : [Link]
sequential-branch-and-bound-algorithm_fig1_281015427 (visité le 01/06/2025).
[69] D. P. Bertsekas, « Regular policies in abstract dynamic programming », SIAM Journal on
Optimization, t. 27, no 3, p. 1694­1727, 2017.
[70] R. Baldacci, A. Mingozzi et R. Roberti, « Recent exact algorithms for solving the vehicle routing
problem under capacity and time window constraints », European Journal of Operational
Research, t. 218, no 1, p. 1­6, 2012.
[71] M. M. Solomon, « Algorithms for the Vehicle Routing and Scheduling Problems with Time
Window Constraints », Operations Research, t. 35, no 2, p. 254­265, 1987.
[72] Y. Crama, A. W. Kolen et E. J. Pesch, « Recherche locale en optimisation combinatoire », French,
Réseaux de neurones artificiels : Introduction à la théorie et à la pratique des ANN, p. 157­174,
2005.

76
Bibliographie

[73] ResearchGate, Principe de la recherche locale, Figure 1.12, 2025. adresse :

[Link]
locale_fig3_323996151 (visité le 04/06/2025).
[74] T. Bouktir, Représentation simplifiée d’une approche métaheuristique, Figure in ResearchGate,
2025. adresse : [Link]
dune-approche-metaheuristique_fig11_338655886 (visité le 05/06/2025).
[75] S. Kirkpatrick, C. D. Gelatt Jr et M. P. Vecchi, « Optimisation par recuit simulé », French,
Science, t. 220, no 4598, p. 671­680, 1983.
[76] V. Crescenz, « Colonies de fourmis », Université de Nice­Sophia Antipolis, rapp. tech., 2006.

77