0% ont trouvé ce document utile (0 vote)

29 vues75 pages

Vehicule Routing Problem

Transféré par

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

29 vues75 pages

Vehicule Routing Problem

Transféré par

agguini

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Table des matières

Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1 Le transport de marchandise et distribution 10

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Historique de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Les différents mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Les types de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 Transport des voyageur . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.2 Le transport routier de marchandises à longue distance . . . . . . . 15
1.5.3 Le transport routier de marchandises à courte distance . . . . . . . 15
1.6 Réglementation contrat de transport marchandise . . . . . . . . . . . . . . 15
1.6.1 La feuille de la route . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.2 Les types des contrat . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.3 Reglementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 Les intervenants de TRM . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.7.1 Le commissionnaire de transport . . . . . . . . . . . . . . . . . . . 17
1.7.2 Les transitaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7.3 Le courtier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7.4 Le transporteur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.7.5 Le logisticien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.8 Les différentes stratégies de transport . . . . . . . . . . . . . . . . . . . . . 18
1.8.1 Le transport pour compte propre . . . . . . . . . . . . . . . . . . . 19
1.8.2 La sous-traitance directe à des transporteurs . . . . . . . . . . . . . 19
1.8.3 La sous-traitance à des transitaires ou auxiliaires de transport . . . 19
1.8.4 Le recours combiné au transport en flotte propre et à la sous-traitance 19
1.9 Lefficacité des stratégies de transport . . . . . . . . . . . . . . . . . . . . . 20
1.10 La gestion du transport marchandise . . . . . . . . . . . . . . . . . . . . . 20
1.10.1 Les outils utilisé dans la gestion de TRM . . . . . . . . . . . . . . . 21
1.11 Les problème de gestion dans le transport du marchandise routier . . . . . 22
1.12 Optimisation des Solutions de Transport de Marchandises . . . . . . . . . . 22
1.13 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Problème de VRP(Véhicule Routing Problème) 24

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Déﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Historique de VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Les paramètres de problème tourné de véhicule . . . . . . . . . . . . . . . 26
2.5 Variante de VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

1
TABLE DES MATIÈRES

2.5.1 Le Capacitated Vehicle Routing Problem (CVRP) . . . . . . . . . 27

2.5.2 Le Véhicule Routing Problem with Time Windows (VRPTW) . . . 27
2.5.3 Le Vehicle Routing Problem with Backhauls (VRPB) . . . . . . . . 28
2.5.4 Le Vehicle Routing Problem with Pick-up and Delivery (VRPPD) . 28
2.5.5 Le Stochastic Vehicle Routing Problem (SVRP) . . . . . . . . . . . 28
2.5.6 Le Periodic Vehicle Routing Problem (PVRP) . . . . . . . . . . . . 29
2.5.7 Le Multi-Depot Vehicle Routing Problem (MDVRP) . . . . . . . . 29
2.5.8 Le Dynamic Vehicle Routing Problem (DVRP) . . . . . . . . . . . 29
2.5.9 Le Vehicle Routing Problem with Split Delivery (VRPSD ou SD-
VRP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5.10 Le Vehicle Routing Problem with Multiple Trips (VRPMT) . . . . 30
2.6 Les formules mathematique . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.1 Les paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 les methode de résolution 34

3.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 les méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 les méthode approchées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1 Les heuristique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.2 méthod de constructive . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 les métaheuristiques . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.4 algorithme génétique . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3.5 recherche tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 Résolution du problème tourné de véhicule 41

4.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2 les outils informatique et méthode de résolution . . . . . . . . . . . . . . . 42
4.2.1 python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.2 matrice de distance . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.3 l’API de Mapbox . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.4 Langages de programmation et outils utilisés pour le développement
de l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2.5 Utilisation de bibliothèques et modules pour le développement de
l’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Explication de l’application DZAIR VRP Solution . . . . . . . . . . . . . . 44
4.3.1 Interface utilisateur : . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.4 L’organisation de résaux de déstribution chez condor logistics . . . . . . . 47
4.4.1 Les points de vente . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4.2 Algorithme déplacement AB . . . . . . . . . . . . . . . . . . . . . . 48
4.4.3 les input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.4.4 les output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Résultat obtenue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5.1 Les déplacement AB de condor logistique . . . . . . . . . . . . . . 51
4.6 Résolution de VRP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6.1 Résolution par méthode approché . . . . . . . . . . . . . . . . . . . 53
4.6.2 algorithme heuristique . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.6.3 algorithme métaheuristique . . . . . . . . . . . . . . . . . . . . . . 59
4.6.4 Les résultat des algorithmes . . . . . . . . . . . . . . . . . . . . . . 63

2
TABLE DES MATIÈRES

4.7 Analyse Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.7.1 Tableau de Bord . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3
Table des ﬁgures

1.1 Les fonction de la chaine logistique . . . . . . . . . . . . . . . . . . . . . . 12

1.2 Transport marchandise routier . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Transport marchandise maritime . . . . . . . . . . . . . . . . . . . . . . . 14
1.4 Schéma de la stratégie de transport[5] . . . . . . . . . . . . . . . . . . . . . 20

2.1 Problem Vehicule routing . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Organigramme de variante VRP[22] . . . . . . . . . . . . . . . . . . . . . . 30

4.1 Logo de DZAIR VRP Solution . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2 l’interface d’application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3 Principales fonctions du l’application . . . . . . . . . . . . . . . . . . . . . 45
4.4 Formulaire des informations . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Portfolio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.6 Les informations de contact . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.7 page de connexion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.8 l’emplacement de dépôt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.9 les déplacement AB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.10 Les tournées obtenues à partir de l’algorithme heuristique . . . . . . . . . 58
4.11 résultats obtenue d’après le déplacement AB . . . . . . . . . . . . . . . . . 64
4.12 Les pourcentages d’utilisation des ressources . . . . . . . . . . . . . . . . . 64
4.13 Les résultats obtenue par VRP Solution . . . . . . . . . . . . . . . . . . . 65
4.14 Les pourcentages de gain obtenus grâce à VRP Solution . . . . . . . . . . . 66
4.15 Les résultats obtenue d’après l’algorithme méthaheuristique . . . . . . . . . 66
4.16 Logo de l’entreprise CONDOR LOGISTICS . . . . . . . . . . . . . . . . . 71

4
Liste des tableaux

4.1 Coûts et distances liés aux missions . . . . . . . . . . . . . . . . . . . . . . 52

4.2 Résultat obtenue par algorithme heuristique . . . . . . . . . . . . . . . . . 58
4.3 Résultat obtenu par algorithme heuristique (mise à jour) . . . . . . . . . . 63

5
List of Algorithms

1 Solve Vehicle Routing Problem . . . . . . . . . . . . . . . . . . . . . . . . 54

6
Liste d’abréviation

VRP Vehicle Routing Problem

CVRP Capacitated Vehicle Routing Problem

MDVRP Multi-Depot Vehicle Routing Problem

PDPTW Pickup and Delivery Problem with Time Windows

VRPPD Vehicle Routing Problem with Pickup and Delivery

PVRP Periodic Vehicle Routing Problem

VRPSD Vehicle Routing Problem with Split Delivery

VRPMT Vehicle Routing Problem with Multiple Trips

VRPB Vehicle Routing Problem with Backhauls

API Application Programming Interface

BBA Bordj Bou Arreridj

TRM Transport Routier de Marchandise

7
introduction générale

Le transport de marchandises et la logistique jouent un rôle essentiel dans toute éco-

nomie. Ils sont responsables de l’acheminement et l’approvisionnement d’une manière
eﬃcace des produits et de la satisfaction des demandes des consommateurs à l’échelle lo-
cal,régionale et mondiale. Les entreprises dans le monde entier s’appuient sur des réseaux
logistiques de distribution et d’approvisionnement complexes pour planiﬁer la livraison
des marchandises. L’optimisation des itinéraires, la gestion des coûts et la coordination
des opérations logistiques sont des enjeux clés dans ce domaine.

L’eﬃcacité des itinéraires et la gestion des coûts liée a tout opérations d’approvision-
nement et de distribution sont des éléments essentiels dans le domaine du transport de
marchandises, l’optimisation de ces éléments est essentiel pour les entreprises qui cherchent
à maintenir leur compétitivité, à améliorer leur rentabilité et à oﬀrir un service de qualité
à leurs clients.

La problématique centrale de cette étude consiste à déterminer comment optimiser

les itinéraires et réduire les coûts associés aux opérations d’approvisionnement et de dis-
tribution ? comment les entreprises peuvent-elles atteindre une eﬃcacité maximale dans
leurs processus logistiques tout en minimisant les distances parcourues et en optimisant
l’utilisation de leurs ressources ? Quelles stratégies, techniques et technologies peuvent
être mises en oeuvre pour améliorer la planiﬁcation des itinéraires, la gestion des coûts
et la coordination des opérations logistiques ? En répondant à ces questions, cette étude
vise à proposer des solutions innovantes pour permettre aux entreprises de maintenir leur
compétitivité, d’améliorer leur rentabilité et de fournir un service de qualité à leurs clients
dans le domaine du transport de marchandises.

Notre objectif principal est de résoudre le Problème de Routage de Véhicules et d’opti-

miser les itinéraires de livraison chez Condor Logistique, en sappuiant sur des techniques
avancées d’analyse des données, d’algorithmes d’optimisation (heuristique et métaheuris-
tique) et des modèles mathématiques, cherchons à minimiser les distances parcourues avec
la réduction des coûts liées a toute opération d’approvisionnement et distribution .

Dans ce chapitre, en premier lieu, nous nous intéresserons au transport de marchan-

dises dans son ensemble, nous commencerons par déﬁnir précisément le concept du trans-
port de marchandises ;Ensuite, nous explorerons les diﬀérents modes de transport utilisés
pour le transport de marchandises, tels que le transport routier, ferroviaire, maritime et
aérien.

8
En second lieu, nous aborderons la réglementation associée au transport de marchan-
dises qui régie le secteur, notamment celle qui ce rapport au transport des marchandises
au niveau nationales et internationales ; enfin, nous discuterons des problèmes majeurs
auxquels sont confrontés les acteurs du transport de marchandises au niveau national et
international. Il s’agit notamment des défis logistiques liés à la planification des itinéraires,
à la coordination des opérations et à la gestion des retards.

Dans le deuxième chapitre, nous nous aborderons sur le Problème de Routage de

Véhicules (VRP), par une définition qui concept, en mettant en évidence son importance
dans l’optimisation des tournées de véhicules de livraison, nous présenterons ensuite les
différents types de VRP, tels que le VRP avec fenêtres de temps, le VRP capacité, le VRP
multi-dépôt, etc. Chacun de ces types présente des caractéristiques et des contraintes
spécifiques, nécessitant des approches et des méthodes de résolution adaptées.

Dans le troisième chapitre, nous avons mis en lumière les diﬀérentes méthodes de
résolution utilisées pour résoudre le Problème de Routage de Vé[Link] lequel nous
exposerons les approches exactes, telles que les algorithmes de programmation linéaire, les
algorithmes branch-and-bound, ainsi que les approches heuristiques et métaheuristiques,
comme les algorithmes génétiques, les algorithmes de colonies de fourmis, les algorithmes
de recuit simulé, etc.

enﬁn, dans le quatrième chapitre, nous exposerons les resutat de la résolution du Pro-
blème de Routage de Véhicules (VRP) en développant une application avec une interface
conviviale, a compagnie un tableau de bord informatif et un backend robuste pour résoudre
eﬃcacement le VRP en utilisant des algorithmes heuristiques et métaheuristiques.

Passé cette étape, il a fallut l’intégration des algorithmes heuristiques et métaheu-

ristiques dans l’application, nous expliquerons comment ces algorithmes sont adaptés et
implémentés pour résoudre le VRP de manière eﬃcace et optimale.

9
Chapitre 1

Le transport de marchandise et
distribution

10
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.1 Introduction

Le transport de marchandises et approvisionnement est une clés de la chaı̂ne logistique,

il s’agit d’un processus de gestion des flux de matières premières, de produits semi-finis
et de produits finis depuis leur point d’origine jusqu’à leur point de consommation.

Le transport de marchandises et la distribution sont des activités clés pout les entre-
prises,une planification efficace de la chaı̂ne d’approvisionnement et de distribution, doit
obillier a certaine critère : une sélection judicieuse des modes de transport et des moyens
contribue a améliorer la rentabilité des entreprises, par la réduction des coûts et à offrir
un meilleure service aux client.

Dans ce premier chapitre, nous allons en premier lieu, présenter des généralités sur
le transport routier de marchandises, en second lieu, nous allons présenter les diﬀérentes
réglementations du transport routier de marchandises.

1.2 Historique de transport

Le transport de marchandises routier est apparu à la ﬁn du XIXe(19 ème) siècle, avec

l’invention de l’automobile et du camion, au début du XXe(21 ème) siècle, le transport
routier était surtout utilisé pour les courtes distances et les livraisons locales.

Cependant, avec le développement des autoroutes et des réseaux routiers, le transport

de marchandises routier est devenu de plus en plus important. Dans les années 1950 et
1960, les camions ont commencé à concurrencer les chemins de fer pour le transport de
marchandises sur les longues distances.

Dans les années 1970, la libéralisation du marché européen a favorisé le développe-

ment du transport de marchandises routier à l’échelle internationale. Les entreprises de
transport ont pu s’implanter dans plusieurs pays et proposer des services de transport
transfrontalier.

Depuis lors, le transport de marchandises routier est devenu un moyen de transport

de plus en plus important pour les entreprises, en particulier pour les livraisons express et
les transports de courte distance. Aujourd’hui, le transport routier est le principal mode
de transport de marchandises en Europe, représentant environ 70 pourcent du tonnage
total transporté.

Cependant, le transport routier est également confronté à plusieurs déﬁs, tels que les
problèmes de congestion routière, les coûts élevés de carburant, les problèmes de sécurité
routière et les impacts environnementaux. Les entreprises de transport travaillent donc
constamment pour améliorer l’eﬃcacité et la durabilité de leurs opérations de transport
de marchandises routier.

11
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.3 Déﬁnition

Transport : Le transport est le déplacement d’objets, de marchandises, ou dindividus

(humains ou animaux) d’un endroit à un autre. avec une distribution des moyens approprie
,infrastructure adéquat dans un périmètre et un temps bien déterminé. Le mode dépend
également du type de véhicule ou dinfrastructure utilisé.

Transport de marchandise Le transport de marchandises est une activité à lorigine du

commerce qui consiste à acheminer des ﬂux dun point A vers un point B, partout dans le
monde et selon des délais. Cela est rendu possible grâce à plusieurs modes de transport :
routier, ferroviaire, maritime, ﬂuvial et aérien.[30]

Transport de marchandise par route : Le transport routier de marchandises consiste

à transporter des marchandises par le réseau routier, généralement par camions. Le trans-
port de marchandises est un élément clé de l’économie. Il constitue une composante in-
dispensable du processus de production et de distribution des biens matériels et utilisant
d’infrastructure routière.[29]

Distribution :

Selon DIOUX ET DUPUIS (2009) la distribution est le chemin suivi par un produit
ou un service, depuis la production jusqu’à la consommation, en regroupant lensemble des
personnes ou des entreprises que lon appelle les intermédiaires. Ces derniers constituent
les éléments de base du canal de distribution de lentreprise.[22]

image//[Link]

Figure 1.1 – Les fonction de la chaine logistique

12
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.4 Les diﬀérents mode

La gestion du transport de marchandises est un domaine qui a connu une croissance

rapide au cours des dernières années. Il est essentiel que les entreprises appréhendent
les différentes méthodes de transport disponibles afin de mieux gérer leurs opérations
logistiques. Les entreprises peuvent choisir parmi plusieurs moyens pour l’acheminement
des marchandises. La méthode sélectionnée doit être en accord avec le type et la quantité
de produits à transporter, le temps disponible et le budget alloué. Chaque option présente
des avantages et des inconvénients qui doivent être pris en compte pour garantir que les
délais de livraison sont respectés et que les coûts sont maı̂trisé[Link] transport terrestre est
la méthode la plus populaire car il est abordable, pratique et offre une variété d’options
pour le chargement et le déchargement des marchandises. Les camions, les remorques et les
conteneurs peuvent être utilisés pour acheminer les produits à travers des routes nationales
et internationales. Les entreprises peuvent également recourir au transport ferroviaire qui
offre une alternative intéressante lorsque la distance à parcourir est importante.

image/65464561 - Copie - [Link]

Figure 1.2 – Transport marchandise routier

13
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

Le transport maritime est couramment utilisé pour acheminer de grandes quantités de

marchandises à l’[Link] bateaux-conteneurs sont particulièrement adaptés au
transport maritime car ils permettent d’embarquer un volume important de marchandise
tout en réduisant les coûts.

image/maritime - [Link]

Figure 1.3 – Transport marchandise maritime

Le transport aérien constitue une solution idéale pour transporter rapidement des pro-
duits sensibles ou très fragiles qui nécessitent un traitement spécial. Cette méthode s’avère
toutefois très coûteuse et n’est donc pas recommandée pour l’acheminement régulier des
produits sur de longues distances. Les entreprises peuvent toutefois recourir aux services
d’un cargo aérien pour expédier de petites quantités de marchandise sensible à destina-
tion internationale. Enfin, il existe des moyens alternatifs de transporter les marchandises
comme le transport par voie fluviale ou routière qui peut être très rentable si les condi-
tions climatiques sont favorables et si la distance à couvrir est relativement courte. De
plus, certaines entreprises optent pour le fret multimodal qui combine plusieurs moyens
de transport (terrestre, fluvial, aérien) afin daccroitre la flexibilité et réduire les coûts
globaux du projet logistique. Ainsi, il existe plusieurs formes de gestion du transport de
marchandises qui peuvent être utilisées selon les besoins spécifiques dune entreprise. Il
convient toutefois de noter quil est indispensable deffectuer un choix judicieux en fonc-
tion des caractéristiques du produit à transporter afin doptimiser la chaı̂ne logistique et
maximiser son efficacité globale.[28]

14
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.5 Les types de transport

1.5.1 Transport des voyageur

Un voyageur est une personne qui se déplace sur un parcours généralement préétabli en
empruntant un moyen de transport particulier, généralement les transports en commun.
Le transport de voyageurs peut être eﬀectué à diﬀérentes échelles, allant du transport
local dans une ville ou une région, au transport interurbain, national ou international.[9]

Transport de voyageurs urbain : Les réseaux de transport public urbain desservent

généralement les zones urbanisées. Pour les zones moins denses et pour les liaisons entre
agglomérations, des réseaux de transport interurbain existent.

Transport de voyageurs interurbain :

Les transports interurbains ont pour caractéristiques de répondre aux besoins de trans-
port à l’extérieur des agglomérations, en général d’une ville à une autre et en autocar.
L’interurbain regroupe les lignes régulières et le transport occasionnel.[15]

1.5.2 Le transport routier de marchandises à longue distance

Le transport routier de marchandises à longue distance désigne lexpédition de mar-

chandises sur de longues distances, généralement entre diﬀérents pays. Cela peut être fait
par une variété de véhicules, des camions aux remorques chargées.

Ces entreprises proposent souvent aussi des services logistiques pour aider les clients à
organiser eﬃcacement leurs expéditions. Les principaux avantages de ce type de transport
routier de marchandises sont la ﬂexibilité, car les envois peuvent être programmés pour
être livrés dans un délai précis.

1.5.3 Le transport routier de marchandises à courte distance

le transport routier de marchandises à courte distance fonctionne de la même manière,

mais avec des itinéraires de service de transport à lintérieur dun seul pays, voire dune
seule province. Le personnel devra donc connaı̂tre les conditions routières au Québec ou
dans la région où il travaillera.[16]

1.6 Réglementation contrat de transport marchandise

Le contrat de transport de marchandises est un contrat commercial Il est matérialisé

par un document dénommé diﬀéremment selon le mode de transport. En transport routier

15
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

de marchandises, le document se nomme légalement lettre de voiture (anciennement ou

usuellement récépissé de livraison, bon de livraison, ...).

Le contrat de transport de marchandises mentionne généralement ce qui est transporté

(catégorie de marchandises, poids, volumes), les lieux de chargement et de déchargement,
le nom du transporteur et celui du commissionnaire de transport, des mentions concer-
nant la dangerosité, les sommes à encaisser, des instructions particulières de livraison, les
incoterms ...

1.6.1 La feuille de la route

La feuille de route constitue la preuve d’existence du contrat de [Link] exploi-

tation permet :
• Le suivi des mouvements de marchandises.
• La maı̂trise des éléments dimposition au réel
• La satisfaction des exigences des transports internationaux.

1.6.2 Les types des contrat

Il existe deux sortes de contrat de transport :

• Le contrat de transport de voyageurs
• Le contrat de transport de marchandises
Un contrat peut être :
• Commercial
• Civil
• Mixte
Le but du contrat déterminera la qualification de celui-ci :
• Si les deux contractants tendent à réaliser un bénéfice, le contrat sera considéré
comme commercial.
• Si aucun contractant na pour but de réaliser des bénéfices, le contrat sera réputé
être civil.
• Au cas où lun des deux contractants seulement tendra à réaliser un bénéfice, le
contrat sera appelé ń contrat mixte ż dans la mesure où est commercial pour lun et
civil pour lautre.

1.6.3 Reglementation

La réglementation du transport de marchandises routier en Algérie repose sur des lois

spéciﬁques visant à garantir la sécurité, la conformité et l’eﬃcacité des opérations. Deux

16
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

lois importantes dans ce domaine sont la loi 0-13 et les lois 04-415 et 04-416. Ces lois
établissent un cadre juridique essentiel pour le transport de marchandises en Algérie, en
fixant des normes et des exigences auxquelles les transporteurs doivent se conformer.
a) Permis de conduire : Les conducteurs de véhicules de transport de marchandises
doivent détenir un permis de conduire approprié pour le type de véhicule qu’ils
conduisent, souvent assorti de certaines restrictions ou qualifications supplémen-
taires.
b) Limites de poids et de dimensions : Les véhicules de transport de marchandises
doivent respecter des limites de poids et de dimensions spécifiques définies par les
autorités routières. Cela inclut le poids total autorisé du véhicule, le poids par essieu,
la longueur, la largeur et la hauteur maximales.
c) Temps de conduite et de repos : Les conducteurs de véhicules de transport de mar-
chandises doivent respecter des règles strictes concernant les temps de conduite et
de repos pour garantir la sécurité routière. Ces règles peuvent inclure des limites sur
la durée quotidienne de conduite, des temps de repos obligatoires et des restrictions
sur les heures de conduite nocturne.
d) Sécurité des marchandises : Les marchandises transportées doivent être sécurisées
de manière appropriée pour éviter tout mouvement ou dommage pendant le trans-
port. Des règles spécifiques peuvent régir la manière dont les marchandises doivent
être chargées, arrimées et protégées à l’intérieur du véhicule.
e) Documents et autorisations : Les transporteurs de marchandises doivent s’assu-
rer d’avoir les documents et les autorisations appropriés pour transporter des mar-
chandises. Cela peut inclure des licences spécifiques, des permis de transport, des
documents de douane et des preuves d’assurance.
f) Équipement de sécurité : Les véhicules de transport de marchandises doivent être
équipés de dispositifs de sécurité obligatoires tels que des feux de signalisation, des
dispositifs réfléchissants, des extincteurs d’incendie et des trousses de premiers soins.

1.7 Les intervenants de TRM

Le transport de fret est un processus complexe. Pour cette raison, les acteurs sont
multiples et indispensables au bon déroulement du transport.

1.7.1 Le commissionnaire de transport

Le commissionnaire de transport dont le rôle est dorganiser le transport des marchan-

dises avec les transporteurs en échange dune commission. Pour ce faire, il choisit les modes
de transport qui lui semblent les plus adaptés. Lintérêt est de gagner du temps et de délé-
guer à un professionnel si on pense ne pas maı̂triser tous les rouages du fret international.
En transport routier, le commissionnaire de transport peut sous-traiter (pour plus de 15
pourcent de son chiffre daffaires) le transport qui lui est confié.

17
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.7.2 Les transitaires

Les transitaires ou agents chargés d’eﬀectuer les opérations de mise sous douane ou de
dédouanement, cest-à-dire des déclarations de douane pour le compte d’autrui, éventuelle-
ment des déclarations complémentaires particulières, pour le compte des expéditeurs, des
transporteurs, des commissionnaires ou des destinataires.

Le transitaire est celui mandaté par un donneur dordre (expéditeur ou destinataire)

pour organiser la liaison entre les diﬀérents transporteurs dans le cas de marchandises
devant emprunter plusieurs transports successifs. Son rôle est dassurer la continuité du
transport.

1.7.3 Le courtier

Un courtier se borne à rapprocher les parties en vue de la conclusion dun contrat. Le

courtier reste étranger au contrat conclu, autrement dit mandataire du client. Cest lui qui
donne lordre de déplacement de marchandises.[1]

1.7.4 Le transporteur

C’est une personne ou une société qui garantit lacheminement dans un lieu donné, des
personnes, des produits ou des marchandises à laide des moyens de transport en respectant
les délais déterminés par le client contre une rémunération.[1]

1.7.5 Le logisticien

C’est un spécialiste ou un professionnel de la logistique. Cest lui qui gère toute la

chaine logistique de lentreprise, de lapprovisionnement à la distribution ﬁnale, sachant
quil est un expert de la fonction.[1]

1.8 Les diﬀérentes stratégies de transport

Pour organiser lacheminement de leurs marchandises, les entreprises ont recours à une
diversité de stratégies de transport (transport pour compte propre, sous-traitance directe
à des transporteurs, sous-traitance à des transitaires ou auxiliaires de transport, et la
stratégie combinée) (Belotti, 1992 ; Cecilia, 2011).[5]

18
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.8.1 Le transport pour compte propre

Il se déﬁnit comme un transport exécuté pour ses besoins propres, par une entreprise,
pour déplacer en gardant la maı̂trise du transport, des marchandises lui appartenant ou
faisant lobjet de son commerce, de son industrie ou de son exploitation, avec des véhicules
lui appartenant ou mis à sa disposition exclusive par location (Cecilia, 2011). Malgré
la croissance exponentielle du volume et de lintensité des ﬂux physiques qui poussent
aujourdhui les chargeurs à faire appel à des prestataires logistiques externes (Belotti,
1992 ; Chevalier et Duphil, 1988 ; Lemeunier, 1989 ; Cecilia, 2011), certaines entreprises
continuent à assurer elles-mêmes le transport de leurs marchandises.[5]

1.8.2 La sous-traitance directe à des transporteurs

Les transporteurs sont des personnes morales, propriétaires des moyens de transport,
qui assurent lacheminement des personnes et/ou des biens. Ils sont généralement spéciali-
sés par mode de transport, par type de produit transporté ou par type de prestation oﬀerte
(Chevalier et Duphil, 1988 ; Belotti, 1992). La catégorisation par nature de marchandises
transportées permet de distinguer les transporteurs de marchandises conventionnelles, les
transporteurs de marchandises conteneurisées, les transporteurs dhydrocarbures...etc[5]

1.8.3 La sous-traitance à des transitaires ou auxiliaires de transport

Les transitaires sont des intermédiaires entre les entreprises et les transporteurs. Ils
assurent un rôle de conseils et oﬀrent aux entreprises une diversité de prestations de
services (Chevalier et Duphil, 1988 ; Belotti, 1992, 2015). En fonction de leur spécialisation
et du type dactivité qui conditionnent leur facturation, ils peuvent prendre le statut de
mandataire, de commissionnaire ou dorganisateur de transport multimodal (OTM).[5]

1.8.4 Le recours combiné au transport en ﬂotte propre et à la sous-

traitance

À défaut de recourir exclusivement à lune des trois stratégies précédentes, lentreprise

peut opter pour une approche combinée. Celle-ci consiste pour lentreprise à utiliser sa
propre ﬂotte automobile et à recourir parallèlement à des sous-traitants (transporteurs
ou transitaires) pour assurer lacheminement de ses marchandises (Belotti, 1992). Cette
approche est privilégiée par certaines PME industrielles et commerciales. Plusieurs raisons
sont avancées par les responsables de ces entreprises pour justiﬁer ce choix stratégique.[5]

19
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.9 Leﬃcacité des stratégies de transport

D’une manière générale, l’efficacité logistique mesure le degré datteinte des objectifs
initiaux fixés par lentreprise (Morana et Gonzalez-Feliu, 2010 ; Marcon, Guinet et Tahon,
2008 ; Tchokogué, Jobin et Beaulieu, 1999).Une stratégie de transport est efficace si elle
permet à lentreprise dassurer lacheminement de ses marchandises dans le respect de ses
objectifs de coûts, de délais, de qualité et de sécurité. À ce propos, plusieurs travaux
de recherche se sont intéressés aux avantages et aux limites des différentes stratégies de
transport.[5]

image//[Link]

Figure 1.4 – Schéma de la stratégie de transport[5]

1.10 La gestion du transport marchandise

La gestion du transport des marchandises est une question très complexe qui nécessite
une bonne compréhension des principes de logistique. En effet, elle implique la mise en
oeuvre d’une variété de méthodes et de procédures visant à assurer que le produit arrive
à l’endroit et au moment requis. Les principaux objectifs poursuivis par la gestion du
transport des marchandises sont l’efficacité, la sûreté, la sécurité et la qualité.En ce qui
concerne l’efficacité et l’optimisation des coûts, le premier élément à prendre en compte
est le choix du mode de transport approprié. .En ce qui concerne la sûreté et la sécurité
des produits pendant le transport, il est essentiel de recourir à des mesures strictes concer-
nant l’emballage et la manutention des marchandises. En outre, il convient d’adopter des
moyens supplémentaires pour assurer un niveau adéquat de sûreté et de sécurité pendant
le trajet (par exemple, utiliser un système GPS pour suivre en temps réel le transport).[28]

20
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

1.10.1 Les outils utilisé dans la gestion de TRM

SAP (Systems, Applications, and Products in Data Processing)

SAP (Systems, Applications, and Products in Data Processing) est une entreprise de
logiciels allemande qui fournit des solutions d’entreprise pour la gestion des processus
mé[Link] propose une gamme de produits logiciels destinés à répondre aux besoins de
gestion de diﬀérentes fonctions de l’entreprise telles que la ﬁnance, la gestion des ressources
humaines, la gestion de la chaı̂ne d’approvisionnement, la vente et la distribution, la
production, la maintenance, etc.

Voici quelques-unes des fonctionnalités de base des logiciels SAP et leur utilisation
dans les entreprises :
• Gestion financière : les logiciels SAP offrent une gamme complète de solutions pour
la gestion financière, y compris la comptabilité, les finances, les rapports financiers.
• Gestion des ressources humaines : SAP propose des solutions pour la gestion des
ressources humaines, y compris la gestion de la paie, la gestion des avantages sociaux,
la gestion du personnel, la gestion des performances, la formation et le développe-
ment.
• Gestion de la chaı̂ne d’approvisionnement : les solutions SAP pour la gestion de la
chaı̂ne d’approvisionnement incluent la planification de la demande, la planification
des approvisionnements, la gestion des stocks, la gestion des commandes et la gestion
des fournisseurs.
• Gestion de la production : SAP propose des solutions pour la gestion de la produc-
tion, y compris la planification de la production, la gestion de la qualité, la gestion
de la maintenance.

TMS (Transportation Management System)

TMS (Transportation Management System) est un logiciel de gestion du transport uti-

lisé dans l’industrie du transport et de la logistique. Il permet aux entreprises de planiﬁer,
d’organiser et de suivre les mouvements de leurs marchandises depuis leur point d’origine
jusqu’à leur destination ﬁnale.

Le TMS est utilisé pour optimiser les opérations de transport en fournissant des infor-
mations en temps réel sur l’emplacement des expéditions, les temps de transit, les coûts
de transport et les capacités de chargement des camions. Les fonctionnalités typiques d’un
TMS comprennent la gestion des commandes, la gestion des tarifs et des factures, ainsi
que la génération de rapports sur les performances de transport.

voici une vue d’ensemble générale de la façon dont fonctionne un système de gestion
de transport (TMS) :
• Gestion des commandes : Le TMS commence par la gestion des commandes, qui
consiste à capturer tous les détails pertinents d’un envoi, tels que l’origine, la desti-
nation et le poids de l’envoi.

21
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

• Sélection du transporteur : Le TMS utilise une base de données de transporteurs

et de leurs tarifs pour sélectionner le meilleur transporteur pour l’envoi. Cela peut
impliquer la comparaison des tarifs, des délais de transit et d’autres facteurs pour
choisir le transporteur qui répond le mieux aux besoins de l’envoi.
• Gestion ﬁnancière : le TMS aide à gérer les aspects ﬁnanciers de l’envoi, tels que la
génération de factures et le paiement des transporteurs.

1.11 Les problème de gestion dans le transport du marchan-

dise routier

Le transport de marchandises routier présente divers problèmes de gestion, notam-

ment :
1. Planification inefficace des itinéraires :Une planification inadéquate des itinéraires
peut entraı̂ner des distances parcourues excessives, une utilisation inefficace des res-
sources et des coûts de carburant élevés. Une mauvaise planification peut également
entraı̂ner des retards dans les livraisons et une insatisfaction des clients.
2. Gestion des capacités : La gestion des capacités est un défi majeur dans le transport
routier, notamment en termes de capacité de chargement des véhicules. Optimiser
l’utilisation de l’espace disponible tout en respectant les limites légales de poids et
de volume peut être complexe
3. Coûts de transport élevés : Les coûts de transport peuvent représenter une part
importante des dépenses pour les entreprises. La gestion efficace des coûts, y compris
la réduction des coûts de carburant, des temps de conduite non productifs et des
coûts de maintenance, est essentielle pour garantir la rentabilité
4. Émissions de gaz à effet de serre : Les camions utilisés dans le transport routier de
marchandises fonctionnent généralement avec des moteurs diesel qui émettent du
dioxyde de carbone (CO2) et d’autres gaz à effet de serre. Ces émissions contribuent
au réchauffement climatique et aux changements climatiques

1.12 Optimisation des Solutions de Transport de Marchan-

dises

Le problème de routage de véhicules (VRP) a émergé comme une solution essentielle

pour l’industrie du transport de marchandises routier. En raison de la complexité des
opérations logistiques, telles que la gestion des itinéraires, des délais et des coûts, le VRP
offre une approche d’optimisation précieuse. Il permet de résoudre les défis liés au transport
de marchandises en trouvant les itinéraires les plus efficaces pour minimiser les distances
parcourues, réduire les coûts de carburant et optimiser l’utilisation des ressources. Grâce
à cette optimisation, les entreprises peuvent respecter les délais de livraison convenus avec
les clients, améliorer leur satisfaction et réduire les coûts opérationnels. En utilisant des
technologies de suivi et de traçabilité, le VRP permet également une meilleure visibilité

22
CHAPITRE 1. LE TRANSPORT DE MARCHANDISE ET DISTRIBUTION

des marchandises tout au long du processus de transport. Ainsi, le VRP joue un rôle
clé dans l’amélioration de l’eﬃcacité et de la rentabilité du transport de marchandises
routier, tout en répondant aux exigences des clients et en garantissant la conformité aux
réglementations régissant le secteur.

1.13 Conclusion

En conclusion, notre exploration du transport de marchandises nous a permis de mieux

comprendre les défis auxquels il est confronté [Link] le prochain chapitre nous défi-
nirons le problème du VRP (le problème du routage des véhicules) et nous identifierons
ses différents types. Ces connaissances nous permettront de développer des solutions plus
efficaces pour optimiser les modes de livraison, réduire les coûts et réduire lempreinte
écologique.

23
Chapitre 2

Problème de VRP(Véhicule Routing

Problème)

24
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

2.1 Introduction

Aﬁn d’optimiser d’une manière eﬃcace la rentabilité des opération de transport et

distribution des marchandises,les entreprises recours a des méthode tel que le VRP qui
concerne la résolution dédié a transport de marchandise. Comment les choses sont livrées
à partir d’un ou plusieurs dépôts qui disposent d’un ensemble donné de véhicules domes-
tiques et exploités par un ensemble de chauﬀeurs qui peuvent se déplacer sur un réseau
routier donné vers un ensemble de clients.

2.2 Déﬁnition

Le VRP, est un problème d’optimisation complexe dans lequel il existe un ensemble

de clients situés à divers endroits, chacun ayant des besoins en matière d’expédition, et
une flotte de véhicules partant du dépôt central qui doit satisfaire de manière optimale
les besoins des clients [13]. L’objectif d’un VRP typique est de trouver la route optimale
pour minimiser les coûts totaux. De plus, divers facteurs affectant la planification de
l’itinéraire, tels que la capacité des véhicules, la consommation de carburant, la congestion
du trafic, etc., doivent être pris en compte pour réaliser la minimisation des coûts totaux
de l’itinéraire.

Le VRP est souvent résolu en utilisant des algorithmes d’optimisation, tels que des
algorithmes génétiques, des algorithmes de recherche tabou et des algorithmes de clus-
tering. Ces algorithmes peuvent être utilisés pour trouver des solutions optimales pour
des problèmes de taille moyenne, mais pour des problèmes plus complexes, des techniques
d’intelligence artiﬁcielle peuvent être nécessaires.

image//[Link]

Figure 2.1 – Problem Vehicule routing

25
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

2.3 Historique de VRP

Dantzig et Ramser (1959) ont été les premiers à introduire le ”problème de dispatching
de camions”, modélisant comment une ﬂotte de camions homogènes pouvait répondre à
la demande en pétrole de plusieurs stations-service à partir d’un centre de distribution
centralisé, avec un minimum de distance parcourue. Cinq ans plus tard, Clarke et Wright
(1964) ont généralisé ce problème en un problème d’optimisation linéaire couramment ren-
contré dans le domaine de la logistique et des transports : c’est-à-dire comment desservir
un ensemble de clients, dispersés géographiquement autour du centre de distribution, en
utilisant une ﬂotte de camions de capacités variables. Ceci est devenu connu sous le nom
de ”Problème de routage de véhicules” (VRP), l’un des sujets les plus étudiés dans le
domaine de la recherche opérationnelle[13].

Au fil des ans, de nombreuses variantes du VRP ont été développées pour prendre
en compte différents aspects du problème, tels que la capacité des véhicules, les coûts de
transport, les fenêtres de temps, les contraintes de synchronisation, etc. En conséquence,
le VRP est devenu un domaine de recherche très actif et diversifié, avec de nombreuses
approches algorithmiques proposées pour résoudre les différentes variantes du problème.

Aujourd’hui, le VRP reste un problème d’optimisation important pour les entreprises

et les gouvernements, car il permet d’optimiser l’utilisation des ressources de transport,
de réduire les coûts de transport et d’améliorer la qualité des services de livraison.

2.4 Les paramètres de problème tourné de véhicule

Le problème du voyageur de commerce (TSP) est un problème d’optimisation combi-

natoire qui consiste à trouver le chemin le plus court pour visiter une série de villes (ou
de points) en une seule fois. Dans ce problème, le chemin doit partir et arriver à la même
ville et ne peut passer par une ville plus d’une fois.

Les paramètres du problème du voyageur de commerce sont les suivants :

— Nombre de véhicules disponibles : le nombre de véhicules disponibles est le nombre
total de véhicules qui peuvent être utilisés pour le routage.
— Capacité des véhicules : la capacité des véhicules est la quantité maximale de mar-
chandises que le véhicule peut transporter.
— Coûts des déplacements entre les points de livraison : le coût des déplacements
entre les points de livraison est le coût des déplacements entre les points de livraison
pour chaque véhicule.
— Temps de livraison et de ramassage : le temps de livraison et de ramassage est
le temps nécessaire pour eﬀectuer la livraison et le ramassage à chaque point de
livraison.
— Contraintes de temps et de distance : les contraintes de temps et de distance sont
les limites de temps et de distance imposées par le [Link] exemple, le VRP peut
imposer une limite de temps pour chaque déplacement entre les points de livraison.

26
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

— Les fournisseurs et usines : les fournisseurs et usines sont les endroits où sont
stockées ou produites les marchandises à livrer.
— Type de véhicules disponibles :le type de véhicules disponibles est le type de vé-
hicules qui peuvent être utilisés pour le routage. par exemple, les véhicules légers,
lourds ou spécialisés.
— Contraintes d’équilibrage des chargements :les contraintes d’équilibrage des charge-
ments sont les contraintes imposées pour s’assurer que le chargement des véhicules
est équilibré. par exemple, les contraintes peuvent imposer une limite de poids ou
de volume pour chaque véhicule.

2.5 Variante de VRP

La multitude d’applications du VRP dans de nombreux domaines, dont celui du trans-

port et de la distribution, a fait naı̂tre dans la littérature de nombreuses variantes de VRP.
La section suivante présente les plus connues :

2.5.1 Le Capacitated Vehicle Routing Problem (CVRP)

Le Capacitated Vehicle Routing Problem (CVRP) est l’une des variantes pour les-
quelles il existe des déﬁnitions contradictoires. Pour certains auteurs (Cordeau et al.,
2005)[12] (Christiansen, 2007) elle se caractérise par la présence de la contrainte de capa-
cité et l’absence de contrainte d’autonomie. Pour d’autres (Chen et al., 2006) [10], c’est
un problème à plusieurs véhicules, avec contraintes de capacité et d’autonomie, et une
seule visite par client.

2.5.2 Le Véhicule Routing Problem with Time Windows (VRPTW)

Le Vehicle Routing Problem with Time Windows (VRPTW), ou VRP avec fenêtres
de temps, quant à lui, spéciﬁe que chaque client a une fenêtre de temps. Celle-ci est
un intervalle de temps au cours duquel son service (par exemple le chargement ou le
déchargement de marchandises) doit être accompli. Un véhicule peut arriver plus tôt,
mais il doit attendre jusqu’à ce que le service soit possible. Sil arrive plus tard, le service
ne peut pas être rendu et le client correspondant ne sera jamais satisfait. Dans ce cas,
le problème est dit ”à contraintes dures” (Hard time window constraints). L’objectif du
problème est alors de minimiser le nombre de véhicules et la distance totale parcourue
pour servir les clients sans violer les contraintes de fenêtres de temps. Dans les modèles
dits à contraintes molles (soft time windows constraints), les véhicules peuvent servir le
client en dehors de sa fenêtre de temps mais au prix d’une certaine forme de pénalité.
Bien que cette déﬁnition du VRP à fenêtre de temps soit la plus répandue, il est possible
de rencontrer dans certaines variantes du problème des fenêtres de temps relatives aux
horaires d’ouverture du dépôt ou aux horaires de travail du personnel (Ombuki et al.,
2006) [26].

27
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

2.5.3 Le Vehicle Routing Problem with Backhauls (VRPB)

Le Vehicle Routing Problem with Backhauls (VRPB), comporte deux types de clients,
soit receveurs (linehauls), soit livreurs (backhauls). Tous les produits livrés sont pris d’un
dépôt et tous les produits prélevés sont retournés au dépôt.

Ce modèle général résulte en trois catégories de VRPB

— Le VRP with Clustered Backhauls ou (Le Problème de Tournées de Véhicules avec
Ramassages ), dans lequel toutes les livraisons sont eﬀectuées avant le premier ra-
massage .
— Le VRP with Mixed Linehauls and Backhauls (VRPMB), dans lequel les ramassages
et les livraisons peuvent être mêlés dans une même tournée.
— Le VRP with Simultaneous Delivery and Pickup (VRPSDP), dans lequel chaque
client peut être receveur et livreur en même temps, (Hoﬀ et Løkketangen, 2006)[20].

2.5.4 Le Vehicle Routing Problem with Pick-up and Delivery (VRPPD)

Le Vehicle Routing Problem with Pick-up and Delivery (VRPPD) ou Problème de

Ramassage et de Livraison est presque identique au VRPB à l’exception du fait que les
produits livrés peuvent être pris, soit au dépôt, soit chez les livreurs et non uniquement
au dépôt.

Ce modèle recouvre deux catégories de problèmes :

1. Dans la première (unpaired pickup and delivery points), les demandes des clients
sont indépendantes, ce qui signiﬁe que chaque unité ramassée (au dépôt ou chez un
livreur) peut être employée pour livrer n’importe quel client receveur. Généralement,
ce problème est désigné sous le nom de Pick-up and Delivery VRP (PDVRP) et il
est mono produit, c’est-à-dire que tous les produits transportés sont du même type.
2. Dans la seconde catégorie (paired pickup and delivery points), les demandes des
clients sont dépendantes (liées) : chaque transport doit lier une origine et une des-
tination précises. Deux types de ce modèle coexistent : le Pickup and Delivery Pro-
blem (PDP) et le Dial-A-Ride Problem (DARP). PDP porte sur le transport des
marchandises (Ambrosini et al., 2004), tandis que DARP porte sur le transport de
personnes (Aldaihani et Dessouky, 2003) [2].

2.5.5 Le Stochastic Vehicle Routing Problem (SVRP)

Le Stochastic Vehicle Routing Problem (SVRP) ou Le Problème de Routage de Véhi-

cules Stochastique PRVS est un VRP dans lequel au moins un élément du problème est
aléatoire. Les trois cas les plus connus de SVRP (Cordeau et al., 2005)[12] sont :
1. Le VRP with Stochastic Customers (VRPSC), où Pi représente la possibilité qu’un
client i émette une demande.

28
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

2. Le VRP with Stochastic Demands (VRPSD), où la demande d’un client est une
variable aléatoire.
3. Le VRP with Stochastic Travel Times (VRPSTT), où le temps de service (si) d’un
client (i) et le temps de trajet (tij) d’un arc (i, j) sont des variables aléatoires.

2.5.6 Le Periodic Vehicle Routing Problem (PVRP)

Le Periodic Vehicle Routing Problem (PVRP) ou Problème de Tournées de Véhicules

Multi-Périodique (PTVMP) considère un horizon de planiﬁcation à M périodes. Chaque
client doit être visité k fois au cours de lhorizon (1 k M), et les demandes quotidiennes
sont ﬁxes (Lacomme et al., 2005)[21].

2.5.7 Le Multi-Depot Vehicle Routing Problem (MDVRP)

Le Multi-Depot Vehicle Routing Problem (MDVRP), comporte plusieurs dépôts dans

lesquels sont localisés les véhicules. Chaque tournée d’un véhicule doit commencer et ﬁnir
au même dépôt. De plus, chaque client doit être visité exactement une fois par l’un des
véhicules situés dans les dépôts indiqués par ce client (Mingozzi, 2005)[24].

2.5.8 Le Dynamic Vehicle Routing Problem (DVRP)

Le Dynamic Vehicle Routing Problem (DVRP) peut être défini comme un VRP où
l’information nécessaire à la planification des tournées :
— nest pas connue entièrement par le planificateur quand le processus de planification
commence.
— peut changer après que les tournées initiales aient été construites.
Autrement dit, certaines données du problème dépendent explicitement du temps, comme
l’apparition dun nouveau client ou la fin de service dun client (Bianchi, 2000)[7].

2.5.9 Le Vehicle Routing Problem with Split Delivery (VRPSD ou SD-

VRP)

Le Vehicle Routing Problem with Split Delivery (VRPSD ou SDVRP) remet en cause
deux contraintes du problème classique :
— Chaque client peut être visité plus dune fois si cela est nécessaire. Autrement dit,
la demande d’un client peut être divisée sur plusieurs tournées.
— la demande de chaque client peut alors être plus grande que la capacité des véhicules
(Archetti et al., 2002)[4].

29
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

2.5.10 Le Vehicle Routing Problem with Multiple Trips (VRPMT)

Le Vehicle Routing Problem with Multiple Trips (VRPMT), se rencontre principale-

ment lorsque la ﬂotte de véhicules est petite. Dans ce cas, certains véhicules peuvent exé-
cuter plusieurs tournées au cours d’une même période, en respectant une durée maximum
(horizon de temps qui correspond à la durée de travail de chaque véhicule par période).
Le VRPMT consiste à déterminer un ensemble de routes qui minimise le coût total de
transport (Alonso et al., 2006)[3].

image//[Link]

Figure 2.2 – Organigramme de variante VRP[22]

30
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

2.6 Les formules mathematique

Le VRP (Vehicle Routing Problem) est un problème d’optimisation combinatoire dans

lequel une ﬂotte de véhicules doit être utilisée pour desservir un ensemble de clients à partir
d’un dépôt central. La formulation mathématique du VRP peut être décrite comme suit :

2.6.1 Les paramètres

• C=1, 2, . . . , m représente l’ensemble des m clients à considérer.
• V = v0, v1, ..., vm, vm + 1 est l’ensemble des sommets dans le graphe. Les sommets
v0=vm+1 représentent le dépôt, et v1, . . . , vm représentent les clients.
• E = {(vi , vj ) | 0 ≤ i, j ≤ m, i ̸= j} est un ensemble de |V | × (|V | − 1)routes/edges
dirigées entre les sommets. Si les distances entre deux sommets dans les deux direc-
tions sont identiques, nous ajoutons alors la restriction (i<j).
• K désigne la ﬂotte de véhicules disponibles dans un seul dépôt. Tous les véhicules
considérés sont homogènes, c’est-à-dire qu’ils ont des capacités égales. Nous avons
n véhicules.
• Q est la capacité maximale d’un véhicule, qui limite le nombre de clients à visiter
avant de retourner au dépôt.
• C = (cij) est le coût de déplacement entre les nuds i et j et ci j ≥ 0 est la
distance correspondante des arêtes (vi,vj), la diagonale de la matrice i.e cii = 0
toujours. Selon que la variante VRP considérée est symétrique ou non, cij = cji.
L’inégalité triangulaire est supposée tenir généralement, c’est-à-dire cij ≤ cik + ckj
et (0 ≤ i, j, k ≤ m).
• Ri = (vi0 , vi1 , vi2 , vi3 , . . . , vik , vi+1 ) est un vecteur de la route du véhicule i qui com-
mence et se termine au dépôt, avec vi0 = vik+1 = v0 , vij ̸= vi , 0 ≤ j < l ≤ ki , et ki
est la longueur de la route Ri,
• S = R1, ..., Rn est l’ensemble de routes qui représentent l’instance de solution VRP.
∑
• C(Ri ) = kij =0 C(vij , vi(j+1) ) est le coût de la route Ri.
∑
• C(S) = ni=1 C(Ri ) est le coût total∪n de la solution S qui satisfait Ri ∩ Rj = {v0 }
∀Ri , Rj , (1 ≤ i, j ≤ n, i ̸= j) et i=1 Ri = S aﬁn que chaque client soit servi une
fois. Les vecteurs de route sont traités ici comme un ensemble.

Le but du VRP est de minimiser C(S) sur le graphe G(V,E). Soit G le graphe qui contient
|E| + 2 sommets, et les clients sont numérotés de 1, 2, . . . , m. Les dépôts de départ et de
retour sont respectivement notés 0 et m + 1. Dans cette section, nous avons introduit le
problème de routage des véhicules que nous avons maintenant défini. Cependant, le pro-
blème ne concerne pas seulement la visite des clients, il y a d’autres exigences liées à leurs
demandes. Dans les définitions suivantes, nous spécifierons ces demandes supplémentaires
des clients :
— la demande ; d = (d0 , . . . , dm , dm+1 ) avec di > 0 et m est le nombre total de clients
qui est un vecteur des demandes des clients, la demande du dépôt est notée par d0 ;
d0 = dm + 1 = 0 toujours.

31
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

— Déﬁnissons notre variable de décision : xijk = 1 si le véhicule k se déplace du nud i

au nud j, 0 sinon.
— qj est la quantité de demande au nud j.
La déﬁnition du problème sera basée sur les hypothèses suivantes :

- Les contraintes de capacité de tous les véhicules sont respectées.

- Chaque client peut être servi par un seul véhicule.
- Chaque itinéraire commence et se termine respectivement aux sommets 0 et m+1.

La formulation mathématique du CVRP est présentée comme suit avec une fonction
objectif de minimisation : ∑∑
min cij xijk (2.1)
k∈K
i∈V j∈V

soumis à :

∑
yik = 1, ∀i ∈ V \{0, f } (2.2)
k∈K

∑ ∑
xijk − xjik = 0, ∀i ∈ V \{0, f }, k ∈ K (2.3)
j∈V \{i} j∈V \{i}

∑ ∑
x0jk − xj0k = 1, ∀k ∈ K (2.4)
j∈V \{v0} j∈V \{v0}

∑
yik = xijk , ∀i ∈ V \{f }, k ∈ K (2.5)
j∈V \{i}

∑
ydk = xif k , ∀k ∈ K (2.6)
i∈V \{v1}

uik + qj ≤ ujk + Q(1 − xijk ), ∀i, j ∈ V, k ∈ K (2.7)

qi ≤ uik ≤ Q, ∀i ∈ V, k ∈ K (2.8)

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

yik ∈ {0, 1}, ∀i ∈ V, k ∈ K (2.10)

32
CHAPITRE 2. PROBLÈME DE VRP(VÉHICULE ROUTING PROBLÈME)

La formulation mathématique du CVRP énonce que l’objectif (1) est de minimiser le coût
total de déplacement des véhicules.
- la contrainte (1.2) oblige chaque client à être visité par exactement un véhicule.
- les contraintes (1.3) et (1.4) définissent le flux de cheminement des véhicules.
- les contraintes (1.5) et (1.6) assurent l’appariement des clients et des véhicules.
- les contraintes (1.7) et (1.8) garantissent le respect des contraintes de capacité.
- les contraintes (1.9) et (1.10) indiquent des contraintes d’intégralité.
La formulation intègre également les nuds de début et de fin (0 et f) pour plus de
commodité.

Les contraintes (1.7) et (1.8) permettent d’éviter les sous-tours dans la solution, c’est-
à-dire les boucles qui ne passent pas par le dépôt. Leur avantage est que, du point de vue
des clients, la formulation possède un nombre polynomial de contraintes

2.7 Conclusion

la résolution de ces problèmes nécessite l’utilisation de méthodes approximatives telles

que les heuristiques et métaheuristiques. Dans le prochain chapitre, nous explorerons en
détail les méthodes de résolution des VRP, en abordant à la fois les approches exactes et
les approches approximatives. Vous découvrirez les outils et les stratégies qui permettent
de trouver des solutions eﬃcaces et satisfaisantes pour ces problèmes complexes.

33
Chapitre 3

les methode de résolution

34
CHAPITRE 3. LES METHODE DE RÉSOLUTION

3.1 introduction

pour la resolution du problem VRP,Il existe plusieurs,ellepresent des avantages et des

inconvénients. Les plus courantes sont comme suit :
• Méthodes exactes : Ces méthodes résolvent le VRP en trouvant la solution optimale
exacte en explorant l’ensemble complet des solutions possibles.
• méthodes approchées : ces dernières sont aussi divisés en deux groupes :
1. Les heuristique
2. Les métaheuristiques.

3.2 les méthodes exactes

Les méthodes exactes comprennent

— la méthode branch and bound :
La méthode de branch-and-bound a été largement utilisée ces dernières décennies
pour résoudre le CVRP et ses principales variantes. Dans de nombreux cas, comme
pour le VRP asymétrique (ACVRP) et le VRP à contraintes de distance (DCVRP),
ces algorithmes représentent toujours l’état de l’art en matière de méthodes de
solution exactes. Dans leur vaste enquête consacrée aux méthodes exactes, Laporte
et Nobert ont donné une analyse complète et détaillée des algorithmes de branch-
and-bound proposés jusqu’à la ﬁn des années [Link] véicule routin prblem.
— la méthode branch and cut
— la méthode branch and price

3.3 les méthode approchées

3.3.1 Les heuristique

Plusieurs familles d’heuristiques ont été proposées pour le VRP. Elles peuvent être
largement classées en deux grandes classes : les heuristiques classiques, développées surtout
entre 1960 et 1990, et les métaheuristiques, dont la croissance s’est produite au cours de la
dernière décennie. La plupart des procédures de construction et d’amélioration standard en
cours d’utilisation aujourd’hui appartiennent à la première classe. Ces méthodes eﬀectuent
une exploration relativement limitée de l’espace de recherche et produisent généralement
des solutions de bonne qualité dans des temps de calcul modestes.

Les heuristiques classiques pour le VRP peuvent être largement classées en trois ca-
tégories. Les heuristiques constructives construisent progressivement une solution réali-
sable en gardant un il sur le coût de la solution, mais elles ne contiennent pas en soi de
phase d’amélioration. Dans les heuristiques à deux phases, le problème est décomposé en

35
CHAPITRE 3. LES METHODE DE RÉSOLUTION

deux composantes naturelles, la regroupement des sommets en itinéraires réalisables et

la construction réelle de l’itinéraire, avec des boucles de rétroaction possibles entre les
deux étapes. Les heuristiques à deux phases sont divisées en deux classes : les méthodes
cluster-ﬁrst, route-second et les méthodes route-ﬁrst, cluster-second. Dans le premier cas,
les sommets sont d’abord organisés en clusters réalisables, et un itinéraire de véhicule est
construit pour chacun d’eux. Dans le second cas, un parcours est d’abord construit sur
tous les sommets, puis est segmenté en itinéraires de véhicules réalisables.

Enfin, les méthodes d’amélioration tentent de mettre à niveau toute solution réali-
sable en effectuant une séquence d’échanges d’arêtes ou de sommets dans ou entre les
itinéraires de véhicules. Ces trois classes de méthodes sont couvertes dans les trois sec-
tions suivantes, respectivement. Cependant, la distinction entre les méthodes constructives
et les méthodes d’amélioration est souvent floue car la plupart des algorithmes construc-
tifs intègrent des étapes d’amélioration à divers stades. Étant donné que le nombre de
méthodes disponibles et de variantes est très grand, nous nous concentrons sur les heu-
ristiques et les améliorations vraiment classiques, en laissant de côté certaines variantes.
Pour des lectures supplémentaires sur les heuristiques classiques pour le VRP, [11]

3.3.2 méthod de constructive

Deux techniques principales sont utilisées pour construire des solutions VRP : la fusion
des itinéraires existants en utilisant un critère d’économies, et l’attribution progressive des
sommets aux itinéraires de véhicules en utilisant un coût d’insertion.

Clarke and Wright Savings Algorithm

L’algorithme de Clarke et Wright est probablement l’heuristique la plus connue pour

le VRP. Il est basé sur la notion d’économies. Lorsque deux itinéraires (0,..., i, 0) et (0,
j,..., 0) peuvent être fusionnés en un seul itinéraire faisable (0,..., i, j,..., 0), une économie
de distance s = Qo + CQJ - Cij est générée. Cet algorithme s’applique naturellement
aux problèmes pour lesquels le nombre de véhicules est une variable de décision, et il
fonctionne également bien pour les problèmes orientés ou non orientés, mais Vigo signale
que le comportement de la méthode se détériore considérablement dans le cas orienté,
bien que le nombre de fusions d’itinéraires potentiels soit alors réduit de moitié. Une
version parallèle et une version séquentielle de l’algorithme sont disponibles. L’algorithme
fonctionne comme suit :

Étape 1 (calcul des économies) : Calculer les économies si,j = Qo + Ci,0 + C0,j − Ci,j
pour i, j = 1, . . . , n et i ̸= j. Créer n itinéraires de véhicules (0, i, 0) pour i = 1, . . . , n.
Classer les économies de manière non décroissante.[27]

Version parallèle

Étape 2 (meilleure fusion réalisable) : À partir du haut de la liste des économies,

exécutez ce qui suit. Étant donné une économie sij, déterminez s’il existe deux routes,

36
CHAPITRE 3. LES METHODE DE RÉSOLUTION

l’une contenant l’arc ou l’arête (0, 7) et l’autre contenant l’arc ou l’arête (z, 0), qui
peuvent être fusionnées de manière réalisable. Si c’est le cas, combinez ces deux itinéraires
en supprimant (0, 7) et (z, 0) et en introduisant (z, 7).

Version séquentielle

Étape 2 (extension de la route) : Considérez tour à tour chaque route (0, z,... ,
7, 0). Déterminez le premier gain S(ki) ou Sji qui peut être utilisé de manière faisable
pour fusionner la route actuelle avec une autre route contenant l’arc ou l’arête (k, 0) ou
contenant l’arc ou l’arête (0, i). Implémentez la fusion et répétez cette opération pour la
route actuelle. Si aucune fusion faisable n’existe, considérez la route suivante et réappliquez
les mêmes opérations. Arrêtez lorsque aucune fusion de route n’est faisable

Les améliorations de l’algorithme de Clarke et Wright

Un inconvénient de l’algorithme original de Clarke et Wright est qu’il a tendance à

produire de bons itinéraires au début, mais des itinéraires moins intéressants vers la ﬁn, y
compris certains itinéraires circonférentiels. Pour remédier à cela, Gaskell [17] ont proposé
des économies généralisées de la forme sij = Ci0 + C0j − Acij où A est un paramètre de
forme d’itinéraire. Plus la valeur de A est grande.

Le l’algorithme de Clarke et Wright peut également être chronophage car toutes les
économies doivent être calculées, stockées et triées. Plusieurs améliorations ont été pro-
posées par un certain nombre d’auteurs pour accélérer les calculs et réduire les besoins
en mémoire. La plupart de ce travail a eu lieu dans les années 1970 et au début des
années 1980, lorsque les chercheurs travaillaient avec des ordinateurs beaucoup moins
puissants que les stations de travail actuelles. Des instances impliquant de 200 à 600 som-
mets pouvaient prendre de 25 à 300 secondes sur un ordinateur IBM 4341, en utilisant
une implémentation directe de la méthode d’économies parallèles [25]. Maintenant, une
instance de 200 sommets peut être résolue en 0,3 seconde sur une station de travail Sun
Ultrasparc 10 avec le même type d’implémentation. Par conséquent, ces améliorations ne
sont utiles que pour les instances très grandes (plus de 1000 sommets). Lors de la mise
en uvre de l’heuristique d’économies, deux problèmes principaux doivent être traités : la
détermination de la valeur maximale d’économies et les besoins en stockage.

La méthode en deux phases

1. Elementary Clustering Methods Nous présentons maintenant trois méthodes élé-

mentaires de regroupement : l’algorithme de balayage (voir Gillett et Miller [18]
l’algorithme basé sur l’assignation généralisée de Fisher et Jaikumar et l’heuristique
basée sur la localisation de Bramel et Simchi-Levi . Seules ces deux dernières heu-
ristiques supposent une valeur ﬁxe pour le nombre de véhicules K.
L’algorithme de balayage(sweep algorithme)
L’algorithme de balayage s’applique aux instances planaires de VRP. Des clusters
réalisables sont formés initialement en faisant tourner un rayon centré sur le dépôt.

37
CHAPITRE 3. LES METHODE DE RÉSOLUTION

Une route de véhicule est ensuite obtenue pour chaque cluster en résolvant un TSP.
Certaines implémentations incluent une phase de post-optimisation au cours de
laquelle les sommets sont échangés entre les clusters adjacents, et les routes sont
réoptimisées. À notre connaissance, les premières mentions de ce type de méthode
se trouvent dans un livre de Wren et dans un article de Wren et Holliday , mais
l’algorithme de balayage est généralement attribué à Gillett et Miller , qui l’ont
popularisé. Une mise en uvre simple de cette méthode est la suivante. Supposons
que chaque sommet i est représenté par ses coordonnées polaires (0 i , p), où 0 est
l’angle et p est la longueur du rayon. Assignez une valeur 0 i = 0 à un sommet
arbitraire i* et calculez les angles restants à partir de (0, i*). Classez les sommets
par ordre croissant de leurs angles 0i .
— Étape 1 (initialisation de la route) : Choisissez un véhicule k non utilisé.
— Étape 2 (construction de la route) : En partant du sommet non-routé ayant le
plus petit angle, assignez les sommets au véhicule k tant que sa capacité ou la
longueur maximale de la route n’est pas dépassée. Dans les DVRP fortement
contraints, la méthode 3-opt peut être appliquée après chaque insertion. Si des
sommets non routés restent, passez à l’étape 1.
— Étape 3 (optimisation de la route) : Optimisez chaque route de véhicule séparé-
ment en résolvant le TSP correspondant (exactement ou approximativement).
Fisher and Jaikumar Algorithm
L’algorithme de Fisher et Jaikumar est également bien connu. Au lieu d’utiliser une
méthode géométrique pour former les clusters, il résout un Problème d’Affectation
Généralisée (PAG). Il peut être décrit comme suit.
• Étape 1 (sélection de la graine) : Choisissez des sommets de graine jk dans V
pour initialiser chaque cluster k.
• Étape 2 (allocation des clients aux graines) : Calculer le coût dik de l’allocation
de chaque client i à chaque cluster k comme dik = min{c0i + cij + cjk + ck0 , c0j +
cjk + cki + ci0 } − (c0j + cjk + ck0 ).
• Étape 3 (affectation généralisée) : Résoudre un PAG avec des coûts dIj, des
poids de client qi et une capacité de véhicule Q.
• Étape 4 (solution TSP) : Résoudre un TSP pour chaque cluster correspondant
à la solution PAG.
Le nombre de trajets de véhicules K est fixé a priori dans l’heuristique de Fisher et
Jaikumar. Les auteurs ont proposé une méthode géométrique basée sur la partition
du plan en K cônes en fonction des poids des clients. Les sommets semences sont
des clients fictifs situés le long des rayons qui biseautent les cônes. Une fois que les
clusters ont été déterminés, les problèmes de TSP sont résolus de manière optimale
à l’aide d’une approche basée sur la relaxation de contraintes [23].
Bramel and Simchi-Levi Algorithm
Bramel et Simchi-Levi [8] ont décrit une heuristique en deux phases dans laquelle
les sommets sont déterminés en résolvant un problème de localisation capacité et
les sommets restants sont progressivement inclus dans leur route allouée dans une
deuxième étape. Les auteurs suggèrent tout d’abord de localiser K sommets, appelés
concentrateurs, parmi les n emplacements de clients pour minimiser la distance
totale des clients à leur sommet le plus proche tout en veillant à ce que la demande
totale attribuée à un concentrateur ne dépasse pas Q. Les routes des véhicules sont

38
CHAPITRE 3. LES METHODE DE RÉSOLUTION

ensuite construites en insérant à chaque étape le client assigné à ce sommet de route

ayant le coût d’insertion le plus faible. Considérons une route partielle k décrite par
le vecteur (0 = i0 , i1 ....il + il+1 = 0) soit Tk = (0, i1 ...., il ) et notons t(Tk ) la longueur
d’une solution TSP optimale sur Tk .Le coût d’insertion dik d’un client non routé i
dans la route k est alors donné par dik = t(Tk ∪ (i)) − t(Tk ).Comme le calcul de
dik exactement peut prendre du temps, deux approximations dik sont proposées : le
coût direct dik = min{cik } et Le coût d’insertion le plus proche dik = min{cik + cjk }
où cik représente le coût de déplacement entre le client i et le sommet de la route k,
et cjk représente le coût de déplacement entre le client j et le sommet de la route k
le plus proche de j. Les auteurs ont montré que l’algorithme défini par la première
règle est asymptotiquement optimal.
2. Route-first, cluster-second
Les méthodes ”Route-first, cluster-second” construisent, dans une première phase,
une tournée de TSP géante, en ignorant les contraintes secondaires, et décomposent
cette tournée en itinéraires de véhicules réalisables dans une seconde phase. Cette
idée s’applique aux problèmes avec un nombre de véhicules libre. Elle a été proposée
pour la première fois par Beasley [6], qui a observé que le problème de la seconde
phase est un problème de chemin le plus court standard sur un graphe acyclique
et peut donc être résolu en O(n2) temps en utilisant des algorithmes traditionnels.
L’algorithme de Dijkstra est utilisé pour résoudre des problèmes de chemin le plus
court. Dans cet algorithme, le coût dij de voyage entre les nuds i et j est égal à C0i
+ C0j + lij , où lij est le coût de voyage de i à j dans la tournée TSP. Haimovich
et Rinnooy Kan [23] ont montré que si tous les clients ont une demande unitaire,
cet algorithme est asymptotiquement optimal. Cependant, cela n’est pas le cas pour
des demandes générales, sauf dans quelques cas triviaux (Bertsimas et Simchi-Levi
. Nous ne sommes pas au courant de toute expérience de calcul montrant que les
heuristiques ”Route-first, cluster-second” sont compétitives par rapport à d’autres
approches[14].

3.3.3 les métaheuristiques

Ces dernières années, plusieurs métaheuristiques ont été proposées pour le VRP. Ce
sont des procédures de solution générales qui explorent l’espace de solution pour identi-
ﬁer de bonnes solutions et intègrent souvent certains des heuristiques de construction et
d’amélioration de route standard.

3.3.4 algorithme génétique

L’algorithme génétique est une technique de recherche globale aléatoire qui résout les
problèmes en imitant les processus observés lors de l’évolution naturelle. Ce paradigme
de résolution de problèmes a été initialement proposé par (Holland) , bien qu’il ait fallu
10 ans avant qu’il ne soit pleinement reconnu par la communauté scientiﬁque. Un AG
pur est une méthode générique de résolution de problèmes qui utilise peu d’informations
heuristiques sur le domaine du problème. Il peut donc être appliqué à une large gamme

39
CHAPITRE 3. LES METHODE DE RÉSOLUTION

de problèmes mal déﬁnis qui ne se prêtent pas à des méthodes spécialisées. Fondamen-
talement, un AG fait évoluer une population de chaı̂nes de bits, ou de chromosomes, où
chaque chromosome code une solution à une instance particulière. Cette évolution se pro-
duit grâce à l’application d’opérateurs qui imitent des phénomènes naturels observés dans
la nature (par exemple, la reproduction, la mutation).

les étapes de l’algorithme génétique

— Initialiser une population de chromosomes (solutions candidates) de manière aléa-
toire.
— Évaluer chaque chromosome en fonction d’une fonction d’adaptation (ou fonction
objectif).
— Sélectionner les meilleurs chromosomes en fonction de leur score d’adaptation (sé-
lection naturelle).
— Utiliser des opérateurs génétiques tels que la croisement (crossover) et la mutation
pour créer de nouveaux chromosomes à partir des chromosomes sélectionnés.
— Évaluer les nouveaux chromosomes.
— Répéter les étapes 3 à 5 jusqu’à ce qu’un critère d’arrêt soit atteint, tel qu’un nombre
maximal d’itérations ou un score d’adaptation suﬃsamment élevé.
Le choix des opérateurs génétiques, tels que le taux de mutation ou de croisement, peut
varier en fonction du problème à résoudre et de la performance de l’algorithme.

3.3.5 recherche tabou

En recherche tabou, des séquences de solutions sont examinées comme dans le recuit
simulé, mais le prochain mouvement est effectué vers le meilleur voisin de la solution
courante xt. Pour éviter les cycles, les solutions récemment examinées sont interdites, ou
taboues, pendant un certain nombre d’itérations. Pour alléger les exigences en temps et
en mémoire, il est courant d’enregistrer un attribut des solutions tabou plutôt que les
solutions elles-mêmes. Le mécanisme de base de la recherche tabou peut être amélioré
par plusieurs fonctionnalités informatiques, telles que des stratégies de diversification et
d’intensification, comme décrit par Glover et Laguna [19].

Tabu search est de plus en plus utilisé pour résoudre des instances du VRP ces der-
nières années. Certains des premiers algorithmes de recherche tabou (Willard [31] n’ont
pas donné de résultats impressionnants, mais les implémentations ultérieures ont été beau-
coup plus réussies. Parmi les auteurs qui ont proposé des algorithmes de recherche tabou
eﬃcaces pour le VRP.

40
Chapitre 4

Résolution du problème tourné de

véhicule

41
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

4.1 introduction

Aﬁn de résoudre le problème lié au VRP (Problème de Routage de Véhicules), nous

proposons une approche efficace pour sa résolution. Cette approche consiste à appliquer
des méthodes visant à améliorer l’efficacité dans la planification des itinéraires et une allo-
cation des ressources de manière optimale, pour ce faire nous examinerons trois approches
algorithmiques : un algorithme de référence avec une stratégie d’affectation simpliste, un
algorithme heuristique basé sur des heuristiques pour un routage optimisé, et un algo-
rithme métaheuristique utilisant des techniques d’optimisation avancées.

En mettant en oeuvre ces algorithmes, notre objectif est d’améliorer l’efficacité opé-
rationnelle du VRP, en ce qui concerne l’evaluation des résultats obtenus à partir de ces
implémentations, présenté sous forme de tableau de bord convivial, ce tableau de bord
offrira des visualisations claires de l’utilisation des itinéraires. Il sera utilisé comme un
outil de prise de décision pour les responsables afin de les aider à prendre des décisions
adéquates alignées sur les objectifs fixés.

4.2 les outils informatique et méthode de résolution

Dans notre cas, nous avons utilisées plusieurs outils pour mettre en oeuvre les méthodes
de résolution du Problème de Routage des Véhicules (VRP)

4.2.1 python

Pour l’implémentation des algorithmes, nous avons utilisées le langage de programma-

tion Python, qui offre une flexibilité et une facilité de manipulation des données. Python
est un langage de programmation polyvalent et puissant. Créé en 1991, Python est très
utilisé dans le domaine du Machine Learning, du Big Data et de la Data Science. Nous
avons choisi Python pour sa simplicité, sa richesse en bibliothèques et son adaptabilité à
différents problèmes de programmation.

4.2.2 matrice de distance

Pour calculer les distances entre les points de livraison, nous avons utilisé une matrice
de distances qui nous permet de déterminer eﬃcacement les distances les plus courtes
entre chaque paire de points. Cette matrice de distances est une composante essentielle
dans la résolution du VRP.

42
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

4.2.3 l’API de Mapbox

En ce qui concerne la visualisation des itinéraires, nous avons utilisé l’API de Mapbox,
qui nous permet de générer des cartes interactives et de représenter visuellement les trajets
des véhicules. Cela oﬀre une meilleure compréhension de la planiﬁcation des itinéraires et
facilite l’analyse des résultats.

4.2.4 Langages de programmation et outils utilisés pour le développe-

ment de l’application

Nous avons utilisé HTML (HyperText Markup Language) pour la structure de base
de notre interface web. CSS (Cascading Style Sheets) a été utilisé pour la mise en forme
et la présentation visuelle, permettant ainsi de personnaliser l’apparence de notre tableau
de bord.

Pour ajouter des fonctionnalités interactives et dynamiques, nous avons utilisé JavaS-
cript et la bibliothèque jQuery. Ces outils nous ont permis de manipuler les éléments de
la page, d’eﬀectuer des calculs et des validations en temps réel, ainsi que d’ajouter des
eﬀets et des animations.

Pour améliorer l’expérience utilisateur, nous avons intégré la bibliothèque Font Awe-
some, qui oﬀre une vaste gamme d’icônes et de symboles prêts à être utilisés. Cela nous
a permis d’ajouter des éléments visuels signiﬁcatifs et attrayants à notre interface.

En combinant ces technologies, nous avons pu créer un tableau de bord interactif et

esthétiquement agréable pour visualiser les résultats de notre solution VRP.

4.2.5 Utilisation de bibliothèques et modules pour le développement de

l’application

Nous avons utilisé plusieurs bibliothèques et outils pour le développement de notre

application. Cela inclut itertools pour la manipulation d’itérables, networkx pour la ma-
nipulation de graphes, math pour les fonctions mathématiques, gurobipy et GRB pour
l’optimisation, ortools pour la résolution de problèmes complexes, et prettytable pour af-
ﬁcher des tableaux bien formatés. Ces bibliothèques ont joué un rôle clé dans la création
de fonctionnalités avancées, le calcul précis et l’aﬃchage convivial des résultats.

43
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

4.3 Explication de l’application DZAIR VRP Solution

nous présenterons en détail l’application que nous avons développée pour résoudre le
problème du VRP. L’application comprend plusieurs composants essentiels :

image/DZAIR VRP [Link]

Figure 4.1 – Logo de DZAIR VRP Solution

4.3.1 Interface utilisateur :

Nous décrirons l’interface utilisateur de notre application, qui permet aux utilisateurs
de fournir les données nécessaires, telles que les coordonnées des clients et les demandes
de livraison. Nous expliquerons également comment les utilisateurs peuvent visualiser les
résultats de la résolution du VRP.

[Link] (Home) :

Cette section de l’application fournit des informations générales sur l’application et

présente des fonctionnalités clés de l’utilisation de l’application de VRP.

image//[Link]

Figure 4.2 – l’interface d’application

44
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

2.À propos (About) :

Cette section fournit des informations détaillées sur l’application de VRP, expliquant
en quoi elle consiste, son objectif et ses avantages pour les utilisateurs.

image/[Link]

Figure 4.3 – Principales fonctions du l’application

[Link] (Service) :

Cette section décrit les diﬀérents services ou fonctionnalités oﬀerts par l’application
de VRP. Les fonctionnalités principales de résolution du problème de routage de véhicules
peuvent être mentionnées ici, telles que la recherche de la meilleure route pour un ensemble
de camions, la minimisation des coûts de carburant ou des distances parcourues etc.

image//[Link]

Figure 4.4 – Formulaire des informations

Formulaire de saisie d’informations (User Information) : Cette fonctionnalité permet

à l’utilisateur de saisir des informations spéciﬁques pour résoudre un problème de routage
de véhicules. Les informations que l’utilisateur doit fournir peuvent inclure :
— Le nombre de camions disponibles pour eﬀectuer les livraisons.

45
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

— La ville de départ des camions.

— Les villes de livraison où les marchandises doivent être livrées.
— Le prix unitaire du carburant pour calculer les coûts.
Ajouter une ville (Add City) : Cette fonctionnalité permet à l’utilisateur d’ajouter des
villes supplémentaires à la liste des villes de livraison.

[Link]

image//[Link]

Figure 4.5 – Portfolio

[Link] :

Cette section fournit des informations de contact pour les utilisateurs qui souhaitent
obtenir de l’aide, poser des questions ou fournir des commentaires sur l’application de VRP.
Les informations de contact peuvent inclure une adresse e-mail, un numéro de téléphone.

image//[Link]

Figure 4.6 – Les informations de contact

46
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

[Link] (Login) :

Cette fonctionnalité permet aux utilisateurs de se connecter à l’application à l’aide de

leurs identiﬁants personnels. La connexion peut être requise pour accéder à des fonction-
nalités avancées, enregistrer des paramètres personnalisés ou visualiser l’historique des
problèmes de routage résolus.

image//[Link]

Figure 4.7 – page de connexion

4.4 L’organisation de résaux de déstribution chez condor

logistics

4.4.1 Les points de vente

Région Est

Composé de 11 clients que nous citons ci-dessous : Tébessa, Souk Ahras, Bordj Bou
Arreridj, Sétif, Constantine, Annaba, Skikda, Guelma, Jijel, Béjaia, Batna.

Région Centre

Composé de 7 clients que nous citons ci-dessous : Tizi Ouzou, Boumerdes, Bouira,
Alger, Blida, M’sila, Tissemsilt.

Région Ouest

Composé de 8 clients que nous citons ci-dessous : Chlef, Tlemcen, Sidi Bel Abbès,
Mostaganem, Oran, Tipaza, Aı̈n Temouchent, Relizane.

47
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Région Sud

Composé de 9 clients que nous citons ci-dessous : Laghouat, El Bayadh, Naama, Tin-
douf, Ghardaia, Biskra, Ouargla, Béchar, El Oued.

image/[Link]

Figure 4.8 – l’emplacement de dépôt

4.4.2 Algorithme déplacement AB

Pendant la durée de notre stage chez Condor Logistique, nous avons constaté que
l’entreprise utilise la méthode de déplacement AB pour l’aﬀectation des camions pour la
distrubition de marchandise, cette méthode fonctionne selon le principe de l’alternance
entre les mouvements allant de l’entrepôt (A) vers les destinations des clients (B). nous
avons élaboré une algorithme pour calculer la distance total, le coût, le taux de pollution
dans le cas de le stratégie adapter par l’entreprise.
1 import itertools
2
3 def calculate_distance ( city1 , city2 , distance_matrix ) :
4 return distance_matrix [ city1 ][ city2 ]
5
6 def calculate_time ( city1 , city2 , time_matrix ) :
7 return time_matrix [ city1 ][ city2 ]+2
8
9 def assign_trucks ( distance_matrix , time_matrix , num_trucks ,
10 depot_city ) :
11 cities =[ 1 , 2 , 4 , 5 , 6 , 7 , 8 , 9 , 11 , 12 , 14 , 15 , 17 ,18 ,
12 20 , 21 , 22 , 23 , 24 , 26 , 27 , 29 , 30 , 31 , 32 , 34 ,
13 36 , 37 , 38 , 39 , 41 , 44 , 45 , 46 , 47 ]
14 total_distance = 0
15 total_time = 0
16 assignment = []
17

48
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

18 # Assign each city to a separate truck

19 for truck , city in enumerate ( cities ) :
20 truck_assignment = [ depot_city , city , depot_city ]
21 assignment . append ( truck_assignment )
22
23 # Calculate distance traveled by this truck
24 distance = calculate_distance ( depot_city , city ,
25 distance_matrix )
26 total_distance += distance * 2 # Include round trip
27
28 # Calculate time traveled by this truck
29 time = calculate_time ( depot_city , city , time_matrix )
30 if time > total_time :
31 total_time = time
32
33 # total_time = total_time / 24 # Convert time units to days
34
35 return assignment , total_distance , total_time
36

37 def format_assignment ( assignment , total_distance , total_time ,

distance_matrix , time_matrix ) :
38 output = []
39 output . append ( " Vehicle \ t \ tRoute \ t \ tDistance \ tTime " )
40
41 for i , truck_assignment in enumerate ( assignment ) :
42 route = " -> " . join ( str ( city +1) for city in truck_assignment )
43 vehicle = f " Vehicle { i +1} "
44 distance = calculate_distance ( truck_assignment [0] ,
truck_assignment [ -2] , distance_matrix )
45 time = calculate_time ( truck_assignment [0] , truck_assignment
[ -2] , time_matrix )
46
47 line = f " { vehicle . ljust (10) }\ t { route }\ t
48 { distance *2} km \ t \ t { time *2} h "
49 output . append ( line )
50
51 output . append ( f " Total Distance :\ t \ t \ t { total_distance } km " )
52 output . append ( f " Maximum Time :\ t \ t \ t \ t \ t { total_time *2:.2 f } h " )
53 output . append ( f " Frait de mission :\ t \ t \ t \ t { total_distance *3} DA " )
54 output . append ( f " Diesel cost :{ total_distance *0.30*29.01 ,2} DA " )
55
56 output . append ( f " Total cost :{ total_distance *3+ total_distance
57 *0.28*29.01 ,2} DA " )
58 output . append ( f " Emmision :\ t \ t \ t \ t \ t { total_distance *0.7} Kg / km " )
59
60 return output
61
62 def main () :
63

64 # the distance matrix

65 distance_matrix = [
66 [0 , 1175 , 1018 , 1454 , 1366 , 1495 , 1252 , ... , 1428] ,
67 [1175 , 0 , 404 , 664 , 588 , 437 , 538 , 740 , ... , 1218] ,
68 [1018 , 404 , 0 , 623 , 447 , 478 , 393 , 644 , ... , 1032] ,
69 [1454 , 664 , 623 , 0 , 119 , 318 , 217 , 1236 , ... , 491] ,
70 . 0
71 . 0
72 . 0

49
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

73 . 0
74 [1428 , 97 , 378 , 754 , 679 , 529 , 629 , 634 , ... , 0 ]
75 ]
76
77
78 # the time matrix
79 time_matrix = [
80 [0.0 , 13.1 , 11.3 , 16.2 , 15.2 , 16.6 , 13.9 , ... 14.3] ,
81 [13.1 , 0.0 , 16.0 , 11.5 , 11.6 , 15.6 , 14.5 , ... 17.6] ,
82 [11.3 , 16.0 , 0.0 , 11.7 , 18.9 , 17.2 , 16.4 , ... 13.3] ,
83 [16.2 , 11.5 , 11.7 , 0.0 , 9.3 , 18.2 , 15.1 , ... 19.4] ,
84 . 0.0
85 . 0.0
86 . 0.0
87 [14.3 , 12.2 , 12.5 , 15.5 , 17.2 , 14.0 , 17.1 , ... 0 ]
88 ]
89
90 num_trucks = 60
91 depot_city = 33
92
93 assignment , total_distance , total_time = assign_trucks (
distance_matrix , time_matrix , num_trucks , depot_city )
94
95 output = format_assignment ( assignment , total_distance , total_time ,
distance_matrix , time_matrix )
96 for line in output :
97 print ( line )
98
99 if __name__ == ’ __main__ ’:
100 main ()
Listing 4.1 – Algorithme aﬀectation AB

4.4.3 les input

a) matrice de distance :Une matrice représentant les distances entre différentes villes.
Chaque élément de la matrice indique la distance entre deux villes spécifiques. Cette
matrice est utilisée pour calculer la distance entre les villes lors de l’assignation des
camions.
b) matrice de temp : Une matrice représentant les temps de trajet entre différentes
villes. Chaque élément de la matrice indique le temps nécessaire pour se déplacer
entre deux villes spécifiques. Cette matrice est utilisée pour calculer le temps de
trajet entre les villes lors de l’assignation des camions.
c) nombre de véhicule : : Le nombre total de camions disponibles pour effectuer les
livraisons.
d) depot : La ville de départ commune pour tous les camions.
e) les point de vente : Villes où les marchandises sont distribuées à le client.

50
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

4.4.4 les output

a) la distance totale (total distance) : Elle est utilisée pour calculer différentes valeurs
liées à la distance parcourue.
b) le temps maximum (maximum time) : Il s’agir du temps maximal alloué pour
accomplir une mission ou une tâche spécifique. Dans le contexte donné, il est utilisé
pour calculer une valeur basée sur le double du temps total.
c) frais de mission (Mission expenses) : Le coût associé à la réalisation de chaque affec-
tation est calculé en multipliant la distance totale parcourue par 3 DA. La société a
fixé ce taux 3 DA par kilomètre comme taux de référence pour l’évaluation des frais
engagés lors des missions. Ainsi, en utilisant ce facteur de conversion, nous pouvons
estimer avec précision les dépenses totales en fonction de la distance parcourue pour
chaque tâche spécifique.
d) coût du diesel (Diesel cost) : Cette estimation représente le coût approximatif du
carburant diesel utilisé pour couvrir la distance totale. Le calcul est basé sur une
consommation moyenne de carburant de 0,30 litre par kilomètre, spécifique aux
camions Scania R500 utilisés en majorité dans l’entreprise. De plus, le coût du diesel
est pris en compte en utilisant un taux de 29,01 DA par litre, fourni par l’entreprise
pétrolière algérienne spécialisée dans la distribution des produits pétroliers, Naftal.
En multipliant la distance totale parcourue par ces facteurs, nous pouvons estimer
le coût du carburant diesel associé à chaque mission, ce qui permet une meilleure
évaluation des dépenses liées à la consommation de carburant.
e) coût total (Total cost) :. Elle représente le coût global associé à la mission, qui est
calculé en additionnant le coût de la mission et le coût du diesel.

4.5 Résultat obtenue

4.5.1 Les déplacement AB de condor logistique

Nous avons choisi une journée pour étudier a partir les bons de commande. Au cours
de cette journée, les planiﬁcateurs de l’entreprise ont utilisé 35 camions pour eﬀectuer les
livraisons des [Link]-dessous quelques exemples des voyages des camions :

— Camion 01 : Dépot (Bordj Bou Arreridj) → Chlef → Dépot

— Camion 02 : Dépot (Bordj Bou Arreridj) → Laghouat → Dépot
— Camion 03 : Dépot (Bordj Bou Arreridj) → Batna → Dépot
— Camion 04 : Dépot (Bordj Bou Arreridj)→ Béjaia → Dépot
— Camion 05 : Dépot (Bordj Bou Arreridj)→ Biskra → Dépot
— Camion 06 : Dépot (Bordj Bou Arreridj)→ Béchar → Dépot
— Camion 07 : Dépot (Bordj Bou Arreridj)→ Blida → Dépot
— Camion 08 : Dépot (Bordj Bou Arreridj)→ Bouira → Dépot
— Camion 09 : Dépot (Bordj Bou Arreridj)→ Tébessa → Dépot

51
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

— Camion 10 : Dépot (Bordj Bou Arreridj)→ Tlemcen → Dépot

— Camion 11 : Dépot (Bordj Bou Arreridj)→ Tizi Ouzou → Dépot
— Camion 12 : Dépot (Bordj Bou Arreridj)→ Alger → Dépot
— Camion 13 : Dépot (Bordj Bou Arreridj)→ Jijel → Dépot
— Camion 14 : Dépot (Bordj Bou Arreridj)→ Sétif → Dépot
— Camion 15 : Dépot (Bordj Bou Arreridj)→ Skikda → Dépot

Distance totale Frais de mission Coût du diesel Émissions de gaz Coût total (Da)
(km) (Da) (Da) (kg/km)
31694 95082 275832.88 22185.8 352526.02

Table 4.1 – Coûts et distances liés aux missions

image/[Link]

Figure 4.9 – les déplacement AB

52
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

4.6 Résolution de VRP

4.6.1 Résolution par méthode approché

[Link]

Nous avons développé un programme qui nous permet de donner une solution initiale
sur la base d’une heuristique [Link] allons expliquer le déroulement de cette
heuristique dans ce qui va suivre :

les données initiale :

1. Matrice de distances : Une matrice qui représente les distances entre différents
points dans le réseau routier. Cette matrice permet de calculer la distance totale
parcourue par les véhicules lors de leurs itinéraires.
2. Matrice de temps : Une matrice qui indique les temps de déplacement entre les
différents villes.
3. Nombre de véhicules : Le nombre total de véhicules disponibles pour effectuer
les livraisons.
4. Dépôt : Le point de départ commun pour tous les itinéraires. C’est le lieu où
les véhicules sont initialement chargés et où ils doivent revenir après avoir effectué
toutes les livraisons.
5. La capacité des véhicules : Fait référence au nombre maximum de villes ou de
points de livraison qu’un camion peut visiter lors d’une tournée. Cela détermine la
quantité de marchandises ou de colis qu’un camion peut transporter d’un point à un
autre. La capacité est exprimée en termes de limitations physiques telles que l’espace
de chargement disponible, le poids maximal autorisé et d’autres contraintes logis-
tiques spécifiques à chaque véhicule. En optimisant l’utilisation de la capacité des
véhicules, il est possible de planifier des tournées efficaces et de maximiser l’efficacité
du transport de marchandises.

le déroulement de l’algorithme :

nous utilisons un algorithme de recherche heuristique basé sur la méthode des arcs
les moins coûteux pour résoudre le problème de routage de véhicules. Nous utilisons la
bibliothèque OR-Tools pour implémenter cet algorithme.

nous initialisons les paramètres de recherche, tels que la stratégie de première solution
à utiliser. Dans ce cas, nous utilisons la stratégie PATH-CHEAPEST-ARC,qui consiste
à sélectionner les arcs les moins coûteux en termes de distance lors de la construction des
routes initiales.

53
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Algorithm 1 Solve Vehicle Routing Problem

Require :
1 : distance matrix : distance matrix between nodes
2 : time matrix : time matrix between nodes
3 : num vehicles : number of vehicles
4 : depot : depot node index
5 : vehicle capacity : list of vehicle capacities
6 : max route time : maximum route time
Ensure :
7 : routes : list of routes
8 : route distances : list of route distances
9 : route times : list of route times
10 : total distance : total distance of all routes
11 : function solve vehicle routing(distance matrix, time matrix, num vehicles, de-
pot, vehicle capacity, max route time)
12 : from [Link] solver import routing enums pb2
13 : from [Link] solver import pywrapcp
14 : from prettytable import PrettyTable
15 : ... ▷ code Python ici
16 : end function
17 : . . . ▷ Appel à la fonction

L’algorithme utilise la méthode ”solve-vehicle-routing” pour trouver les itinéraires opti-

maux. Cette méthode prend en paramètre une matrice de distances, une matrice de temps,
le nombre de véhicules, le point de départ (dépôt), la capacité maximale des véhicules et
le temps maximum de trajet.

Le modèle de routage est créé à l’aide de la classe ”Routing Model” et les diﬀérentes
contraintes sont ajoutées à l’aide des fonctions telles que ”Add Dimension With Vehicle
Capacity” pour la dimension temporelle et la capacité des véhicules, et ”Set Arc Cost
Evaluator Of All Vehicles” pour déﬁnir le coût des arcs.

L’algorithme utilise également des paramètres de recherche spéciﬁés par la classe ”De-
fault Routing Search Parameters” pour déﬁnir la stratégie de recherche. Ensuite, la mé-
thode ”Solve With Parameters” est utilisée pour résoudre le problème de routage.

Une fois la solution obtenue, les itinéraires, les distances et les temps de trajet sont
calculés en parcourant les véhicules et les emplacements. Les résultats sont ensuite aﬃchés
à l’aide de la bibliothèque ”Pretty Table” pour une présentation claire et lisible.

4.6.2 algorithme heuristique

1 from ortools . constraint_solver import routing_enums_pb2
2 from ortools . constraint_solver import pywrapcp
3 from prettytable import PrettyTable
4
5

54
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

6 def solv e _v eh i cl e _r ou t in g ( distance_matrix , time_matrix , num_vehicles ,

depot , vehicle_capacity , max_route_time ) :
7 # Create the routing index manager .
8 manager = pywrapcp . Rou tingInd exManag er ( len ( distance_matrix ) ,
num_vehicles , depot )
9
10 # Create the routing model .
11 routing = pywrapcp . RoutingModel ( manager )
12
13 # Define the distance callback .
14 def distance_callback ( from_index , to_index ) :
15 return distance_matrix [ manager . IndexToNode ( from_index ) ][
manager . IndexToNode ( to_index ) ]
16

17 tr an s it _ c a l lba c k _i n d e x = routing . R e g i s t e r T r a n s i t C a l l b a c k (
distance_callback )
18
19 # Define the cost of each arc .
20 routing . S e t A r c C o s t E v a l u a t o r O f A l l V e h i c l e s ( t r an s i t _c a l l b ac k _ i n de x )
21
22 # Define the time callback .
23 def time_callback ( from_index , to_index ) :
24 return time_matrix [ manager . IndexToNode ( from_index ) ][ manager .
IndexToNode ( to_index ) ]
25

26 time_cal lback_i ndex = routing . R e g is t e r T r a n s i t C a l l b a c k (

time_callback )
27
28 # Add time dimension .
29 routing . A d d D i m e n s i o n W i t h V e h i c l e C a p a c i t y (
30 time_callback_index ,
31 0 , # no slack
32 [ max_route_time ] * num_vehicles , # vehicle maximum time
33 True , # start cumul to zero
34 " Time "
35 )
36

37 # Add capacity constraint .

38 def demand_callback ( from_index ) :
39 return 1
40
41 dema n d_ ca l lb a ck _i n de x = routing . R e g i s t e r U n a r y T r a n s i t C a l l b a c k (
demand_callback )
42 routing . A d d D i m e n s i o n W i t h V e h i c l e C a p a c i t y (
43 demand_callback_index ,
44 0 , # no slack
45 vehicle_capacity , # vehicle maximum capacities
46 True , # start cumul to zero
47 " Capacity "
48 )
49
50 # Set the search parameters .
51 search_parameters = pywrapcp . D e f a u l t R o u t i n g S e a r c h P a r a m e t e r s ()
52 search_parameters . f i r s t _ s o l u t i o n _ s t r a t e g y = (
53 routing_enums_pb2 . F ir st S ol ut i on S tr at e gy . PATH_CHEAPEST_ARC )
54
55 # Solve the problem .
56 solution = routing . SolveWi thParam eters ( search_parameters )

55
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

57
58 # Retrieve the routes and their times .
59 routes = []
60 route_distances = []
61 route_times = []
62 total_distance = 0
63 total_time = 0
64 if solution :
65 for vehicle_id in range ( num_vehicles ) :
66 index = routing . Start ( vehicle_id )
67 route = [ manager . IndexToNode ( index ) ]
68 route_distance = 0
69 route_time = 0
70 while not routing . IsEnd ( index ) :
71 previous_index = index
72 index = solution . Value ( routing . NextVar ( index ) )
73 route . append ( manager . IndexToNode ( index ) )
74 route_distance += distance_matrix [ manager . IndexToNode (
previous_index ) ][ manager . IndexToNode ( index ) ]
75 route_time += time_matrix [ manager . IndexToNode (
previous_index ) ][ manager . IndexToNode ( index ) ]
76 if ( route_time +4) > total_time :
77 total_time = route_time +4
78 routes . append ( route )
79 route_distances . append ( route_distance )
80 route_times . append ( route_time )
81 total_distance += route_distance
82
83 # Print the routes and their times
84 table = PrettyTable ()
85 table . field_names = [ " Vehicle " , " Route " , " Distance " , " Time " ]
86 for i , route in enumerate ( routes ) :
87 table . add_row ([ f " Vehicle { i +1} " , route , f " { round (
route_distances [ i ] ,2) } km " , f " { round ( route_times [ i ]+4 , 1) } h " ])
88 print ( table )
89
90 # Print the total distance
91 print ( f " Total Distance :\ t \ t \ t { round ( total_distance ,2) } km " )
92 print ( f " Maximum Time :\ t \ t \ t { total_time :.2 f } h " )
93 print ( f " Frait de mission :\ t \ t \ t \ t { round ( total_distance *3 ,2) } DA " )
94 print ( f " Diesel cost :\ t \ t { round ( total_distance *0.30*29.01 , 2) } DA " )
95 print ( f " Total cost :\ t \ t { round
96 ( total_distance *3+ total_distance *0.28*29.01 , 2) } DA " )
97 print ( f " Emmision :\ t \ t \ t \ t \ t { round ( total_distance *0.7) } Kg / km " )
98 return routes , route_distances , route_times , total_distance
99
100 # une partie de matrice de distance
101 distance_matrix = [
102 [0.0 , 326.9 , 243.6 , 128.3 , 201.5 , 160.2 , ... 184.1] ,
103 [326.9 , 0.0 , 495.3 , 61.1 , 390.7 , 433.8 , ... 669.8] ,
104 [243.6 , 495.3 , 0.0 , 465.5 , 688.6 , 689.9 , ... 716.9] ,
105 [128.3 , 61.1 , 465.5 , 0.0 , 741.2 , 668.1 , ... 681.4] ,
106 . 0.0
107 . 0.0
108 . 0.0
109 [201.5 , 523.9 , 442.7 , 284.0 , 248.1 , 278.1 , ... 0.0 ]
110 ]
111

56
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

112 # une partie de matrice de distance

113 time_matrix = [
114 [0.0 , 3.5 , 2.6 , 1.6 , 2.4 , 1.7 , 3.0 , 1.1 , ... 8.8] ,
115 [3.5 , 0.0 , 1.2 , 3.9 , 5.9 , 8.2 , 20.2 , 6.6 , ... 7.3] ,
116 [2.6 , 1.2 , 0.0 , 8.2 , 8.6 , 7.4 , 4.3 , 5.1 , ... 6.4] ,
117 [1.6 , 3.9 , 8.2 , 0.0 , 4.9 , 3.3 , 2.9 , 3.5 , ... 2.3] ,
118 . 0.0
119 . 0.0
120 . 0.0
121 [8.8 , 2.0 , 3.6 , 1.8 , 8.7 , 5.4 , 6.3 , 1.7 , ... 0.0 ]
122 ]
123
124 num_vehicles = 35
125 depot = 22
126 vehicle_capacity = [ 3 , 3 , 4 , 4 , 4 , 2 , 3 , 2 , 2 , 3 , 3 , 3 ,
127 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 4,
128 2, 2, 3, 3, 3, 3, 3, 3, 2, 4, 5, 3 ]
129 max_route_time = 10
130 solve _v eh i cl e _r ou t in g ( distance_matrix , time_matrix , num_vehicles ,
depot , vehicle_capacity , max_route_time )
131 # end
Listing 4.2 – Algorithme Heuristique.

[Link]́sultat de l’heuristique

Dans cette section, nous présenterons les résultats issus de la mise en oeuvre de l’heu-
ristique que nous avons programmée.

Le nombre des camions utilisés est : 18 camions

Le temps maximale de la tournée est : 61.20 heure

• Camion 1 : Bordj Bou Arreridj→ Chlef → BBA

• Camion 2 : BBA→ Tlemcen → BBA
• Camion 3 : BBA→ Sidi Bel Abbès → BBA
• Camion 4 : BBA→ Oran → Mostaganem → BBA
• Camion 5 : BBA→ Ait Temouchent → Tipaza → BBA
• Camion 6 : BBA→ M’sila → Laghouat → Relizane → BBA
• Camion 7 : BBA→ Tissemsilt → BBA
• Camion 8 : BBA→ El Bayadh → BBA
• Camion 9 : BBA→ Béchar → Naama → BBA
• Camion 10 : BBA→ Ghardaia → Tindouf → BBA
• Camion 11 : BBA→ Biskra → Batna → BBA
• Camion 12 : BBA→ El oued → Ouargla → BBA
• Camion 13 : BBA→ Souk Ahras → Tébessa → BBA
• Camion 14 : BBA→ Constantine → Sétif → BBA

57
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

• Camion 15 : BBA→ Annaba → BBA

• Camion 16 : BBA→ Jijel → Gualma → Skikda → BBA
• Camion 17 : BBA→Bouira → Boumerdes →Tizi Ouzou → Béjaia →BBA
• Camion 18 : BBA→ Blida → Alger → BBA

Distance totale Frais de mission Coût du diesel Émissions de gaz Coût total (Da)
(km) (Da) (Da) (kg/km)
20292.59 60877.76 176606.37 14205 225710.37

Table 4.2 – Résultat obtenue par algorithme heuristique

image/[Link]

Figure 4.10 – Les tournées obtenues à partir de l’algorithme heuristique

[Link]́taheuristique

Après avoir exploré l’algorithme heuristique, nous avons décidé de passer à l’algo-
rithme métaheuristique en raison de sa capacité à trouver des solutions de qualité supé-
rieure, même dans des situations difficiles, telles que des problèmes de grande taille et
de complexité élevée. Les métaheuristiques offrent une approche avancée pour résoudre
le Problème de Routage des Véhicules (VRP) en explorant de manière efficace l’espace
de recherche complexe. En utilisant l’algorithme métaheuristique, nous visons à améliorer
encore davantage nos solutions et à nous rapprocher de l’optimalité.

58
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

L’outil utilisé :

Aﬁn de mettre en oeuvre l’algorithme métaheuristique, nous avons utilisé le logiciel

Gurobi, qui est un puissant solveur d’optimisation mathématique. Gurobi oﬀre une grande
variété d’outils pour résoudre des problèmes d’optimisation complexes. Il prend en charge
plusieurs types d’algorithmes, y compris les algorithmes métaheuristiques.

L’implémentation de l’algorithme métaheuristique dans Gurobi s’est déroulée en plu-

sieurs étapes. Tout d’abord, nous avons défini le problème d’optimisation en utilisant un
langage de modélisation tel que Python, et plus précisément la programmation linéaire
(PL). Ensuite, nous avons configuré les paramètres spécifiques de l’algorithme métaheu-
ristique, tels que le nombre de véhicules, le nombre de villes et leurs coordonnées dans un
repère cartésien.

4.6.3 algorithme métaheuristique

2 import networkx as nx
3 import math
4 import gurobipy as gp
5 from gurobipy import GRB
6
7 k = 17 # number of vehicles
8 n = 34 # number of demand points
9
10 depot = 0
11 dem_points = list ( range (1 , n +1) ) # nodes 1 , 2 , ... , 20
12
13 G = nx . complete_graph ( n +1)
14 my_pos = {
15 0:( -91.00 , -127.71) , 1:( -31.64 ,487.00) , 2:( -12.42 ,405.09) ,
16 3:(70.67 , 308.33) , 4:(50.78 , 379.00) , 5:(109.04 , 22.47) ,
17 6:( -91.00 , 243.69) , 7:(8.58 , 181.03) , 8:( -40.28 , -220.49) ,
18 9:( -50.25 , -296.95) ,10:(86.83 , 119.47) , 11:( -177.2 , -112.02) ,
19 12:( -202.22 ,508.28) , 13:( -500.73 ,510.81) ,14:( -567.9 , 1827.0) ,
20 15:(638.90 ,10 .94) , 16:(439.14 , -307.36) ,17:(422.03 , -137.49) ,
21 18:(151.65 , -504.69) , 19:(471.20 , -389.16) ,20:(515.95 , -390.22) ,
22 21:(390.51 , -350.21) , 22:(81.93 ,180.43) , 23:( -186.05 , -206.86) ,
23 24:( -312.80 , -314.98) ,25:( -340.53 , -428.6) ,26:( -291.72 , -373.47) ,
24 27:( -301.27 , -383.11) ,28:( -193.19 , -265.5) ,29:( -148.56 , -197.60) ,
25 30:( -18.06 , -85.39) , 31:(0.72 , -54.09) , 32:( -36.60 , -71.19) ,
26 33:(70.13 ,8.21) , 34:(85.42 ,24.57) }
27
28 # coordonées de dépot
29 my_pos [ depot ] = ( -91.00419788 , -127.71268069)
30 nx . draw (G , pos = my_pos )
31

32 # for convenience , suppose that distances are Euclidean

33 def eucl_dist ( x1 , y1 , x2 , y2 ) :
34 return math . sqrt (( x1 - x2 ) **2 + ( y1 - y2 ) **2)
35
36 for i , j in G . edges :
37 ( x1 , y1 ) = my_pos [ i ]
38 ( x2 , y2 ) = my_pos [ j ]

59
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

39 G . edges [i , j ][ ’ length ’] = eucl_dist ( x1 , y1 , x2 , y2 )

41 # suppose each vehicle has capacity 100

42 Q = 100
43 # suppose each demand point has demand 20
44 q = { i : 20 for i in dem_points }
45 q [ depot ] = 0
46 # First , solve a relaxation
47 m = gp . Model ()
48 x = m . addVars ( G . edges , vtype = GRB . BINARY )
49
50 m . setObjective ( gp . quicksum ( G . edges [ e ][ ’ length ’] * x [ e ] for e in G .
edges ) , GRB . MINIMIZE )
51

52 # Degree -(2* k ) constraints at depot

53 m . addConstr ( gp . quicksum ( x [ e ] for e in G . edges if e in G . edges ( depot ) )
== 2 * k )
54
55 m . update ()
56
57 # create a function to separate the rounded capacity inequalities ( or
subtour elimination )
58 def roun d ed _c a pa c it y_ i ne q (m , where ) :
59 # check if LP relaxation at this branch - and - bound node has an
integer solution
60 if where == GRB . Callback . MIPSOL :
61 # retrieve the LP solution
62 xval = m . cbGetSolution ( m . _x )
63
64 # which edges are selected ?
65 tour_edges = [ e for e in m . _G . edges if xval [ e ] > 0.5]
66
67 # if connected , add rounded capacity inequalities ( if any are
violated )
68 if nx . is_connected ( m . _G . edge_subgraph ( tour_edges ) ) :
69 non_depot_edges = [( i , j ) for (i , j ) in tour_edges if m .
_depot not in {i , j }]
70
71 for component in nx . co nne ct ed_ co mpo nen ts ( m . _G .
edge_subgraph ( non_depot_edges ) ) :
72 component_demand = sum ( m . _q [ i ] for i in component )
73
74 if component_demand > m . _Q :
75 cut_edges = [( i , j ) for (i , j ) in m . _G . edges if ( i
in component ) ^ ( j in component ) ]
76 m . cbLazy ( gp . quicksum ( m . _x [ e ] for e in cut_edges )
>= 2 * math . ceil ( component_demand / m . _Q ) )
77 else :
78 for component in nx . co nne ct ed_ co mpo nen ts ( m . _G .
edge_subgraph ( tour_edges ) ) :
79 if m . _depot not in component :
80 inner_edges = [( i , j ) for (i , j ) in m . _G . edges if
i in component and j in component ]
81 m . cbLazy ( gp . quicksum ( m . _x [ e ] for e in inner_edges )
<= len ( component ) - 1)
82
83 # tell Gurobi that we will be adding ( lazy ) constraints
84 m . Params . lazyConstraints = 1

60
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

85
86 # designate the callback routine
87 m . _callback = r ou n de d_ c ap a ci ty _ in eq
88
89 # add the variables and graph to our model object , for use in the
callback
90 m . _x = x
91 m . _G = G
92 m . _q = q
93 m . _Q = Q
94 m . _depot = depot
95
96
97 # solve the MIP with our callback
98 m . optimize ( m . _callback )
99
100
101 # get the solution and draw it
102 tour_edges = [ e for e in G . edges if x [ e ]. x > 0.5 ]
103 nx . draw ( G . edge_subgraph ( tour_edges ) , pos = my_pos )
104 # end
Listing 4.3 – Algorithme métaheuristique.

Le code fourni implémente une solution au problème de routage des véhicules (VRP) avec
contraintes de capacité. Dans le VRP, une ﬂotte de véhicules doit desservir un ensemble
de points de demande tout en minimisant la distance totale parcourue, utilise le solveur
Gurobi pour trouver une solution optimale.

Le code commence par déﬁnir le nombre de véhicules (k) et le nombre de points de

demande (n). Il crée un graphe représentant le dépôt et les points de demande, où chaque
noeud correspond à un emplacement. Les positions des noeuds sont spéciﬁées à l’aide de
coordonnées.

Ensuite, le code calcule les distances entre les nuds en utilisant la formule de distance
euclidienne. Il attribue ces distances comme longueurs aux arêtes du graphe. Le code
déﬁnit également la capacité des véhicules (Q) et la demande de chaque point de demande
(q).

À l’aide de la bibliothèque Gurobi, le code crée un modèle et des variables de décision

représentant les arêtes sélectionnées. L’objectif est de minimiser la longueur totale des
arêtes sélectionnées. Le code ajoute une contrainte garantissant que le dépôt est visité
exactement deux fois le nombre de véhicules.

Pour améliorer la solution, le code définit une fonction de rappel qui est exécutée
lorsqu’une solution entière est trouvée pendant le processus d’optimisation. La fonction
de rappel vérifie la solution et identifie les arêtes sélectionnées. Si les arêtes sélectionnées
forment un graphe connecté, la fonction vérifie les composants (sous-tours) qui enfreignent
les contraintes de capacité. Elle ajoute des contraintes tardives pour garantir que certaines
arêtes coupées sont traversées au moins deux fois. Si les arêtes sélectionnées ne forment
pas un graphe connecté, la fonction identifie les composants individuels et ajoute des
contraintes pour garantir que chaque composant est un sous-tour valide.

61
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Le code définit le paramètre Gurobi pour les contraintes tardives et attribue la fonc-
tion de rappel au modèle. Ensuite, il résout le modèle, récupère la solution et visualise
le parcours résultant en sélectionnant les arêtes ayant des valeurs supérieures à 0,5 (la
valeur de 0,5 est utilisée comme seuil pour déterminer quels tronçons sont inclus dans la
visite résultante. Après avoir résolu le problème de routage des véhicules, la solution est
obtenue et les arêtes avec des valeurs supérieures à 0,5 sont considérées comme faisant
partie du circuit optimal. Ce seuil agit comme un point de coupure, indiquant que les
arêtes avec des valeurs supérieures au seuil sont sélectionnées, tandis que celles en dessous
ne sont pas incluses. Le seuil spécifique de 0,5 est arbitraire et peut être ajusté en fonction
des exigences du problème ou des préférences d’interprétation.). Cependant, il est impor-
tant de noter que les résultats obtenus par ce code sont basés sur des hypothèses et des
simplifications.

Résultat de Métaheuristiques

Le programme a trouvé une solution heuristique initiale avec une valeur objective
de 14050,759376. Ensuite, il a utilisé l’optimiseur Gurobi pour résoudre le problème de
routage des véhicules. Le modèle optimisé comportait 1 contrainte, 595 variables et 34
coeﬃcients non nuls. La prérésolution a éliminé 1 contrainte et 34 variables redondantes ou
triviales, laissant le problème avec 0 contrainte, 561 variables entières et aucune valeur non
nulle. L’optimiseur a exploré 0 noeuds supplémentaires pour trouver une solution unique,
satisfaisant toutes les contraintes, avec une valeur objective de 14050,8. Cette solution est
prouvée optimale dans la tolérance donnée, aﬃchant un écart de 0,0000%. En résumé, le
programme a résolu avec succès le problème de routage des véhicules en fournissant une
solution optimale, tout en présentant des détails sur le processus d’optimisation et les
caractéristiques du problème.

Les résultats obtenus à partir de l’algorithme métaheuristiques implémenté dans le

code fourni peuvent ne pas être directement applicables dans un scénario réel pour plu-
sieurs raisons :

Premièrement, l’algorithme suppose un modèle simpliﬁé du problème de routage de

véhicules avec certaines hypothèses et contraintes. Les instances réelles du problème im-
pliquent souvent des complexités supplémentaires, telles que des conditions de circulation
variables, des demandes imprévisibles des clients, des contraintes de créneau horaire et
des limitations de capacité de véhicule spéciﬁques.

Deuxièmement, l’algorithme s’appuie sur les distances euclidiennes entre les empla-
cements pour calculer les longueurs de bord. Cependant, en réalité, les réseaux routiers
sont beaucoup plus complexes et les distances et temps de trajet réels peuvent être très
différents des distances en ligne droite utilisées dans l’algorithme. De plus, l’algorithme
ne tient pas compte d’autres facteurs critiques, tels que la disponibilité des véhicules, la
planification des chauffeurs, les temps de chargement/déchargement des véhicules et les
considérations opérationnelles pratiques. Ces facteurs peuvent avoir un impact considé-
rable sur la faisabilité et l’efficacité de la solution de routage.

Enﬁn, l’algorithme suppose une solution optimale basée sur le modèle mathématique

62
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

et les contraintes déﬁnies. Cependant, en raison de la complexité inhérente du problème

d’itinéraire de véhicules, trouver une solution vraiment optimale dans des instances du
monde réel est souvent irréalisable sur le plan informatique dans des délais raisonnables.
Par conséquent, bien que l’algorithme fournisse une démonstration utile du problème
d’acheminement de véhicules avec des contraintes de capacité, il doit être traité comme
un point de départ ou une approximation simpliﬁée.

Les implémentations dans le monde réel nécessitent un examen approfondi des contraintes
opérationnelles spéciﬁques, des conditions dynamiques et l’utilisation d’algorithmes plus
sophistiqués ou de logiciels spécialisés capables de gérer plus eﬃcacement les complexités
du problème.

4.6.4 Les résultat des algorithmes

Aﬀectation AB Heuristique Métaheuristique

Distance totale 31964 20292.59 14050.75
(km)
Frais de mission 95082 60877.76 /
(Da)
Coût du diesel 275832.88 176606.37 /
(Da)
Émissions de 22185.8 14205 /
gaz (kg/km)
Coût total (Da) 352526.02 225710.37 /

Table 4.3 – Résultat obtenu par algorithme heuristique (mise à jour)

4.7 Analyse Générale

4.7.1 Tableau de Bord

Notre tableau de bord offre une présentation claire et visuelle des résultats des algo-
rithmes utilisés pour résoudre le problème de routage des véhicules (VRP). Nous mettons
l’accent sur les premier et deuxième algorithmes, qui sont les plus pratiques et applicables
dans des scénarios réels. En fournissant des visualisations réalistes des résultats, nous
permettons aux décideurs d’évaluer les performances, les coûts et les émissions associés
à chaque algorithme. Grâce à ces informations, les décideurs peuvent comparer les diffé-
rentes approches, prendre des décisions éclairées et optimiser le routage des véhicules en
fonction de leurs priorités et contraintes. Le tableau de bord est un outil précieux pour les
décideurs, leur offrant une vue d’ensemble complète et facilitant la prise de décisions stra-
tégiques pour améliorer l’efficacité opérationnelle et réduire les coûts dans leurs activités
de transport.

63
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Normal Dashbord ( premier algorithme )

image//[Link]

Figure 4.11 – résultats obtenue d’après le déplacement AB

Les résultats du premier algorithme, qui utilisait une stratégie d’aﬀectation simpliste,
ont révélé plusieurs problèmes. Les camions ont parcouru une distance totale de 31 694 km
pour desservir les clients, ce qui indique une utilisation ineﬃcace des ressources. Certains
camions ont pris des itinéraires plus longs ou ont subi des retards lors des livraisons,
ce qui a entraı̂né un temps de retour maximal de 49,2 heures. Les coûts associés à cet
algorithme étaient élevés, avec un coût de mission de 95 082 DA et un coût de diesel
de 275 832,88 DA, conduisant à un coût total de 352 526,02 DA. De plus, les émissions
générées lors des missions ont atteint 22 185,8 kg/km de CO2, ce qui souligne un impact
environnemental important. Le tableau de bord fournit une visualisation de ces résultats, y
compris une carte montrant les itinéraires des camions, permettant ainsi aux décideurs de
mieux comprendre le gaspillage des ressources et d’envisager des stratégies d’optimisation
pour améliorer les itinéraires, réduire les coûts et minimiser l’impact environnemental.

image//[Link]

Figure 4.12 – Les pourcentages d’utilisation des ressources

64
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

VRP-S Dashbord ( deuxième algorithme )

Après l’amélioration de l’algorithme, le deuxième algorithme a produit des résultats

prometteurs. En utilisant une approche heuristique, il a réussi à réduire considérablement
la distance totale parcourue par les camions, passant de 31 694 km à 20 292,59 km par
rapport au premier algorithme. Bien que le temps maximum requis pour les livraisons ait
légèrement augmenté à 61,20 heures, cela peut être attribué à la complexité des itinéraires.
Les avantages sont évidents en termes de coûts : le coût de mission a été réduit de 60 877,76
DA et le coût du diesel de 176 606,37 DA, aboutissant à un coût total de 225 710,37 DA,
soit une économie signiﬁcative. De plus, les émissions de CO2 générées lors des missions
ont également été réduites à 14 205 kg/km, ce qui représente une amélioration notable de
l’impact environnemental par rapport au premier algorithme. Globalement, ces résultats
mettent en évidence l’eﬃcacité de l’approche heuristique dans l’optimisation du routage,
la réduction des coûts et des émissions, tout en utilisant un nombre réduit de camions.

image//[Link]

Figure 4.13 – Les résultats obtenue par VRP Solution

Le tableau de bord présente également une visualisation cartographique des itinéraires

de chaque véhicule, permettant ainsi de mieux comprendre la planification et la répartition
des livraisons. En termes d’optimisation, le deuxième algorithme a permis d’obtenir des
améliorations significatives. Le coût total a été réduit de 35 % par rapport au premier
algorithme, passant de 352,526.02 DA à 225,710.37 DA. La distance totale parcourue a
également été réduite de 35 %, passant de 31,694 km à 20,292.59 km. De plus, le deuxième
algorithme a permis de prolonger la durée de vie des véhicules de 11 %, ce qui témoigne
de l’amélioration de l’efficacité de leur utilisation. En ce qui concerne les émissions, le
taux d’émission a été réduit de 36 %, passant de 22,185.8 kg/km à 14,204.8 kg/km de
CO2, ce qui a un impact environnemental moindre. Ces pourcentages reflètent les gains
significatifs obtenus grâce à l’optimisation du deuxième algorithme. La combinaison de ces
améliorations et de la visualisation cartographique des itinéraires permet aux utilisateurs
de mieux comprendre les résultats et de prendre des décisions éclairées pour optimiser les
ressources et réduire l’impact environnemental.

65
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

image//[Link]

Figure 4.14 – Les pourcentages de gain obtenus grâce à VRP Solution

Résultat du troisième algorithme

Le troisième algorithme, une approche métaheuristique, a présenté un processus d’op-

timisation plus complexe. Le modèle impliquait un grand nombre de variables et de
contraintes, avec 1 ligne, 595 colonnes et 34 valeurs diﬀérentes de zéro. L’algorithme a
initialement trouvé une solution heuristique avec une valeur objective de 14050.759376,
qui s’est avérée plus tard être la solution optimale avec la même valeur objective. Cela
suggère que l’algorithme a exploré avec succès diverses possibilités et a convergé vers la
meilleure solution. Cependant, il est important de noter que l’algorithme métaheuristique
peut ne pas être directement applicable dans des scénarios réels en raison de sa complexité
et de ses exigences de calcul.

image//[Link]

Figure 4.15 – Les résultats obtenue d’après l’algorithme méthaheuristique

66
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Compte tenu des résultats, on peut conclure que l’algorithme heuristique est le choix
le plus approprié pour le problème de routage de véhicules dans les applications pratiques.
Il trouve un équilibre entre l’optimisation des itinéraires, la minimisation des coûts et la
réduction des émissions. La capacité de l’algorithme heuristique à fournir des solutions
quasi optimales avec un nombre réduit de camions et un impact environnemental moindre
en fait le choix préféré pour une mise en oeuvre dans le monde réel. Cependant, l’explo-
ration par l’algorithme métaheuristique d’un espace de solutions plus large et sa capacité
à trouver des solutions globalement optimales peuvent oﬀrir des informations précieuses
et servir de référence pour évaluer l’eﬃcacité d’autres algorithmes.

4.8 Conclusion

En résumé, les résultats mettent en évidence les compromis entre diﬀérents algorithmes
en termes de distance, de temps, de coût et d’émissions. Le premier algorithme a entraı̂né
des coûts élevés et des émissions importantes en raison des longues distances parcourues.
En revanche, le deuxième algorithme, qui utilisait une approche heuristique, a réussi à
réduire la distance, les coûts et les émissions en optimisant le routage des camions et en
utilisant moins de véhicules. Le troisième algorithme, basé sur une approche métaheu-
ristique, a démontré sa capacité à trouver une solution optimale, mais il a nécessité un
processus d’optimisation plus complexe.

Ces résultats fournissent des informations précieuses sur l’efficacité et l’efficience des
différents algorithmes pour résoudre le problème de routage des véhicules. Ils permettent
aux décideurs de prendre des décisions éclairées en fonction de leurs priorités et de leurs
contraintes, en tenant compte des compromis entre la distance parcourue, le temps requis,
les coûts engendrés et les émissions générées. Il est important de noter que l’approche
heuristique s’est révélée particulièrement efficace en termes de réduction des coûts et
des émissions, tout en fournissant des résultats acceptables pour le routage des véhicules.
Cependant, l’approche métaheuristique, bien qu’elle puisse trouver des solutions optimales,
peut être plus complexe à mettre en oeuvre dans la réalité en raison de son temps de calcul
plus élevé.

67
Conclusion générale

Dans ce projet de ﬁn d’étude, nous avons exploré le domaine vital du transport de

marchandises et la logistique de distribution, nous nous intéressons spécialement aux déﬁs
posés par le Problème de Routage des Véhicules (VRP). Tout au long des chapitres,
nous avons examinés diﬀérents aspects de ce problème, depuis la compréhension de ses
fondements théoriques jusqu’à la mise en oeuvre de solutions pratiques.

En premier lieu, nous avons étudié le transport de marchandises et de la logistique de

distribution, qui nous a permis de comprendre l’importance de ce domaine et les différents
éléments qui le composent,en mettant en exergue, les stratégies de transport, l’efficacité
de leur mise en oeuvre et les défis liés à la gestion du transport routier de marchandises
et allocation des ressources, en prenant en compte des problèmes spécifiques du secteur,
tels que planification des itinéraires, les coûts de transport elevés et les émissions de gaz
à effet de serre.

En second lieu, le problème de VRP (Vehicle Routing Problem) est un défi majeur en
logistique et de la planification des tournées, il consiste à optimiser la création de tournées
de véhicules en tenant compte de contraintes telles que les capacités de chargement, les
contraintes de temps et les variantes du problème de base, exprimé par des VRP avec
fenêtres de temps, avec contraintes de capacité, une fois résolut,il va apporter des solutions
efficaces aux problème ( améliorer l’efficacité et la rentabilité des opérations logistiques).

En troisième lieu, on s’est concentré sur les diverses méthodes de résolution du VRP,
nous avons exploré des algorithmes d’optimisation, les approches heuristiques et les mé-
taheuristiques, en évaluant leurs forces et leurs limites.

Enﬁn, nous avons réalisé une transition signiﬁcative de la théorie à la pratique, nous
avons mis en oeuvre des algorithmes heuristique et métaheuristique en utilisant comme
outil principale d’optimisation ” Python” et exploitation de divers outils et bibliothèques
tels que networkx, math, gurobipy et ortools, grâce à des implémentations pratiques, nous
avons pu résoudre des problèmes réels de VRP cas de CONDOR LOGISTICS.

En outre, nous avons développé une application web conviviale utilisant HTML, CSS
et JavaScript, intégrant des frameworks comme jQuery et FontAwesome. Elle permet la
visualisation des itinéraires, l’analyse des ressources et une aide la prise de décisions, avec
l’intégration d’API de cartographie ( Mapbox pour une meilleure expérience utilisateur).

Les résultats obtenus grâce à nos implémentations et à nos analyses démontrent le

68
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

potentiel d’amélioration de la planiﬁcation des itinéraires, de l’allocation des ressources

et de l’eﬃcacité opérationnelle globale. Le tableau de bord de l’application web et les
visualisations sur la carte oﬀrent des informations claires sur l’utilisation des itinéraires,
permettant aux décideurs de prendre des décisions éclairées qui optimisent l’allocation des
ressources, réduisent les coûts et améliorent les performances opérationnelles globales.

69
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Ce projet de ﬁn d’étude s’est concentré sur le transport de marchandises et la lo-

gistique de distribution, en mettant l’accent sur le Problème de Routage des Véhicules
(VRP), nous avons exploré les fondements théoriques du VRP, les défis spécifiques du
secteur et les différentes méthodes de résolution, en mettant en pratique des algorithmes
heuristiques et métaheuristiques, nous avons développé une application web conviviale
intégrant des fonctionnalités de visualisation des itinéraires et d’analyse des ressources,
avec l’intégration d’API de cartographie pour une meilleure expérience utilisateur. Les
résultats obtenus ont démontré le potentiel d’amélioration de la planification des itiné-
raires, de l’allocation des ressources et de l’efficacité opérationnelle. Ce projet offre une
base solide pour de futures avancées dans le domaine du transport de marchandises et de
la distribution.

70
Annex

Presentation de l’entreprise CONDOR LOGISTICS

image/[Link]

Figure 4.16 – Logo de l’entreprise CONDOR LOGISTICS

Condor Logistics est une filiale du groupe Condor spécialisée dans le transport de mar-
chandises, le transport de personnel, la location et la maintenance de véhicules et d’engins.
Fondée en 2014, l’entreprise s’est rapidement positionnée comme un acteur majeur dans le
domaine du transport. Avec environ 600 employés, elle offre des services de transport de
marchandises par voie terrestre à ses clients à travers tout le territoire national. Grâce à
sa flotte de véhicules diversifiée, Condor Logistics est en mesure de répondre efficacement
aux besoins de ses clients en matière de transport de cargaison.

historique
1. 2014 : lors de sa création, Condor Logistics disposait déjà d’un important parc
roulant dédié aux ﬁliales du Groupe Condor.
2. 2016 : Dans le cadre de son développement, Condor Logistics a élargi son champ
initial d’expertise de transport de marchandises pour l’étendre aux activités de trans-
port du Personnel, de location et de maintenance de véhicules et d’engins.
3. 2018 : Condor Logistics a délibérément opté pour une démarche ( Qualité - Santé
- Sécurité - Environnement ) en adaptant son Système de Management, et obtenir
une certiﬁcation SMI : ISO 9001, ISO 14001 et ISO 45001, dans une vision de
développement durable d’Entreprise responsable et citoyenne, non seulement vis-à-
vis de ses collaborateurs, clients et fournisseurs, mais également de ses concurrents.

71
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Condor dispose d’un Réseau de distribution comprenant 25 entrepôts sur le territoire

national totalisant 260 000 M2.
4. 2021 : Mise en exploitation du nouveau Centre logistique intégré, dont la nouvelle
Méga-Plateforme logistique de [Link].
— Superﬁcie totale 20 Ha
— Superﬁcie couverte 65 000 M2
— Capacité stockage 150 000 Palettes
— Parc à conteneurs 2 000 TEU
— Atelier Central de Maintenance
— Aire de Stationnement pour 500 équipements

domaine d’activité

Transport de marchandises

Pour tout besoin de transport de marchandises sur le territoire national et à l’interna-

tional, Condor Logistics met à disposition

Une ﬂotte de véhicules nouvelle génération, à faible émission de CO2, et répondant aux
dernières normes en vigueur, est composée de semi-remorques, camions porteurs, porte
engins, camion de dépannage, portes conteneurs... L’ensemble de notre ﬂotte étant doté
de chronotachygraphes et d’un système de géolocalisation GPS.

Une équipe de conducteurs expérimentés

Transport du personnel

Condor Logistics comme partenaire de conﬁance, met à disposition des bus et minibus
(12 à 100 places) pour les besoins de transport du personnel.

Location d’engins et manutention

Pour les opérations de manutention, Condor Logistics dispose d’un Parc d’engins com-
posé de Nacelles Télescopiques, Reach Stackers, Chariots Élévateurs multi-tonnage [2.5T-
35T], camions-nacelles, camions-grues ...

72
CHAPITRE 4. RÉSOLUTION DU PROBLÈME TOURNÉ DE VÉHICULE

Location de véhicules

Condor Logistics comme partenaire de conﬁance, met à disposition des véhicules uti-
litaires et des véhicules touristiques multimarques, avec ou sans chauﬀeur.

Maintenance de véhicules et d’engins

Condor Logistics met à disposition son savoir-faire pour assurer la maintenance de

véhicules et engins (camions, bus, minibus, chariot élévateurs, véhicules légers...).

les mission de l’entreprise

— Fournir un niveau de qualité de nos services digne de notre clientèle.
— Améliorer en continu, les dynamiques de progrès et les synergies
— Participer avec les diﬀérents opérateurs à atteindre l’excellence dans la chaine logis-
tique.

73
Bibliographie

[1] Le rôle et l’importance du transport routier de marchandise dans le développement de

la chaı̂ne logistique. [Link]
11262/1/Le%20r%C3%B4le%20et%20l%E2%80%99importance%20du%20transport%
20routier%20de%20marchandise%20dans%20le%20d%C3%A9veloppement%20de%
20la%20chaine%[Link].
[2] M. Aldaihani and M. M. Dessouky. Hybrid scheduling methods for paratransit ope-
rations. Computers & Industrial Engineering, 45(1) :75–96, 2003.
[3] F. Alonso, M. J. Alvarez, and J. E. Beasley. A tabu search algorithm for the perio-
dic vehicle routing problem with multiple vehicle trips and accessibility restrictions.
Journal of the Operational Research Society, 59 :963–976, 2008.
[4] C. Archetti, M. G. Speranza, and A. Hertz. A tabu search algorithm for the split
delivery vehicle routing problem. Transportation science, 40(1) :64–73, 2006.
[5] M.-N. Assene and E. L. Djoukuo. Organisation du transport des marchandises et
eﬃcacité logistique des entreprises en contexte camerounais. Revue management et
avenir, (7) :35–57, 2018.
[6] J. E. Beasley. Route ﬁrstcluster second methods for vehicle routing. Omega,
11(4) :403–408, 1983.
[7] L. Bianchi. Notes on dynamic vehicle routing-the state of the art. 2000.
[8] J. Bramel and D. Simchi-Levi. A location based heuristic for general routing problems.
Operations research, 43(4) :649–660, 1995.
[9] Centre National de Ressources Textuelles et Lexicales. Voyageur. [Link]
[Link]/definition/voyageur.
[10] A.-l. Chen, G.-k. Yang, and Z.-m. Wu. Hybrid discrete particle swarm optimization
algorithm for capacitated vehicle routing problem. Journal of Zhejiang University-
Science A, 7(4) :607–614, 2006.
[11] C. H. Christiansen. Elements of vehicle routing under uncertainty. Aarhus School of
Business, Department of Business Studies, 2007.
[12] J.-F. Cordeau, G. Laporte, M. W. Savelsbergh, and D. Vigo. Vehicle routing. Hand-
books in operations research and management science, 14 :367–428, 2007.
[13] G. B. Dantzig and J. H. Ramser. The truck dispatching problem. Management
science, 6(1) :80–91, 1959.
[14] E. W. Dijkstra. A note on two problems in connexion with graphs. In Edsger Wybe
Dijkstra : His Life, Work, and Legacy, pages 287–290. 2022.

74
BIBLIOGRAPHIE

[15] Dom Formateur. Transport de voyageurs. [Link]

transport-de-voyageurs/.
[16] Formation Matières Dangereuses. Transport routier de marchandises. https://
[Link]/transport-routier-de-marchandises/.
[17] T. Gaskell. Bases for vehicle fleet scheduling. Journal of the Operational Research
Society, 18(3) :281–295, 1967.
[18] B. E. Gillett and L. R. Miller. A heuristic algorithm for the vehicle-dispatch problem.
Operations research, 22(2) :340–349, 1974.
[19] F. Glover. Tabu search and adaptive memory programmingadvances, applications
and challenges. Interfaces in computer science and operations research : Advances in
metaheuristics, optimization, and stochastic modeling technologies, pages 1–75, 1997.
[20] A. Hoff and A. Løkketangen. Creating lasso-solutions for the traveling salesman
problem with pickup and delivery by tabu search. Central European Journal of
Operations Research, 14 :125–140, 2006.
[21] P. Lacomme, C. Prins, and W. Ramdane-Chérif. Evolutionary algorithms for periodic
arc routing problems. European Journal of Operational Research, 165(2) :535–553,
2005.
[22] Merzak and Abbaz. Problème de tournées de véhicules avec gestion de stock dans
un réseau de distribution, 2015-2016.
[23] P. Miliotis. Integer programming approaches to the travelling salesman problem.
Mathematical Programming, 10 :367–378, 1976.
[24] A. Mingozzi. The multi-depot periodic vehicle routing problem. In Abstraction,
Reformulation and Approximation : 6th International Symposium, SARA 2005, Airth
Castle, Scotland, UK, July 26-29, 2005. Proceedings 6, pages 347–350. Springer, 2005.
[25] M. D. Nelson, K. E. Nygard, J. H. Griffin, and W. E. Shreve. Implementation tech-
niques for the vehicle routing problem. Computers & Operations Research, 12(3) :273–
283, 1985.
[26] B. Ombuki, B. J. Ross, and F. Hanshar. Multi-objective genetic algorithms for vehicle
routing problem with time windows. Applied Intelligence, 24 :17–30, 2006.
[27] P. Toth and D. Vigo. The vehicle routing problem. SIAM, 2002.
[28] Trouver un Transporteur. La gestion du transport de marchandises. [Link]
[Link]/la-gestion-du-transport-de-marchandises.
[29] UMC. Chapitre 01 - transport et logistique. [Link]
cours-en-ligne/G%20Transport/G%20Trasport/TL/Chapitre%2001_L1_TL.pdf.
[].
[30] ViaPost. Le transport de marchandises. [Link]
nos-actualites/post/le-transport-de-marchandises-definitions-et-roles.
[31] J. Willard. Vehicle routing using r-optimal tabu search. Master’s thesis, The Mana-
gementSchool, ImperialCollege, London, 1989.

Vous aimerez peut-être aussi

Elaboration D'un Programme de Distribution de GPLc. Au Niveau de L'entreprise NAFTAL de Béjaia PDF
0% (1)
Elaboration D'un Programme de Distribution de GPLc. Au Niveau de L'entreprise NAFTAL de Béjaia PDF
86 pages
Elaboration D'un Plan de Distribution Des Carburants Cas Entreprise NAFTAL-Béjaia Distribution
Pas encore d'évaluation
Elaboration D'un Plan de Distribution Des Carburants Cas Entreprise NAFTAL-Béjaia Distribution
71 pages
Optimisation de la collecte avec transbordement
100% (1)
Optimisation de la collecte avec transbordement
202 pages
Optimisation du Transport avec Transbordement
Pas encore d'évaluation
Optimisation du Transport avec Transbordement
205 pages
Medina J 12 2016 V2
Pas encore d'évaluation
Medina J 12 2016 V2
177 pages
Optimisation des Transports Logistiques
Pas encore d'évaluation
Optimisation des Transports Logistiques
176 pages
Modélisation Et Optimisation de Mouvement Des Conteneurs Au Niveau Du Terminal À Conteneurs BMT.
Pas encore d'évaluation
Modélisation Et Optimisation de Mouvement Des Conteneurs Au Niveau Du Terminal À Conteneurs BMT.
72 pages
Optimisation du Temps de Manutention BMT
Pas encore d'évaluation
Optimisation du Temps de Manutention BMT
58 pages
Memoire Finale PDF
100% (2)
Memoire Finale PDF
116 pages
Ref 10
Pas encore d'évaluation
Ref 10
72 pages
Introduction à la logistique et transport
Pas encore d'évaluation
Introduction à la logistique et transport
160 pages
Opt de La Distrb Des Produits Agricoles
Pas encore d'évaluation
Opt de La Distrb Des Produits Agricoles
62 pages
Mfe Ameur
Pas encore d'évaluation
Mfe Ameur
9 pages
Chaine Logistique
Pas encore d'évaluation
Chaine Logistique
70 pages
Organisation des tournées de livraison
Pas encore d'évaluation
Organisation des tournées de livraison
6 pages
Optimisation des flux en logistique
Pas encore d'évaluation
Optimisation des flux en logistique
156 pages
Cahier-Exercice Odoo 18
100% (1)
Cahier-Exercice Odoo 18
47 pages
Minimisation Du Temps de Séjour Des Navires Dans Un Port Cas Entreprise Portuaire de Bejaia (EPB
Pas encore d'évaluation
Minimisation Du Temps de Séjour Des Navires Dans Un Port Cas Entreprise Portuaire de Bejaia (EPB
62 pages
Résolution du problème VRPTW par colonnes
Pas encore d'évaluation
Résolution du problème VRPTW par colonnes
75 pages
Traçabilité Agroalimentaire Innovante
Pas encore d'évaluation
Traçabilité Agroalimentaire Innovante
63 pages
Khelfa Amani
Pas encore d'évaluation
Khelfa Amani
42 pages
Crainic Semet CRT
Pas encore d'évaluation
Crainic Semet CRT
66 pages
RapportFinal PDF
Pas encore d'évaluation
RapportFinal PDF
56 pages
Pfe Rapport
Pas encore d'évaluation
Pfe Rapport
82 pages
Optimisation des tournées en logistique inverse
Pas encore d'évaluation
Optimisation des tournées en logistique inverse
141 pages
Extension adaptative du protocole DSR
Pas encore d'évaluation
Extension adaptative du protocole DSR
152 pages
Pfe 2023 Gi-Moussaouiyounes Hibayounès
Pas encore d'évaluation
Pfe 2023 Gi-Moussaouiyounes Hibayounès
92 pages
2021IMTA0253 Dumez-Dorian
Pas encore d'évaluation
2021IMTA0253 Dumez-Dorian
210 pages
Optimisation du Transport de Gaz
100% (1)
Optimisation du Transport de Gaz
103 pages
Heuristique Clarke & Wright en Logistique
Pas encore d'évaluation
Heuristique Clarke & Wright en Logistique
34 pages
Optimisation de La Logistique Internationale À Horizon Stratégique - Application À Un Constructeur Automobile - Thèse 2011
Pas encore d'évaluation
Optimisation de La Logistique Internationale À Horizon Stratégique - Application À Un Constructeur Automobile - Thèse 2011
163 pages
Memoire Optimitation
Pas encore d'évaluation
Memoire Optimitation
84 pages
Rapport de Stage D' Approfondissement PDF
Pas encore d'évaluation
Rapport de Stage D' Approfondissement PDF
35 pages
Optimisation Logistique Automobile
Pas encore d'évaluation
Optimisation Logistique Automobile
163 pages
Projet - Pfa - VF El Azzaoui Mohammad
Pas encore d'évaluation
Projet - Pfa - VF El Azzaoui Mohammad
52 pages
Optimisation Des Tournées
Pas encore d'évaluation
Optimisation Des Tournées
9 pages
Optimisation du Transport Urbain à La Rochelle
Pas encore d'évaluation
Optimisation du Transport Urbain à La Rochelle
278 pages
Probleme Du VRP
Pas encore d'évaluation
Probleme Du VRP
6 pages
Optimisation des tournées de véhicules
Pas encore d'évaluation
Optimisation des tournées de véhicules
134 pages
Optimisation Logistique Cevital
Pas encore d'évaluation
Optimisation Logistique Cevital
68 pages
Automatisation des Données Facebook
Pas encore d'évaluation
Automatisation des Données Facebook
88 pages
Cours Transport
100% (4)
Cours Transport
73 pages
Exemple Rapport Stage Copy Copy Rayen Sabri
Pas encore d'évaluation
Exemple Rapport Stage Copy Copy Rayen Sabri
38 pages
Ordonnancements Coopératifs Pour Les Chaînes Logistiques
Pas encore d'évaluation
Ordonnancements Coopératifs Pour Les Chaînes Logistiques
177 pages
Supply Chain S4-5-6
100% (1)
Supply Chain S4-5-6
165 pages
Ref 5
Pas encore d'évaluation
Ref 5
69 pages
Ima500460403 Optimisationtransports
Pas encore d'évaluation
Ima500460403 Optimisationtransports
18 pages
Support Cours Transport GL 2024 2025
100% (1)
Support Cours Transport GL 2024 2025
177 pages
Gestion de Projets Informatique
Pas encore d'évaluation
Gestion de Projets Informatique
132 pages
Maintenance Préventive des Équipements BMT
Pas encore d'évaluation
Maintenance Préventive des Équipements BMT
106 pages
Pfe Boulmerdj Boussahoul
Pas encore d'évaluation
Pfe Boulmerdj Boussahoul
90 pages
Pfe Ameur
Pas encore d'évaluation
Pfe Ameur
90 pages
Memoire Ver2
Pas encore d'évaluation
Memoire Ver2
71 pages
Chabane Yacef
Pas encore d'évaluation
Chabane Yacef
4 pages
Classification Des Produits Chimiques
Pas encore d'évaluation
Classification Des Produits Chimiques
28 pages
Ch2 AnnB
Pas encore d'évaluation
Ch2 AnnB
12 pages
Méthode en deux phases pour PMF
Pas encore d'évaluation
Méthode en deux phases pour PMF
14 pages
Infrastructures de Transport
Pas encore d'évaluation
Infrastructures de Transport
47 pages
Seance 2
Pas encore d'évaluation
Seance 2
27 pages
Gestion de la Sécurité Ferroviaire
Pas encore d'évaluation
Gestion de la Sécurité Ferroviaire
20 pages
Guide Utilisation Arena 2016
Pas encore d'évaluation
Guide Utilisation Arena 2016
4 pages
Logistique Et Distribution
Pas encore d'évaluation
Logistique Et Distribution
18 pages
Logistique Et Distribution
100% (2)
Logistique Et Distribution
90 pages
Gestion Avancée d'Entrepôt e-Prélude
Pas encore d'évaluation
Gestion Avancée d'Entrepôt e-Prélude
49 pages
Fiabilité humaine et erreurs au travail
0% (1)
Fiabilité humaine et erreurs au travail
26 pages
Chapitre 1 - La Logistique de Distribution - Enjeux Et Concepts Fondamentaux
67% (3)
Chapitre 1 - La Logistique de Distribution - Enjeux Et Concepts Fondamentaux
17 pages
Logistique E-commerce : Enjeux et Solutions
Pas encore d'évaluation
Logistique E-commerce : Enjeux et Solutions
83 pages
Logistique et SCM : Fondements et Pratiques
Pas encore d'évaluation
Logistique et SCM : Fondements et Pratiques
98 pages
Faux Par Robert Kiyosaki PDF
Pas encore d'évaluation
Faux Par Robert Kiyosaki PDF
27 pages
Roadmap
Pas encore d'évaluation
Roadmap
4 pages
M21 - Réponses Examens - Abrégé
Pas encore d'évaluation
M21 - Réponses Examens - Abrégé
10 pages
Gestion Financière
Pas encore d'évaluation
Gestion Financière
79 pages
Contrat Sarl
Pas encore d'évaluation
Contrat Sarl
2 pages
PROJET S Performance
Pas encore d'évaluation
PROJET S Performance
11 pages
Appel d'offres pour constructions scolaires
Pas encore d'évaluation
Appel d'offres pour constructions scolaires
123 pages
DetailedBill F24070097814
Pas encore d'évaluation
DetailedBill F24070097814
2 pages
Examen Contrôle de Gestion 2019-2020
Pas encore d'évaluation
Examen Contrôle de Gestion 2019-2020
4 pages
Droit Des Affaires Et Covid 19
Pas encore d'évaluation
Droit Des Affaires Et Covid 19
85 pages
Chap 2
Pas encore d'évaluation
Chap 2
33 pages
AM041
Pas encore d'évaluation
AM041
26 pages
Facture Cartouche Encore
Pas encore d'évaluation
Facture Cartouche Encore
1 page
El Bazi QCM GF 2023-1
Pas encore d'évaluation
El Bazi QCM GF 2023-1
3 pages
Memoire GONI TAL Org
Pas encore d'évaluation
Memoire GONI TAL Org
73 pages
Formation Trading Binaire Gratuite Complet
Pas encore d'évaluation
Formation Trading Binaire Gratuite Complet
3 pages
Assurances Chantiers 3ibuilding
Pas encore d'évaluation
Assurances Chantiers 3ibuilding
2 pages
COURS de comptabilité-SYSCOHADA 1
Pas encore d'évaluation
COURS de comptabilité-SYSCOHADA 1
21 pages
FC2 Support de Cours Cage
Pas encore d'évaluation
FC2 Support de Cours Cage
41 pages
Lancement du Produit Bancaire SAHTI
Pas encore d'évaluation
Lancement du Produit Bancaire SAHTI
124 pages
Instruments de Paiement et Monnaie
Pas encore d'évaluation
Instruments de Paiement et Monnaie
13 pages
Examen Compta Analytique Taki KADIRI Youssef Session Normale 2020
Pas encore d'évaluation
Examen Compta Analytique Taki KADIRI Youssef Session Normale 2020
4 pages
Acte de Vente Immobilière à Guadeloupe
Pas encore d'évaluation
Acte de Vente Immobilière à Guadeloupe
1 page
Exercices Inflation
71% (7)
Exercices Inflation
8 pages
3 Iconic Clavinet Grooves - Adam Maness
Pas encore d'évaluation
3 Iconic Clavinet Grooves - Adam Maness
2 pages
TD N°11 - Analyse - Fin - TF - 20
Pas encore d'évaluation
TD N°11 - Analyse - Fin - TF - 20
2 pages
Consolidation Comptes IFRS: Théorie et Pratique
Pas encore d'évaluation
Consolidation Comptes IFRS: Théorie et Pratique
22 pages
Monte Escalier Scalamobil Centre Autonomie
Pas encore d'évaluation
Monte Escalier Scalamobil Centre Autonomie
84 pages
Capture D'écran . 2024-09-09 À 01.12.16
Pas encore d'évaluation
Capture D'écran . 2024-09-09 À 01.12.16
4 pages
TP de Droit
Pas encore d'évaluation
TP de Droit
10 pages