Upload
others
View
2
Download
0
Embed Size (px)
Citation preview
1
Problèmes de localisation
« Facility location problems »
2
Décisions à prendre ?
Quel est le rôle ou la mission d’un site?
Localisation des sites : Où?
Allocation de la capacité : Combien de capacité doit-on allouer à
chaque site?
Allocation (affectation) de l’offre et de la demande :
• Quels marchés devraient être desservis par chaque entrepôt?
• Quelles usines devraient desservir chaque entrepôt?
• Quels fournisseurs devraient desservir chaque usine?
Fournisseurs Usines CD Clients
3
Facteurs qui influencent la décision
4
Facteurs qui influencent la décision
Stratégiques et technologiques (proximité aux marchés,
fournisseurs, ressources, clusters,…)
Politique et Macroéconomique (réglementation, Impôts,
taxes, tarifs, …)
Infrastructure (gaz, électricité, eau, communication,
transport, ….)
….
Coûts associés à la logistique et à l’opération d’un site
5
Facteurs qui influencent la décision
Exemple :
6
Types de problèmes
Single-Facility Location Problems: détermination optimale de la
localisation d’un site.
Multi-Facility Location Problems : recherche simultanée de la
localisation de plusieurs sites (problème de localisation / allocation)
• Center of gravity method
• The p-Median Problem
• SS-Capacitated Facility Location Problem
• MS-Capacitated Facility Location Problem
• Multi-Commodity Network Design
7
Localisation d’un site :
Méthode du barycentre
Exemple: Localisation d’un entrepôt / usine
m points à desservir;
Chaque point i à une localisation (xi,yi) et une demande
(ou poids) wi;
Distance Euclidienne (carré):
Min TC = Σi wi [(x-xi)2 + (y-yi)
2 ]
8
Localisation d’un site :
Méthode du barycentre
Exemple: Localisation d’un entrepôt / usine
m points à desservir;
Chaque point i à une localisation (xi,yi) et une demande
(ou poids) wi;
Distance Euclidienne (carré):
Min TC = Σi wi [(x-xi)2 + (y-yi)
2 ]
9
Région (Xi-Yi) Wi
A (11-22) 15
B (10-7) 10
C (4-1) 12
D (3-6) 4
Exemple
10
Région (Xi-Yi) Wi WiXi WiYi
A (11-22) 15 165 330
B (10-7) 10 100 70
C (4-1) 12 48 12
D (3-6) 4 12 24
Total 41 325 436
10.641
436 ; 7.9
41
325
i
ii
c.g.
i
ii
c.g.
W
YWY
W
XWX
Exemple
11
p-Median
p entrepôts (usines) à localiser sur un ensemble de m sites potentiels
pour livrer n clients.
Chaque client est livré par un seul entrepôt.
Pas de coût fixe;
Pas de contraintes de capacités.
cij : le coût de transport de l’entrepôt j au client i.
12
p-Median
p entrepôts (usines) à localiser sur un ensemble de m sites potentiels
pour livrer n clients.
Chaque client est livré par un seul entrepôt
Pas de coût fixe;
Pas de contraintes de capacités.
cij : le coût de transport de l’entrepôt j au client i.
sinon.,0
choisie,est on localisati la si,1 jy j
sinon.,0
i,client ledessert on localisati la si,1 jxij
13
p-Median
mjy
mj
nix
yx
Py
nix
xc
j
ij
jij
m
j
j
m
j
ij
n
i
m
j
ijij
,..,11,0
..,,1
..,,11,0
,
,
..,,1,1
:S.t
zMinimiser
1
1
1 1
14
SS-Capacitated Facilty Location
Sélectionner un ensemble d’entrepôts à localiser sur m sites
potentiels pour desservir n clients.
Il existe un coût fixe fj pour la localisation de l’entrepôt j et celui-ci a
une capacité maximale kj
di : la demande du client i
cij : le coût de transport de l’entrepôt j au client i.
15
SS-Capacitated Facilty Location
Sélectionner un ensemble d’entrepôts à localiser sur m sites
potentiels pour desservir n clients.
Il existe un coût fixe fj pour la localisation de l’entrepôt j et celui-ci a
une capacité maximale kj
di : la demande du client i
cij : le coût de transport de l’entrepôt j au client i.
sinon.,0
choisie,est on localisati la si,1 jy j
sinon.,0
i,client ledessert on localisati la si,1 jxij
16
SS-Capacitated Facilty Location
mjy
mj
nix
nix
mjykxd
xcyf
j
ij
m
j
ij
n
i
jjiji
m
j
n
i
ijijj
m
j
j
..,,11ou 0
..,,1
..,,11ou 0
..,,1,1
..,,1,
:S.t
zMinimiser
1
1
1 11
17
Mutli-Source Capacitated Facility Location
Sélectionner un ensemble d’entrepôts (usines) à localiser sur m sites
potentiels pour livrer n clients.
Il existe un coût fixe fj pour la localisation de l’entrepôt (usine) j et
celui-ci a une capacité maximale kj
di : la demande du client i
cij : le coût de transport de l’entrepôt j au client i.
18
Mutli-Source Capacitated Facility Location
Sélectionner un ensemble d’entrepôts à localiser sur m sites
potentiels pour livrer n clients.
Il existe un coût fixe fj pour la localisation de l’entrepôt j et celui-ci a
une capacité maximale kj
di : la demande du client i
cij : le coût de transport de l’entrepôt j au client i.
Notons la fraction (pourcentage) de la demande du client i livrée à
partir de l’entrepôt (usine) j
Et
sinon.,0
choisie,est on localisati la si,1 jy j
ijx
19
mjy
mj
nix
nix
mjykxd
xcyf
j
ij
m
j
ij
n
i
jjiji
m
j
n
i
ijijj
m
j
j
..,,11ou 0
..,,1
..,,11 0
..,,1,1
..,,1,
:S.t
zMinimiser
1
1
1 11
Mutli-Source Capacitated Facility Location
20
Il existe une formulation forte du problème de localisation sans
capacités (uncapacitated facility location problem) lorsque la
capacité des entrepôts n’entre pas en jeu, alors la contrainte :
peut s’écrire
n
i
jjiji ykxd1
nimjyx jij ,..,1 ..,,1,
Mutli-Source Capacitated Facility Location
21
• C’est le problème dit de localisation simple
(formulation forte) :
njy
mix
yx
njx
xcyf
i
ij
iij
m
i
ij
m
i
n
j
ijiji
m
i
i
,,11ou 0
,,1,10
,0
,,1,1
:S.t
zMin
1
1 11
(FF):
22
On peut réduire le nombre de contrainte en adoptant une
formulation plus faible du problème de localisation simple.
En sommant sur les indices j de la contrainte
Elle devient
,0 iij yx
01
i
n
j
ij nyx
23
C’est la formulation faible du problème de localisation simple:
njy
mix
minyx
njx
xcyfz
i
ij
n
j
iij
m
i
ij
m
i
m
i
n
j
ijijii
,,11ou 0
,,110
,,1,0
,,1,1:(Ff)
:S.t
Min
1
1
1 1 1
24
Modèle pour l’allocation
de la demande (multi sources)
Quel marché sera desservi par quel site?
Quelles sont les sources pour un site?
– m clients ou marchés potentiels
– n sites potentiels
– Dj : demande du client j
– Ki : capacité de l’usine i
25
Modèle pour l’allocation
de la demande (multi sources)
0
..
1
1
1 1
x
Kx
Dx
xc
ij
i
m
jij
j
n
iij
n
i
m
jijij
ts
Min
xij = Qté livrée du site i au client j
26
Localisation multi sites
et allocation multi sources
coût fixe fi pour la localisation i
Max k sites parmi n
27
Localisation multi sites
et allocation multi sources
yi = 1 si le site (ou usine) i est utilisé, 0 si non
xij = Qté transportée du site i au client j
28
Localisation multi sites
et allocation multi sources
1 1 1
1
1
1
. .
; {0,1}
n n m
ij iji ii i j
n
jiji
m
iij ij
m
i ii
Min
s t
k
f y c x
x D
yx K
y y
29
Localisation simultanée d’usines et de
centres de distribution
Fournisseurs Usines CDs Clients
30
Localisation simultanée d’usines et de
centres de distribution
• j= 1,..,m clients ou marchés
• i=1,..,n sites potentiels pour les usines
• h=1,..,l fournisseurs potentiels
• e=1,..,w sites potentiels pour les CDs
• Dj : demande annuelle pour le client j
• Ki : capacité de l’usine i
• Sh : Capacité du fournisseur h
• We : Capacité du CD e
• Fi : Coût fixe de l’usine i
• Fe : Coût fixe du CD e
• Chi : coût de transport d’une unité du fournisseur h à l’usine i
• Cie : coût de production et de transport d’un produit du site i au CD e
• Cek : coût de transport d’un produit du CD e au client k
31
Localisation simultanée d’usines et de
centres de distribution
• j= 1,..,m clients ou marchés
• i=1,..,n sites potentiels pour les usines
• h=1,..,l fournisseurs potentiels
• e=1,..,w sites potentiels pour les CD
• Dj – demande annuelle pour le client j
• Ki – capacité de l’usine i
• Sh – Capacité du fournisseur h
• We – Capacité du CD e
• Fi – Coût fixe de l’usine i
• Fe – Coût fixe du CD e
• Chi – coût de transport d’une unité du fournisseur h à l’usine i
• Cie – coût de production et de transport d’un produit du site i au CD e
• Cek - coût de transport d’un produit du CD e au client k
• Variables de décision:– yi =1 si l’usine i est utilisée, 0
autrement
– ze =1si le CD e est utilisé, 0 autrement
– xcej : qté transportée du CD e
au client j
– xbie : qté transportée de l’usine
i au CD e
– xahi : qté transportée du
fournisseur h à l’usine i
32
Localisation simultanée d’usines et de
centres de distribution
1 1 1 1 1 1 1 1
1
1 1
1
1
. t
(1) , pour 1,...
(2) 0, pour 1,...
(3) , pour 1,...,
(4)
hi ie ej
hi
hi ie
ie
ie
n w l n n w w ma b c
i i e e hi ie ej
i e h i i e e j
na
h
i
l wa b
h e
wb
i ì
e
b
i
Min f y f z c x c x c x
s
x S h l
x x i n
x K y i n
x
1
1
1
0, pour e 1,...
(5) , pour e 1,...,
(6) , pour j 1,...,
(7) , z 0,1
ej
ej
ej
n mc
j
mc
e e
j
wc
j
e
i e
x w
x W z w
x D m
y
33
Quelques astuces pour la modélisation
• maximisation des profits• Soit rj le revenu associé au produit dans le marché j
• Traitement de différent modes de transport
34
Quelques astuces pour la modélisation
• maximisation des profits• Soit rj le revenu associé au produit dans le marché j
• La fonction objectif devient
• Il faut aussi modifier l’équation de la demande
• Traitement de différent modes de transport– Utiliser une variable différente pour chaque mode
• x1ij, x
2ij
1 1 1 1 1
m n n n m
j ij ij iji ij i i i j
Max r x f y c x
1
pour 1,...n
ij j
i
x D j m
35
Problème d’allocation pure :
cas multi-produits
On veut distribuer des produits p: 1.. P à des points de demandes d :
1..D connus, soit : Directement à partir des sources d’approvisionnement
(fournisseurs, usines) ou par l’intermédiaire des entrepôts.
Chaque produit provient d’une source d’approvisionnement unique
qui a une capacité qui dépasse largement les besoins
Les entrepôts peuvent distribuer plusieurs produits et ont une
capacité limitée
Objectif :
• Déterminer quels produits et quels points de demande à affecter à chaque
entrepôt.
• Déterminer les flux annuels de marchandises entre les entrepôts et les
sources d’approvisionnements / clients
36
Formulation mathématique
37
Formulation mathématique
38
Coût unitaire de transport de
source d’approvisionnement
de P1 à l’entrepôt 1
Coût unitaire d’entreposage
dans l’entrepôt 1
Exemple
39
Exemple
40
Problème de localisation – allocation:
cas multi-produits
Exemple :
– plusieurs produits (ou familles de produits) proviennent de sources
uniques
– Ces produits doivent être acheminés vers des zones de
consommation par le biais de chaînes d'approvisionnement qui
partent d’une usine et qui passent par un entrepôt
– Certaines usines et entrepôts existent déjà, mais on a identifié des
sites potentiels pour l’implantation de nouvelles installations
– Objectif :
• Choisir une chaîne pour l'approvisionnement de chaque produit dans
chaque zone
• Et déterminer quels usines/entrepôts devraient être ouverts, ou fermés
41
Problème de localisation – allocation:
cas multi-produits
42
Formulation mathématique
43
Formulation mathématique
44
Variables de décisions
Formulation mathématique
45
Exemple
Usine
potentielle
Usine
potentielle
Entrepôt
potentiel
46
Exemple