UNE MÉTAHEURISTIQUE DE RÉSOLUTION DE PROBLÈMES

FRANCIS LASALLE

UNE MÉTAHEURISTIQUE DE RÉSOLUTION DE PROBLÈMES STOCHASTIQUES DE

LOCALISATION-TRANSPORT

Mémoire présentée à la Faculté des études supérieures de l’Université Laval

dans le cadre du programme de maître en Science de l’Administration pour l’obtention du grade de Maître ès Sciences (M. Sc.)

DÉPARTEMENT D’OPÉRATIONS ET SYSTÈMES DE DÉCISION FACULTÉ DES SCIENCES DE L’ADMINISTRATION

UNIVERSITÉ LAVAL QUÉBEC

2009

© Francis Lasalle, 2009

Résumé Ce mémoire étudie un problème de localisation et de tournées de véhicules multi‐périodes

considérant un univers stochastique, plus connu sous l’intitulé « Problèmes Stochastiques de

Localisation‐Transport » (PSLT). Il est caractérisé par plusieurs modes de transport et plusieurs

périodes de demandes générées par un processus stochastique et stationnaire. Nous voulons

déterminer le nombre d’entrepôts requis afin de satisfaire aux demandes d’un ensemble de clients

et leur localisation. De plus, la mission des entrepôts en termes du sous‐ensemble de clients à

servir, doit être précisée. Le problème est formulé comme un programme stochastique avec

recours, et une approche heuristique et hiérarchique de résolution est proposée. Cette approche

comprend une procédure de recherche Tabou, une formule approximant la longueur des routes et

une procédure Clarke et Wright modifiée. Trois stratégies d’exploration dans le voisinage sont

proposées et comparées entre elles sur de nombreux problèmes réalistes faisant partie d’un large

plan d’expérience.

Chapitre 1 : Introduction iii

Abstract This thesis studies a Stochastic Location‐Transportation Problem (SLTP) characterized by

multiple transportation options, multiple demand periods and a stochastic stationary demand. We

consider the determination of the number and location of the depots required to satisfy a set of

customer’s demands, and the mission of these depots in terms of the subset of customers they

must supply. The problem is formulated as a stochastic program with recourse, and a hierarchical

heuristic solution approach is proposed. It incorporates a Tabu search procedure, an approximate

route length formula, and a modified Clarke and Wright procedure. Three neighbourhood

exploration strategies are proposed and compared with extensive experiments based on realistic

problems.

Chapitre 1 : Introduction iv

Avant‐propos

Ce mémoire a fait l’objet de l’article « The Stochastic Multi‐Period Location‐Transportation

Problem » rédigé par Walid Klibi, Alain Martel, Soumia Ichoua, ainsi que moi‐même. Cet article a

été diffusé comme document de recherche du centre de recherche CIRRELT en 2008. Les sujets de

déploiement de réseaux logistiques m’intéressent depuis quelques années et ce fut un honneur

de travailler avec des gens reconnus pour leurs connaissances en la matière.

Ces années ont été bien remplies et je dois dire que j’apprécie énormément les moments

passés avec mon directeur Alain Martel et avec Walid Klibi, toujours à discuter de façons et de

méthodes permettant de rendre notre travail accessible, réaliste et à la fine pointe des

développements scientifiques du domaine de design de réseaux logistiques. Un sincère et vibrant

remerciement se doit d’être témoigné à ces deux personnes sans qui aucune des lignes qui

suivent n’auraient pu voir le jour. Merci Walid pour ta patience, tes explications et tes

nombreuses soirées de disponibilité physique ou virtuelle. Travailler avec des gens passionnés

comme tu l’as été fut un réel cadeau de la vie pour moi. Sans oublier Soumia Ichoua dont la

participation à la réalisation de l’article fut essentielle. Merci Soumia pour tes nombreux conseils,

ton regard critique, de même que ta grande intégrité. Merci également à Ossama Kettani et à

Jacques Renaud qui ont été les examinateurs de ce mémoire. De plus, je pense à tous les gens que

j’ai côtoyés à l’intérieur du CIRRELT notamment Wissem, Mehdi, Marc, Houssam, Sylvain, Francis,

Rémi, Simon, Pierre, Frédéric, Brigitte et Louise. Une pensée toute spéciale également à Gilles

D’Avignon par qui le merveilleux monde de la recherche fut possible pour moi. Ensuite, pour leur

accueil et leur support, merci à Mori et Virginie, Mat et Sophie, Rémi et Geneviève, Sèverine et

Philippe, Geneviève et David, Amélie et Éric, Pat de même qu’Anne.

Finissons cet avant‐propos avec les gens qui comptent le plus et qui font vibrer mon cœur.

Merci à ma sœur Véronic et à son copain Sébastien, merci à mes parents Danielle et Mario et à ma

copine et fidèle complice de tout temps Édith. Vous êtes et serez toujours ma vraie raison de

savourer le bonheur de la vie et l’accomplissement d’un tel projet.

Chapitre 1 : Introduction v

Table des matières

1. Introduction................................................................................................................................................ 1

1.1. Contexte ...................................................................................................................... 1

1.2. Problématique............................................................................................................. 2

1.3. Organisation du mémoire ........................................................................................... 3

2. Définition et formulation du problème............................................................................................. 5

2.1. Revue de littérature .................................................................................................... 5

2.2. Contexte logistique ..................................................................................................... 8

2.3. Problème opérationnel du réseau de distribution.................................................... 11

2.4. Problème stratégique et design du réseau de distribution ...................................... 15

2.5. Modèle approximatif basé sur la moyenne échantillonnale .................................... 17

3. Approche heuristique............................................................................................................................20

3.1. Problème opérationnel ............................................................................................. 21

3.2. Méthode de recherche Tabou appliquée au design du réseau ................................ 25

3.2.1. Évaluation dans le voisinage ............................................................................. 25 3.2.2. Évaluation approximative du coût des routes................................................... 27 3.2.3. Exploration restreinte des solutions .................................................................. 29 3.2.4. Méthode de réaffectation des clients................................................................ 31 3.2.5. Organisation des listes taboues ........................................................................ 33

3.3. Algorithmes d’initialisation et de recherche Tabou.................................................. 34

4. Évaluation de l’approche......................................................................................................................39

4.1. Taille du réseau logistique ........................................................................................ 40

4.2. Structures de coût..................................................................................................... 42

4.3. Caractéristiques des clients et de leur demande...................................................... 44

5. Résultats numériques............................................................................................................................47

5.1. Calibration des paramètres....................................................................................... 48

5.2. Analyse des résultats................................................................................................. 53

5.2.1. Solutions optimales du modèle AMÉ................................................................. 53 5.2.2. Comparaison des heuristiques .......................................................................... 54

6. Conclusion .................................................................................................................................................67

6.1. Pistes d’amélioration et travaux futurs..................................................................... 69

Liste des tables Table 4.1 – Tailles des problèmes analysés .............................................................................. 41

Table 4.2 – Structures de coût analysées ................................................................................. 43 Table 4.3 – Processus de demande des clients......................................................................... 45

Table 5.1 –Calibration des paramètres de la procédure Transport. ........................................ 48

Table 5.2 – Impact de la procédure Réaffecter par rapport à la méthode globale.................. 49 Table 5.3 – Analyse des paramètres de la procédure Tabou ................................................... 50 Table 5.4 – Statistiques des écarts moyens par rapport à la solution optimale....................... 52 Table 5.5 – Comparaison avec les solutions de CPLEX‐11 du modèle AMÉ pour P1................. 54 Table 5.6 – Détail des statistiques obtenues avec P1 pour les trois stratégies......................... 57 Table 5.7 – Valeurs moyennes des designs pour chaque type de problèmes. ......................... 59 Table 5.8 – Caractéristiques des routes construites par la procédure Transport .................... 66

Table des figures Figure 1.1 – Exemple d’un réseau «Entrepôts potentiels‐Clients»............................................. 3

Figure 2.1 – Réseau de « Localisation‐Transport » multi‐périodes .......................................... 11

Figure 2.2 – Processus stochastique de la demande des points de livraison ........................... 13 Figure 2.3 – Procédure MonteCarlo pour la génération d’un scénario .............................. 18

Figure 3.1 – Routes considérées dans le calcul des économies pour l’entrepôt l ................... 24 Figure 3.2 – Procédure Transport pour l’entrepôt l à la période t du scénario ................ 24 Figure 3.3 – Procédure Réaffecter ............................................................................................ 32 Figure 3.4 – Procédure Initialiser.............................................................................................. 35 Figure 3.5 – Procédure Tabou................................................................................................... 37

Figure 4.1 – Carte du réseau de P1............................................................................................ 42

Figure 4.2 – Carte du réseau de P2............................................................................................ 42 Figure 4.3 – Carte du réseau de P3............................................................................................ 42 Figure 4.4 – Exemple de répartition des types de clients ......................................................... 46

Figure 5.1 – Exemple de réseaux géographiques pour chacune des tailles de problèmes ...... 56

Figure 5.2 – Écart des valeurs des stratégies avec la meilleure solution heuristique obtenue.60 Figure 5.3 – Temps d’exécution des stratégies de recherche................................................... 61 Figure 5.4 – Évolution de la recherche pour (P3‐a‐RG‐SD2)...................................................... 63 Figure 5.5 – Comparaison des deux phases de la stratégie 3 pour (P3‐b‐RP‐SD2).................... 64 Figure 5.6 – Rapport entre l’estimation et la valeur réelle des routes..................................... 65

Chapitre 1

Introduction

1.1. Contexte

La réalité des problèmes vécus par l’ensemble des intervenants du domaine manufacturier

permet, aujourd’hui, d’établir l’importance d’une juxtaposition entre les besoins réels et les

approches proposées par les nouveaux systèmes d’aide à la décision. En effet, pour être en

mesure d’apporter des solutions innovatrices et adaptables, celles‐ci doivent tenir compte du plus

grand nombre de contraintes réellement assujetties aux activités des industries visées. Les réseaux

logistiques étant de plus en plus complexes, il devient primordial d’en maîtriser les moindres

détails. Ainsi, tout au long de cette séquence d’opérations logistiques, plusieurs décisions seront à

prendre et plusieurs variables influenceront également celles‐ci. Ces dernières varieront tout au

long de l’horizon de planification et s’ajusteront selon l’impact qu’elles auront sur le fil des

événements.

La présente étude vise justement à répondre aux besoins réels des entreprises qui désirent

mieux comprendre les impacts des différentes structures possibles de leur réseau. Les coûts et les

répercussions des décisions stratégiques et opérationnelles qui doivent être prises dans le temps

se doivent d’être connus et compris. Ceci dans le but de discerner les options possibles et de

Chapitre 1 : Introduction 2

positionner de façon stratégique les diverses ressources matérielles, humaines, financières ou

informationnelles du réseau logistique. C’est l’efficacité avec laquelle l’entreprise pourra répondre

à la demande et établir de façon précise son offre qui lui permettra de devancer la concurrence de

son industrie. Ce concept d’efficacité est directement relié aux designs du réseau logistique et à la

position des nœuds qui le définissent. Ainsi, l’entreprise est confrontée à divers problèmes de

logistique qui deviendront de plus en plus complexes au fur et à mesure de son expansion. On

tentera alors d’établir les modèles reliés à ces problèmes et de proposer des méthodes de

résolution qui incluent les contraintes de performance fixées par l’environnement de l’entreprise.

1.2. Problématique

La problématique traitée dans ce mémoire porte sur des problèmes de localisation et de

tournées de véhicules considérant un univers stochastique et multi‐périodes. Le problème étudié

est plus connu sous l’intitulé «Problèmes stochastique de Localisation‐Transport » (PSLT). Il se

démarque des problèmes classiques de Localisation‐Routage (PLR) tout en conservant la

combinatoire « NP‐Complet » de ces problèmes comme démontré dans Laporte (1988). À chaque

période donnée, le sous‐problème de transport considéré dans le PSLT est un problème de

tournées de véhicules (PTV) ouvert ayant les mêmes propriétés combinatoires que le PTV

classique (Sariklis et Powell, 2000). Il s’agit donc d’un problème d’optimisation stochastique « NP‐

complet ». En conséquence, si des approches de résolution exactes peuvent être utilisées dans le

but de résoudre de façon optimale les plus petits problèmes du PSLT, elles sont en revanche

incapables de traiter des problèmes de taille réaliste. Cela justifie en soit la nécessité de

développer des heuristiques permettant d’obtenir des solutions de qualité à ce genre de

problèmes.

Cette étude se démarque à plusieurs niveaux et se caractérise entre autres par le choix des

modes de transport et par la nature du processus de demande. Ce processus fait intervenir la

multiplicité des périodes dans l’horizon de planification ainsi que l’aspect stochastique qui en

découle. Nous considérons donc le problème qui doit déterminer le nombre d’entrepôts utilisés à

travers le réseau, leur localisation de même que la mission de ceux‐ci. Une telle mission se définie


comme étant l’ensemble des clients que l’entrepôt devra approvisionner. Mentionnons,

également, le choix de divers modes de transport « TruckLoad » (TL) ou du mode de transport

« Less than TruckLoad » (LTL) dans la construction des routes d’expédition utilisées par les

transporteurs publics. Des cas tests seront développés à l’intérieur de régions représentant divers

territoires de l’Est des États‐Unis (voir la figure 1.1 ci‐dessous). L’objectif de ce mémoire consiste à

apporter une définition plus précise du PSLT, à le formuler comme un programme stochastique

avec recours puis à proposer une métaheuristique qui permet de le résoudre.

Figure 1.1 – Exemple d’un réseau «Entrepôts potentiels‐Clients»

1.3. Organisation du mémoire

Le chapitre qui suit présente la définition et la formulation du problème en précisant les

caractéristiques propres aux deux niveaux décisionnels et à l’imbrication de ceux‐ci. Ce chapitre

formule également le problème comme un programme stochastique avec recours et il propose

une approximation basée sur la moyenne échantillonnale. Le chapitre 3, quant à lui, décrit

l’ensemble de l’approche heuristique développée afin de résoudre le problème hiérarchique

défini. Il commence par décrire certaines procédures communes utilisées au niveau opérationnel.

En fait, la procédure principale de recherche Tabou fait appel soit à une formule d’approximation

de la longueur des routes ou à une version modifiée de l’algorithme de Clarke et Wright. Ce


chapitre traite également de chacune des stratégies de recherche heuristiques envisagées. Puis le

chapitre 4 se consacre à l’évaluation de l’approche à l’aide de divers problèmes réalistes. L’étude

comprend un vaste plan d’expérience couvrant quatre aspects majeurs : la taille et la région

géographique du réseau, la variabilité des coûts pertinents, les caractéristiques des points de

livraison et les différentes structures de génération de la demande. Chacun des problèmes ainsi

générés permet, à l’intérieur du chapitre 5, de comparer entre elles l’efficacité et la rapidité des

heuristiques retenues. Il est également possible, pour de petits problèmes, d’identifier une borne

supérieure de comparaison obtenue en résolvant le modèle d’approximation de façon optimale.

Finalement, le chapitre 6 est réservé aux conclusions de ce mémoire.

Chapitre 2

Définition et formulation du problème

2.1. Revue de littérature

Les décisions de localisation d’entrepôts doivent être prises au niveau de la planification

stratégique du réseau de distribution. Fondamentalement, pour un contexte logistique donné, les

problèmes de localisation et d’affectation impliquent la détermination du nombre d’entrepôts

requis afin de satisfaire les demandes des clients de même que la localisation physique de ces

entrepôts. On détermine aussi la mission des entrepôts, soit l’ensemble des clients qu’ils auront à

servir. Plusieurs modèles déterministes, dynamiques et stochastiques ont été proposés au cours

de la dernière décennie dans le but de résoudre un éventail de problèmes variés de localisation

d’entrepôts. Une revue détaillée de la littérature dédiée à ce type de modèles est répertoriée dans

Owen et Daskin (1998) de même que dans Klose et Drexl (2005). Trois formulations de problèmes

en univers incertains sont également étudiées. Celles‐ci sont basées respectivement sur la

programmation stochastique (Birge et Louveaux, 1997; Snyder et Daskin, 2005), l’optimisation

robuste (Kouvelis et Yu, 1997) et la théorie des files d’attente (Berman et al., 1995). Dans la

plupart de ces formulations, seule la demande est considérée comme une variable aléatoire.

Chapitre 2 : Formulation du problème 6

Ainsi lorsqu’un tel réseau de distribution se déploie, sur une base périodique, les entrepôts

doivent expédier les produits requis par leurs clients vers les endroits ciblés de livraison. De plus, il

existe de nos jours un nombre impressionnant et grandissant de compagnies qui utilisent des

ressources externes afin de combler leurs besoins en transport. Ne détenant que quelques

équipements restreints, ces compagnies ne contrôlent pas, à toute fin pratique, leur propre flotte

de véhicules et impartissent la gestion de celle‐ci vers un partenaire logistique. À l’intérieur de ce

contexte d’affaire et tout dépendant de la taille des commandes enregistrées, ces entreprises

devront expédier leurs produits via des charges complètes (FTL) ou partielles et dédiée à un seul

client (STL). Elles peuvent également décider de livrer leurs produits sur des routes (MTL) ou bien

de privilégier le transport en charges partielles (LTL). Ces options de transport seront définies de

façon plus précise au cours des pages suivantes. Les profits ainsi générés à travers le réseau de

distribution dépendent largement de l’efficience avec laquelle les décisions de transport seront

prises. Les problèmes de routage ou de tournées de véhicules rencontrés dans les cas MTL ont été

étudiés de manière intensive dans la littérature. Laporte et Osman (1995) présente une

bibliographie des études faites en ce sens. Malgré l’ensemble de méthodes de solution exactes

développées pour le problème déterministe de routage (Toth et Vigo, 1998), la complexité de

celui‐ci a mené plusieurs chercheurs du domaine à opter pour une approche de résolution basée

sur les méthodes heuristiques (Laporte et al., 2000). Quelques versions stochastiques du PTV ont

également été étudiées (Laporte et Louveaux, 1998). Même si une portion importante de la

littérature classique considère les problèmes de localisation et de transport comme étant

indépendants, il apparaît clairement en pratique que ces problèmes ne peuvent être dissociés et

agissent mutuellement l’un sur l’autre. Cependant, depuis quelques années, des efforts majeurs

ont été consacrés au développement de modèles complets intégrant l’ensemble des décisions de

localisation, de routage et de détention des inventaires. On les retrouve sous la forme de

problème de localisation‐routage (PLR) ou d’inventaire‐routage (PIR). Une revue récente des ces

modèles intégrés est disponible dans Shen (2007).

La première classification des problèmes de localisation‐routage (PLR) est trouvée dans

Laporte (1988), lequel propose une variété de formulations déterministes du problème en

question. Plus récemment, les articles de Chien (1993), Tuzun et Burke (1999), Barreto et al.

(2007) et Prins et al. (2007) présentent tous des méthodes heuristiques développées afin de

résoudre les PLR déterministes. Une version multi‐échelons incluant les coûts d’inventaire est


proposée dans les travaux d’Ambrosino et Scutella (2005). Un PLR sans capacité avec contrainte de

distances est étudié dans Berger et al. (2007). Ceux‐ci proposent une formulation basée sur les

algorithmes de couverture de même qu’une résolution par la méthode de séparation et évaluation

progressive. Nagy et Salhi (1996a, b) ont, quant à eux, mis l’emphase sur la structure hiérarchique

du problème en développant une heuristique au cours de laquelle la phase de transport est

imbriquée à même la méthode de localisation. Un PLR dynamique appliqué à un horizon de

planification donné est traité dans Laporte et Dejax (1989) et dans Salhi et Nagy (1999). De plus,

un PLR stochastique est étudié dans Laporte et al. (1989) et dans Albareda‐Sambola et al. (2007).

Ces programmes stochastiques considèrent, pour le premier niveau, les localisations des entrepôts

de même qu’un ensemble de routes formées à priori. Puis, le second niveau implante des

décisions de recours permettant de corriger les infaisabilités rencontrées avec les routes générées

au premier niveau. Dernièrement, Shen (2007) nous a offert un modèle de PLR stochastique basé

sur l’estimation du coût des routes. Une approche permettant de résoudre le PLR continu est

également présentée dans Salhi et Nagy (2007). Une revue exhaustive des modèles de localisation‐

routage et de leurs applications est disponible dans Min et al. (1998) puis dans Nagy et Salhi

(2007).

Les modèles de PLR trouvés dans la littérature ont généralement deux points faibles lorsque

comparés aux entreprises qui distribuent leurs produits en utilisant des ressources externes de

transport.

Premièrement, la plupart des modèles de PLR assument que les distributeurs détiennent leur

propre flotte de transport et que les problèmes qui en découlent sont de purs PTV. Par contre,

plusieurs options deviennent disponibles lorsque des transporteurs publics ou contractuels sont

utilisés. Il s’agit des routes directes avec charges complètes FTL où partielles STL, des routes avec

arrêts multiples MTL et/où des routes de transport par LTL. Ainsi, les options d’envoi FTL, STL et

MTL sont toutes sous la responsabilité des transporteurs TL et diffèrent seulement par la façon

dont les véhicules seront utilisés par ces derniers. Le terme FTL (Full Truck Load) fait référence au

cas où une remorque chargée à pleine capacité sera expédiée vers une destination unique.

L’appellation STL (Single Drop Truck Load), quant à elle, correspond au cas où la capacité de la

remorque n’est pas complètement requise. Puis les routes MTL (Multiple Drop Truck Load)

correspondent aux situations dans laquelle les routes de livraison impliquent plus d’une

destination. Dans le dernier cas, une route est élaborée par l’expéditeur dans le même esprit que


s’il détenait effectivement sa propre flotte de véhicules. Pour ce qui est du quatrième mode, les

envois LTL se caractérisent par des quantités ponctuelles ne correspondant qu’à une partie

restreinte de l’espace d’un véhicule et sont optimisés par le transporteur en consolidant la

demande de plusieurs clients. Ces distinctions nous permettent alors de parler de problèmes de

Localisation‐Transport (PLT) au lieu de problèmes de localisation‐routage. Ces problèmes peuvent

être associés à la série de problèmes connue sous le nom de « problèmes de transport‐

localisation » lesquels, cependant, correspondent à des problèmes de transbordement‐localisation

tel que spécifié dans Nagy et Salhi (2007).

Deuxièmement, la majorité des PLR considèrent implicitement les décisions de localisation et

de routage comme pouvant être prises simultanément pour un horizon de planification donné. En

fait, cela implique que les routes restent fixes d’une période à l’autre et que la demande des

clients devient statique. Dans le contexte logistique qui nous intéresse, seules la localisation et la

mission des entrepôts doivent être fixées pour la totalité de l’horizon de planification. Les

décisions de transport, quant à elles, sont prises sur une base périodique en réaction aux

commandes reçues des clients. C’est ce que l’on appelle le « Problème Stochastique de

Localisation‐Transport » (PSLT) avec périodes multiples. Ce problème est peu traité dans la

littérature, et il y a peu de modèles de PLR qui considèrent le processus d’arrivée des commandes

de façon explicite. Salhi et Nagy (1999) ont introduit un problème multi‐périodes déterministe de

localisation‐routage afin d’analyser la robustesse des solutions obtenues avec les méthodes des

modèles statiques de localisation‐routage. Laporte et Dejax (1989) traitent un problème de

localisation‐routage dynamique mais ils n’obligent pas les localisations et les missions des

entrepôts à demeurer fixes pour l’ensemble de l’horizon de planification.

2.2. Contexte logistique

Pour commencer, examinons de façon plus approfondie le contexte logistique du PSLT. Une

compagnie achète (ou fabrique) une famille de produits similaires qui seront considérés comme

un seul et unique produit. Ce produit est vendu sur un marché couvrant une région géographique

donnée. Chaque produit doit donc être distribué vers un nombre important de points de livraison.

Afin d’offrir un service de qualité, l’entreprise ne peut satisfaire les demandes des clients


directement à partir des sources d’approvisionnement et doit ainsi opérer un certain nombre de

centres de distribution ou d’entrepôts publics non restreints sur la capacité disponible. Ces

derniers ne peuvent répondre à la demande de leurs clients qu’à l’intérieur d’un rayon d’action

fixe et prédéterminé selon le niveau de service exigé. Un nombre aléatoire de clients commandent

une quantité aléatoire de produits sur une base périodique. Les produits doivent être expédiés au

plus tard à la période suivant la commande des clients. Cette livraison se fait à l’aide de

transporteurs publics ou contractuels. Pour une période donnée t, lorsque toutes les commandes

sont répertoriées, l’entreprise planifie les routes de transport à chaque entrepôt de même que le

besoin en véhicules permettant de livrer les produits à chaque point de livraison identifié. Elle doit

également sélectionner les routes de transport qui seront attitrées aux voyages complets FTL, aux

voyages partiels direct STL, aux voyages avec arrêts multiples MTL où bien aux envois en mode de

transport LTL. Il est à noter que les routes sont empruntées par les véhicules d’un transporteur

externe et que cela implique que l’arc de retour n’est pas la responsabilité de l’entreprise.

Nous considérons, ici, L comme étant l’ensemble des entrepôts potentiels et P l’ensemble

des points de livraison émettant les commandes. Le paramètre pL L représente, quant à lui,

l’ensemble des entrepôts pouvant servir le point de livraison p P avant la fin de la période

suivante. En conséquence, lP P dénote l’ensemble des points de livraison pouvant être

approvisionnés par l’entrepôt l . Définissons également TLltK comme étant l’ensemble des routes

TL possibles (FTL, STL ou MTL) partant de l’entrepôt l pour la période t , compte‐tenu de

l’ensemble des demandes des clients, du niveau de service requis et des caractéristiques propres

aux véhicules. On dénote aussi l’ensemble ordonné des points de livraison d’une route TLltk K

identifié par kP P . Le tarif chargé par le transporteur suite à l’affectation d’un véhicule sur une

de ces routes TL correspond à :

max( ; ) ( 1)k k k l l kw r m TL a P

où

km = distance totale parcourue sur la route k

kr = tarif par unité de distance pour le véhicule associé à la route k

lTL = frais minimum de transport pour toutes routes TL en provenance de l’entrepôt l

la = frais de déchargement pour chaque arrêt supplémentaire nécessaire aux routes qui

partent de l’entrepôt l .


Il est important de mentionner que le montant kw doit être déboursé indépendamment de la

quantité expédiée ou de l’espace occupé à l’intérieur du véhicule. De plus, lorsqu’un client désire

recevoir une quantité excédant la capacité maximale d’un véhicule, l’entrepôt doit s’assurer de lui

acheminer les produits avec le plus grand nombre possible de véhicules en charge complète et

donc le plus de routes FTL envisageables.

Regardons maintenant le cas des demandes inférieures à la capacité d’un véhicule. Dans ce

cas, il sera normalement plus avantageux d’utiliser des routes TL lorsque la quantité à expédier se

rapprochera de la capacité du véhicule. D’autre part, si on regarde les demandes reçues pour une

période donnée, il se peut qu’il soit impossible de construire des routes avec un taux de

chargement intéressant. Il sera alors peut‐être plus économique d’expédier certaines de ces

quantités par mode de transport LTL. En particulier, si le fait d’expédier les commandes à chacun

des clients par des routes uniques LTL s’avère moins onéreux que la route TL reliant ces clients,

cette route TL sera abandonnée. Une telle route TLltk K ne sera pas utilisée si

( )kk p P ptw LTL l p d , ; où ptd représente la quantité devant être acheminée au point de

livraison kp P à la période t, et ( )LTL l p d, ; dénote le coût en mode LTL associé à l’envoi

d’une quantité d en provenance de l’entrepôt l au point de livraison p . Ainsi lorsque la route

LTL alternative domine une route TL, cette dernière peut être éliminée à priori de l’ensemble des

routes possibles. Nous supposons donc à partir de maintenant que toutes les routes comprises

dans l’ensemble TLltK sont non‐dominées. À l’opposé, pour une période t donnée, l’envoi LTL sur

l’arc l p, sera considéré intéressant seulement s’il est plus avantageux que l’envoi STL sur cet

arc, c'est‐à‐dire seulement si ( ) <ptLTL l p d, ;( (

max( )l p l pk k lr m TL, ) , )

; . Ceci implique que la

planification périodique des transports à l’entrepôt l inclut non seulement les routes TL réalisables

et non‐dominées TLltk K mais également toutes les routes LTL directes LTL

ltk K . On peut alors

considérer l'ensemble TL LTLlt lt ltK K K . Le prix à payer pour une route LTL LTL

ltk K est

( )kk k p tw LTL l p d , ; , où kp est le point de livraison de la route k .

À partir de maintenant, connaissant le contexte du réseau de distribution au niveau

opérationnel, nous pouvons nous attarder sur les décisions stratégiques. Celles‐ci impliquent la

sélection du sous‐ensemble d’entrepôts L L* à ouvrir durant l’horizon de planification

T considéré et l’affectation des points de livraison l lP P l L * *, à ces entrepôts. Le tout dans

le but de maximiser le profit total espéré. Il est important de mentionner que dans les sections qui

suivent, la notation L fait référence au sous‐ensemble d’entrepôts ouverts compris dans L , et


\L L L à son complément. De façon similaire, l lP P permet de représenter le sous‐ensemble

de points de livraison affectés à l L . De plus, un aspect important du problème réside dans le

fait que la mission des entrepôts, définie par les ensembles lP l L* *, , doit être maintenue pour

l’ensemble des périodes t T de l’horizon de planification. Aussi, lorsqu’un entrepôt l L est

utilisé, un coût fixe d’ouverture et d’opération lA est encouru et la valeur unitaire d’un produit

expédié par cet entrepôt est lv . Cette valeur lv prend en compte tous les coûts de production du

produit et d’approvisionnement des matières premières, l’ensemble des frais unitaires de

transport en amont vers les centres de distribution ainsi que les coûts totaux unitaires

d’entreposage et de manutention. Enfin, le prix unitaire de vente du produit au point de livraison

p est pu . La structure multi‐périodes du réseau de localisation‐transport examinée

précédemment est illustrée à la Figure 2.1 ci‐dessous.

Figure 2.1 – Réseau de « Localisation‐Transport » multi‐périodes

2.3. Problème opérationnel du réseau de distribution

Le réseau de distribution comprend donc un ensemble d’entrepôts L L et de

missions , lP l L . Il est aussi convenu que les entrepôts l L reçoivent les commandes de leurs

clients lp P sur une base périodique. Le système logistique de ces entrepôts doit alors

construire les routes de transport qui seront utilisées à chaque période. On considère, ici, que la


demande des points de livraison p P suit un processus stochastique composé et stationnaire.

Donc, le temps compris entre deux commandes pq et la quantité demandée po sont aléatoires.

Les fonctions de distribution cumulative des temps inter‐arrivées et des quantités demandées sont

dénotées respectivement par (.)qpF et par (.)o

pF . Une réalisation possible de ces processus

stochastiques composés pour un horizon de planification T est illustrée à la figure 2.2, pour un

temps inter‐arrivées exponentiel et une quantité demandée obéissant à la loi normale. De telles

réalisations constituent un scénario de demande, et l’ensemble des scénarios possibles est noté

par . De même, la probabilité que le scénario de demande soit éventuellement observé

est dénotée par ( ) . Aussi, pour un scénario donné , l’ensemble des points de livraison

qui commandent effectivement un certain nombre de produits à la période t est identifié par

tP .

Cette structure de demande de même que la nature des décisions à prendre à chaque

période caractérisent le problème de transport (PT). Celui‐ci inclut certaines caractéristiques

concernant, entre autres, le choix du mode de transport. Considérons, ici, les besoins des clients à

la période t T pour l’entrepôt l L comme défini par les quantités pt ltd p P , , où

lt l tP P P correspond à l’ensemble des points de livraison de l’entrepôt l qui

commandent à la période t . Le choix du mode de transport retenu afin d’expédier ces quantités

pt ltd p P , , est fait en suivant deux étapes séquentielles. Premièrement, pour les

quantités excédant la capacité d’un véhicule, le processus décisionnel permet d’envoyer le plus

possible de chargements complets FTL.


Figure 2.2 – Processus stochastique de la demande des points de livraison

Considérons, ici, FTLpltK comme l’ensemble des véhicules ou des routes reliant le point

p par le mode FTL, sans oublier les quantités résiduelles qui seront insérées dans les routes STL,

MTL ou dans les envois LTL. Ces dernières quantités représentent alors la portion excédentaire des

chargements complets FTL d’un entrepôt l à la période t . Elles sont définies comme suit:

FTLplt

FTLpt pt k klt lt

k K

d d b y p P

,

[1]

où FTLklty est le nombre d’expéditions FTL au point p à partir de l’entrepôt l sur la route k , et

kb correspond à la capacité du véhicule utilisé sur la route k . Ayant isolé les envois FTL, les

meilleures routes peuvent donc être construites en ne considérant que les quantités résiduelles.

Identifions maintenant les trois paramètres nécessaires au problème de transport :

ltK : Ensemble réalisable des routes de livraison non dominées [soit celles dont

k ltP P et kp P pt kd b , ltk K ] en provenance de l’entrepôt l , pour

la période t du scénario ;

kp : Variable entière prenant la valeur 1 si le point de livraison p est servi par la route k

(donc si kp P ), et 0 autrement;

klty : Variable entière prenant la valeur 1 si la route k est utilisée par l’entrepôt l à la

période t du scénario , et 0 autrement.


En conséquence, pour le scénario de demande , les meilleures routes de l’entrepôt l à la

période t sont obtenues en résolvant le sous‐problème de routage:

lt

Oplt k klt

k K

C Min w y

y

[2]

soumis aux contraintes:

1

lt

kp klt ltk K

y p P

;

[3]

0 1klt lty k K , ; [4]

où y désigne le vecteur des décisions de routage, et Op

ltC est le coût minimal des

expéditions faites par l’entrepôt l à la période t du scénario . Ce modèle est similaire à la

formulation classique de l’algorithme de couverture du PTV déterministe (Toth et Vigo, 1998)

lorsqu’on ne considère aucune limite sur le nombre de véhicules disponibles.

De plus, les envois requis sur une base périodique génèrent des revenus sur la vente des

produits. Les profits réalisés découlent donc de ces revenus, de même que des coûts de

production et d’approvisionnement en amont, des coûts d’entreposage et de manutention, des

coûts de détention des inventaires ainsi que des coûts de commandes des clients. Ceci nous

amène à définir l’équation des revenus nets OpR générés par le réseau de distribution sous le

scénario de demande :

FTL

lt lt plt

Op FTL Opp l pt k klt lt

l L t T p P p P k K

R u v d w y C

[5]

Ces revenus nets constituent un élément important à prendre en compte dans la construction

du modèle de design au niveau stratégique.


2.4. Problème stratégique et design du réseau de distribution

Le PSLT est un problème hiérarchique parce qu’on ne peut considérer dans le même horizon

de temps les décisions de localisation d’entrepôts et les routes de transport utilisées par ceux‐ci.

Au niveau stratégique, les seules et uniques décisions à prendre sont la sélection du sous‐

ensemble d’entrepôts L L* en opération durant l’horizon T considéré, de même que la

mission lP l L* *, de ces derniers. Puis, après une période plus ou moins longue permettant le

déploiement du réseau et de ses infrastructures, les décisions de transport seront prises pour

chaque période ouvrable. Cependant, les décisions stratégiques nécessaires à la confection du

design doivent être connues au moment où les décisions périodiques de transport sont prises.

Cette particularité fait en sorte que les choix adéquats quant au design du réseau ne peuvent être

pris sans anticiper d’une façon ou d’une autre les revenus nets [5] générés par les ventes

périodiques et les problèmes de transport. La meilleure anticipation possible implique d’inclure

explicitement le modèle de transport [2‐4] à l’intérieur du modèle stratégique de même que

l’expression des revenus nets [5]. Cependant, on ne peut considérer, au moment où les décisions

relatives au design du réseau doivent être prises, que les informations réellement disponibles.

Puisque la demande des clients n’est pas connue pour l’horizon T lorsque les décisions

stratégiques de design sont prises, l’information disponible se limite à l’ensemble des scénarios de

demande défini précédemment. Cela nous mène à la formulation du PSLT comme un

programme stochastique à deux étapes avec recours. La première étape tient compte des

décisions de localisation et de mission des entrepôts et la deuxième modélise les problèmes

quotidiens de transport.

Les variables suivantes représentent les décisions de première étape et sont requises dans la

formulation du modèle :

lx : Variable entière prenant la valeur 1 si l’entrepôt l est ouvert, et 0 autrement;

lpx : Variable entière prenant la valeur 1 si le point de livraison p est servi par l’entrepôt l , et

0 autrement;

La notation x est utilisée, ici, pour représenter le vecteur regroupant ces deux variables et xl ,

quant à lui, correspond au vecteur d’assignation des points de livraison à l’entrepôt l . Notons que,


pour un vecteur binaire x donné, les ensembles L et lP sont uniques et définis comme suit

1 0l lL l x L l x , , et

1l lpP p x l L , . Définissons maintenant le

programme stochastique à résoudre :

( ) ( )* StOpl l

l L

R Max R R , A x

x

x x

[6]


1p

lpl L

p Px

,

[7]

, , llp l l L p Px x

[8]

0 1 ll lp l L p Px x , ,, ,

[9]

où, d’après [2‐5], la valeur optimale StOpR x , du problème de deuxième étape pour le design

x et le scénario est donné par:

FTL

t plt

StOp FTL StOpp l pt k klt lp lt l

l L t T p P k K

R u v d w y x C

x x, ,

[10]

avec:

lt

StOplt l k klt

k K

C Min w y

y

x ,

[11]


lt

kp klt lp tk K

y x p P

,

[12]

0 1klt lty k K , ,

[13]

Les deux termes de la fonction objectif [6] correspondent respectivement au calcul des

revenus nets espérés et aux coûts fixes d’ouverture des entrepôts. Comme ces derniers sont

soustraits des revenus nets cela nous permet d’obtenir les profits espérés. La contrainte [7], force

les points de livraison à n’être affectés qu’à un seul entrepôt, tandis que la contrainte [8] limite

l’affectation des points de livraison aux entrepôts ouverts. Pour ce qui est de la contrainte [12] elle

assure que la sélection d’une route pour une période donnée respecte les missions de chacun des

entrepôts.


Considérant la complexité combinatoire inhérente au modèle, il sera virtuellement impossible

de le résoudre. À cette complexité s’ajoute le nombre extrêmement grand de scénarios

composant l’ensemble . En fait, lorsque les distributions du temps inter‐arrivées des

commandes qpF (.) et de la taille de celles‐ci pF (.) sont continues, il existe un nombre infini de

scénarios possibles. C’est le cas, par exemple, lorsque le temps inter‐arrivées est exponentiel et la

taille des commandes suit une loi log‐normale, un cas fréquent en pratique. Cette difficulté peut

cependant être atténuée par l’utilisation de la méthode d’échantillonnage de Monte Carlo.

2.5. Modèle approximatif basé sur la moyenne échantillonnale

L’approche proposée, afin de réduire la complexité stochastique du problème, est basée sur

la méthode d’échantillonnage de Monte Carlo que l’on retrouve dans Shapiro (2003). Elle est

également appliquée au PTV dans Verweij et al. (2003) et Rei et al. (2007) puis aux problèmes de

design de la chaîne logistique dans Santoso et al (2005) et Vila et al. (2007). Dans le cas qui nous

occupe, un échantillon aléatoire de scénarios est généré à l’extérieur de la procédure

d’optimisation puis un programme approximatif basé sur la moyenne échantillonnale (AMÉ) est

construit et résolu. Le principe consiste à générer directement, à partir des distributions

cumulatives respectives, deux observations associées aux deux composants du processus de

demande. Ainsi, en générant deux nombres pseudo‐aléatoires qu et ou uniformément distribués

dans l’intervalle [0;1] , on peut calculer respectivement l’inverse des fonctions de distribution

-1( )qp qF u et 1o

p oF u du temps inter‐arrivées et de la taille des commandes. La génération

successive de commandes, jusqu’à la fin de l’horizon de planification forme donc un scénario à

part entière. Considérant chacune des observations comme étant indépendantes, la génération

des n scénarios équiprobables 1,..., n n de l’échantillon s’effectue en répétant la

procédure n fois et en utilisant les distributions de probabilités initiales. Ceci implique qu’il n’est

pas requis d’estimer explicitement la probabilité d’occurrence des scénarios ( ) . Ainsi, lorsqu’on

se base sur [6‐13], on obtient le programme AMÉ :

1n FTL

t ltplt

FTLn p l pt k klt lp k klt

l L t T p P k Kk K

l ll L

R Max u v d w y x w y

A x

n

x y

,

[14]



1p

lpl L

p Px

,

[15]

l llp l L p Px x , , [16]

lt

nkp klt lp t

k K

y x l L t T p P

, , , ,

[17]

0 1 nklt ltl lp y l L t T p P k Kx x , , , , , , ,,

[18]

La procédure MonteCarlo utilisée afin de générer les demandes périodiques

ptd p P t T , , d’un point de livraison donné au cours du scenario est présentée à la

figure 2.3. À l’intérieur de celle‐ci, la variable continue représente les temps d’arrivées des

commandes. Ceux‐ci sont générés dans l’intervalle 0 T , et incorporés dans la période de

planification correspondante t T . Enfin, lorsque cette procédure échantillonnale de Monte Carlo

est répétée n fois cela nous permet d’obtenir l’échantillon de scenarios n requis.

Remarquez qu’on utilise la syntaxe suivante pour l’ensemble des procédure écrites dans ce

document : Procédure (Variables d’entrée; Paramètres de la procédure; Variables de sortie).

( (.), (.), ); ; ( )q op p ptF F p P T d p P t T MonteCarlo , ,

Pour tout p P , faire

1) 0 ; 0 ptd t T ,

2) Tant que T , faire

a) Générer les nombres aléatoires uniformes qu et u dans l’intervalle [0,1]

b) Calculer le prochain temps d’arrivée -1( )qp qF u et t

c) Calculer la demande 1( )pt pt p ud d F - de la période t

Figure 2.3 – Procédure MonteCarlo pour la génération d’un scénario


Évidemment, la qualité des solutions obtenues avec cette approche s’améliore de façon

significative lorsque le nombre n de scénarios compris dans les échantillons augmente. Le modèle

AMÉ ci‐dessus présente une structure similaire au problème de localisation‐routage déterministe

(Berger et al. 2007) tout en étant plus vaste et en séparant explicitement les décisions

d’affectation et de routage. Il utilise également un nombre exponentiel de variables de décision

binaires pour la sélection des routes. L’ensemble préétabli de routes non dominées peut

effectivement être construit et servir de données de base pour ce modèle. Cependant, cette

approche permet de résoudre que des petits problèmes de façon optimale, à l’aide de solveurs

commerciaux. Une meilleure approche serait d’utiliser la technique de génération de colonnes qui

évite la considération explicite de toutes les routes possibles. Cependant, comme nT * peut

s’accroître très rapidement, l’approche optimale ne peut être utilisée que pour des problèmes

relativement petits. L’objectif du prochain chapitre est justement de proposer une méthode

heuristique qui permet de résoudre des problèmes de taille réaliste.

Chapitre 3

Approche heuristique

L’approche heuristique proposée dans le but de résoudre le PSLT correspond à une méthode

imbriquée qui intègre de façon hiérarchique les décisions de localisation, d'affectations et de

transport. Nagy et Salhi (2007) ont présenté une revue des approches séquentielles, par

regroupement, itératives et hiérarchiques permettant de résoudre le PLR. La principale différence

entre ces heuristiques revient essentiellement au traitement de la relation entre la localisation et

le sous‐problème de routage. Selon la définition du problème à deux niveaux présenté à la figure

2.1, l’approche de résolution proposée comprend une heuristique de transport au niveau

opérationnel et une heuristique de « localisation‐affectation » au niveau stratégique le tout

combiné de façon efficace à l’intérieur d’une procédure qui permet d’imbriquer ces deux niveaux.

Pour le problème stratégique de construction du design, la recherche Tabou proposée

détermine la localisation des entrepôts et affecte chaque point de livraison à un des entrepôts

présentement ouverts. Il s’agit en fait d’une recherche locale qui explore la configuration des

entrepôts compris dans le voisinage en modifiant également l’affectation des points de livraison.

Cette exploration n’est possible qu’à travers un sous‐ensemble restreint de mouvements autorisés

selon la solution courante. De plus, pour le problème opérationnel de transport, une version

Chapitre 3: Approche heuristique

21

modifiée de l’algorithme des économies de Clarke et Wright est proposée. Cet algorithme est

utilisé afin d’évaluer chacun des nouveaux designs construits par les itérations de la recherche.

On peut voir que plusieurs centaines de mouvements devront être considérés tout au long du

processus de résolution. Par conséquent, une évaluation exacte de chaque solution potentielle par

l’heuristique de transport serait très coûteuse en termes de temps d’exécution. Afin de résoudre

le modèle AMÉ [14‐18], l’évaluation des solutions considérées doit être basée sur une estimation

de leur valeur espérée pour un échantillon donné de scénarios n . Ainsi, pour réduire l’effort

nécessaire aux calculs, nous proposons une procédure rapide et approximative d’évaluation des

mouvements, procédure basée sur une formule d’estimation du coût des routes. L’analyse de

notre approche de résolution nous permet de l’associer aux heuristiques hybrides de bas niveau

que l’on retrouve dans la nomenclature proposée par Talbi (2002). Les sections suivantes

présentent respectivement les heuristiques développées pour le problème opérationnel et le

problème stratégique.

3.1. Problème opérationnel

Au niveau opérationnel, le problème réside dans la confection des routes de transport qui

seront effectuées périodiquement. Ces routes se distinguent, ici, selon le mode de transport opéré

par le fournisseur de service. En fait, pour un réseau de distribution donné comprenant l’ensemble

des entrepôts L L et des missions lP l L , les envois peuvent être acheminés par l’entrepôt

l selon quatre modes présentés comme le FTL, le STL, le MTL et le LTL. Il est donc nécessaire

d’utiliser le bon mode de transport dans le but de minimiser les coûts suite aux commandes des

points de livraison ltP reçue par l’entrepôt l à la période t du scénario .

La méthode en deux étapes présentée ici permet de déterminer d’abord les envois FTL puis

les quantités résiduelles à livrer avec les autres modes de transport. Ainsi, le nombre de routes FTL

de chaque type FTLpltk K qui partira de l'entrepôt l à la journée t est obtenu en résolvant le

problème de programmation en nombre entier suivant:


22

arg max 0 1

yFTLplt FTL FTL

plt plt

FTLltklt k k k k pt kk K

k K k K

y b y b y d y p P

, , , ... ,

[19]

Ensuite, les quantités résiduelles pt ltd p P , obtenues avec [1] s’ajouteront aux

autres demandes initialement inférieures à la capacité des routes.

La deuxième étape vise à résoudre le problème [2‐4], c.‐à.‐d. à minimiser les coûts des envois

en mode "Truck Load" (MTL ou STL) ou "Less than Truck Load" (LTL). Notons une première

différence avec les problèmes classiques de tournées de véhicules mise en évidence à ce stade‐ci.

En fait, il s'agit des deux modes de transport pouvant être utilisés pour les routes directes vers le

client. En effet, la méthode de solution devra déterminer si le coût du transport LTL domine la

tarification d'une charge complète en mode STL pour ce genre de route. De plus, il est toujours

possible dans le cas d'une route MTL de séparer chacun de ses clients et de répondre à leurs

besoins par le mode LTL, favorisant justement la consolidation de plusieurs petites quantités. Voilà

que toutes ces particularités nous permettent maintenant d'évaluer adéquatement les coûts de

transport. On définira ainsi trois différents types d'arc représentant le trajet d’un véhicule entre

deux points du réseau. Il s'agit donc de l'arc de départ rejoignant l'entrepôt au premier point de

livraison, de celui rejoignant deux points de livraison et de l'arc de retour vers l'entrepôt. La

deuxième particularité du problème de transport consiste à la prise en charge du véhicule, par le

transporteur public, une fois le dernier client visité. Cette particularité du problème se reflète par

un coût de transport nul pour l’arc de retour vers l'entrepôt. L’élimination du processus

décisionnel de cet arc de retour et des voyages en charges complètes FTL permet d’obtenir, à

partir du PTV général, un problème standard de routage considéré comme ouvert et appelé « PTV

ouvert ».

Afin de résoudre le problème de routage qui se présente alors au niveau opérationnel, une

méthode heuristique de PTV simple et efficace est proposée. Cette approche est basée sur

l'algorithme de Clarke et Wright perturbé (CW+) et augmenté d'une amélioration 2‐opt

développée par Girard et al. (2006). Elle mise essentiellement sur le classement variable des

meilleures économies, comparant la fusion de deux points sur une même route plutôt que de les

desservir par des routes séparées. Ainsi, si l'on regarde la possibilité de visiter deux clients sur le

même trajet, on peut déterminer à priori quel serait le meilleur moyen de parcourir le premier arc


23

vers ces deux clients. Le coût du meilleur envoi direct de l'entrepôt l vers un de ces clients p

tient alors compte du mode de transport LTL ou STL de la façon suivante:

( , ) ( , ) ( , ) min ( , ; );max( ; ) , ltl p pt l p l p lw LTL l p d r m TL p P [20]

Le calcul des économies permet donc de comparer la somme des fonctions de coût

dominantes (LTL ou TL) sur chacun des arcs de premier type avec la fonction de coût TL d’une

route unique qui s’arrêterait à chacun des clients. La figure 3.1 présente de façon concrète les

choix possibles de routes et l’alternative opérationnelle qu’elles représentent. En effet, pour deux

points de livraison p et 'p , l’économie associée à l’utilisation d’une seule route TL avec arrêts

multiples , , 'l p p aux dépens de deux envois directs ,l p et , 'l p peut être calculée avec

l’expression suivante :

' ( , ) ( , ') ( , , ') - , , ' \lt ltpp l p l p l p pe w w w p P p P p

[21]

où ( , , ') ( , , ') ( , , ')max( ; )l p p l p p l p p l lw r m TL a . L’heuristique de Clarke et Wright perturbé est

maintenant utilisée en respectant le même fonctionnement que l’algorithme original CW.

Cependant, la formule des économies est modifiée de la façon suivante:

' ( , ) ( , ') ' ( , , ') - , , ' \lt ltpp l p l p pp l p pe w w w p P p P p

[22]

où le poids 'pp est aléatoirement choisi entre deux limites prédéterminées et

pour

chaque paire , 'p p . L’heuristique “2‐opt” passe ensuite en revue chacune des routes afin

d’améliorer la solution obtenue. Cette procédure est exécutée fois, ce qui permet de diversifier

les valeurs 'pp et l’importance relative des économies. La meilleure solution trouvée suite à ces

itérations sera retenue et constituera la route évaluée. Le coût total de transport de cette

meilleure solution est noté par StOpltltC P ˆ et le revenu net généré par l’entrepôt l L à la

période t T pour le scénario n est donné par :

FTLpltlt

StOp FTL StOplt ltlt p l pt k kt lt

k Kp P

R P u v d w y C P

ˆˆ

[23]


24

Figure 3.1 – Routes considérées dans le calcul des économies pour l’entrepôt l

Cela nous amène à la présentation de la procédure Transport qui résume l’heuristique

proposée pour le problème opérationnel. Cette procédure définie à la figure 3.2 ci‐dessous peut

être utilisée afin d’évaluer un design x . Pour obtenir le revenu net total d’un scénario donné,

nous devons simplement calculer la somme des revenus nets pour tous les entrepôts et toutes les

périodes, soit StOp StOpltltl L t T

R R P

xˆ ˆ, . Pour obtenir l’estimation ( )R x de la

valeur espérée du design considéré à l’aide d’un échantillon n de n scénarios, on utilise la

relation suivante :

1( ) n

StOpltn lt ll L t T l L

R R P An

x ˆ

[24]

( ( )) ( ) ( ); ; ( )FTL dult ltk plt pt ltb k K d p P R P Transport ˆ, , , , ,

S1: 1) Résoudre [19] afin d’obtenir les envois FTL

FTL FTLltklt plty k K p P , ,

2) Calculer les quantités résiduelles ltptd p P , , avec [1]

S2: 1) Sélectionner les meilleurs modes de transport par arc direct (LTL où STL), et calculer

leurs coûts ( , ) , ltl pw p P , avec [20]

2) a) Résoudre fois le PTV Ouvert correspondant avec l’algorithme modifié de Clarke

et Wright utilisant les économies ' , , ' \lt ltppe p P p P p calculées

avec [22]. b) Retenir la meilleure solution de transport.

S3: Calculer le revenu net ( )StOpltltR P ˆ avec [23].

Figure 3.2 – Procédure Transport pour l’entrepôt l à la période t du scénario


25

3.2. Méthode de recherche Tabou appliquée au design du réseau

L’heuristique proposée afin de résoudre le programme approximatif basé sur la moyenne

échantillonnale (AMÉ) [14‐18] s’appuie sur les principes de la recherche Tabou. Cette recherche

itérative se caractérise par la possibilité d’une dégradation de la solution lui permettant de quitter

les régions d’exploration menant à un optimum local. Ceci constitue une différence par rapport

aux méthodes de descente pure. À partir du moment où les mouvements sans amélioration sont

permis, il devient possible que des solutions précédemment rencontrées au cours de la recherche

soient revisitées. Afin de contourner ce problème cyclique, une mémoire à court terme, appelée

liste taboue, garde la trace des mouvements récemment utilisés. Il est possible de trouver de plus

amples détails à propos de cette approche dans Glover et Laguna (1997). Plus spécifiquement, à

chaque itération de l’heuristique Tabou, le design courant xc peut être amélioré. Les solutions

potentielles non‐taboues situées dans le voisinage de xc sont évaluées avec une formule rapide

mais approximative d’estimation du coût des routes. La meilleure solution potentielle trouvée par

cette approximation est ensuite évaluée précisément avec Transport afin de déterminer si elle est

plus avantageuse que la meilleure solution x* obtenue jusqu’à maintenant. Les prochains

paragraphes décrivent les principales caractéristiques de l’heuristique de recherche Tabou

proposée de même que trois stratégies d’exploration du voisinage.

3.2.1. Évaluation dans le voisinage

Prenons l’ensemble cM qui regroupe tous les mouvements possibles à partir de la solution

courante cx obtenue au cours d’une itération donnée de l’heuristique. Puis, utilisons l’opérateur

qui lie la solution courante au mouvement pouvant y être appliqué. Le Voisinage Général

c m m c cVG m m M x x x x , du design cx est alors défini par l’ensemble complet de

solutions réalisables suite à l’application d’un mouvement. Malheureusement, la taille de

cVG x augmente rapidement avec le nombre de points de livraison et le nombre de

localisations potentielles. Il devient alors trop demandant en terme de temps de calcul d’accéder à

toutes les solutions potentielles comprises dans cVG x . Nous allons donc restreindre la

recherche d’un meilleur design aux seuls mouvements d’ouverture, de fermeture et de


26

remplacement d’entrepôts un à un. Cette recherche est également combinée à une réaffectation

sommaire des points de livraison basée sur la maximisation du revenu unitaire.

De plus, il est possible d’éliminer les mouvements qui ne présentent à prime abord que peu

de chance de succès puisqu’ils impliquent des entrepôts très éloignés ou que ces derniers se

trouvent dans des régions non connexes. La structure de recherche dans les régions influentes

inspirée par Nagy et Salhi (1996 a) nous permet d’y arriver. Cette méthode procède à un

changement de design qui ne considère que les mouvements d’entrepôts adjacents. En fait, pour

que deux entrepôts soit considérés adjacents ou voisins, il doit y avoir un client p pour lequel les

entrepôts en question constituent les deux meilleurs choix d’affectation en regard du revenu

unitaire qu’ils procurent. Nous utilisons l pour dénoter l’ensemble de tous les entrepôts

voisins de l’entrepôt l . Donc, pour chaque entrepôt ouvert cl L , nous définissons la région

l formée de l’entrepôt l , de tous les entrepôts voisins compris dans l ainsi que de tous

les points de livraison c clP l l l L ' , '

affectés à ces entrepôts. La recherche d’un

meilleur design par l’algorithme dépend des mouvements possibles dans chacune de ces régions,

celles‐ci étant aussi nombreuses que le nombre d’entrepôts ouverts. De plus, il sera permis

comme décrit ci‐dessus, d’effectuer seulement trois types de mouvements à l’intérieur de chaque

région. Il devient alors plus judicieux de ne considérer qu'une partie restreinte du Voisinage

Général cVG x des solutions. De ce fait, le Voisinage Restreint c cVR VGx x limite la

recherche au sous‐ensemble ( ) cl M , cl L de mouvements possibles. Il s’agit donc pour

une région l donnée de considérer les mouvements autorisés suivants :

Mouvement FERMER ( fermer ( )m l ):

Si cl L , l’entrepôt l est fermé et chaque point de livraison p l P est affecté à

l’entrepôt ' ','arg max c

pp p l l pl l L

l u v w

Mouvement OUVRIR ( ouvrir ( )l ):

Si cl L , pour tous les entrepôts cl l L , l’entrepôt l est ouvert et chaque

point de livraison p l P est affecté à l’entrepôt

'' '',''arg max c

pp p l l pl l L l

l u v w

.


27

Mouvement REMPLACER ( remplacer ( )l ):

Si cl L , pour tous les entrepôts cl l L , l’entrepôt l est ouvert et,

simultanément, l’entrepôt l est fermé. Chaque point de livraison p l P est affecté à

l’entrepôt '' '',''

arg max cp

p p l l pl l L ll u v w

.

Dans ce qui suit, nous utilisons l’ensemble de mouvements possibles présenté ci‐dessous:

fermer fermer ( ) cl Lm l

, ouvrir ouvrir ( )cl L

l

, remplacer remplacer ( )cl Ll

fermer ouvrir remplacer , fermer ouvrir remplacer( ) ( ) ( ) ( )l m l l l

Remarquons que seuls les mouvements permettant d’obtenir une solution réalisable peuvent être

considérés. Par exemple, si un mouvement FERMER fait en sorte qu’un point de livraison soit isolé

et se trouve trop loin de tout autre entrepôt, empêchant ce dernier de respecter la contrainte de

service, ce mouvement ne peut pas être considéré. Aussi, durant l’exploration dans le voisinage,

les mouvements appartenant à sont évalués seulement s’ils ne se trouvent pas dans la liste

des mouvements tabous.

3.2.2. Évaluation approximative du coût des routes

Afin d’évaluer la valeur estimée du design m cVRx x , nous devons appliquer l’heuristique

Transport pour l’ensemble des scénarios Monte Carlo compris dans l’échantillon n . Ceci

implique, pour chacun des mouvements évalués, la construction de plusieurs routes en

provenance de tous les entrepôts cl l L pour chaque période t de chacun des scénarios

n et puis le calcul de ( )mnR x avec [24]. Évidemment, il devient très lourd et fastidieux d’exécuter

la procédure Transport pour chaque évaluation d’un design mx . Une fonction d’approximation

sera donc utilisée afin d’augmenter la vitesse d’exécution et faciliter l’évaluation des mouvements

créés. La fonction d’évaluation proposée implique une régression linéaire basée sur l’estimation

de la longueur des routes construites (introduite par Daganzo (1984) et repris par Nagy et Salhi

(1996b)). Celle‐ci est quelque peu modifiée afin de tenir compte, entre autres, de la particularité

touchant le mode de transport LTL. En fait, elle estime le coût total de transport ( )mStOpltltC P

de l’entrepôt l

à la période t sous le scénario en fonction de l’ensemble des clients ( )m

ltP qui


28

sont couverts par les routes du design mx . La fonction est ainsi obtenue à l’aide d’un modèle de

régression multiple impliquant trois variables explicatives : i) la variable associée au trajet

direct ( ( )) /mltl lP NS , où ( )l P est la somme des distances de l’entrepôt l vers tous les

points de demande p P , et lNS est le nombre moyen d’arrêts sur les routes de l’entrepôt l ; ii)

la variable associée au détour ( ( )) / | ( ) | m mlt ltl P P ; et iii) la variable associée au LTL

( ( ))mLTLltl l P , où ( )l P est la somme de la statistique distances‐poids de l’entrepôt l vers

tous les points de demande p P , et LTLl est la proportion des distances‐poids de l’entrepôt l

affectées à des routes LTL. Ceci nous amène donc à formuler l’approximation suivante:

1 2 3

ˆ ( ) ( )

ˆ ˆ ˆ

m mStOp StOplt ltlt lt

m mlt ltl l mLTL

ltl lm

llt

C P C P

P PP

NS P

[25]

où 1̂ , 2̂ et 3̂ sont des coefficients de régression estimés en utilisant un historique de routes

périodiques de livraison. Ils peuvent également être calculés à partir d’échantillons de routes

construites par la procédure Transport pour différents réseaux logistiques. Les paramètres lNS et

LTLl sont initialement estimés avec le même échantillon de routes et sont mis à jour à chaque

fois que la procédure Transport est utilisée pour évaluer un nouveau design. Une approximation

adéquate de ( )mnR x est ensuite obtenue en remplaçant ˆ ( )mStOp

ltltC P dans [23] par

( )mStOpltltC P , et en la substituant dans [24], afin d’obtenir:

m FTL

pltlt

m mStOp FTL StOplt ltlt p l pt k kt lt

k Kp P

R P u v d w y C P

[26]

1( ) m mn

mm StOpltn lt ll L t T l L

R R P An

x [27]


29

3.2.3. Exploration restreinte des solutions

Trois stratégies différentes sont proposées afin d’explorer le voisinage restreint ( )cVR x de la

solution courante cx . Ces stratégies diffèrent essentiellement au niveau de la séquence des

mouvements possibles durant chacune des itérations de l’heuristique. En effet, les trois stratégies

identifient à quel moment il sera permis de procéder à un mouvement FERMER, OUVRIR ou

REMPLACER. Voici les principales caractéristiques de chacune de ces stratégies.

Stratégie 1

La première stratégie présentée part d’un design initial obtenu en affectant chaque point de

demande à l’entrepôt potentiel menant au plus grand revenu unitaire marginal. Cette façon de

procéder mène à une solution initiale qui tend à ouvrir un grand nombre d’entrepôts. En fait,

chaque entrepôt avantageant au moins un client lorsqu’il le sert à l’aide d’une route directe sera

ouvert dans cette solution. Ensuite, afin de visiter les solutions voisines d’itérations en itérations,

cette stratégie autorise tous les mouvements possibles. On évalue ensuite chaque solution

mx obtenue suite à un mouvement m l , pour chaque entrepôt cl l L . La

meilleure solution mx devient la nouvelle solution cx de l’itération. Nous verrons à la section

3.2.4 que la solution mx est construite en ajoutant une phase de raffinement influençant la nature

des affectations suite à l’application d’un mouvement. De même, l’évolution des autorisations ou

non de certains mouvements est décrite dans la section se rapportant aux listes taboues. Ces listes

déterminent essentiellement le caractère tabou ou non de certains mouvements tout dépendant

du type d’ouverture ou de fermeture qu’ils impliquent. Cette stratégie s’inspire de la recherche

Tabou proposée par Salhi et Nagy (1996a) pour un problème déterministe de localisation‐routage.


30

Stratégie 2

La stratégie 2, quant à elle, débute par la construction d’un design initial avec un minimum

d’entrepôts. Une heuristique rapide de couverture est utilisée dans le but d’obtenir un nombre

restreint d’ouvertures, permettant de desservir chacun des clients du réseau. Cette solution

initiale contraste avec celle de la stratégie 1 en favorisant les mouvements OUVRIR au cours des

premières itérations. Comme les deux stratégies ont des designs de départ extrêmes et opposés, il

sera intéressant de voir avec quelle rapidité chacune d’elles atteindra leurs meilleures solutions.

En fait, la stratégie 2 constitue une extension de la méthode des trois phases proposée par Kuehn

et Hamburger (1963) pour résoudre le problème déterministe de « localisation‐affectation ». Ainsi,

pour chacune des phases de l’heuristique, un seul type de mouvement est possible. La première

phase utilise seulement des mouvements OUVRIR et s’arrête lorsqu’un certain nombre

d’ouvertures qui détériorent la solution est observé. Ensuite, à partir de la meilleure solution de

cette phase, seuls des mouvements FERMER sont effectués. Puis, lorsque le niveau d’ouverture se

stabilise, la troisième phase de l’heuristique se concentre exclusivement sur des mouvements

REMPLACER. Il est à noter que la notion de listes et de mouvements tabous n’entre en vigueur que

lors de cette troisième étape. En fait, lorsque les mouvements restent simples et n’impliquent que

des fermetures (Phase 1) ou des ouvertures (Phase 2), il n’est pas nécessaire de gérer les

mouvements tabous. Il en va ainsi sachant que l’heuristique ne risque pas d’ouvrir un entrepôt

ouvert ou de fermer un entrepôt fermé.

Stratégie 3

Cette troisième stratégie commence la recherche à partir de la même solution que la

stratégie 1. Il est clair que cette solution initiale ouvre tous les entrepôts potentiellement

intéressants, laissant fermés ceux qui sont isolés de tout client. Puis, la stratégie est composée

d'une phase principale dédiée aux mouvements FERMER à laquelle s’imbrique une phase

d’exploration réservée aux mouvements REMPLACER. La récursivité de cette heuristique permet

donc d’utiliser une recherche Tabou sur les mouvements REMPLACER entre chaque fermeture

d’entrepôt. Cette phase prend donc en entrée la solution actuelle de la recherche sur les

mouvements FERMER et fait ressortir, s’il existe, le meilleur remplacement à partir de cette


31

solution. Notons que l’exploration des solutions lors de la phase imbriquée peut être vue comme

une intensification dans l’espace de recherche contenant des solutions de même niveau. En

d’autres mots, le nombre de dépôts ouverts reste le même suite à l’appel de la phase réservée aux

mouvements REMPLACER.

Essayons de bien comprendre ce qui se passe lorsque la stratégie 3 est implantée. Dans la

majorité des cas étudiés, la solution 0x utilise tous les entrepôts, c.‐à.‐d. : 0L L . Ceci est

d’autant plus vrai lorsque les sites potentiels des entrepôts se trouvent dans des régions

regroupant plusieurs clients. Puis, la recherche principale évalue, en tout premier lieu, les L

fermetures possibles d’entrepôts déjà ouverts. La meilleure des solutions réalisables mx * , est alors

conservée pour l’amorce de la phase d’intensification. Cette phase essaie de remplacer un des

entrepôts encore ouverts par l’entrepôt précédemment fermé. Ce qui consiste en fait à revisiter le

même ensemble d’ouvertures testées dans la 1ère itération de la phase principale. Cependant, le

fait d’avoir implanté un mouvement FERMER et d’avoir réaffecté l’ensemble des points de

livraison de la région fait en sorte que les solutions générées dans la 2e phase peuvent être

passablement différentes. En fait, il se peut que le seul moyen de fermer un entrepôt l donné ne

soit que par l’implantation d’un mouvement REMPLACER possible seulement dans la phase

d’intensification. On peut donc voir comment cette étape récursive permet d’améliorer les

solutions connues. Normalement, la phase d’intensification devrait être plus performante lorsque

le nombre d’entrepôts ouverts est faible puisque, dans ce cas, le nombre de mouvements

REMPLACER augmente. Finalement, en ce qui a trait à la gestion des listes taboues, celles‐ci sont

propres à chacune des phases d’intensification. Ces phases doivent être vues comme des

processus autonomes utilisant des solutions mx * différentes et un voisinage également distinct.

3.2.4. Méthode de réaffectation des clients

La présente section s’intéresse à la procédure de réaffectation des clients. Celle‐ci se présente

comme une étape de raffinement permettant aux affectations plus ou moins rentables d’être

ajustées. En effet, bien que chaque solution visitée soit construite en incluant une procédure

d’affectation de base, rien ne nous laisse présager que les affectations ainsi obtenues ne peuvent

pas être améliorées. Afin d’obtenir une nouvelle solution cx , nous avons élaboré une procédure


32

de réaffectation des points de livraison jugés critiques. Cette procédure s’inspire directement de

l’heuristique proposée par Zainuddin et Salhi (2007) dans le but de résoudre le problème avec

capacité de Weber. Plus précisément, un point p affecté à l’entrepôt ml L (soit mlP ), est

considéré critique si sa distance avec l’entrepôt l excède une certaine cible maxm prédéfinie,

donc si l pm m max, . Définissons comme étant l’ensemble des points de livraison critiques.

Ainsi, le point de livraison mlp P est transféré de l’entrepôt l à l’entrepôt m

ppl L

seulement dans le cas où le ratio de ses distances ( , ) ( , )p pl l p l pm m constitue le moins élevé

des ratios calculés sur l’ensemble des entrepôts éligibles. Un tel ratio ne doit cependant pas

dépasser la valeur maximale max fixée à priori. Lorsque cette étape est exécutée pour tous les

points de livraison critiques p compris dans xm , un nouveau vecteur de solution x en

résulte. Enfin, plusieurs vecteurs de solution alternatifs x peuvent être générés en considérant

un ensemble max de valeurs max . Ces solutions peuvent ensuite être évaluées avec [27] dans le

but de déterminer si une des réaffectations trouvées constitue une meilleure option que la

solution actuelle. Cette discussion nous mène donc à la définition de la procédure Réaffecter

présentée à la Figure 3.3 et appliquée aux trois stratégies.

max max; ; cnm R Réaffecter x x x, ,

1 Définir x xc et calculer xnR avec [27]

2) Construire l’ensemble des points critiques

3) Pour chaque max max faire

x xm Pour chaque p faire

a) ( , ) ( , ) max ,arg min , 0, 1 m

pp

m mp l l p l p l lp l pl L

l m m x x

b) Calculer mnR x avec [27]

c) Si ( x x mn nR R ), alors

x xm et x x mn nR R

Figure 3.3 – Procédure Réaffecter


33

3.2.5. Organisation des listes taboues

Tout au long de la procédure de recherche, deux listes taboues de taille variable sont utilisées

dans le but de traiter adéquatement chacun des mouvements exécutés. Plus précisément,

lorsqu’un entrepôt l est ouvert ou fermé pour former une nouvelle solution, l est inséré dans la

liste taboue 1 . Cette liste 1 , telle que définie ici, inclut tous les entrepôts ne pouvant être

ouverts lors du prochain mouvement OUVRIR ou fermés lors du prochain mouvement FERMER.

D’autre part, lorsqu’une nouvelle solution est obtenue suite à un mouvement REMPLACER de deux

entrepôts l et 'l , la paire ( l , 'l ) est insérée dans la liste taboue 2 . Ceci implique donc qu’il est

interdit pour la prochaine itération de procéder à un mouvement REMPLACER impliquant les deux

entrepôts l et 'l en question. Soulignons que lorsqu’un mouvement simple de fermeture ou

d’ouverture implique l’entrepôt l , celui‐ci devient tabou à ouvrir ou à fermer peu importe le type

de mouvement pouvant le mettre en cause. Ainsi, lorsqu’un entrepôt l est inséré dans la liste 1 ,

chaque paire ( l , 'l ) est également répertoriée dans la liste 2 . Cette subtilité évite à la recherche,

comme ce serait le cas dans la stratégie 1, de revenir plusieurs fois sur les mêmes solutions en se

servant d’un mouvement REMPLACER qui implique un entrepôt récemment ouvert ou fermé.

Également, comme le nombre maximal d’éléments admissibles dans les listes 1 et 2 est géré de

façon indépendante, le caractère tabou n’est assujetti qu’aux mouvements et non pas aux

entrepôts. Par exemple, le fait qu’un entrepôt l soit libéré de la liste 1 n’implique donc pas que

chaque mouvement associé à l soit libéré dans 2 . En ce qui a trait aux mesures de remise en

disponibilité des mouvements, celles‐ci font intervenir la longueur variable des deux listes. Cette

longueur correspond, en fait, au nombre de mouvements maximum pouvant se retrouver dans

chacune des listes pour une itération en particulier. Suite à l’insertion du mouvement dans la liste

taboue correspondante, la longueur de la liste 1 ou 2 est modifiée à chaque itération. S’il s’agit

d’un mouvement d’ouverture ou de fermeture, la longueur ou la taille de 1 est générée

aléatoirement dans l’intervalle 1[ 2 2] | | ,| |L L . Par contre, en ce qui a trait au mouvement

d’échange, la taille de la liste 2 est plutôt générée aléatoirement dans l’intervalle

2[ 2 ] | |, | |L L afin de refléter le nombre beaucoup plus élevé de ce type de mouvements. Quant

à elles, les valeurs 1 2 0 1 , , constituent des paramètres fixes et prédéterminés. Advenant le

cas où les nouvelles tailles de listes devenaient moindres que le nombre d’éléments s’y trouvant,

les éléments libérés sont ceux dont l’entrée dans cette liste précède celle des autres éléments.


34

Cette procédure très connue est communément appelée la règle du « premier arrivé‐premier

sorti ».

3.3. Algorithmes d’initialisation et de recherche Tabou

Avant de commencer, la recherche Tabou doit compléter le processus d’initialisation

permettant, entre autres, de construire une solution initiale réalisable. Il est également nécessaire

d’initialiser certaines variables essentielles à l’évolution de la recherche. Ainsi, outre les variables

précédemment identifiées, les deux paramètres suivants doivent être définis :

MI = Nombre maximal d’itérations de la phase.

MNI = Nombre maximal d’itérations n’améliorant pas la meilleure solution de la phase.

Il s’agit en fait des critères qui mènent à un nouveau départ ou à l’arrêt de la procédure de

recherche. Ces critères d’arrêt peuvent très bien être vus comme une limite sur le temps

d’exécution. C’est sur cette base que se fait la comparaison des temps d’exécution des différentes

stratégies. Ainsi, on comptabilise les temps pour atteindre une première fois la meilleure solution,

plutôt que le temps total de complétion de toutes les itérations. De plus, un ensemble de n

scénarios de demande ( )=[ ( )] , npt p P t Td d , y est généré en utilisant la procédure

MonteCarlo n fois. La méthode de génération privilégiée consiste à obtenir les périodes et les

quantités de commande à priori plutôt que de les générer au fur et à mesure qu’une évaluation

est nécessaire. Cette façon de procéder permet d’améliorer les performances de recherche en

requérant, par contre, davantage de support de la part des structures de données. Ceci s’explique

par la possibilité de se référer en tout temps à l’ensemble des périodes de demande générées.

Chaque solution est donc évaluée avec le même ensemble de scénarios assurant une certaine

stabilité et une meilleure mesure de comparaison. Puis, on doit construire, à même cette phase

d’initialisation de la recherche, la structure de voisinage des entrepôts

l , l L .

En ce qui a trait à la construction des solutions initiales permettant la recherche dans le

voisinage, celle‐ci comprend deux approches qui diffèrent selon la stratégie de recherche utilisée.

La première approche est l’heuristique de couverture minimum utilisée avec la deuxième stratégie


35

de recherche. Dans ce cas, une solution initiale 0x est obtenue en ouvrant séquentiellement les

entrepôts fermés l L qui maximisent les revenus marginaux nets. Ces revenus marginaux sont

calculés lorsque l’entrepôt sert les points de livraison P n’ayant pas encore été affectés à aucun

autre entrepôt. Plus spécifiquement, le meilleur entrepôt pour le plus de clients est ouvert et

chacun de ses points de livraison lui est affecté. Ensuite, les meilleurs entrepôts restants sont

ouverts de façon séquentielle jusqu’à la couverture complète de tous les clients. En ce qui

concerne les stratégies 1 et 3, l’ensemble des entrepôts ouverts 0L correspond initialement à

l’ensemble des entrepôts potentiels L . Ensuite, les missions des entrepôts sont obtenues en

affectant chaque point de livraison p P à l’entrepôt p pl L qui maximise le revenu net

unitaire. Advenant le cas où aucun point de demande n’était affecté à l’entrepôt 0l L , celui‐ci se

retrouverait sans mission et serait automatiquement fermé dans la solution 0x . La figure 3.4 ci‐

dessous présente la procédure Initialiser telle que définie précédemment.

1 2 max maxStratégie;; , , , , , , ,( ( ), ),( , ), , ( )n o onn m MI MNI l l L R Initialiser d x x, , ,

1) Initialiser les paramètres de l’heuristique 1 2 max max( , , , , ) , , , , ,n m MI MNI

2) Pour chaquen , faire ( (.) (.) ) ( )q o

p p ptF F p P T d p P t T MonteCarlo , , , ; , ,

3) Obtenir l’ensemble des voisins l , l L

4) Si Stratégie = 2, alors

Définir 0L , P P

Tant que P , faire

0arg maxl

p l l pl L p P Pl u v w

,'

Définir a) 0 0L L l '

b) ' 'l lP P P

c) '\ lP P P

Sinon : Définir 0 L L

5) Construire le design initial xo en affectant chaque point de livraison p P à l’entrepôt

0 ,arg max

pp p l l pl L

l u v w

et en fermant tous les entrepôts 0l L tel que lP

6) Pour chaque ( , , ) o nl t L T , faire

( ( )) ( ) ( ); ; ( )o oFTL StOplt ltk plt pt ltb k K d p P R P Transport ˆ, , , , ,

7) Calculer la valeur espérée o

nR x avec [24]

Figure 3.4 – Procédure Initialiser


36

Regardons maintenant la procédure de recherche Tabou proposée telle qu'elle apparaît à la

figure 3.5 ci‐dessous. Les itérations de cet algorithme sont contrôlées par deux paramètres : iter

correspondant au nombre d’itérations totales et iter_ni représentant le nombre d’itérations sans

amélioration. L’étape E2 examine les différents mouvements possibles à l’intérieur du voisinage de

la solution courante cx tandis que l’étape E3 y applique la procédure de réaffectation des clients.

En ce qui a trait à l’étape E4, elle évalue le meilleur mouvement et met à jour les paramètres

nécessaires à la fonction d’estimation des coûts de transport. Après avoir procédé à la gestion des

listes taboues lors de l’étape E5, l’étape E6, généralement réservée à la stratégie 3, enclenche une

phase d’intensification. Cette phase permet d'exécuter une série de mouvements REMPLACER

inclus à travers chaque mouvement FERMER de l’appel de base. Le choix de cette étape est régi

par la valeur 1 ou 0 du paramètre d’entrée améliorer. Puis, l’étape E7 vérifie si la solution courante

cx améliore la meilleure solution x* connue jusqu’à maintenant. Finalement, les étapes E8 et E9

permettent de contrôler les itérations de l’algorithme. L’exploration se poursuit alors à partir de

E2 tout en conservant la solution courante cx et ce, aussi longtemps qu’il faut pour atteindre l’une

ou l’autre des conditions d'arrêt. Dans le cas contraire et advenant que MNI itérations sans

amélioration soient observées, l’exploration repartira de E1 en conservant la meilleure solution

connue x* . Dans tout autre cas, lorsque MI itérations totales seront exécutées, l’algorithme

s’arrête. Il est important de mentionner que pour en simplifier l'écriture, nous avons réutilisé les

paramètres MI et MNI lors de l’appel récursif de la procédure Tabou. Néanmoins, au moment de

l’implantation, les critères d'arrêt utilisés à l’étape E6 ne sont pas les mêmes qu’à l’intérieur de la

procédure principale. Cet aspect technique permet de tenir compte de l’ampleur beaucoup plus

grande de mouvements REMPLACER que de mouvements FERMER.


37

( ) ; ; o on nR MI MNI améliorer RTabou x x x x* *, , , , ,

E0: 1) Définir * ox x et x xon nR R* et initialiser les listes taboues ( 1 et 2 )

E1: 1) Définir *c x x et *cn nR Rx x

E2: 1) 0xnR

2) Pour tout cl L , faire

Construire la région l

Pour tout ( )m l l et m l non tabou, faire

Définir x xm c m l et calculer xmnR avec [27]

Si ( x xmn nR R ), alors

x xm et x xmn nR R

3) c x x

E3: 1) max max; ; cnm R Réaffecter x x x, , et définir c x x

E4: 1) Pour tout ( , , ) c nl t L T , faire

( ( )) ( ) ( ); ; ( )c cFTL StOp

lt ltk plt pt ltb k K d p P R P Transport ˆ, , , , ,

2) Calculer la valeur estimée cnR x avec [24]

3) Mettre à jour les moyennes lNS et , LTL cl l L , suite à la construction de

nouvelles routes de transport.

E5: 1) Mettre à jour les listes taboues ( 1 et 2 )

E6: 1) Si (améliorer=1), alors

a) remplacer( ) ; 0; c cn nR MI MNI R Tabou x x x x, , , , ,

b) c x x et cn nR R x x

E7: 1) Si ( *cn nR Rx x ), alors

=* cx x , =* cn nR Rx x et iter_ni = 0.

Sinon, iter_ni = iter_ni + 1

E8: 1) iter = iter + 1

E9: 1) Si (iter < MI) et (iter_ni < MNI), alors

aller à E2.

Sinon, si (iter < MI), alors

Iter_ni=0 et aller à E1. Sinon, arrêter

Figure 3.5 – Procédure Tabou


38

Voici l’implantation des stratégies d’exploration dans le voisinage considérées lorsqu’on

utilise les procédures Initialiser et Tabou précédemment décrites :

Stratégie 1:

1 2 max max1;; , , , , , , , , , ,( ( ), ),( , ), , ( )n o onn m MI MNI l l L R Initialiser d x x

( ) ; 0; o on nR MI MNI RTabou x x x x* *, , , , ,

Stratégie 2:

1 2 max max2;; , , , , , , , , , ,( ( ), ),( , ), , ( )n o onn m MI MNI l l L R Initialiser d x x

ouvrir( ) ; 0; o o ouvrir ouvrirn nR MI MNI RTabou x x x x, , , , ,

fermer( ) ; 0; ouvrir ouvrir fermer fermern nR MI MNI RTabou x x x x, , , , ,

remplacer( ) ; 0; fermer fermern nR MI MNI RTabou x x x x* *, , , , ,

Stratégie 3:

1 2 max max3;; , , , , , , , , ,( ( ), ),( ), , ( )n o onn m MI MNI l l L R Initialiser d x x, ,

fermer( ) ; 1; o on nR MI MNI RTabou x x x x* *, , , , ,

Le guide d’utilisateur de l’application informatique développée pour implanter les heuristiques se

trouve à l’Annexe 1.

Chapitre 4

Évaluation de l’approche

Dans le but de comparer la performance des différentes stratégies et d’en vérifier leur

comportement, certains problèmes types ont été considérés. Ces problèmes ont été construits et

identifiés selon des critères précis représentant les variétés possibles de situations réelles du

réseau logistique. Afin de résoudre le problème stochastique de localisation‐transport étudié, les

divers cas testés ont été générés en considérant quatre dimensions distinctes. Il s’agit de la taille

du réseau logistique, des structures de coût, des caractéristiques associées aux clients et du

processus de demande. De façon aléatoire, chacun de ceux‐ci a été créé en respectant un cadre

réaliste provenant partiellement du cas Usemore documenté dans Ballou (1992). Ce cadre permet

de considérer une étendue plus ou moins restreinte de valeurs pour chacun des paramètres. Plus

précisément, le réseau logistique s’étend sur différentes régions couvrant l’Est et le Midwest des

États‐Unis. Chacune des distances à parcourir afin de relier les différents points du réseau ont été

calculées au moyen de l’outil PC*MILER (www.alk.com). Cet outil prend en considération des

véhicules parcourant le plus court trajet sur les routes actuelles du territoire américain. De plus,

on utilise pour chaque cas une distribution exponentielle des temps inter‐arrivées des commandes

http://www.alk.com/�

Chapitre 4 : Évaluation de l’approche 40

avec une moyenne . La taille des commandes suit, quant à elle, la distribution log‐normale de

moyenne et d’écart‐type . Ces distributions permettent de construire les scénarios

nécessaires à l’évaluation des différentes solutions. Ces scénarios respectent le nombre de

périodes indépendantes qui composent l’horizon de planification T . Ce nombre est fixé à 200, ce

qui représente le cours d’une année. À ce sujet, l’annexe 2 présente six tableaux qui permettent

de vérifier la qualité du processus de génération des tailles de commandes et des temps inter‐

arrivées. On peut y remarquer la bonne correspondance de la loi log‐normale sur un échantillon

de 10 000 commandes générées pour différents points de livraison. De même, l’ensemble des

temps obtenus s’ajuste de façon presque parfaite à la loi exponentielle. Les statistiques ,

et des échantillons de comparaison sont aussi très près des paramètres théoriques de ces

mêmes distributions.

4.1. Taille du réseau logistique

Chacun des problèmes élaborés présente des caractéristiques propres concernant l’étendue

du territoire couvert par le réseau. Trois tailles de réseau sont considérées : les problèmes de

petite taille (P1), de taille moyenne (P2) et de grande taille (P3). Dans chaque cas, la taille des

problèmes varie en termes du nombre d’entrepôts et du nombre de points de livraison. La région

géographique occupée par le problème permet également de jouer avec la densité de celui‐ci. Un

problème sera jugé plus dense si pour une même région géographique, un plus grand nombre de

localisations est considéré. De plus, les problèmes construits permettent de refléter les

particularités industrielles où le nombre de clients est beaucoup plus élevé que le nombre

d’entrepôts potentiels. Ainsi, le nombre de ces entrepôts potentiels est sélectionné aléatoirement

dans l’intervalle : 2% ;3,5%P P . La table 4.1 présentée ci‐dessous dresse le portrait des cas

générés.


Problèmes Étendue géographique Nombre

d’entrepôts Nombre de points

de livraison

P1 États centraux du Nord‐est des É‐U 7 206

P2 États de l’Est et du Midwest des É‐U 15 706

P3 États de l’Est et du Midwest des É‐U 28 1206

Table 4.1 – Tailles des problèmes analysés

Il est intéressant de remarquer le rapport entre le nombre d’entrepôts et le nombre de points

de livraison pour chacune des tailles des problèmes. En fait, pour ce qui est de P1, on retrouve 3,4

entrepôts pour 100 points de livraison, alors que pour P2, le rapport passe à 2,1% et pour P3, à

2,3%. Il est donc possible d’évaluer l’impact de ces différents rapports sur plusieurs aspects : le

nombre d’entrepôts ouverts, le nombre de clients affectés à ces entrepôts ainsi que la longueur

des routes construites. Zainuddin et Salhi (2007) et Daganzo (1984) construisent un réseau

aléatoire contenant n points générés dans un espace de longueur et de largeur définies. Dans le

cas de Zainuddin et Salhi, chaque point est appelé à devenir soit un centre de distribution, soit un

point de livraison. Cette distinction permet de considérer simultanément un regroupement de

points de livraison et l'affectation de ces derniers à plusieurs sites d'entreposage potentiels. Ces

problèmes virtuels sont généralement associés à des cas où les coûts de transport sont affectés à

des arcs directs plutôt qu'à des routes. Cependant, dans le cas qui nous concerne, le problème est

constitué d'emplacements réels et les distances qui les séparent constituent non pas des distances

directes mais des routes parcourues par les véhicules. De plus, les sites de production, de livraison

et d'entreposage sont identifiés à priori éliminant ainsi la décision quant à la nature d'un

emplacement. Ainsi, en prenant comme point de départ le réseau agrégé du cas Usemore, la

majorité des grandes villes de tout l'Est des États‐Unis ont été incluses. Afin de faire varier la

densité des différents problèmes, certaines villes se trouvant dans de grandes régions

métropolitaines, contenant habituellement un ou deux entrepôts, ont été préférées à d'autres

(c'est le cas, par exemple, du problème P1). Tandis que pour d'autres problèmes, les localisations

se dispersent davantage sur l'ensemble du territoire. Nous pouvons constater l’allure des cas

construits dans les figures 4.1, 4.2 et 4.3 suivantes. Ces cartes montrent les points de livraison en

jaune et les entrepôts potentiels en blanc pour chacune des tailles de problèmes traitées.


Figure 4.1 – Carte du réseau de P1 Figure 4.2 – Carte du réseau de P2

Figure 4.3 – Carte du réseau de P3

Si on se réfère au « Guide de l’utilisateur » à l’Annexe 1, on remarque une section complète

sur la génération des problèmes. Il a donc été possible d’étudier au préalable d’autres structures

de problèmes, que se soit en divisant le réseau par territoire, par état ou par code postal. Par

conséquent, les trois problèmes définis ici représentent des réseaux réalistes, que ce soit en

termes de région ou en termes de nombre de nœuds considérés.

4.2. Structures de coût

De façon à considérer différentes structures de coûts, deux niveaux de coûts fixes et de coûts

variables ont été considérés. Le coût lA lié à l’opération de l’entrepôt l constitue le volet fixe et

est généré dans un intervalle de valeurs élevées (0,23 à 0,24 M$/an) ou de valeurs faibles (0,13 à


0,15 M$/an). De même, les valeurs unitaires lv des produits aux entrepôts l et le prix des

produits pu aux différents lieux de consommation p complètent les structures de coûts

variables. En ce qui a trait à la variable pu , celle‐ci est dépendante du point de livraison p et de ce

fait peut varier d’un client à l’autre. Cependant, bien que l’on utilise différents pu dans la

construction de nos problèmes, ceux‐ci restent identiques pour tous les points du réseau. Cette

combinaison des aspects fixes et variables ainsi que des niveaux de coûts faibles et élevés nous

mènent à quatre cas énumérées a, b, c, d dans la table 4.2 ci‐dessous.

(Structure): [Coût fixe ( lA )]; [Valeur du produit ( lv )]; Prix unitaire ( pu )

; ; l l pA v u Valeur et prix unitaire élevés Valeur et prix unitaire faibles

Coûts d’opération des entrepôts élevés

(a): 230 , 250 ; 19, 21 ; 23K K (b): 230 , 250 ; 9,11 ;13K K

Coûts d’opération des entrepôts faibles

(c): 130 ,150 ; 19, 21 ;23K K (d): 130 ,150 ; 9,11 ;13K K

Table 4.2 – Structures de coût analysées

Prenons un cas particulier situé dans la case a de cette table. On a généré pour chaque

entrepôt, un coût fixe d’opération entre 230 000 $ et 250 000 $. Cette variation permet de se

rapprocher des cas réels où la mise en marche d’un entrepôt est influencée par divers facteurs

régionaux, géographiques ou financiers. Tout en ayant sensiblement la même importance, les

montants annuels à débourser pour garder un entrepôt en fonction peuvent donc changer en

regard à ces facteurs. La table 4.2 montre deux niveaux de coût d’ouverture qui permettent de

modifier leur impact décisionnel. En fait, ces coûts pourraient arriver à engloutir tout autre coût

du réseau amenant les décisions d’ouverture et de fermeture à n’être dictées que par cette

caractéristique. En ce qui a trait à lv , cette valeur est calculée en additionnant le coût total de

fabrication aux usines (production, approvisionnement), le coût de transport en provenance du

site de production et le coût total de gestion du matériel à l’entrepôt (manutention, frais de

financement en inventaire). Ainsi, on a généré une valeur associée au coût total unitaire de

fabrication et de gestion du matériel à laquelle on a ajouté les frais réels de transport en amont.

Cette valeur se situe entre 19 $ et 21 $ pour le présent exemple. En fait, lv correspond au coût de

revient du produit une fois qu’il se trouve aux différents entrepôts et ce, juste avant qu’il entre

dans une route de livraison. Cette valeur est identique pour tous les produits expédiés par le


même entrepôt à partir du moment où ce dernier est approvisionné par une source unique. Trois

coûts distincts servent donc à identifier l’avantage stratégique des entrepôts et à leur affecter les

différents points de livraison. Il s’agit du coût fixe d’ouverture lA , de la valeur d’un produit à

l’entrepôt lv et du coût de transport kw vers le point de livraison. Enfin, le prix unitaire pu des

produits à chacun des points de livraison est fixé à 23$. L’inclusion du prix unitaire dans les

différents problèmes qui sont évalués permet de faire varier l’importance des revenus par rapport

aux coûts du réseau logistique. Comme le contexte d’affaires met en place le calcul des profits

engendrés par l’exploitation du réseau, le seul fait de minimiser les coûts totaux n’est pas

suffisant. La quantité de produits vendus à un client peut donc influencer son affectation tout

dépendant du rapport plus ou moins élevé entre les revenus nets et les coûts totaux encourus.

4.3. Caractéristiques des clients et de leur demande

Tous les clients du réseau logistique ont des caractéristiques qui leur sont propres et celles‐ci

influencent grandement le déploiement logistique des ressources. En fait, chaque client est

caractérisé par son processus de demande et par la taille moyenne de chacune de ses commandes

ponctuelles. Ainsi, nous identifions trois types de clients : les grands clients qui commandent

généralement de grandes quantités de produits, les clients intermédiaires auxquels on associe des

commandes de taille moyenne et les petits clients ayant une consommation plutôt réduite. Ces

clients, présentés dans la table 4.3 ci‐dessous, requièrent chacun une quantité liée à la taille

moyenne de leurs commandes et ce, à un rythme déterminé par la moyenne des temps

inter‐arrivées. Selon le type de client, ces statistiques sont sélectionnées aléatoirement dans un

intervalle unique pour chacun de ceux‐ci. Prenons le cas d’un grand client. Celui‐ci commande une

quantité dont la moyenne varie entre 480 cwt et 580 cwt à toutes les 2,5 à 4,5 périodes. L’écart‐

type de ses commandes, quant à lui, est fixé à 7% et s’applique à la taille moyenne . En fait,

l’écart‐type nécessaire à la génération des tailles de commandes selon la loi log‐normale se situe

entre 33,6 cwt (480*0,07) et 40,6 cwt (580*0,07).


Caractéristiques des clients et de leurs demandes

Grands Intermédiaires Petits

Réseau de grands clients (RG)

15% 65% 20%

Réseau de petits clients (RP)

10% 30% 60%

(cwt) [480,580] [300,400] [120,220]

(% ) 7% 10% 16%

2 réplications de la structure des demandes (SD1, SD2)

(périodes) [2.5,4.5] [5.5,15.5] [20.5,35.5] Table 4.3 – Processus de demande des clients

Examinons tout d’abord les différentes tailles de commandes définissant autant de types de

clients. Pour ce qui est des grands clients, ceux‐ci achètent en moyenne plus d’un chargement

complet FTL à chaque fois qu’une commande est passée. En réalité, ce ne sont que les quantités

excédentaires qui entreront dans la construction des routes à plusieurs arrêts. Ces quantités

excédentaires se trouvent en moyenne dans l’intervalle [1001, 180] et se rapprochent des

quantités commandées par les petits clients. Ce sont essentiellement ces commandes qui

composent les routes de transport MTL ou LTL. On remarque donc qu’il est très difficile d’inclure

une demande d’un client intermédiaire dans une route avec arrêts multiples puisque la taille de

ses commandes est très près de la capacité maximale sans toutefois l’atteindre. Ces demandes

constitueront la plus grande proportion des routes à un seul arrêt STL. Le fait de faire varier la

proportion des différents clients par rapport à la totalité des points qui composent le réseau

modifie la diversité des routes construites et par le fait même, des coûts de transport. Le réseau

RP favorise les routes avec arrêts multiples ou LTL, tandis que le réseau RG inclut plusieurs envois

directs à chaque période.

La périodicité des commandes influence également l’allure du routage et celle‐ci est

directement reliée à la moyenne des temps inter‐arrivées. On peut constater que ces temps

sont beaucoup plus grands lorsque la quantité moyenne commandée diminue. Ceci permet de

refléter le fait que les clients qui commandent de grande quantité de produits le font plus souvent

et vice‐versa. Deux types de réseaux sont donc générés : les réseaux composés principalement de

grands clients (RG) dans lequel on retrouve 80% de grands clients ou de clients intermédiaires et

1 La quantité minimale pouvant excéder la capacité d’un véhicule est fixée à 100 cwt


les réseaux incluant 60% de petits clients (RP). Également, le réseau RG génère un nombre et des

tailles de commandes beaucoup plus élevés que le réseau RP. À ce propos, la figure 4.4 nous

donne un aperçu de la répartition des types de clients pour le problème P1 avec un réseau de petit

client RP (P=petit, I=intermédiaire, G=grand). Ainsi, le fait de résoudre le PSLT sur l’un ou l’autre de

ces réseaux a des répercussions sur le revenu net espéré.

Figure 4.4 – Exemple de répartition des types de clients

La première colonne de la table 4.3 fait référence à la réplication des structures de demandes

ou des caractéristiques des clients. Il s’agit ici de vérifier la robustesse de l’heuristique et du

modèle en résolvant le problème avec plusieurs instances différentes des paramètres de

demande. Ainsi, pour une même taille de réseau et une même structure de coût, différentes

générations de scénarios de demandes seront analysées. Plus spécifiquement, on génère une

deuxième fois les valeurs et , puis on modifie l’attribution des différents types de clients à

travers le réseau. Cette attribution aléatoire résulte en un problème pour le moins différent du

précédent puisqu’elle permet une variabilité dans la taille et la provenance des demandes.

Finalement, la combinaison des quatre dimensions prises en compte forme un plan d’expérience

comprenant 48 problèmes différents. Leur identification se fait comme suit :

1 2 3, , , , , , , , , , , , 1, 2 .i j k l i P P P j a b c d k RG RP l SD SD

Les trois stratégies de recherche dans le voisinage proposées au chapitre précédant ont été

testées pour chacun de ces 48 problèmes et les résultats numériques obtenus sont présentés au

chapitre 5.

Chapitre 5

Résultats numériques

Mentionnons dès maintenant le support informatique utilisé pour la résolution des

heuristiques développées. L’application informatique a été développée en langage VB.Net 2005 et

les expériences présentées dans ce chapitre ont été exécutées sur une station de travail de 2

gigahertz dit « double‐cœur » avec 3 giga‐octets de mémoire vive. Tout d’abord, une première

section comprend la calibration détaillée des paramètres utilisés par les différentes procédures

communes aux stratégies de recherche. En fait, une série de tests préliminaires a été réalisé sur

plusieurs des 48 problèmes construits pour l’évaluation des heuristiques. On traite également, à ce

stade ci, de la taille des échantillons de scenarios permettant de bien contrôler la stochasticité du

problème. Ensuite, l’analyse exhaustive des performances des trois stratégies de recherche dans le

voisinage est présentée pour la totalité des problèmes du plan d’expérience. De plus, pour huit

problèmes de petite taille P1, l’heuristique est comparée à la solution optimale du modèle AMÉ

[14‐18] obtenue avec CPLEX‐11. Ces tests d’optimalité on été rendus possible par l’utilisation d’un

ensemble prédéterminé regroupant toutes les routes potentielles non dominées par le mode de

Chapitre 5: Résultats numériques 48

transport. Un serveur 64‐bits utilisant un processeur de 2.5 gigahertz Intel XEON et 16 giga‐octets

de mémoire vive a servi pour la résolution du modèle AMÉ.

5.1. Calibration des paramètres

Tel que mentionné, l’approche de résolution utilise plusieurs procédures basées sur un

ensemble de paramètres devant être calibrés à priori. Utilisant plusieurs problèmes de petite (P1),

de moyenne (P2) et quelques fois de grande taille (P3), les trois stratégies ont été exécutées de

façon alternative afin de déterminer les paramètres à utiliser dans leur procédure respective

d’initialisation. À noter que ces paramètres sont fixes d’une stratégie à l’autre et qu’ils

représentent le meilleur compromis entre la vitesse de recherche de l’algorithme et la qualité des

solutions. De tels paramètres touchent trois procédures en particulier soient : la procédure

Transport, la procédure Réaffecter de même que la procédure Tabou. Commençons par la

procédure Transport et ses valeurs , et concernant la perturbation de l’algorithme de

routage CW+. Ce dernier s’inspire directement des études de Girard et al. (2006) à quelques

différences près mentionnées à la section 3.1 précédente. Leurs études détaillent un large éventail

de valeurs pour chacun des trois paramètres obtenant ainsi leurs meilleurs résultats avec des

valeurs variant entre 0,9 et 1,2 pour et entre 1,3 et 1,6 pour . Le tout avec des valeurs de

se rapprochant de 100 itérations mais demandant par contre beaucoup plus de temps de calculs.

La table 5.1 ci‐dessous de même que les figures A‐3.1 et A‐3.2 de l’Annexe 3 donnent le compte

rendu des tests effectués et des valeurs choisies. En ce qui concerne les facteurs de perturbation

ceux‐ci s’apparentent à ceux indiqués dans la littérature. Pour ce qui est du nombre de

réplications, le temps d’exécution est suffisamment plus critique que la détérioration des coûts de

transport.

Paramètres Valeurs testées

Valeurs choisies

[1-50] 10

[0,5-1,5] 1

[1-2] 1,2

Table 5.1 –Calibration des paramètres de la procédure Transport.


Ensuite, bien que la procédure Réaffecter puisse apparaître suite à l’exécution de chacun des

mouvements uniques, celle‐ci sera utilisée lorsque chacun des mouvements m l ont été

évalués et que le meilleur de ceux‐ci a été retenu. En effet deux options sont possibles pour

comparer deux solutions : d’une part, on peut évaluer chacune des deux solutions et appliquer, à

postériori, la procédure Réaffecter à la meilleure d’entre elles; d’autre part, il est possible

d’appliquer, à priori, la procédure Réaffecter aux deux solutions et de ne conserver que la

meilleure. Les expériences pratiques sur divers cas nous indiquent qu’il est plus intéressant sur le

plan de la qualité des solutions de même que sur le plan des temps de calcul de ne retenir que la

première méthode d’utilisation de la procédure. La table 5.2 ci‐dessous fait état des observations

en termes de déviation moyenne par rapport à la valeur de l’objectif et aux temps d’exécution

obtenus sur divers problèmes du plan d’expérience. La procédure Réaffecter utilisée localement

sur ces derniers présente une déviation moyenne de ‐0,1% sur la méthode globale. On y remarque

également les résultats associés à l’utilisation ou non de la procédure. Le pourcentage de

déviation de ‐0,07% témoigne de la détérioration moyenne provoquée par l’absence de la

procédure Réaffecter. De plus, la recherche semble moins bien se comporter lorsque la procédure

n’est pas implantée puisque les temps nécessaires à l’atteinte de la meilleure solution sont plus

élevés de 9,5%. La dernière colonne, quant‐à‐elle montre les changements dans les designs. Les

deux méthodes mènent à des designs différents dans 44% des cas.

Paramètres de réaffectation max 1;0,75;0,5

250m max miles

Méthode Déviation sur

l'objectif Déviation sur le

temps d'exécution Changement

de design

Réaffecter local -0,10% 0,00% 44,44%

Réaffecter inactif -0,07% 9,50% 44,44%

Table 5.2 – Impact de la procédure Réaffecter par rapport à la méthode globale.

Deux autres paramètres nécessaires à la procédure doivent également être fixés avant le

lancement de l’initialisation de la recherche. Il s’agit de l’ensemble max de valeurs max

représentant les ratios limites de réaffectation et du paramètre mmax déterminant la distance

jugée critique dans l’affectation des clients. La table 5.2 ci‐dessus indique le choix des trois valeurs

max retenues ainsi que la distance maximale apportant le plus de résultats significatifs. Notons

que les valeurs testées de mmax se situaient dans l’intervalle [50 miles, 300 miles] et couvraient

ainsi la presque totalité des distances critiques réalistes. De même, plusieurs choix de trois ou


quatre valeurs comprises ente 0 et 1,5 ont servi de ratio maximum de réaffectation. Les tables A‐

3.1 à A‐3.3 de l’annexe 3 présentent le détail des tests effectués sur les différentes implantations

de la procédure Réaffecter.

La recherche Tabou nécessite elle aussi la fixation de certains paramètres de départ. Il en est

ainsi pour les critères d’arrêt MI et MNI, de même que pour les paramètres 1 et 2 agissant sur

la taille des listes taboues. La table 5.3 ci‐dessous donne un aperçu des différentes valeurs qui ont

été testées pour chacun de ces paramètres. La présente analyse s’est effectuée pour chacune des

trois stratégies de recherche appliquées à un problème P0. Ce problème plus réduit a été utilisé

lors d’une phase de pré‐test permettant entre autres de fixer les paramètres de la procédure et

d’étudier la convergence de la recherche. Les cellules en jaune dans cette table indiquent le choix

final des paramètres pour tous les problèmes évalués. Ainsi, le critère d’arrêt est fixé à 100

itérations avec un nouveau départ à toutes les 10 itérations négatives. La taille des listes taboues

comme indiqué à la section 3.2.5, dépend du nombre d’entrepôts L répertoriés dans le réseau et

des paramètres 1 et 2 . Ces derniers auront tous deux la valeur 0,25 ce qui nous donnera des

listes dont la taille variera entre [ 8 2]L L| | ,| | pour 1 et entre [ 4 2 ]L L| | , | | pour 2 .

Table 5.3 – Analyse des paramètres de la procédure Tabou

Le compromis met l’emphase sur la qualité de la solution plutôt que sur les quelques

secondes de différences au niveau du temps d’exécution. Aussi, la combinaison des quatre

paramètres présente des comportements adéquats concernant les cycles possibles de la


recherche. La qualité du comportement de la recherche quant aux retours à d’anciennes solutions

sera abordée plus en détails au cours des sections suivantes.

Il est important d’étudier un autre aspect de la résolution du PSLT soit le nombre de scénarios

ainsi que le nombre de périodes qui doivent être générés afin d’obtenir de bonnes solutions.

Chaque scénario couvre une année, soit 200 jours ouvrables. Une façon de diminuer les temps

nécessaires à la recherche pourrait être de contrôler le nombre de périodes à évaluer. Nonobstant

la variation dans l’espérance du profit qui est répartit annuellement, les solutions restent

comparables même avec des scénarios comportant un nombre plus restreint de périodes. Cette

option de résolution est possible avec le programme « SLTP‐Application » (voir annexe 1). Il est

important de noter que le processus de demande est stationnaire, que le problème de transport

doit être résolu à chaque jour ouvrable pour chaque entrepôt et que l’horizon de planification

inclut 200 jours. Ainsi pour n scénarios, ce sont 200 n problèmes de transport prélevés à partir de

la même distribution de probabilité qui sont évalués pour chaque entrepôt. Pour cette raison, un

nombre relativement petit de scenarios est requis afin d’obtenir de bons résultats. Pour

déterminer la meilleure valeur de n , plusieurs tailles d’échantillon ont été testées et la qualité des

solutions obtenues a été évaluée en utilisant la statistique de l’écart avec la solution optimale.

Cette technique est couramment utilisée lorsque la méthode AMÉ sert à résoudre des

programmes stochastiques. Le problème de petite taille P1 a servit à cette calibration avec un

réseau de grands clients (RG). Le tout en se basant sur la solution optimale du modèle AMÉ [14‐

18] obtenue avec CPLEX‐11. Les différentes valeurs de n qui ont été testées sont 1, 2, 4, 6 et 8,

étant incapable de résoudre de façon optimale des problèmes de plus grande taille sans tronquer

l’ensemble des routes non‐dominées.

Dans le but d’estimer la statistique des écarts avec la solution optimale pour un nombre n de

scénarios, plusieurs résolutions du modèle AMÉ basées sur des échantillons indépendants furent

exécutées. Considérons jnR et 1j

nˆ , j ,...,m,x come étant la valeur de la solution optimale du

modèle AMÉ pour les m résolutions utilisées. Un résultat bien connu en programmation

stochastique est que [ ] *nR R , où [ ] dénote la valeur espérée, nR la valeur optimale de [14]

et *R la valeur optimale de [6]. De plus, 1

m jn,m nj

R R / m

est un estimateur non‐biaisé de

[ ]nR (Shapiro, 2003). Une borne supérieure par rapport à la valeur optimale est ainsi fournie

par *n,mR R . Aussi, la valeur réelle de la fonction objectif ( )j *

nˆR Rx des solutions réalisables

1jnˆ , j ,...,m,x peut être estimée par:


1( ) ( )

n'

j StOp j jn' n n l l n

l L

ˆ ˆ ˆR R , A xn'

x x

[28]

où n ' est un ensemble de n' scenarios générés indépendamment de l’échantillon qui a

été utilisé afin d’obtenir jnx̂ et avec n n' . Une borne inférieure ( )j *

n' nˆR Rx par rapport à la

valeur optimale est ainsi obtenue. Plus particulièrement, si la procédure Transport est utilisée

pour résoudre le programme du niveau opérationnel, la valeur ( , )StOp jnˆR x peut être remplacée

dans [28] par la valeur StOp j StOp jn nR R x xˆ ˆ ˆ, , calculée avec Transport pour obtenir

( ) ( )j jn' n n' n

ˆ ˆ ˆR Rx x . Ensuite, un estimé de l’écart de la solution jnx̂ avec la solution optimale peut

être calculé comme suit : écart ( ) ( )j jn,m,n' n n,m n' n

ˆˆ ˆR R x x . À partir du moment où m résolutions

du modèle AMÉ sont exécutées pour un échantillon de taille n , une estimation de la moyenne des

écarts pour cet échantillon est: 1

écart écart ( )m j

n,n' n,m,n' njˆ / m

x .

Quatre sous‐ensembles différents de scénarios ont été utilisés pour chacune des tailles

d’échantillon analysées. Les designs obtenus avec CPLEX‐11 ont ensuite été évalués avec [28] en

utilisant la procédure Transport et un échantillon de taille 100n ' scénarios. Les écarts moyens

calculés entre le profit espéré des designs obtenus et leur évaluation avec n n' sont présentés

dans la table 5.4. On peut également se référer à la figure A‐3.3 de l’annexe qui présente plus en

détail chacun des écarts observés.

Taille échantillonnale (n )

1 2 4 6 8

Écartn,100 (en %) 2,32% 3,42% 2,21% 0,67% 0,07%

Table 5.4 – Statistiques des écarts moyens par rapport à la solution optimale

Il est donc facile de remarquer que les échantillons de 6 ou 8 scénarios donnent de très bons

résultats. De plus, lorsqu’on analyse les designs trouvés avec ces échantillons, on observe leur

grande similarité: ils ouvrent les mêmes entrepôts et seulement un ou deux points de livraison

sont affectés différemment. Cependant, le temps de recherche augmente considérablement avec

l’ampleur des échantillons. Pour cette raison, nous sommes arrivés à la conclusion que des

échantillons formés de n = 6 scénarios constituent le meilleur compromis à appliquer tout au long

du plan d’expérience. Cela signifie que 1200 problèmes de transport, prélevés de la même

distribution de probabilité, sont résolus par chaque entrepôt lorsqu’un design est évalué.


5.2. Analyse des résultats

Cette section traite de la qualité des réseaux de distribution générés par les trois stratégies de

recherche dans le voisinage proposées. Que ce soit en termes de profit espéré ou de temps

d'exécution, chacun des résultats propres aux stratégies sont rapportés et analysés tout au long

des sections qui suivent. La première section traite plus particulièrement de l'optimalité des

solutions générées et des comparaisons possibles pour le sous‐ensemble de problèmes utilisé.

Une deuxième section s'attarde de façon plus précise à l'analyse des heuristiques développées. Il y

est entre autres question du comportement et de l'efficacité de celles‐ci en regard aux

particularités intrinsèques des différents réseaux testés. Cette section se termine par une analyse

de l'impact sur les procédures utilisées de même que sur la composition des routes construites.

5.2.1. Solutions optimales du modèle AMÉ

La présente section démontre la proximité des solutions obtenues par rapport à l’optimalité.

À cette fin, le modèle AMÉ [14‐18] a été résolu avec CPLEX‐11 pour huit problèmes de P1 en

utilisant une tolérance relative de 0,001 et un échantillon de n = 6 scénarios. Il s’agit des plus

grands problèmes AMÉ que nous ayons pu résoudre de façon optimale. Les résultats de nos trois

stratégies de recherche et ceux obtenus avec CPLEX sont présentés dans la table 5.5. Les valeurs

inscrites dans cette table correspondent à l’estimation de la valeur réelle ( )R x de la fonction

objectif qui est donnée par ( )n'R̂ x avec une taille échantillonnale n' = 100. La dernière ligne

fournie le pourcentage de différence entre les solutions de CPLEX et le meilleure design obtenu

avec nos stratégies de recherche heuristique. De plus, les cellules ombragées permettent de

rapidement cibler les meilleures solutions fournies par les heuristiques. Il est à noter que des

valeurs identiques témoignent de la similarité des designs. On peut donc remarquer que plusieurs

stratégies génèrent le même design et que, pour le cas (b, RP), l’heuristique et CPLEX arrivent à la

même solution. On peut aussi constater que les différences sont visiblement minimes. Par

exemple, pour le problème (b, RG) la solution du design généré par la stratégie 1 est légèrement

meilleure que la solution donnée par CPLEX. Ceci est possible puisque le modèle AMÉ qui est

résolu à l’optimalité avec un échantillon de n = 6 scénarios constitue une approximation en soit.


Pour une certaine taille donnée, notre heuristique peut donc fournir de meilleures solutions du

modèle de programmation stochastique original [6‐13] que ne le fait le modèle AMÉ. Ces résultats

confirment la qualité de l’heuristique de recherche dans le voisinage par rapport aux conditions

d’optimalité fixées. Le fait que de tels résultats soient obtenus pour les problèmes de petite taille

P1 laisse présager une performance raisonnable des stratégies de recherche pour des problèmes

de plus grande taille.

Problème (a, RG) (b, RG) (c, RG) (d, RG) (a, RP) (b, RP) (c, RP) (d, RP)

S1 2 689 489 2 493 083 4 204 796 4 145 389 1 430 919 1 306 351 2 396 894 2 360 981

S2 2 689 162 2 492 898 4 204 796 4 145 389 1 430 919 1 306 142 2 396 894 2 360 981

S3 2 632 805 2 439 453 4 203 591 4 144 280 1 430 919 1 306 142 2 396 894 2 360 981

CPLEX‐11 2 689 481 2 493 069 4 204 851 4 145 394 1 431 210 1 306 351 2 397 181 2 361 277

%‐différence 0,000% ‐0,001% 0,001% 0,000% 0,020% 0,000% 0,012% 0,013%

Table 5.5 – Comparaison avec les solutions de CPLEX‐11 du modèle AMÉ pour P1

Le modèle AMÉ traité inclut 2 501 456 variables binaires pour les réseaux composés de

grands clients (RG). Les solutions sont obtenues en 939 secondes en moyenne par CPLEX‐11. Par

contre, il ne faut que 10 secondes en moyenne pour obtenir la meilleure solution à partir de nos

heuristiques, lorsqu’elles sont exécutées sur une station de travail de 32 bits. Ainsi, pour une

qualité de solutions presque identique, le recours aux heuristiques plutôt qu’a l’évaluation

optimale du modèle AMÉ semble beaucoup plus efficace. Il faut aussi mentionner que la taille

d’échantillon prise pour l’évaluation optimale pourrait être relativement plus grande et améliorer

sensiblement la qualité des solutions obtenues. Encore une fois cela contribuerait à augmenter les

temps d’exécution et l’avantage du processus serait plus difficile à défendre.

5.2.2. Comparaison des heuristiques

Cette section s’intéresse à nos trois stratégies de recherche et à leur comparaison. Celle‐ci

s’effectue pour l’ensemble des 48 problèmes composant le plan d’expérience. La valeur estimée

de la fonction objectif de chacun des designs x construits est obtenue avec ( )n'R̂ x et un

échantillon de 100n ' scénarios. Pour un problème donné, on doit s’assurer que les solutions

générées par les stratégies sont comparées sur des bases communes. Pour ce faire, les 6 scenarios


utilisés dans l’heuristique et les 100 scénarios nécessaires à l’estimation de la valeur des designs

ont été les mêmes pour les trois stratégies de recherche.

Regardons, tout d'abord, le design géographique des réseaux obtenus. La figure 5.1 présente

la carte d'une solution générée pour chacune des tailles de problèmes. Les cercles de plus grande

dimension représentent les entrepôts sélectionnés tandis que les carrés font référence aux sites

potentiels non retenus par la solution. On peut y remarquer l'ouverture respective de 3, 6 et 11

entrepôts pour les trois problèmes. Ces ouvertures représentent 40% du nombre d’entrepôts

potentiels. Ainsi, les entrepôts sélectionnés tendent à se rapprocher l’un de l’autre plus la taille du

problème augmente. En fait, pour un plus grand réseau, les entrepôts répondent à une demande

beaucoup plus important mais qui provient de régions généralement moins vastes. Ainsi, pour

couvrir le même territoire du Nord‐est des États‐Unis, la solution passe de trois entrepôts dans P1

à six entrepôts dans P3 et ce même si les coûts fixes d’ouverture conservent le même ordre de

grandeur. Cette observation est directement reliée à la densité propre à chacun des problèmes de

même qu’à l’importance du routage dans l’évaluation des solutions et la construction des designs.

Par ailleurs, à l’exception de P1 où deux points apparaissent clairement éloignés de leur entrepôt,

le réseau présente une configuration misant sur des affectations concentrées dans des régions

claires et bien délimitées. Le cas de P1 s’explique en partie par la contrainte de service disqualifiant

certain entrepôts à prime à bord. Il est alors intéressant de vérifier le comportement des

recherches et les caractéristiques des solutions pour d’autres structures de coût ou processus de

demande.

La table 5.6 présentée ci‐dessous détaille l'ensemble des statistiques pertinentes pour chacun

des 16 problèmes de petite taille. Les points dans l’appellation des sous‐ensembles de problèmes

servent à signifier l’agrégation des autres caractéristiques qui lui sont associées.


A): (P1,c,RG,SD1)

B): (P2,a,RP,SD1)

(P3,a,RG,SD2)

Figure 5.1 – Exemple de réseaux géographiques pour chacune des tailles de problèmes

Par exemple, (P1,a,.,.) représente le sous‐ensemble formé des quatre problèmes de taille P1

avec la structure de coût a. Les valeurs qui y sont inscrites, quant à elles, indiquent la moyenne

observée sur ces problèmes. Comme le montre cette table, peu de designs comprenant trois

entrepôts ont été générés et il s'agit principalement des solutions obtenues par la stratégie 3 sur

des problèmes où les coûts fixes d'ouverture sont faibles (c, d). Bien que les solutions de cette

stratégie entraînent une augmentation des coûts fixes, celles‐ci diminuent le ratio du nombre de

clients par entrepôt et par le fait même des coûts de transport. Aussi, on peut constater que près

d’une centaine de clients sont affectés par entrepôts et que le nombre d’entrepôts des solutions

est restreint lorsque les commandes des clients sont petites (comme c’est le cas avec RP). Une

autre conclusion frappante est le fait que les différentes structures de demandes ne semblent pas

influencer outre mesure les caractéristiques des solutions. Notons, par contre, qu’en ce qui

Chapitre 5: Résultats numérique

57

concerne les valeurs comme le revenu net, les coûts fixes d’ouverture et les coûts de transport,

celles‐ci changent quelque peu d’une structure à l’autre. Ce constat est plus flagrant pour P1 où les

coûts de transport peuvent varier d’environ 10%. Cependant, ces variations influencent que très

légèrement la valeur des différentes solutions. Ceci témoigne d’une certaine robustesse des

stratégies de recherche qui affichent une faible variation par rapport aux valeurs théoriques des

commandes de même qu’a l’emplacement des divers types de clients.

Table 5.6 – Détail des statistiques obtenues avec P1 pour les trois stratégies

Les tables A‐4.1 et A‐4.2 de l’Annexe 4 présentent ces mêmes statistiques pour l’ensemble

des problèmes de moyenne et de grande taille. On constate que, toutes proportions gardées, les

résultats sont comparables d’une taille de problèmes à l’autre. Plus précisément, le nombre

moyen d’entrepôts ouverts tourne autour de 2,5 pour P1, de 7,5 pour P2 et de 10 pour P3. Ainsi, les

solutions de P3 ouvrent quatre fois plus d’entrepôts que les solutions de P1. Ce rapport est

exactement le même que le rapport entre leur nombre de site potentiels d’entreposage (7 pour P1

et 28 pour P3). En ce qui a trait au nombre d’affectations moyennes par entrepôt, celles‐ci passent

de 92 à 128 en passant par 96 pour P2. Cette donnée semble être stable pour les deux premières

tailles de problèmes et augmente quelque peu pour la troisième. Ceci reflète le fait que la

différence entre le nombre de points de livraison est sensiblement plus grande entre P1 et P3. C’est

donc quatre fois plus d’entrepôts qui tenteront de répondre à la demande de six fois plus de

points de livraison comparativement à seulement trois fois plus de clients entre P1 et P2 . Il est


58

également important de noter que les résultats des stratégies sont sensiblement les mêmes et que

la réflexion entamée plus haut s’applique pour les deux autres régions géographiques traitées.

Ceci étant dit, les différentes stratégies, quoi qu’affichant des résultats et des solutions plutôt

stables, seront quelques fois plus performantes et plus avantageuses dans certains types de

problèmes plutôt que d’autres. À ce sujet, regardons en détail la performance des stratégies par

rapport à la valeur des meilleures solutions obtenues.

La valeur des différentes solutions, représentée par le profit moyen généré par celles‐ci, est

fournie dans la table 5.7 pour différents sous‐ensembles de problèmes. Ces valeurs moyennes ont

été obtenues en évaluant chacun des 48 problèmes du plan d’expérience pour chaque entrepôt

l à chaque période t de chacun des n' = 100 scénarios. La meilleure stratégie de recherche pour

chaque problème est encore une fois identifiée par les cellules mises en surbrillance. On peut

constater que les stratégies 1 et 2 présentent des résultats moyens semblables (surtout pour les

problèmes de P1) et supérieurs à la stratégie 3. En fait, sur les résultats moyens présentés dans

cette table, la stratégie 3 n’obtient aucune fois la meilleure évaluation. La stratégie 1 semble plus

performante pour les problèmes de P1 alors qu’elle est comparable à la stratégie 2 pour ce qui est

des problèmes de P2 et de P3. De plus, il apparaît que la stratégie 1 donne d’excellents résultats

pour les réseaux formés de grands clients tandis que S2 performe davantage pour les problèmes

de grandes tailles constitués de plusieurs petits clients (RP) qui consomment des quantités

réduites de produits. Ceci s’explique, en partie, par l’importance du nombre d’entrepôts ouverts

pour les problèmes P3. Ce qui permet à la stratégie 2 de se démarquer davantage sur les

problèmes (RP) nécessitant l’ouverture d’un nombre plus faible d’entrepôts. Pour ce qui est de la

stratégie 3, elle obtient ses meilleurs résultats pour les petits réseaux composés de petits clients

RP. Aussi, on remarque une différence marquée entre les valeurs des problèmes de moyenne taille

P2 comprenant des coûts variables élevés (a et c). Il peut paraître surprenant que seuls les coûts

fixes d’ouverture donnent une telle différence dans le calcul de la valeur moyenne. En réalité,

étant donné que les coûts variables utilisés entre a et c ne sont pas les mêmes, quoi que générés

dans le même intervalle, une toute petite variation de ceux‐ci entraîne un changement

considérable dans le calcul du revenu net généré. Cependant, cette particularité semble avoir peu

d’impact sur la performance des différentes stratégies.


59

P1 (P1,a,.,.) (P1,b,.,.) (P1,c,.,.) (P1,d,.,.) (P1,.,RG,.) (P1,.,RP,.) (P1,.,.,.)

S1 2 119 638 1 957 886 3 365 995 2 884 254 3 255 870 1 908 016 2 581 943S2 2 119 556 1 957 788 3 365 265 2 883 577 3 255 103 1 907 990 2 581 546S3 2 048 156 1 927 984 3 365 372 2 883 854 3 204 709 1 907 974 2 556 341

P2 (P2, a,.,.) (P2, b,.,.) (P2,c,.,.) (P2,d,.,.) (P2,., RG,.) (P2,., RP,.) (P2,.,.,.)

S1 9 578 586 8 845 539 4 929 752 9 631 837 10 712 395 5 780 462 8 246 428S2 9 521 073 8 836 155 4 930 624 9 633 208 10 677 916 5 782 614 8 230 265S3 9 560 879 8 809 231 4 913 246 9 616 201 10 691 160 5 758 618 8 224 889

P3 (P3, a,.,.) (P3, b,.,.) (P3, c,.,.) (P3,d,.,.) (P3,.,RG,.) (P3,.,RP,.) (P3,.,.,.)

S1 20 752 448 15 848 841 20 142 791 17 554 079 23 447 483 13 701 596 18 574 540S2 20 645 080 15 971 828 20 162 960 17 547 339 23 437 516 13 726 087 18 581 802S3 20 640 702 15 663 930 20 091 728 17 530 314 23 325 136 13 638 200 18 481 668

Table 5.7 – Valeurs moyennes des designs pour chaque type de problèmes.

Des comparaisons plus détaillées de la valeur des designs des trois stratégies sur l’ensemble

du plan d’expérience sont disponibles à la figure 5.2. Les trois premiers graphiques de cette figure

sont dédiés respectivement à P1, P2, et P3. On y montre le % d’écart entre la valeur des designs et

la meilleure solution connue pour chaque problème résolu. Une première observation s’impose

d’elle‐même lorsqu’on regarde les résultats détaillés : si aucune des stratégies n’est à proprement

parlé complètement dominée, il semble cependant que les stratégies de recherche S1 et S2 nous

mènent vers de meilleurs résultats. La stratégie 1 fournie la meilleure solution pour 65% des

problèmes résolus et celles‐ci se situent à moins de 0,5% des meilleures solutions pour 96% des

problèmes. La stratégie 2 donne, elle aussi, des résultats appréciables pour P2 et P3, mais est

relativement dépendante de la qualité de la solution initiale. Elle fournie 52% des meilleures

solutions sur l’ensemble des problèmes générés et est à moins de 0,5% de la meilleure solution

dans 90% des cas. Enfin, la stratégie 3 trouve le meilleur design que pour 27% des problèmes

testés.

Un autre aspect important de la performance des stratégies est le temps d’exécution

nécessaire à l’atteinte de la meilleure solution fournie par l’heuristique. La figure 5.3 ci‐dessous

indique pour chacune des tailles de problèmes le temps d’exécution des huit sous‐ensembles

précédemment traités. Comme mentionné à la section 3.3, les temps comptabilisés sont ceux

nécessaires afin d’atteindre une première fois la meilleure solution et non pas les temps totaux

pour l’ensemble des itérations. À titre indicatif, le rapport entre les temps comptabilisés et le

temps total de recherche est de 47% sur l’ensemble des problèmes étudiés avec des pourcentages

variant de 38% pour P2 à 59% pour P1. C’est donc dire que les temps comptabilisés correspondent

à près de la moitié des temps totaux de recherche.


60

Figure 5.2 – Écart des valeurs des stratégies avec la meilleure solution heuristique obtenue.

Cette figure indique un changement marqué dans la rapidité relative de chacune des

stratégies. En fait, les rangs respectifs des stratégies 1 et 3 sont complètement inversés entre les

problèmes de petite et de grande taille. Le fait, par exemple, que la stratégie 3 ralentisse de plus

en plus à mesure que la taille du problème augmente s’explique par l’ajout de la phase

d’intensification qui fait en sorte que l’ensemble des mouvements possibles augmente de façon

considérable. La stratégie 1, quant à elle, est légèrement influencée par les structures de demande

SD1 et SD2 comparativement aux autres stratégies. Ses temps se situent près de la moyenne pour

les problèmes P2 et P3. Pour ce qui est de la stratégie 2, celle‐ci requiert des temps relativement

courts et s’avère être la stratégie la plus rapide pour les problèmes de moyenne taille P2. Ce

phénomène s’explique par le nombre relativement faible d’entrepôts ouverts qui se rapproche

fréquemment du minimum d’entrepôts requis afin de respecter le niveau de service souhaité. Le

fait, par exemple, d’éliminer la contrainte de service obligeant les clients à être situés à moins de

400 miles de leur entrepôt, pourrait changer passablement l’allure et la performance de la

stratégie 2. Il est donc intéressant d’examiner la rapidité de la convergence de la stratégie vers des


61

solutions comprenant un nombre économique d’entrepôts ouverts et le degré d’amélioration

engendré par la troisième phase de l’heuristique.

Figure 5.3 – Temps d’exécution des stratégies de recherche

À ce sujet, la figure 5.4 fait état de 3 processus de recherche complets pour chacune des

stratégies appliquées à un problème de grande taille P3. On peut y voir chacune des solutions

heuristiques de même que le moment où la meilleure solution a été atteinte. Cette solution est

mise en évidence par un trait noir et continu à l’intérieur de chacune des figures. On peut

constater que le comportement des stratégies 1 et 2 se ressemble à plusieurs niveaux. Ils

stabilisent le niveau d’entrepôts beaucoup plus rapidement et exécutent sensiblement le même

type de mouvement au même moment. Un nombre semblable d’itérations est par le fait même

observé. Les 20 itérations de différence témoignent du temps nécessaire à la stratégie 2 pour


62

réaliser les deux premières phases de la recherche. Lorsque l’heuristique commence, une série de

mouvements OUVRIR détériorent la solution à la différence de la stratégie 1 qui améliore la

fonction objectif en procédant à des fermetures. Ce phénomène est directement relié à la

construction de la solution initiale et à la qualité de celle‐ci. En fait, pour la stratégie 2, il semble

qu’un ou deux entrepôts n’ont pu être ouverts puisque toute la succession des mouvements

REMPLACER s’effectue avec des profits plus bas que la stratégie 1. Cette phase a d’ailleurs

beaucoup de difficultés à améliorer la meilleure solution connue qui a justement été générée vers

l’itération 25 comparative à 85 pour S1. En ce qui a trait à la stratégie 3, celle‐ci est beaucoup plus

riche en termes du nombre de solutions visitées. Elle est aussi beaucoup plus lente puisque

chacune des phases d’intensification retarde l’atteinte du nombre adéquat d’entrepôts ouverts.

Ce nombre est effectivement atteint aux alentours de l’itération 135 ce qui est assez élevé par

rapport aux deux premières stratégies. L’heuristique a générée un total de près de 330 solutions

comparativement à la centaine créées précédemment.

Si on regarde le comportement décrit par le graphique C) de la figure 5.4, on s’aperçoit que la

recherche améliore considérablement les solutions au cours des toutes premières itérations. Ceci

est le reflet de plusieurs fermetures consécutives et de l’importance non négligeable de ces

fermetures sur l’évolution des phases d’intensification. Les mouvements REMPLACER qui

impliquent ces entrepôts limitent la liberté des phases d’amélioration. De plus, la séquence des

solutions visitées semble se répéter plusieurs fois au cours de la recherche. Bien que ces solutions

ne soient pas identiques, un patron est facilement repérable à certains endroits. Ce constat nous

force d’admettre qu’il s’agit de la stratégie la moins stable des trois. De par ce fait et par la nature

de l’heuristique appliquée pour cette recherche, nous pourrions nous demander si les phases

REMPLACER ont permis d’améliorer la meilleure solution connue. La figure 5.5 retrace cet aspect

de la recherche en montrant les meilleures solutions S* de chacune des phases exécutées. Ainsi

pour les 16 phases d'intensification indiquées en bleu sur la figure, cinq de celles‐ci (encerclées)

permettent d'améliorer la solution obtenue par la dernière fermeture (indiquée en rouge). L'étape

récursive permet d’améliorer les solutions connues pour cinq phases d’intensification sur les 16

exécutées ce qui correspond à plus de 30% des appels. Il est à noter que généralement, le meilleur

mouvement REMPLACER est généré au tout début de la phase d'intensification. Ceci témoigne de

la proximité des meilleures solutions et de la qualité des mouvements FERMER.


63

A : Stratégie 1)

B: Stratégie 2)

C : Stratégie 3)

Figure 5.4 – Évolution de la recherche pour (P3‐a‐RG‐SD2)


64

Cependant, on peut facilement remarquer que l’intensification est de plus en plus

performante lorsque le nombre d’entrepôts sélectionnés diminue. En fait, la meilleure solution du

problème de la figure 5.5 comporte sept entrepôts et est obtenue par un mouvement REMPLACER

(dernier point bleu). Le nombre d’entrepôts étant significativement plus faible vers l’itération 150,

on s’aperçoit que les mouvements REMPLACER sont alors plus fréquents. Ceci indique que la

stratégie 3 tend à être plus performante lorsque les entrepôts ouverts sont moins nombreux.

C’est‐à‐dire lorsque la phase d’intensification peut pleinement jouer son rôle. Les cas, comme celui

présenté, où le nombre d’itérations est élevé mènent généralement à des solutions plus

intéressantes.

Figure 5.5 – Comparaison des deux phases de la stratégie 3 pour (P3‐b‐RP‐SD2).

Prenons maintenant le temps d’analyser les divers résultats en rapport aux procédures

utilisées dans la recherche Tabou. On constate que lorsque la densité du problème est faible,

comme c’est le cas pour P1 (voir la figure 5.1 et la table 5.6), le nombre de points de livraison

critiques est plus élevé. La procédure Réaffecter devrait donc être plus sensible et améliorer

davantage la qualité du design obtenu. Cependant, ces problèmes sont composés d’un nombre

d’entrepôts plus faible et, par conséquent, les choix possibles de réaffectation sont pour le moins

réduits. Ainsi, si on se rapporte à la table A‐3.2 de l’annexe, on remarque une amélioration de la

procédure dans les cas où la stratégie 1 est employée et lorsque le réseau est composé de petits

clients RP. Comme ces réseaux sont normalement composés d’un nombre inférieur d’entrepôts,

un plus grand ensemble de points critiques rend, pour une même taille de problème, la procédure


65

Réaffecter plus efficace. De plus, la liberté quant aux choix des mouvements tout au long de

l’heuristique (comme c’est le cas pour la première stratégie) favorise le travail de la procédure.

Nos résultats montrent aussi que la formule d’estimation du coût des routes [27] est très

fiable. Comme on peut l’observer dans la première table de la figure 5.6 ci‐dessous, lorsqu’on

évalue chacune des 48 solutions du plan d’expérience, la moyenne d’estimation se trouve à

101,45%. Ceci indique que la formule [27] surestime le coût des routes de 1,45% en moyenne. Les

meilleures estimations se trouvant avec la stratégie 3 pour des problèmes de petite et moyenne

taille. Son utilisation dans l’évaluation des mouvements intermédiaires dirige également la

recherche vers de très bonnes solutions. On remarque dans la deuxième table de la figure les

mêmes rapports obtenus pour l’ensemble des itérations générées lors de la résolution d’un

problème de grande taille. Les estimations se situent alors entre 99,18%,105,52% , la stratégie

1 étant cette fois‐ci la plus stable.

A)Évaluation des 48 solutions du plan d’expérience

B)Évaluation sur l’ensemble des itérations d’un problème P3

Figure 5.6 – Rapport entre l’estimation et la valeur réelle des routes

Au‐delà des estimations des coûts de transport, on peut regarder ce qu’il en est des routes

réellement construites. En vérifiant le nombre moyen de routes créées par période, les

caractéristiques de ces routes de même que leur longueur. La table 5.8 fournie de telles

statistiques pour différents sous‐ensembles de problèmes. On y dénombre le pourcentage de

chacun des types de routes construites par la procédure Transport pour plusieurs solutions

générées par les recherches. Ainsi, le pourcentage de routes FTL tourne autour des 60% et est plus

élevé pour les problèmes RG regroupant des grands clients. Les réseaux RP, quant à eux,

favorisent les routes avec arrêts multiples où près de 20% des routes construites sont en mode

MTL. Cette observation est directement reliée à la définition de cet axe du plan d’expérience, les


66

réseaux RG étant composés d’un plus grand nombre de points de livraison qui commandent

fréquemment de grandes quantités de produits. En conséquence, il est normal de constater que le

nombre de routes par période est supérieur pour les réseaux RG (33,8 routes/période) que pour

les réseaux RP (25,79 routes/période). Aussi, les routes avec arrêts multiples sont composées de 2

arrêts dans près de 80% des cas, de 3 arrêts dans près de 20% des cas ou de 4 arrêts dans de très

rares cas. En ce qui concerne les routes d’un seul arrêt avec chargement partiel (STL ou LTL),

celles‐ci sont stables et présentent chacune tout près de 13 % de l’ensemble des routes

répertoriées. Ces statistiques expliquent en partie la très bonne estimation du coût des routes

puisqu’entre 80 et 85 % des routes de transport ne comportent qu’un seul arrêt et que près de

60% de celles‐ci (FTL) est isolées à priori. L’erreur des estimations n’est donc affectée qu’à 40% des

routes construites. Enfin, l’importance de la taille des problèmes bien qu’elle augmente le nombre

de routes par périodes n’affecte pratiquement pas la composition de telles routes de livraison.

Table 5.8 – Caractéristiques des routes construites par la procédure Transport

Chapitre 6

Conclusion

Ce mémoire traite de la formulation et de la résolution d’un problème fondamental de

planification stratégique auquel font face nombres d’entreprises. La confection et le design d’un

réseau de distribution impliquent en effet plusieurs facteurs décisionnels et le support des

différentes activités composant le réseau logistique. On s’est intéressé, de façon plus précise, aux

cas où l’implication des ressources externes de transport permet d’acheminer les produits à

travers un réseau de distribution composé d’un nombre limité d’entrepôts. Plusieurs objectifs ont

ainsi été fixés pour traiter fidèlement la séquence opérationnelle que rencontrent les entreprises

qui expédient leurs produits vers divers points de livraison. Il s’agissait premièrement d’inclure la

dimension temporelle des décisions stratégiques de design et des décisions opérationnelles de

transport. De plus, le problème présenté à permis d’inclure plusieurs choix quant aux modes de

transports disponibles.

Le problème stochastique de localisation‐transport (PSLT) tient compte de plusieurs décisions

propres aux deux niveaux décisionnels en y insérant la multiplicité des périodes qui caractérise

Chapitre 6: Conclusion

68

l’horizon de planification. Le problème est ainsi défini par la hiérarchisation des décisions capable

de considérer les localisations des entrepôts, leurs missions en termes des endroits devant être

visités ainsi que les problèmes de transport qui y sont associés. Ainsi, suite à une revue exhaustive

des cas traités dans la littérature et à l’exposé de la problématique, le chapitre 2 s’est attardé à la

formulation précise du problème. Il a alors été possible de formuler le problème comme un

programme stochastique à deux étapes avec recours. Le processus permettant de prendre les

décisions opérationnelles de transport constitue le recours mis à la disposition des entrepôts,

compte tenu de leur mission. En dernier lieu, ce chapitre a montré comment un échantillon de

scenarios composés de plusieurs périodes peut être généré à partir du processus stochastique de

demande des clients. Cette façon de faire a permis d’exposer les principes de la méthode de

solution approximative basée sur la moyenne échantillonnale (AMÉ) qui a été utilisée pour

résoudre le problème.

Nous en avons conclu que le problème de programmation en nombres entiers mixte basé sur

la méthode AMÉ est extrêmement grand. Pour des réseaux de taille réaliste, ce problème ne peut

pratiquement pas être résolu de façon exacte par les solveurs commerciaux standards. Ainsi, le

chapitre 3 était dédié à l’approche heuristique de résolution qui a été proposée dans le but de

résoudre le problème de façon hiérarchique. Cette approche est basée sur une heuristique de

transport utilisée au niveau opérationnel permettant d’inclure les caractéristiques propres à

l’utilisation de la flotte de véhicules. De même, une heuristique de « localisation‐affectation » a

été développée rendant possible la conception de design du niveau stratégique. On a alors défini

les particularités de notre recherche Tabou et des voisinages restreints qui ont permis de

parcourir intelligemment les solutions les plus favorables. Ces sections nous ont également permis

d’identifier les mouvements possibles à chaque itération et de proposer une formule révisée

d’approximation de la longueur des routes. Ce fut également l’occasion de présenter trois

stratégies de recherche basées sur des mouvements primaires de fermeture, d’ouverture ou de

remplacement d’entrepôts. Ces stratégies d’exploration du voisinage des solutions ont pour la

plupart été améliorées par la création de la procédure Réaffecter visant à corriger certaines

affectations extrêmes.

Par ailleurs, afin de vérifier la qualité des heuristiques développées, plusieurs cas réalistes ont

été développés. Le chapitre 4 était dédié à la construction de 48 problèmes agissant comme base

d’évaluation. Ces problèmes étaient construits en respectant quatre axes d’analyse : y étaient ainsi


69

détaillés diverses tailles de réseaux, structures de coûts, caractéristiques de clients et processus de

demande. Les expériences réalisées ont montré que l’approche de résolution proposée fournie

des résultats vraiment intéressants au niveau de la qualité des designs et du temps d’exécution

requis par la recherche. En fait, le chapitre 5 a montré que les stratégies S1 et S2 fournissent une

exploration dans le voisinage plus stable et mieux dirigée vers les meilleures solutions. Elles

apportent les résultats les plus probants en termes de qualité des solutions et se comparent

favorablement aux solutions optimales pour certaines tailles de réseau logistique. Également, la

rapidité d’exécution est remarquable même pour les problèmes de très grandes tailles. Ceux‐ci se

situant dans la grande majorité des cas sous les 400 secondes. La stratégie 2 dominant ce point de

vue. L’excellente performance de la résolution imbriquée des stratégies est principalement causée

par l’efficacité avec laquelle les coûts de transport sont anticipés au niveau stratégique. En

sommes, on constate que la combinaison des différentes procédures et heuristiques permet de

concevoir des designs appropriés et d’engendrer des solutions rentables.

6.1. Pistes d’amélioration et travaux futurs

Nous croyons que l’approche telle qu’elle a été développée est suffisamment évoluée pour

résoudre avec efficience la plupart des cas pratiques. Il existe cependant plusieurs opportunités et

autres aspects connexes qui pourraient donner lieu à des recherches additionnelles. Dans ce qui

suit on identifie des avenues de recherche future possibles pouvant mener à des avantages

significatifs:

Nous avons considéré un contexte d’affaire où les points de livraison doivent être affectés au

même entrepôt tout au long de l’horizon de planification. Dans d’autres contextes le choix

des entrepôts à utiliser pour faire les livraisons pourrait varier d’une journée à l’autre. Le

problème opérationnel serait alors un problème de transport multi‐entrepôts et il serait

plus difficile à résoudre.

Nous avons constaté la très grande qualité de l’approximation des coûts de transport et donc de

l’anticipation des décisions du problème opérationnel. On pourrait vérifier l’allure des

résultats et le comportement des heuristiques en utilisant cette formule d’approximation


70

pour l’évaluation des solutions intermédiaires. Cette façon de procéder permettrait de

considérablement diminuer les temps requis par la recherche. On pourrait également faire

appel à un algorithme de routage plus évolué élargissant les possibilités de construction des

routes et l’échange des arcs qui les composent. Ceci dans le but d’améliorer les solutions du

PTV. Cependant, étant donné le petit nombre de clients dans les routes construites,

l’utilisation de meilleurs algorithmes de routage n’améliorerait sans doute que très

légèrement la valeur de l’objectif et les designs obtenus.

Nous avons supposé que le processus de génération des commandes était stationnaire. S’il

s’avérait que ce ne soit pas le cas, la taille n des échantillons de scenarios à utiliser serait

considérablement plus volumineuse. Le modèle AMÉ serait alors très difficile à résoudre et

ne conserverait peut‐être pas les mêmes statistiques d’écarts par rapport à l’optimal.

Nous avons été capables de résoudre le modèle AMÉ de façon optimale avec CPLEX‐11.

Seulement, il est rapidement apparu qu’il serait impossible de traiter des réseaux dont la

taille dépasse celle des petits problèmes (P1). Le développement de méthodes plus

spécialisées de décomposition pourrait permettre de résoudre de plus grands problèmes de

façon optimale. Par contre, ceci reste extrêmement difficile puisque, comme indiqué

précédemment, le nombre de variables binaires nécessaires à la sélection des routes croit

de façon exponentielle. Cette préoccupation mériterait toutefois une investigation future

plus poussée.

Les trois stratégies de recherches examinées laissent place à divers raffinements et au

perfectionnement des différentes phases qui les composent. De même, d’autres méthodes

de recherche telles que celles faisant intervenir les voisinages variables pourraient être

utilisées et ainsi mener à l’élaboration d’heuristiques alternatives.

Bibliographie

[1] M. Albareda‐Sambola, E. Fernandez and G. Laporte, “Heuristic and lower bound for a stochastic location routing problem”, European Journal of Operational Research 179, 940‐955 (2007).

[2] D. Ambrosino and M.G. Scutella, “Distribution network design: New problems and related models”, European Journal of Operational Research 165, 610–624 (2005).

[3]R. H. Ballou, Business Logistics Management. 3rd ed., Prentice Hall (1992).

[4] S. Barreto, C. Ferreira, J. Paixao and B.S. Santos, “Using clustering analysis in a capacitated location‐routing problem”, European Journal of Operational Research 179, 968–977 (2007).

[5] R.T. Berger, C.R. Coullard and M.S. Daskin, “Location‐Routing Problems with Distance Constraints”, Transportation Science 41, 1, 29‐43 (2007).

[6] O. Berman, D. Krass and C.W. Xu, “Location discretionary service facilities based on probabilistic customer flows”, Transportation Science 29, 3, 276‐290 (1995).

[7]J.R. Birge and F. Louveaux, Introduction to Stochastic Programming, Springer (1997).

[8] T.W. Chien, “Heuristic procedures for practical‐sized uncapacitated location‐capacitated routing problems”, Decision Sciences 24, 5, 995‐1021 (1993).

[9] G. Clarke and J.W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points”, Operations Research 12, 568‐581 (1964).

[10] C.F. Daganzo, “The distance traveled to visit N points with a maximum of C stops per vehicle: An analytic model and an application”, Transportation Science 18, 4, 331‐350 (1984).

[11] S. Girard, J. Renaud and F.F. Boctor, “Heuristiques rapides pour le problème de tournées de véhicules”, ASAC 2006 Proceedings. Banff, Alberta (2006).

[12]F. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, Boston (1997).

[13] W. Klibi, F. Lasalle, A. Martel and S. Ichoua, “The Stochastic Multi‐Period Location‐Transportation Problem”, Société Canadienne de Recherche Opérationnelle (SCRO‐Proceedings), Québec (2008).

Bibliographie 72

[14] A. Klose and A. Drexl, “Facility location models for distribution system design”, European Journal of Operational Research, 162, 4‐29, (2005).

[15] P. Kouvelis and G. Yu, Robust discrete optimization and its applications. Kluwer Academic Publishers (1997).

[16] A.A. Kuehn and M.J Hamburger, “A heuristic program for locating warehouses”, Management science, 9, 643‐666 (1963).

[17] G. Laporte, “Location‐routing problems”, in Vehicle Routing: Methods and Studies, B.L. Golden and A.A. Assad (eds), 163‐198, North‐Holland, Amsterdam, (1988).

[18] G. Laporte and P.J Dejax, “Dynamic Location Routing Problems”, Journal of Operational Research Society 40, 5, 471‐482 (1989).

[19] G. Laporte and I.H. Osman, “Routing problems: a bibliography”, Annals of Operations Research 61, 227‐262 (1995).

[20] G. Laporte, F.V. Louveaux and H. Mercure, “Models and Exact solutions for a class of

stochastic location‐routing problems”, European Journal of Operational Research 39, 71‐78 (1989).

[21] G. Laporte and F.V. Louveaux, “Solving Stochastic Routing Problems”, in Fleet Management and Logistics, T.G. Crainic and G. Laporte (eds), Kluwer Academic Publishers, (1998).

[22] G. Laporte, M. Gendreau, J‐Y. Potvin and F. Semet, “Classical and modern heuristics for the vehicle routing problem”, International Transaction in Operational Research 7, 285‐300 (2000).

[23] H. Min, V. Jayaraman, R. Srivastava, “Combined location‐routing problems: A synthesis and future research directions”, European Journal of Operational Research 108, 1‐15 (1998).

[24] G. Nagy and S. Salhi, “Nested Heuristic Methods for the Location‐Routeing Problem”, The Journal of the Operational Research Society 47, 9, 1166‐1174 (1996a).

[25] G. Nagy and S. Salhi, “A nested Location‐Routing Heuristic Using Route Length Estimation”, Studies in Locational Analysis 10, 109‐127 (1996b).

[26] G. Nagy and S. Salhi, “Location‐Routing: Issues, models and methods”, European Journal of Operational Research 177, 649‐672 (2007).

[27] S.H. Owen and M.S. Daskin, “Strategic facility location: A review”, European Journal of Operational Research 111, 423‐447 (1998).

[28] C. Prins, P. Prodhon, A. Ruiz, P. Soriano and R.W. Calvo, “Solving the Capacitated Location‐routing Problem by a Cooperative Lagrangian Relaxation‐Granular Tabu Search Heuristic”, Transportation Science, 41, 4, 470–483 (2007).

Bibliographie 73

[29] W. Rei, M. Gendreau and P. Soriano, “A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem with Stochastic Demands”, CIRRELT Research Document CIRRELT‐2007‐24.

[30] S. Salhi and G. Nagy, “Consistency and Robustness in Location‐Routing”, Studies in Locational Analysis 13, 3‐19 (1999).

[31] S. Salhi and G. Nagy, “Local Improvement in planar facility location using vehicle routing”,

Annals of Operations Research, DOI: 10.1007/s10479-007-0223-z, (2007).

[32] T. Santoso, S. Ahmed, M. Goetschalckx and A. Shapiro, “A stochastic programming approach for supply chain network design under uncertainty”, European Journal of Operational Research 167, 96‐115 (2005).

[33] D. Sariklis and S. Powell, “A Heuristic Method for the Open Vehicle Routing Problem”, Journal of the Operational Research Society 51, 564‐573 (2000).

[34] A. Shapiro, “ Monte Carlo Sampling Methods” in Stochastic Programming, A. Ruszczynski and A. Shapiro (eds), Handbooks in Operations Research and Management Science 10, Elsevier (2003).

[35] Z.‐ J. Shen, “Integrated Supply Chain Design Models: A Survey and Future Research Directions”, Journal of Industrial and Management Optimization 3, 1, 1‐27 (2007).

[36] L.V. Snyder, and M. S. Daskin, “Reliability Models for Facility Location: The Expected Failure Cost Case”, Transportation Science 39, 400‐416 (2005).

[37]E.G. Talbi, “A Taxonomy of Hybrid Metaheuristics”, Journal of Heuristics 8, 541‐564 (2002).

[38] P. Toth and D. Vigo, “Exact Solution of the Vehicle Routing Problem” in Fleet Management and Logistics, T.G. Crainic and G. Laporte (eds), Kluwer Academic Publishers (1998).

[39] D. Tuzun and L.I. Burke, “A two‐phase tabu search approach to the location routing problem”, European Journal of Operational Research 116, 87‐99 (1999).

[40] B. Verweij, S. Ahmed, A.J. Kleywegt, G. Nemhauser and A. Shapiro, “The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study”, Computational Optimization and Applications 24, 289–333 (2003).

[41] D. Vila, A. Martel and R. Beauregard, “Taking Market Forces into Account in the Design of Production‐Distribution Networks: A Positioning by Anticipation Approach”, The Journal of Industrial and Management Optimization 3, 1, 29‐50 (2007).

[42] Z.M. Zainuddin and S. Salhi, “A perturbation‐based heuristic for the capacitated multisource Weber problem”, European Journal of Operational Research 179, 1194‐1207 (2007).

Annexes

Annexe 2

Annexe 1 “SLTP‐Application”‐Guide de l’utilisateur

« SLTP-Application» Guide de l’utilisateur

Produit par Francis Lasalle

Dans le cadre du mémoire MSc « Une Métaheuristique de Résolution de Problèmes Stochastiques de

Localisation-Transport »

7 juin 2008 Département Opération et Systèmes de Décision

Faculté des sciences de l’administration

Annexe 3

« SLTP-Application» Guide de l’utilisateur

Table des matières

0. INTRODUCTION‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 4

1. INTERFACE UTILISATEUR‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 5

2. PRINCIPALES OPÉRATIONS‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 5

2.1. PROBLEM‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 6

2.1.1. Fichier de lecture‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 6 2.1.2. Node‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 9 2.1.3 Arc‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 10 2.1.4 Facility‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 11 2.1.5 Ship‐to‐point‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 12

2.2. SCENARIOS‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 13

2.2.1. Fichier de lecture‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 13 2.2.2. Création de scénarios‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 14

2.3. DESIGN GENERATION‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 15

2.3.1. Fichier de lecture‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 15 2.3.2. Regression Mode‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 18 2.3.3. Update Choices‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 19 2.3.4. Evaluation Partition‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 20 2.3.5. Generation‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 22

2.4. EVALUATION ONLY‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 24

2.4.1. Fichier de lecture‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 24 2.5.1. Section d’initialisation‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 27

3. LANCEMENT‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 28

4. CONCLUSION‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 28

5. RÉFÉRENCES‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 29

Annexe 4

0. Introduction

Le présent guide de l’utilisateur permet de comprendre et d’utiliser l’application « SLTP

Application ». Cette application permet de générer et de résoudre des problèmes de localisation‐

transport stochastiques. À travers les options de génération des points de livraison, de génération

des arcs et de génération des scénarios, nous pouvons créer l’ensemble des caractéristiques du

cas test qui nous intéresse. Puis, aidés par l’ensemble des sous‐menus du programme, nous

sommes en mesure de construire des solutions initiales toutes différentes les une des autres et de

lancer l’heuristique de notre choix selon les spécificités voulues. Ainsi, il sera possible de

partitionner le problème en une région donnée, de partitionner les scénarios en un découpage

plus ou moins grossier et de résoudre selon une des trois heuristiques implantées.

Certains documents sont également nécessaires au bon fonctionnement de l’application. En

fait, l’application nécessite un fichier de lecture qui indique les principales caractéristiques fixes

tout au long de la résolution ou de la génération des problèmes. Ce fichier doit être construit de

façon rigoureuse afin que le programme soit capable de répertorier les bonnes informations aux

bons endroits. De même, elle requiert la présence d’une base de données qui doit correspondre

en tous points à celle utilisée lors du développement de l’application soit la base de données SCNF

située sur le réseau Dresnet du CIRRELT de l’Université Laval dont les tables sont ajoutées sur la

version électronique du mémoire. Enfin, certaines tables doivent être chargées dès le départ

puisqu’elles ne sont pas initialisées par le programme. Il s’agit de la table State comprenant tous

les états américains. Comme expliqué dans le document, la table comprenant tous les nœuds

possibles doit elle aussi être remplie et être nommée à la discrétion de l’utilisateur. Elle doit

cependant être construite de la même façon que les tables All_Node ou All_Node_2 déjà

présentes dans la base de données et présenter dans l’ordre les SOP (usines), les DC (entrepôts) et

les clients (D). De plus, les tables Arc_Type, indiquant la fonction de coûts sur chacun des arcs, et

Vehicule_Type, déterminant la capacité des routes, doivent être remplies adéquatement. À noter

que chaque table importée ou remplie par l’utilisateur doit être triée en ordre croissant par son

identifiant unique (Node_ID par exemple).

Annexe 5

1. Interface utilisateur

Le menu présente 4 modules différents. Voir figure 1 ci‐dessous. Cette interface est la

première apparaissant lors de l’exécution de l’application. Les 4 modules pouvant être

sélectionnés à ce niveau sont : « Problem» qui permet de générer un problème test, « Scenario »

qui permet de bâtir l’échantillon des scénarios, « Design Generation » permettant de générer des

solutions à l’aide des heuristiques développées et « Evaluation Only» utilisé seulement pour

l’évaluation, avec l’heuristique de transport, d’un design fixé à priori. La case dans la partie

inférieure de l’affichage permet d’identifier l’emplacement du fichier d’informations nécessaire à

l’exécution (voir les sections fichiers de lecture).

Figure 1: Interface de départ

2. Principales opérations

Chacun des modules étant indépendant, on ne peut que les utiliser en séquence. Par

exemple, si notre base de données est vide, on commence par créer un problème avec le «Module

1 : Problem» puis on construit nos scénarios avec le «Module 2 : Scenario» et on lance les

Annexe 6

heuristiques avec le «Module 3 : Design Generation». À noter que le module 3 évalue également

tous les designs ou solutions crées afin d’être capable de les différencier. Les prochaines sections

présentent chacun des modules de façon détaillée.

2.1 Problem

Tout d’abord, bien avant de penser à la résolution comme telle de notre problème, il faut le

décrire et le construire. La section « Problem » le permet. Certaines tables importantes étant

considérées vides, il faut sélectionner les points qui feront partie du réseau. De plus, il faut définir

leurs statistiques de même que l’ensemble des arcs caractérisant ce réseau. Le fichier de lecture

nécessaire au module 1 est présenté à la prochaine section.

2.1.1 Fichier de lecture

Le fichier de lecture est un fichier « Bloc‐notes » contenant les principales informations pour

le bon fonctionnement du module. Ce fichier doit être rempli comme présenté dans la figure 2 ci‐

dessous et ce avant le lancement de l’application.

Annexe 7

Figure 2: Exemple du fichier de lecture « Module 1 : Problem »

Annexe 8

26 informations sont requises à ce niveau :

1. (DataBaseConnection) Le lien texte permettant d’ouvrir la base de données.

2. (NodeTable) Le noms de la table contenant tous les points créés. (Permet d’utiliser plusieurs densités)

3. (TotalPeriod) Le nombre total de périodes par scénario.

4. (UnitSalePrice) Le prix unitaire de vente. (Initialement identique pour tous

les clients) 4u

5. (SopCostMin) La limite inférieur de tous les coûts unitaires de

production. 4dc sop dcv wy ,

6. (SopCostMax) La limite supérieure de tous les coûts unitaires de

production. 4dc sop dcv wy ,

7. (A_min) Le coût fixe minimum d’ouverture d’un entrepôt. 4A

8. (A_max) Le coût fixe maximum d’ouverture d’un entrepôt. 4A

9. (MaxServiceArc) La distance maximale entre un client et son entrepôt.

10. (ProportionSmall) La proportion de petits clients dans le réseau.

11. (ProportionLarge) La proportion de grands clients dans le réseau.

12. (MOQSmallMin) Le Mean Order Quantity minimum d’un petit client.

13. (MOQMediumMin) Le Mean Order Quantity minimum d’un client

intermédiaire.

14. (MOQLargeMin) Le Mean Order Quantity minimum d’un grand client.

15. (MOQSmallMax) Le Mean Order Quantity maximum d’un petit client.

16. (MOQMediumMax) Le Mean Order Quantity maximum d’un client intermédiaire.

17. (MOQLargeMax) Le Mean Order Quantity maximum d’un grand client.

18. (MOQSigmaSmall) L’écart‐type du Mean Order Quantity pour un petit client.

Annexe 9

19. (MOQSigmaMedium) L’écart‐type du Mean Order Quantity pour un client intermédiaire.

20. (MOQSigmaLarge) L’écart‐type du Mean Order Quantity pour un grand client.

21. (TBOSmallMin) Le Time Between Order minimum d’un petit client.

22. (TBOMediumMin) Le Time Between Order minimum d’un client

intermédiaire.

23. (TBOLargeMin) Le Time Between Order minimum d’un grand client.

24. (TBOSmallMax) Le Time Between Order maximum d’un petit client.

25. (TBOMediumMax) Le Time Between Order maximum d’un client intermédiaire.

26. (TBOLargeMax) Le Time Between Order maximum d’un grand client.

2.1.2 Node

La première sous‐section représente la partition que nous désirons faire de la table All_Node

(ou autre) comprenant tous les points identifiés dans la base de données. Trois options s’offrent à

nous. Il s’agit d’une partition par « Territory », par « State » ou par « Zip Code ». La figure 3

montre, ci‐dessous, le cas où nous sommes intéressés par une partition des points comprenant

seulement ceux du territoire du Midwest des États‐Unis. Les figures 4 et 5 montrent quant à elles

la partition par état et par code postal. Dans la figure 4 tous les points des états du Texas et du

Vermont constituent le problème traité tandis que dans la figure 5 se sont les points ayant un code

postal entre 76600 et 77000. Il est à noter qu’advenant le cas où aucun nœud représente des

usines (SOP) ou entrepôt (DC) tous les nœuds externe représentant ces installations font parti, par

défaut, de la partition choisie. Également, suite à cette exécution, le coût unitaire total de

production et d’entreposage dc sop dcv wy , est inscrit dans la table SOP et le coût fixe

d’ouverture des DC A dans la table DC.

L’impact, à ce niveau, se fait pour la table Zone (une zone par point), la table Node (les nœuds

choisis), la table SOP (les usines), la table DC (les DC), la table Anticipations (Définition de

l’anticipation), la table Planning_Period (Nombre maximal de période) et la table Usage_Period

Annexe 10

(Toutes les périodes uniques). Ces impacts entrent en jeu à ce stade puisque la régénération des

points ou des nœuds témoigne d’un changement radical de problèmes tests.

Figure 3: Génération des “Nodes” (Territoire) et des arcs

On remarque que deux options sont sélectionnées dans le module « Problem». À noter que la

suite du menu qui apparaît est exclusive à ce module.

2.1.3 Arcs

Le fait de cocher la case Arcs du module « Problem » nous permet de générer

immédiatement tous les arcs du réseau choisi par la partition. Nous pouvons faire les deux

opérations en deux lancements mais cela revient exactement au même puisque l’application doit

créer ses nœuds avant ses arcs. Il est à noter que la construction des arcs permet de compléter la

table DC en y ajoutant la valeur unitaire du produit à l’entrepôt 3dcv égal au coût total de

production, d’entreposage et de transport en amont. L’impact, à ce niveau, se fait pour la table

User_Arcs (tous les arcs pertinents) et la table DC (les entrepôts).

Annexe 11

Figure 4: Génération des points (État) et des arcs

Figure 5: Génération des points (Code Postal) et des arcs

2.1.4 Facility

Le fait de cocher la case Facility du module « Problem » nous permet de modifier les valeurs

associées aux installations. En fait, une fois le réseau obtenu, cette action nous permet de

Annexe 12

régénérer de nouveaux coûts totaux aux SOP dc sop dcv wy , et de nouveaux coûts fixes

d’ouverture des entrepôts. Advenant le cas où les variables SopCostMin, SopCostMax, A_min et

A_max restent inchangées, de nouvelles valeurs sont tout de même générées à l’intérieur de ces

intervalles. L’impact, à ce niveau, se fait pour la table SOP (coûts totaux) et pour la table DC (les

coûts fixes d’ouverture et la valeur unitaires aux entrepôts).

2.1.5 Shiptopoint

Le fait de cocher la case SToPoint du module « Problem » nous permet de construire les

statistiques théoriques des clients. Deux options s’offrent alors à nous. La première étant de

générer l’ensemble des statistiques selon les intervalles mentionnées dans le fichier de lecture. La

deuxième quant‐à‐elle ne peut être exécutée que lorsque la table ShipToPoints contient déjà des

statistiques. On peut alors choisir de ne changer que le prix unitaire de vente pour tous les points

de livraison u et de garder toutes les autres statistiques intactes. (Voir figure 6 ci‐dessus).

L’impact, à ce niveau, se fait pour la table Ship‐to_points (statistiques théoriques des clients).

Figure 6: Génération des ShipToPoints (Changement seulement dans le prix de vente)

Annexe 13

Finalement, les options Node, Arcs et SToPoint (All_Generation) peuvent être exécutées une

à la fois ou simultanément. Les autres options étant relatives à des modifications, elles ne peuvent

être exécutées qu’en deuxième vague.

2.2 Scenarios

Il s’agit ici de former un ou plusieurs scénarios de demande. En fait, à l’aide du module « Module

2 : Scenario », l’application construit un échantillon de scénarios de cardinalité choisie.





Figure 7: Exemple du fichier de lecture « Module 2, Scenario »


1. (DataBaseConnection) Le lien texte permettant d’ouvrir la base de données. 2. (NbScenario) Le nombre de scénarios désirant être crées. 3. (SampleNumber) Le numéro de l’échantillon crée. Les scénarios crées feront

partie de cet échantillon.

Annexe 14

4. (MinimumOver) La quantité excédentaire minimale d’une commande qui dépasse la capacité d’un véhicule. Order Quantity ≥ (Capacity+MinimumOver) ou Order Quantity ≤ Capacity

2.2.2 Création de scénarios

L’exemple à la figure 8 montre l’interface du module 2. Cet exemple permet de créer

l’échantillon 1 comprenant 10 scénarios (point 3 et point 2 du fichier de lecture). Ces scénarios

contiennent le nombre de périodes inscrites aux tables Planning_Period et Usage_Period

initialisées par le module 1. Une option est disponible à ce niveau‐ci indiquant si l’on désire

réinitialiser toutes les tables relatives aux scénarios avant de créer les nouveaux scénarios. En

conséquence, le fait de ne pas cocher cette case permet d’ajouter des scénarios à ceux déjà

générés. À noter que le fait d’inscrire 0 au numéro d’échantillon et au nombre de scénario et de

cocher cette case implique une remise à l’état initial de toutes les tables associées aux scénarios.

Enfin, le traitement de la quantité excédentaire s’effectue comme suit : le processus de génération

des quantités demeure inchangé et l’application procède à un arrondissement a postériori. Ainsi,

cette contrainte ne permet à aucune commande de se trouver entre la capacité d’un véhicule et

cette même capacité additionnée du « MinimumOver ». L’impact, à ce niveau, se fait pour la table

Sample (les échantillons), la table Scenarios (les scénarios) et la table Point_Demand (les

commandes des clients par périodes et par scénarios)

Annexe 15

Figure 8: Génération des scénarios

2.3 Design Generation

Une fois la génération du problème complétée et les scénarios crées, nous pouvons

commencer le début de la résolution. Cette résolution consiste à la création de designs ou de

solutions à l’aide de trois différentes heuristiques permettant d’obtenir une solution finale au

problème SLTP. Premièrement, une méthode de construction est nécessaire pour toutes les

heuristiques afin d’obtenir une solution de départ réalisable. Ainsi, que l’on obtienne un design de

départ à l’aide de l’interface ou bien qu’on ajoute manuellement les informations du design, ces

données sont essentielles à la génération des designs. Mentionnons également que ce module

évalue chacune des solutions intermédiaires nécessaires à la performance des recherches

effectuées. Enfin, ce module se compose de 4 sections distinctes qui seront reprises à l’intérieur

des paragraphes suivants ainsi que les informations nécessaires au fichier de lecture.





Annexe 16

Figure 9: Exemple du fichier de lecture « Module 3 : Design Generation »

Annexe 17


Connexion 1. (DataBaseConnection) Le lien texte permettant d’ouvrir la base de données.

Stratégie 2. (Strategy) Identifie le numéro de la stratégie/heuristique (1, 2, 3)

Clarke & Wright 3. (CWIteration) Le nombre de répétitions ou de perturbations de

l’algorithme du Clarke & Wright. 4

4. (CWAlpha) La perturbation minimale des économies du Clarke &

Wright. 4

5. (CWBeta) La perturbation maximale des économies du Clarke &

Wright. 4

Route Cost Estimation 6. (DCMeanStop) Statistique de départ pour tous les entrepôts déterminant

le nombre moyen d’arrêts par route. 4NS

7. (DCNbRoute) Nombre de routes prises en compte dans l’échantillon

initial servant à fixer les paramètres de départ. (Cette statistique est nécessaire à la mise à jour des moyennes).

8. (DCLtlPerc) Statistique de départ pour tous les entrepôts déterminant

le pourcentage de CWT*Miles effectués en LTL par rapport

à tous les CWT*Miles d’une journée donnée. 4LTL

9. (DCNbRoutingDay) Nombre de journées prisent en compte dans l’échantillon


10. (LH) Coefficient de régression représentant l’explication de la

variable Line‐Haul. 1̂ 4

11. (Detour) Coefficient de régression représentant l’explication de la

variable Detour. 2ˆ 4

12. (LTL) Coefficient de régression représentant l’explication de la

variable LTL. 3ˆ 4

Annexe 18

Cost Structure

13. (MinCostRoutingTL) Le coût minimal d’une route en mode TL. 4TL

14. (MinCostRoutingLTL) Le coût minimal d’une route en mode LTL.

Reassign 15. (CriticDistance) La distance critique qui détermine les points jugés éloignés

de leur dépôt. Ces points sont sujets à être « Borderline ».

max 4m

16. (RhoMax) Le plus grand ratio de comparaison « cut‐off point » à être

utilisé dans le « Reassign ». max 4

17. (RhoMin) Le plus petit ratio de comparaison « cut‐off point » à être

utilisé dans le « Reassign ». max 4

18. (RhoStep) Augmentation des ratios de comparaison « cut‐off point »

à être utilisés dans le « Reassign ». max 4

Tabou 19. (IteTotalMultiple) Nombre total d’itérations pour un mouvement multiple

(> 1 DC d’impliqué). 4MI

20. (IteMoinsMultiple) Nombre total d’itérations sans amélioration pour un

mouvement multiple (> 1 DC d’impliqué). 4MNI

21. (AddDegreeMove) Nombre d’entrepôts pouvant être ouverts simultanément

lors d’un mouvement. 22. (MinSingleTabuMove) Paramètres compris entre 0 et 1 permettant de varier le

nombre minimal d’entrepôts « Tabous ». 1 4

23. (MinMultipleTabuMove) Paramètres compris entre 0 et 1 permettant de varier le

nombre minimal de mouvements REMPLACER identifiés

comme « Tabous ». 2 4

2.3.2 Regression Mode

Cette section du module 3 est exclusive à l’obtention ou non des procédures de régression. Il

s’agit en fait d’identifier si les générations de design et le transport associé sont exécutés dans le

but de construire un échantillon de données. Les données sur le routage étant utilisées pour une

Annexe 19

régression à priori dans le but de fixer les paramètres de départ. En fait, ces paramètres sont pris

en compte lors de l’estimation du coût de transport engagé au court d’une période donnée pour

un entrepôt en particulier. La figure 10 qui présente l’interface du module 3 nous permet de

constater que la génération permettra d’obtenir les valeurs de régression et éliminera les

anciennes valeurs générées. La case « Reset Values » agit effectivement de façon à réinitialiser la

table de régression. L’impact, à ce niveau, se fait seulement pour la table Regression Cost (les

données de régression).

Figure 10: Module 3. Options de Régression et de mise‐à‐jour

2.3.3 Update Choices

Cette section du module 3 nous permet de déterminer quelles sont les opérations de

sauvegarde qui nous intéressent. Étant donné le nombre variable et parfois très élevé de routes

générées pour chaque solution visitée, il s’avère judicieux de déterminer à l’avance le besoin des

informations correspondantes. Par exemple, si on se réfère à la figure 10, on désire faire une mise

à jour des routes générées (Update Routes) et ne pas obtenir les compléments (Add Route

Annexe 20

Complement) sur les routes de même que l’information sur les designs intermédiaires (Update

Inter Design). Ce choix nous permet d’économiser du temps lors de la résolution et de la mise‐à‐

jour des données. Cependant, la partie la plus exigeante étant toutefois sélectionnée, l’exécution

est de beaucoup ralentie. En résumé, voici en quoi consistent les trois options possibles et les

tables affectées.

Add Route Complement

Permet d’ajouter toutes les routes directes (un seul point de livraison). Ainsi, pour chaque journée

et selon l’affectation obtenue, les arcs directs à partir des entrepôts ouverts font partie de

l’ensemble des routes. Cela indépendamment de leur utilisation lors du transport. Action sur les

tables Routes et Route Segment.

Update Routes

Indique si les informations sur les routes doivent être mises à jour dans la base de données. Ces

informations déterminent les arcs formant toutes les routes ainsi que le type et le coût de ces

routes. Action sur les tables Routes et Route Segment.

Update Inter Design

Indique si les informations sur les entrepôts ouverts et sur les arcs sélectionnés doivent être mises

à jour dans la base de données. Il s’agit ici des données relatives aux solutions intermédiaires

outre l’initiale et la finale qui elles sont toujours mises à jour. Action sur les tables Design Decision

et Arc lp.

2.3.4 Evaluation Partition

La section qui nous intéresse ici est partagée par les modules 3 et 4 et permet de diviser

l’ensemble des périodes à évaluer afin d’obtenir la valeur d’une solution donnée. Comme l’indique

la figure 11 ci‐dessous, des choix sur les échantillons (Sample), sur les scénarios (Scenario) et sur

les périodes (Period) sont possibles. Plus précisément, chacun de ces choix présente deux options.

Ainsi, pour les échantillons et les scénarios il s’agit de choisir entre « All » ou « One » afin de

Annexe 21

déterminer si nous évaluons tous les échantillons/scénarios ou seulement qu’un. L’exemple

présenté ci‐dessous évalue les solutions sur le scénario 2 de tous les échantillons. Puis pour la

division sur les périodes nous pouvons choisir entre « Alll » ou « <Max » ce qui donne le choix

entre l’évaluation de toutes les périodes ou d’un sous‐ensemble de périodes. Encore une fois, si

l’on reprend la partition de la figure 11, nous évaluons les solutions sur les 25 premières périodes

du scénario 2 de tous les échantillons. À noter que les périodes sont partitionnées en commençant

par la première jusqu’au nombre voulu ceci afin de récupérer facilement le numéro des périodes

prises en compte.

Figure 11: Module 3. Partition des scénarios et génération des designs

L’impact à ce niveau n’implique que les calculs d’évaluation et influence les tables User

Decision et Design Évaluation. Enfin, il est important de mentionner que lorsque la partition fait en

sorte que seulement un sous‐ensemble de périodes est requis, les valeurs des statistiques sont

quand même rapportées sur une base commune. Cette base est le nombre maximal de périodes

par scénario.

Annexe 22

2.3.5 Generation

La section génération proprement dite supporte les options possibles pour la génération ou le

lancement des stratégies. Elle est composée de trois options qui permettent d’initialiser les tables

(Reset Tables), de construire une solution initiale (Construction) et de générer les solutions

(Generation). L’exemple de la figure 11 exécute ces trois tâches successivement. Regardons plus

attentivement chacune des trois options.

1) Initialisation‐ « Reset Tables »

Une initialisation est effectuée lorsqu’on désire recommencer la résolution en éliminant les

résultats de tests préalablement effectués. À la première résolution, le système est dans une

condition identique à celle résultant d’une initialisation. En fait l’initialisation permet d’effacer le

contenu de la table Arc_lp (les affectations), la table Design_Decision (les ouvertures), la table

Route_segment (les arcs des routes), la table Routes (les routes), la table User_Decision (les

résultats par scénarios), la table Design Evaluation (l’évaluation de tous les designs obtenus) et la

table Design (les designs). Le fait de ne cocher que cette case permet de remettre le système en

situation initiale sans plus. Cela peut être intéressant lorsqu’on désire importer dans la base de

données des informations nécessaires à la prochaine génération de designs.

2) Solution initiale réalisable ‐ « Construction »

La procédure de construction est intimement liée aux choix de la stratégie de recherche. En

fait, tout dépendant si on indique la stratégie 1,2 ou 3 au point 2 du fichier de lecture du module

3, la construction sera différente. Pour les stratégies 1 et 3 la construction fait référence à

l’affectation à l’entrepôt le plus économique de chacun des points de livraison et par conséquence

à l’ouverture des entrepôts ayant au moins un point pour lequel il est le plus avantageux. Par

contre, si on utilise la stratégie 2, la procédure de construction tente d’ouvrir un minimum

d’entrepôt en utilisant un algorithme spécifique à cette stratégie. Chaque entrepôt avec le plus

grand nombre d’arcs incidents est ouvert séquentiellement jusqu’à ce qu’aucun point reste

orphelin.

Annexe 23

Maintenant, pensons au cas où certains designs sont déjà implantés dans la base de données

et que nous voulons lancer la génération à partir d’un de ces designs. Il se peut également que

nous voulions relancer la stratégie une deuxième fois sans avoir à refaire la construction. Comme

l’indique la figure 12 ci‐dessous, il suffit de garder la case « Construction » libre et d’indiquer le

numéro du scénario qui jouera le rôle de solution initiale réalisable.

Figure 12: Module 3. Construction initiale

L’impact de ces choix se fait essentiellement dans la table Arc_lp (les affectations), la table

Design_Decision (les ouvertures), la table Design_Evaluation (l’évaluation de tous les designs

obtenus) et la table Design (les designs).

3) Génération des solutions ‐ « Generation »

En sélectionnant la case Generation, nous pouvons, maintenant, résoudre le problème de

« localisation‐transport » selon le type d’heuristique adopté. Trois stratégies ou heuristiques sont

disponibles. Voici en quoi consiste chacune d’elle:

1: Cette stratégie s’inspire de l’approche de recherche Tabou proposée par Salhi et Nagy

(1996a). À chaque itération, tous les mouvements FERMER, OUVRIR et REMPLACER sont

considérés;

2: Cette stratégie est une extension de la méthode d’exploration du voisinage en trois phases

proposée par Kuehn et Hamburger (1963). La première phase explore seulement les

mouvements OUVRIR, la seconde phase considère exclusivement les mouvements FERMER et

la troisième phase se concentre sur les mouvements REMPLACER;

Annexe 24

3: Cette stratégie mixte est basée sur les mouvements qui réduisent le nombre d’entrepôts

en alternance avec des phases d’amélioration. À chaque itération, un mouvement FERMER

est appliqué puis, au cours d’une phase d’intensification précédant la prochaine fermeture,

seuls les mouvements REMPLACER sont autorisés;

2.4 Evaluation Only

Le dernier module de l’application est utilisé advenant le cas où nous avons besoin d’évaluer

un certain design. En fait, à partir du moment où les informations sur une solution ou un design

sont adéquatement inscrites dans la base de données, nous pouvons l’évaluer avec le module 4

« Evaluation Only ». Celui‐ci, un peu à l’image du module précédent, est divisé en quatre sections

qui permettent d’évaluer de différentes façons chacune des solutions. À noter que le programme

exécute les deux méthodes d’évaluation du problème opérationnel soit la méthode « Clarke &

Wright » et la méthode d’estimation du coût des routes par « Daganzo ».





Annexe 25

Figure 13: Exemple du fichier de lecture « Module 4 : Evaluation Only »


Connexion 1. (DataBaseConnection) Le lien texte permettant d’ouvrir la base de données.

Design 2. (Design_ID) Identifie le numéro du design à évaluer.

Clarke & Wright 3. (CWIteration) Le nombre de répétitions ou de perturbations de

l’algorithme du Clarke & Wright. 4

Annexe 26

4. (CWAlpha) La perturbation minimale des économies du Clarke &

Wright. 4

5. (CWBeta) La perturbation maximale des économies du Clarke &

Wright. 4

Route Cost Estimation 6. (DCMeanStop) Statistique de départ pour tous les entrepôts déterminant

le nombre moyen d’arrêts par route. 4NS

7. (DCNbRoute) Nombre de routes prisent en compte dans l’échantillon


8. (DCLtlPerc) Statistique de départ pour tous les entrepôts déterminant

le pourcentage de CWT*Miles effectués en LTL par rapport

à tous les CWT*Miles d’une journée donnée. 4LTL

9. (DCNbRoutingDay) Nombre de journées prisent en compte dans l’échantillon


10. (LH) Coefficient de régression représentant l’explication de la

variable Line‐Haul. 1̂ 4

11. (Detour) Coefficient de régression représentant l’explication de la

variable Detour. 2ˆ 4

12. (LTL) Coefficient de régression représentant l’explication de la

variable LTL. 3ˆ 4

Cost Structure

13. (MinCostRoutingTL) Le coût minimal d’une route en mode TL. 4TL

14. (MinCostRoutingLTL) Le coût minimal d’une route en mode LTL.

Annexe 27

2.4.2 Sections d’initialisation

L’interface du module 4 nous présente encore une fois 4 sections d’initialisation qui sont

essentiellement les mêmes que pour le module 3 (voir figure 14). Il est donc souhaitable à ce

niveau‐ci de se référer aux sections 2.3.2 (Regression Mode), 2.3.3 (Update Choices) et 2.3.4

(Evaluation Partition). Seulement indiquer que l’option « Update Inter Design » de la section

« Update Choices », n’a aucun impact pour le module 4 étant donné que le design utilisé est déjà

connu. Cette case reste donc vide comme indiqué à la figure 14 ci‐dessous.

La section « Evaluation Partition » fait ressortir l’option de réinitialisation de certaines tables

avant l’évaluation souhaitée. Ainsi, il est possible, lorsque voulu, de remettre à zéro les tables

Route_segment (les arcs des routes), Routes (les routes), User_Decision (les résultats par

scénarios) et Design Evaluation (l’évaluation de tous les designs obtenus). À noter qu’un axe de

partition à été ajouté comparativement au module 3. Celui‐ci nous permet maintenant d’évaluer

seulement un des entrepôts compris dans la solution traitée. Comme pour les autres axes, notre

choix consiste à « All » (tous les entrepôts) ou « One » (un seul).

Figure 14: Interface du Module 4 : « Evaluation Only »

Annexe 28

Ainsi, lorsque toutes les options ont été fixées, l’évaluation peut être lancée. Les

renseignements de cette évaluation sont disponibles dans la table « User Decision » et « Design

Evaluation ». Le reste des mises à jour dépend des sélections observées dans les différentes

sections du module 4.

3. Lancement

Chacun des modules de l’application détient son propre dispositif de lancement qui est

programmé à l’intérieur d’un « bouton‐objet ». Ce dernier est habituellement visible au bas de la

section réservée à ce module. Ainsi lorsque toutes les informations sont entrées aux endroits

appropriés, l’application peut être lancée. Une fois toutes les opérations terminées, une fenêtre

apparaît pour indiquer la fin de l’application. Pour ce qui est du module 3‐« Design Generation »,

un chronomètre précède la fenêtre finale. Ce dispositif ne fait que renseigner sur le temps

nécessaire à la résolution. Advenant le cas où d’autres tests doivent être exécutés avec la même

application, on doit absolument arrêter le programme avec l’outil d’arrêt de Visual basic puis

appuyer de nouveau sur l’outil de compilation toujours dans Visual basic.

4. Conclusion

Cette application est en fait un programme permettant de générer des cas pour des

problèmes de localisation‐transport stochastiques et de les résoudre via différentes stratégies. Les

options offertes à l’utilisateur apparaissent aux endroits appropriés à l’intérieur de la fenêtre

d’exécution. Que ce soit simplement pour générer un scénario de plus, pour construire une

solution initiale différente ou pour reconstruire un problème en entier, l’application permet de

bien définir les opérations que l’on désire voir s’exécuter. Ainsi, en portant une attention

particulière aux fichiers de lecture nous sommes en mesure de fixer certains paramètres pour

l’ensemble des tests effectués. Finalement, le programme est intimement lié à la base de données

utilisée car il y puise une grande partie des informations et y inscrit l’ensemble de ses résultats.

Annexe 29

5. Références

[1] Clarke and Wright, (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. Vol.12, pp.568‐581.

[2] Daganzo C.F. (1984). The distance traveled to visit N points with a maximum of C stops per vehicle: An analytic model and an application. Transportation Science, Vol.18, No.4, pp 331‐350.

[3] Girard S., J. Renaud and F.F. Boctor (2006). Heuristiques rapides pour le problème de tournées de véhicules. ASAC 2006 proceedings. Banff, Alberta.

[4] Klibi W., F. Lasalle, A. Martel and S. Ichoua (2008). The Stochastic Multi‐Period Location‐Transportation Problem. CIRRELT‐2008.

[5] Kuehn A.A. and M.J Hamburger (1963). A heuristic program for locating warehouses. Management science. 9, pp. 643‐666.

[6] Nagy G. and S. Salhi (1996a). Nested Heuristic Methods for the Location‐Routeing Problem. The Journal of the Operational Research Society, Vol. 47, No. 9, pp. 1166‐1174.

Annexe 30

Annexe 2 Étude des distributions log‐normale et exponentielle

Cette annexe présente l’étude des distributions permettant la construction des différents

scénarios. Les trois premières figures montrent la qualité de l’ajustement entre la simulation de

10 000 commandes et les principales lois continues. Ces comparaisons ont été réalisées avec l’outil

Crystal Ball (www.oracle.com) pour un petit client (figure A‐2.1) un client intermédiaire (figure A‐

2.2) et un grand client (figure A‐2.3). À noter que l’ensemble des commandes a été généré sous

l’environnement du problème P1‐c‐RP‐SD1 en ne considérant aucun arrondissement des tailles des

commandes (qui visait à éliminer les quantités excédentaires trop faibles).

Pour ce qui est des figures A‐2.4 à A‐2.6, il s’agit du même exercice s’appliquant cette fois‐ci

aux temps inter‐arrivées. Ces statistiques ont été générées avec le même problème que

précédemment et, tout dépendant du type de clients traités, un nombre variable de temps inter‐

arrivées a constitué l’ensemble de référence.

Figure A‐2.1– Taille des commandes pour un petit client avec 161,75

et 25,88

http://www.oracle.com/�

Annexe 31

Figure A‐2.2– Taille des commandes pour un client intermédiaire avec 408,81

et 40,88

Figure A‐2.3– Taille des commandes pour un grand client avec 579,92

et 40,59

Annexe 32

Figure A‐2.4– Temps inter‐arrivées pour un petit client avec 0,035

Figure A‐2.5– Temps inter‐arrivées pour un client intermédiaire avec 0,166

Annexe 33

Figure A‐2.6– Temps inter‐arrivées pour un grand client avec 0,263

Annexe 34

Annexe 3 Calibration des paramètres nécessaires à la recherche

Figure A‐3.1 – Analyse des réplications sur P1 par la méthode MAÉ avec n=4.

Figure A‐3.2 – Écart avec le meilleur coût de transport pour P1 par la méthode MAÉ avec n=4.

Annexe 35

max 1;0,75;0,5 250m max miles

Table A‐3.1 – Impact de la méthode d’application de la procédure Réaffecter.

max 1;0,75;0,5

250m max miles

Table A‐3.2– Impact de l’application ou non de la procédure Réaffecter globale.

Annexe 36

Stratégie i j k l

1 P2 a RG SD1

m Max Rho 1 Rho 2 Rho 3 Rho 4 Objectif Revenu net Entrepôt Transport100 1 0,75 0,5 0,25 17 899 324 23 484 274 1 675 039 3 909 911 100 1 0,85 0,7 - 17 899 169 23 484 910 1 675 039 3 910 702 100 1,25 1 - - 17 897 114 23 498 643 1 675 039 3 926 490 50 1 0,75 0,5 0,25 17 899 496 23 484 274 1 675 039 3 909 740 50 1 0,85 0,7 - 17 899 381 23 484 910 1 675 039 3 910 490 50 1,25 1 - - 17 896 646 23 498 643 1 675 039 3 926 959 300 1 0,75 0,5 0,25 17 900 487 23 496 921 1 675 039 3 921 395 300 1 0,85 0,7 - 17 899 875 23 496 921 1 675 039 3 922 007 300 1,25 1 - - 17 899 908 23 495 477 1 675 039 3 920 530 250 1 0,75 0,5 - 17 900 400 23 496 921 1 675 039 3 921 482

17 899 180 23 492 189 1 675 039 3 917 970 Moyenne Table A‐3.3– Paramètres de la procédure Réaffecter avec un échantillon aléatoire (n=6)

‐2,00

‐1,00

0,00

1,00

2,00

3,00

4,00

5,00

6,00

7,00

0 1 2 3 4 5 6 7 8 9 10

Profit espéréNombre de Scénarios

Éca

rt(%

)su

r l'é

valu

atio

n av

c n'

=10

0

Figure A‐3.3‐ Impact du nombre de scénarios sur l’évaluation des designs

Annexe 37

Annexe 4 Résultats détaillés des problèmes de moyenne (P2) et de grande taille (P3)

Table A‐4.1‐ Détail des statistiques obtenues avec P2 pour les trois stratégies

Table A‐4.2‐ Détail des statistiques obtenues avec P3 pour les trois stratégies

Documents

UNE MÉTAHEURISTIQUE DE RÉSOLUTION DE PROBLÈMES