Chapitre 2
Problèmes de localisation
Objectifs pédagogiques
• Connaitre l’Importance de la localisation
• Les différents problème de localisation
• Modélisation des problèmes de localisation
• Méthodes de résolutions des problèmes de
localisation
• Notions de couverture
Importance de la localisation 1/2
• Un réseau de transport bien conçu, impliquera une
économie importante des ressources. Tout
transporteur est amené à bien prendre ces décisions
de localisation à cause de:
– les marchés sont plus étendus, mais souvent avec une
clientèle dispersée,
– les livraisons à distance sont plus faciles, grâce à
l'ouverture des frontières,
– les sites possibles sont donc plus nombreux
• La localisation est un problème complexe, crucial à
cause des enjeux financiers, et avec des compromis à
trouver
Importance de la localisation 2/2
• Exemple de choix
– Installation dans un pays à bas coût de main d‘œuvre
(Low cost contries LCC):
• augmentation des coûts d'expédition si on est loin des zones
de consommation
• Manque de main d’œuvre qualifiée
• …
– Installation près des consommateurs :
• Augmentation des coûts d'approvisionnement de la matière
première exotiques (bois, minerais).
• Main d’œuvre chère
• …
Classification et exemples 1/8
• Objectif : trouver l’emplacement optimal
d’installations (usines etc.) sur un ensemble
de sites possibles, pour :
– minimiser le nombre d’installations pour couvrir
les demandes,
– ou maximiser la demande couverte avec un
nombre fixe d'installations,
– ou minimiser les coûts (construction,
fonctionnement, charges, coûts de livraison aux
clients, etc).
Classification et exemples 2/8
• Problèmes à résoudre:
– combien d'installations faut-il placer ?
– où doit-on placer chaque installation ?
– comment affecter les demandes aux sites créés ?
• Problèmes associés
– Transports (placement d'entrepôts, de hubs)
– Placement d'unités de production,
– Logistique de secours (interventions, ambulances),
– Télécommunications (relais TV, BTS), etc.
– Le centres hospitaliers
– Les écoles
– Les centres de polices
Classification et exemples 3/8
• Critères de classification en localisation
• Localisation planaire, discrète, et sur un réseau
• Planaire ou continue : les sites peuvent être
partout dans le plan (relais de TV).
• Discrète : nombre fini de sites, et on connaît la
matrice des "distances" au sens large entre sites
ou distancier: en km, en temps, en coût, etc.
• Sur un réseau : localisation discrète sur les nœuds
d'un réseau.
Classification et exemples 4/8
• Type de graphe : problèmes un peu plus faciles
sur certains types de réseau. Exemple: stations de
pompage sur un arbre de pipe-lines.
• Nombre de sites à localiser. Peut être une variable
du de décision ou une donnée.
– Le cas particulier d'un seul site est facile (méthodes du
barycentre).
• Problèmes statiques ou dynamiques.
– Pour les problèmes dynamiques:
• les paramètres et les variables évoluent dans le temps.
Classification et exemples 5/8
• Problèmes déterministes ou probabilistes.
– Paramètres connus (demande connues, …)
– Paramètres variables dans le cas probabiliste (modèles
probabilistes, plus complexes).
• Problèmes mono ou multi-produits. Quand la nature
des produits n’est pas importante (transport en vrac),
on se ramène à un produit fictif pour simplifier:
palettes, m3 de liquide…
• Secteur privé ou public.
– Le privé maximise le profit ou minimise le coût, et la même
entité paie les coûts d'installation puis de fonctionnement.
– Secteur public: facilité pour l’acquisition du terrain
Classification et exemples 6/8
• Public : notion de service plus importante.
L’entité ne paie souvent que l’installation ou le
fonctionnement.
• Objectifs simples ou multiples. Si objectifs
antagonistes, il faut souvent une approche
d'optimisation multicritère.
• Capacité finie ou infinie. La capacité d’un site est
le plus souvent limitée. Parfois elle est « infinie »
(= suffisante): un relais de TV couvre tous les
habitants de sa zone.
Classification et exemples 7/8
• Affectation des demandes. Chaque demande est traitée
par un site (assignment) ou par plusieurs (allocation).
Second cas fréquent si sites de capacité finie
• Problèmes à un ou plusieurs niveaux.
– Exemple : réseaux de distribu on à 1 étage (usines →
clients) ou 2 (usines→ entrepôts (hub)→ clients).
• Installations indésirables. Placement des installations
près des clients, sauf les "indésirables« .
– Décharge loin d'une ville → coût de transport élevé
• d'où choix entre le coût de transport et nb de personnes affectées
par la décharge
• La recherche d’un compromis entre plusieurs objectifs
– Optimisation multi-objective
Classification et exemples 8/8
• Interactions entre sites
– Deux sites intéressants pour un hypermarché
peuvent desservir des zones en commun:
• ouvrir les 2 sites en même temps n’est pas souhaitable.
• Problème du choix entre les deux sites
– Les interactions entre sites voisins compliquent
beaucoup les problèmes.
• BTS (problème d’interférence)
Localisation d’une installation 1/3
• Scores charge-distance (load-distance scores) Données
– m sites possibles pour une nouvelle installation,
– n entités (clients, fournisseurs, etc.) à desservir,
– mesure simple de « charge » Lj pour chaque entité j. A
définir :
• tonnage entrant ou sortant,
• nombre de déplacements/semaine,
• patients venant consulter, etc.
– distances dij entre tout site i et toute entité j.
• Objectif: choisir un site i* minimisant un score estimant
le travail de déplacement des charges.
Localisation d’une installation 2/3
• Méthode 1:
– calcul pour tout site i d'un score charge-distance ld(i),
– puis choix du site de score minimal.
– Exemple : Localisation d’un dispensaire dans une ville.
– entités : quartiers.
– charges: nombre d'habitants (patients potentiels).
– distances : du centre des secteurs aux sites possibles.
Localisation d’une installation 3/3
• Méthode 2: le Barycentre
Pour la localisation continue (= non discrète).
– on connaît les coordonnées xj et yj de l'entité j.
– on cherche les coordonnées (x*,y*) de l’installation.
– choix évident : centre de gravité des charges
Le lieu obtenu doit souvent être ajusté. La
localisation planaire de plusieurs installations est
plus difficile (PNL).
Exemple
• Une ville souhaite installer un nouveau dispensaire pour desservir 7 quartiers dont les
informations sont présentées par le tableau suivant: avec des coordonnées en km et le
nombre d’habitants en mil habitants.
• Le quadrillage des rues des villes US impose l'utilisation de la distance "Manhattan
• Deux terrains sont disponibles au centre des quartiers C et F. Déterminer le meilleur site en
utilisant des scores charge × distance en 103 habitants × km et la norme L1. Comparer ensuite
avec une localisation "continue" basée sur le centre de gravité (faire dès le début une
représentation graphique).
Solution
Problèmes de couverture 1/21
• Problème de couverture totale
• Données :
– m points de demande ou "clients" (indexés par i)
– n sites potentiels (indexés par j)
– Dc distance de couverture (distance max de service)
– booléens aij =1 ssi i est couvert par le site j (distance ≤
Dc).
– cj coût d'ouverture du site j.
Objectif: déterminer les sites à ouvrir pour couvrir toutes
les demandes, avec un coût total minimal.
Problèmes de couverture 2/21
• NP-difficile. Formulable par un PL en 0-1 :
(1) Min c j x j
j 1, n
(2) i 1...m : aij x j 1
j 1, n
(3) j 1...n : x j 0,1
(4) ...
– (3) Xj les variables de décisions (0-1, 1 si le site j est ouvert)
– (1) la fonction-objectif à minimiser (coût des sites ouverts)
– (2) contraintes, tout client i couvert par au moins un site
Problèmes de couverture 3/21
• Ecriture matricielle:
– A : matrice binaire m×n des aij
– 1I : vecteur formé de m "1".
• Min c.x
• A.x ≥ 1I
• x {0,1} n
• Explication : une colonne j de A est un m-vecteur
binaire codant le sous-ensemble des clients
couverts par le site j.
– Il faut choisir un sous-ensemble de colonnes j (xj = 1)
dans lequel chaque client apparaît au moins une fois.
Problèmes de couverture 4/21
• Techniques de réduction de taille :
– soit Li la ligne i de A et Cj la colonne j.
– par convention, Ck ≥ Cj aik ≥ aij pour tout i.
– un site k domine un site j si ck ≤ cj et Ck ≥ Cj
– k couvre tous les clients de j sans coûter plus cher!
– donc on peut éliminer la colonne j et forcer xj à prendre la
valeur 0.
Problèmes de couverture 5/21
• Techniques de réduction (suite) :
Moins évident : un client k domine un client i ssi Lk ≤ Li. Tout site j
qui couvre k (akj = 1) couvre aussi i. Si la contrainte (2) pour k
est vérifiée, celle pour i aussi. On peut donc supprimer la ligne
(contrainte) i de A.
Problèmes de couverture 6/21
• Techniques de réduction (suite )
• Ouverture évidente
• Si une ligne i de A a un seul 1, en aij, alors seul le site j couvre
le client i. On peut forcer xj à prendre la valeur 1 et supprimer
toute autre contrainte k satisfaite (telle que akj = 1).
• Utilisation des réductions
– teste des lignes et colonnes en ordre quelconque
– si on trouve des réductions, on doit tout retester
– en effet, une réduction peut en créer d'autres
– stop quand on ne trouve plus de réductions.
Problèmes de couverture 7/21
• Exemple avec m = n = 6 et Dc = 12 :
Problèmes de couverture 8/21
• Réductions :
– Site A dominé par B et F par C : on force XA = XF = 0.
– Seul C couvre F : XC = 1 et suppression des contraintes satisfaites
(2),(3),(5),(6).
– (1) et (4), si A couvert alors D aussi : supprimer (4).
• Après réduction, le PL devient :
• 2 optima à deux sites ouverts: Xb=Xc = 1 ou Xc = Xd =1
Problèmes de couverture 9/21
• Problème de couverture maximale
• Pb de couverture totale parfois inadapté :
– trop de sites à ouvrir
– clients de même poids, même si demandes faibles.
• Couverture maximale : maximiser la demande totale
couverte, avec un nombre limité de sites ouverts.
• NP-difficile*. Paramètres et variables additionnels :
– p nombre max. de sites à ouvrir (donné),
– di demande du point i (donnée)
– zi variable 0-1 indiquant si le client i est couvert ou non.
Problèmes de couverture 10/21
• On a encore une formulation sous forme de PL
en 0-1:
Problèmes de couverture 11/21
• équation (1): demande totale satisfaite, à maximiser.
• Contraintes (2) : comment régler les zi ?
• Par définition, zi = 1 client i couvert :
• Contrainte (3): ouverture d’au plus p sites, on peut
avoir des clients non couverts
• Si moins de p sites suffisent, la fonction-objectif sera
égale à la demande totale.
Problèmes de couverture 12/21
• Résolution des problèmes de couverture
• Avec un logiciel de programmation linéaire
– PL en 0-1 donc en nombres entiers
– algorithme du simplexe inutilisable.
– méthodes arborescentes (xj = 0 ou xj = 1)+réductions
– exemple de problème gérable : 100 clients, 20 sites.
• Note : les problèmes de partitionnement (A.x = 1)
sont encore plus durs car pas toujours faisables.
Exemple : découpage électoral, secteurs
commerciaux.
Problèmes de couverture 13/21
• Heuristiques gloutonnes
PL trop longs à résoudre pour les grands problèmes.
Des heuristiques sont alors nécessaires.
• Heuristiques gloutonnes (les plus simples)
– suite de décisions définitives (sans retours en arrière)
– choix le plus avantageux à chaque étape
– selon un certain critère (à définir)
– exemple, Plus Proche Voisin pour le TSP.
Problèmes de couverture 14/21
• Heuristique gloutonne de Chvàtal (couverture
totale)
• Ouvrir le site de + faible coût par nouveau client
non couvert
• Cout := 0 // coût total des sites ouverts
• Ouverts := // ensemble des sites ouverts
• Repeat
• j := site libre de coût moyen minimal par nouveaux points couvert : c(j)
/ nb de nouveaux points couverts.
• Ajouter j à Ouverts
• Cout := Cout + c(j)
• enlever du pb le site j et les nouveaux points couverts
• Until (couverture complète).
Problèmes de couverture 15/21
• Heuristique analogue pour la couverture maximale :
• site augmentant le plus la demande totale couverte.
• Ouverts := // ensemble des sites ouverts
• NbOuverts := 0 // nombre de sites ouverts
• QteCouverte := 0 // quantité totale couverte
• Repeat
• j := site libre augmentant QteCouverte au maximum
• NbOuverts := NbOuverts + 1
• Ajouter j à Ouverts
• QteCouverte := QteCouverte +somme des nouvelles demandes couvertes
• Until (NbOuverts = p) ou (toutes les demandes sont satisfaites).
• p insuffisant : NbOuverts = p et QteCouverte < demande totale.
• p suffisant : NbOuverts < p, QteCouverte = demande totale.
Problèmes de couverture 16/21
• Exemple d’application
Problèmes de couverture 17/21
• Recherches locales (local search)
• Principes :
– heuristiques pour l'optimisation combinatoire
– amélioration progressive d'une solution initiale S,
par exemple donnée par une heuristique
gloutonne
– basées sur un "petit" sous-ensemble de solutions
V(S), appelé voisinage de S (neighborhood, N(S)).
– V(S) est défini implicitement par une
transformation simple de S.
Problèmes de couverture 18/21
• Chercher une solution initiale S
• Repeat
– Construire un voisinage N(S)
– chercher une meilleure solution S’
dans N(S)
– si S' trouvée alors S := S'
• Until S' non trouvée
• Deux versions sont possibles pour
le choix de la meilleure solution.
A chaque itération on prend :
– soit la 1ère solution S' trouvée qui
améliore S
– soit la meilleure solution S' du
voisinage.
• S optimum local pour le type de
voisinage choisi
Problèmes de couverture 19/21
• 2 vues imagées, solution S initiale, S' finale, S*
optimale
Problèmes de couverture 20/21
• Exemple de voisinage pour la couverture maximale :
• tester toutes les façons de remplacer un site ouvert par un
autre actuellement fermé, p.(n-p) solutions à tester.
Exercice
• On considère le problème de couverture totale défini par une
matrice binaire quelconque A, mn. m points de demandes
(clients), n sites potentiels.
• a) Rappeler très brièvement en termes d'ensembles la
signification des lignes et colonnes de A. A quelle condition existe-t-
il des solutions?
• b) En supposant le problème réalisable, que signifie le fait que la
somme d'une ligne i soit égale à un entier kn? Que la somme
d'une colonne j soit égale à un entier k m? Que peut-on conclure
si une colonne j ne contient pas de zéros? Si toute paire de
colonnes n'a aucune ligne avec deux 1?
• c) Simplifier au maximum la matrice suivante en précisant les
éliminations (quelle ligne ou colonne est dominée par quelle autre).
Puis résoudre optimalement le problème en précisant les sites
ouverts et les sites qui couvrent chaque client.
1 2 3 4 5 6
1 1 0 1 0 0 1
2 0 1 0 1 0 1
3 0 1 1 0 1 0
4 0 1 0 0 0 0
5 1 0 1 1 1 1
Exercice 3
• Pendant la conception de la ville de Tamasna, les responsables ont prévu
qu’elle aura M quartiers. Le nombre d’enfants estimé pour chaque
quartier i est donné par hi, et on a prévu l’ouverture de n écoles au
maximum dans cette ville pour scolariser ses enfants (n<=m). La distance
entre deux quartiers i et j est donnée par dij. Une école ouverte ne peut
couvrir qu’au maximum k quartiers dont le quartier qui l’abrite. Les élèves
d’un quartier doivent être affectés à la même école. Pour cette première
version on considère qu’on n’a pas de contrainte concernant la distance de
couverture.
• Questions :
– Modéliser le problème de localisation des écoles sous la forme d’un
programme linéaire
– On suppose maintenant que M=6, n=6 et k=3. Les autres données du
problème sont présentées dans le tableau 1. Modéliser ce problème sous la
forme d’un problème de couverture totale. Résoudre ce problème en utilisant
la méthode de chvatal, la distance de couverture est de 12.
Exercice 3
Q1 Q2 Q3 Q4 Q5 Q6
Q1 0 8 15 10 24 27
Q2 0 12 7 16 33
Q3 0 19 9 11
Q4 0 11 17
Q5 0 13
Q6 0
Nb élèves 120 135 95 80 105 115
Coût 8 7 8.5 6 9 5.5
d’installation
P-centre
• L’objectif de ce problème linéaire est de
minimiser la distance maximale entre un client
et le centre auquel il est rattaché, et non plus
la somme des distances. Les contraintes
restent cependant les mêmes. Dans la
formulation de ce problème, il n’y a alors que
la fonction à minimiser qui change. La
distance maximale à minimiser est
z d ij xij i
P-centre
• On considère que tous les clients sont accessibles (pas de
distance de couverture) mais on tient compte des distances.
• Problème des p-centres (NP-difficile)
• Fréquents en logistique de secours. Données :
– m clients à servir (indice i), sans distance de couverture,
– n sites (indice j) mais on peut ouvrir p sites au maximum,
– distances dij au sens large entre nœuds et sites.
• Objectif
• Placer les sites en minimisant la distance maximale aux
clients.
• Exemple : placer 4 casernes de pompiers dans une ville pour
minimiser le temps d'intervention sur un incendie.
P-centres
• PL dit "mixte" :
variables entières et
réelles.
• Variables de décision :
– xj =1 si site j choisi,
– yij =1 si i affecté au site j.
• Variable réelle z :
– distance maxi
d’intervention.
p-médians 3/7
• PL plus compliqué que les précédents !
• Facile : (1) objectif à minimiser, (2) chaque nœud est affecté
à un site, (3) p sites ouverts, (6)(7)(8) définition des
variables.
• Chaque contrainte (4) traduit l'implication : si le site j
fermé, aucun client ne peut lui être affecté.
• Contraintes (5) minimise la distance maximale
d'intervention :
– calcul du maximum des dij tels que yij = 1*.
– on linéarise en bornant les distances d’intervention par z.
– cette borne z va être compressée par la minimisation.
– à l’optimum, z sera égal à la distance d’intervention maximale.
p-médians 4/7
• Le problème p-médian a pour objectif de minimiser la
somme totale des coûts de distribution entre les clients
et leur site de rattachement ( le coût totale du
transport). C’est alors un problème linéaire et pour
formuler ce problème, il faut tout d’abord expliciter les
contraintes sous forme d’équations ou inéquations. Ici
sont explicitées des cas généraux.
– On veut que chaque client i soit affecté à un seul site j
– Tout client i affecté ne peut l’être que si le site j existe et
est ouvert xij <= yj
– Ensuite, on verifie l’ouverture exacte de p sites
– En fin, (contraintes d’intégrité) x et y doivent être des
entiers
p-médians
• PL en 0-1 plus simple :
– mêmes variables binaires
– (1) distance moyenne
– (2) clients affectés à un site
– (3) nombre de sites à ouvrir
– (4) pas de clients pour un site
fermé
– qi: la quantité demandée par le
client i
– dij: le côut de transport unitaire
entre le centre j et le client i
• Note :
• La méthode des scores charge
distance traite le cas p = 1.
P-centres et p-médians 6/7
• Une heuristique très efficace valable aussi dans le cas
continu :
– ouvrir p sites au hasard
– REPEAT
– affecter chaque client au plus proche site ouvert
– on obtient des clusters (un site + ses clients)
– calculer le meilleur site dans chaque cluster
– UNTIL l'ensemble des sites ne change pas.
• Le calcul du meilleur site dans chaque cluster se fait :
– avec la méthode des scores, si la liste de sites est finie
– en calculant un centre de gravité, si localisation continue.
P-centres et p-médians 7/7
Pb de localisation d’entrepôts 1/4
• En anglais location-allocation problems :
– déterminer quels entrepôts ouvrir (locate).
– allouer les clients aux entrepôts (allocate).
– un client peut être livré par plusieurs entrepôts !
– minimiser coût des entrepôts + coûts de transport.
• Cas avec capacités d'entrepôts "infinies" et "un seul"
produit ou single-commodity, uncapacitated facility
location problem :
• m sites (indice i) et n clients (indice j)
– fi coût fixe d'ouverture du site i
– dj demande du client j, cij coût unitaire de transport de i à j
– yi variable binaire d’ouverture
– xij quantité livrée par le site i au client j.
Pb de localisation d’entrepôts 2/4
• PL mixte :
• (1) coût total, à minimiser
• (2) demandes satisfaites
• (3) : M grande constante
> 0.
• Un dépôt fermé ne livre
rien.
• Un dépôt ouvert peut ne
rien livrer mais
l'optimisation va le
fermer!
Pb de localisation d’entrepôts 3/4
• Problème stratégique (long terme) et macroscopique
(agrégé) :
– Un "client" peut être une ville avec une demande annuelle
agrégée et estimée.
– Mélange de coûts ponctuels d’ouverture et coûts de
transport quotidiens? En fait fi peut être un coût
d’exploitation quotidien.
– Sites de capacité infinie? Les sites peuvent être des
terrains libres : on construira les sites ouverts en fonction
des quantités livrées dans la solution. Borner la capacité
des sites*.
– Un seul produit? En fait, on veut dire que les produits sont
indiscernables pour le transport (palettes, containers).
Pb de localisation d’entrepôts 4/4
• Grâce aux capacités infinies, chaque client
peut toujours être affecté à un seul site (le
moins coûteux).
• On peut étendre le modèle à des capacités
limitées : certains clients doivent alors être
livrés à partir de plusieurs sites.
• On peut aussi généraliser à plusieurs produits.
