Problèmes de couverture de zones irrégulières

Résumé du document

Ce projet est proposé et encadré par M. Gourdin, en partenariat avec Orange - France Télécom.
L'enseignement d'approfondissement "Problèmes de couverture de zones irrégulières" se rattache directement au secteur des télécommunications. En
effet, pour offrir un service de téléphonie mobile le plus étendu possible, ou pour diffuser une émission de radio dans une zone donnée, un opérateur doit assurer une couverture effcace du territoire. Il doit donc choisir p sites stratégiques pour y installer des antennes, avec les objectifs suivants : couvrir toute la zone,et utiliser des antennes de puissance minimale.
Le problème classique du p-centre permet de traiter la problématique idéale où l'on doit couvrir un ensemble discret de clients dans un plan par p disques
(centrés en des points particuliers, les sites d'émission), en s'assurant que le rayon maximal est minimal.

Extraits

[...] Choisir les variables zj pour minimiser la somme des aires revient donc à choisir les wj pour minimiser yj π wj . On remarque en particulier que la minimisation impose : (yj = (wj = Le critère choisi est donc : π wj Modication des contraintes On a toujours :ri,j = La contrainte devient : (ai Aj + (bi Bj i j J i j J z ri,j xi,j , wj (ri,j xi,j CHAPITRE 3. PROBLÈME DU P-CENTRE-SOMME Problème du p-centre-somme : couverture par des disques de rayons diérents Fig. [...]

[...] LE PROBLÈME DU P-CENTRE L'équation s'écrit alors : 2 A)2 + λ2 B)2 = za 2 et l'aire devient : π za /λ. On considère la distance : 9 ri,j = (ai Aj + λ2 (bi Bj Le problème des ellipses de mêmes dimensions est complexe : En eet, l'aire d'une ellipse dépend de deux variables za et λ, et il n'est pas possible de dissocier les contraintes relatives à ces variables : za (ai Aj + λ2 (bi Bj xi,j On décide donc d'étudier le cas où λ est un paramètre, ce qui revient à xer l'aplatissement de l'ellipse. [...]

[...] On trouve 3 zones délimitées par les droites d'équation π/(4 π) y π/(4 π) x π/(4 ou si y π/(4 et x. Le disque est préférable au carré, si x Ayant un nombre p de sites choisis, dans le cas général, on obtient donc un pavage optimal de la zone, si on accepte de panacher les disques et les carrés Comparaison disque/ellipse Le rayonnement circulaire est un cas particulier du rayonnement elliptique pour λ=1. Donc le cas de l'ellipse est préférable au disque pour le λ optimal. [...]

[...] Si on xe les sites choisis, on est capable de déterminer les cas où le disque est préférable au carré. Fig Comparaison des couvertures par des disques et des carrés Démonstration : Notons les deux cas limites : CHAPITRE 2. LE PROBLÈME DU P-CENTRE 17 le cercle de rayon optimal est circonscrit au carré de coté optimal (extérieur, passant par les sommets du carré), le cercle de rayon optimal est inscrit dans le carré (intérieur, passant par les milieux des côtés). [...]

[...] Pour s'en convaincre, il sut d'imaginer une répartition très simple: deux sites et et un unique client situé à équidistance de et Il y a alors deux solutions optimales, celle choisissant et celle choisissant Exemple Pour cette modélisation du problème, on étudie un exemple simple : 10 clients à couvrir, 5 sites possibles, un nombre p = 3 de sites à sélectionner. Fig Localisation des clients (croix) et des sites (triangles) Les clients sont représentés par des croix et les sites par des triangles. Les sites choisis sont les centres des cercles bleus et sont signalés par des triangles rouges. [...]