Problème d'optimisation

[Tango716]

Bonjour à tous,

Je suis face à un problème d'optimisation et j'aimerais avoir vos avis sur des pistes de méthode algorithmique.

Supposons une ville selon un polygone avec à l'intérieur n points (adresses) selon deux paramètres (lat lon) ; Il faut déterminer des "hotspot" en sélectionnant les meilleurs points. Chaque adresse émets un signal de 300 m, donc le but de l'algorithme va être au fil des itérations de trouver la meilleure combinaison d'adresse tout en minimisant leur nombre.

Par exemple :

Chaque point a un signal d'une portée de 300m. Ainsi, si pour ce jeu d'adresses nous ajoutons les portées, on a :

(ce screenshot montre aussi le traitement de classification des points en hors champ afin d'adapter les aires)

De ce fait, si j'effectue un calcul simple de comparaison j'obtiens :

Avec :
Aire de la zone couverte: 0.0005055475481536275
Aire totale: 0.0007334658607563916
Couverture relative: 68.92584579632353
Temps de calcul: 96.36 sec

Ainsi, le projet est de prendre toutes les adresses d'une ville, puis au fur et à mesure trouver les meilleurs hotspots minimisés couvrant théoriquement 100% de l'aire de la zone.

J'espère que mes explications sont claires, de ce fait avez vous des pistes d'algorithmes à me proposer vers lesquels je pourrais m'orienter ? J'ai fait de l’optimisation et de la recherche opérationnelle mais j'avoue ne pas encore trouver chaussure à mon pied pour ce problème..

Je vous remercie par avance de votre aide !

[danyL]

bonjour
Comme personne ne te répond je me lance mais je ne suis spécialiste ni des algos ni des maths trop complexes

Les idées qui me viennent en lisant ton post :

- pour sélectionner le meilleur hot spot, ne pas accéder directement à la liste de tous les hots spots trouvés mais passer par une étape intermédiaire, un quadrillage grossier de la zone, par ex des cases de 100 m de côté, avec pour chaque case le nombre de hots spots positionnés dans cette case, et les informations de chaque hot spot (un identifiant, ses coordonnées, le nombre de connexions actuelles ...)

pour rechercher le meilleur hot spot pour un logement donné, calculer dans quelle case est ce logement, et chercher uniquement un hot spot dans la même case, ou si rien trouvé, dans les cases adjacentes qui ont le plus grand nombre de hots spots
peut etre répartir les connexions pour ne pas surcharger un hot spot alors que le voisin n'a aucune connexion

- lorsque l'algo de recherche a trouvé un hot spot pour un logement, ne pas réexécuter tout l'algo pour le logement suivant à 50 m du premier, car il aboutira aux mêmes résultats
par ex pour le n° 25 de la rue Casimir, si on trouve que la case juste au Nord contient de bons hots spots,
pour le n° 27 de la rue Casimir on aura la même conclusion

[Tango716]

Merci de ta proposition et de ton aide !

Effectivement, le quadrillage est une super idée. J'ai résolu le problème grâce à la géométrie.
En trouvant le centroid de la forme, j'ai ensuite quadrillé la zone pour créer le hotspot idéal et donc prendre le point le plus proche de cet idéal.




Cependant, si quelqu'un a une solution plus élégante, c'est avec plaisir.