Discussion :

[doudoubapt]

Bonjour a tous, j'ai actuelement un probleme sous sas. J'ai deux bases SAS constituées comme tel:
Uen base A d'agences commerciales (plus ou moins 5000) avec
un identifiant agence (idag)
Les coordonées geographiques sous format X Y (Xag et Yag)

Une seconde base constituée des clients avec les clients (un gros million) avec
Leur identifiant idcl
leur coordonées geographiques (Xcl et Ycl)

La problematique est de determiner pour chaque client les deux agences les plus proches. J'ai essayé via un systeme de macros et je m'y suis cassé le nez dessus. je pense que le solution doit passer par des indexes, mais j'ai quelques problemes a les utiliser.
Merci d'avance.

[olivier.decourt]

Bonjour.
Commençons par une solution un peu rude, histoire de défricher le problème. On pourra toujours chercher à optimiser un peu ensuite.
L'idée est de travailler en SQL, pour faire plaisir à Green et pour avoir une combinaison de toutes les agences avec tous les clients (donc 5 milliards de lignes environ). On ne va pas créer une table physique avec ces combinaisons, plutôt une vue, qu'on retravaille ensuite dans une étape Data pour extraire les 2 premières lignes de chaque client.
On peut limiter un peu les frais (et les temps de calcul) avec un WHERE qui ne retient que les distances en-dessous d'une limite, genre 200 km par exemple. Mais bon, ce sera un peu long d'exécution.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
DATA work.clients ;
	INPUT idCli xcl ycl ;
CARDS ;
1 12 50
2 15 30
3 56 89
4 79 54
5 78 79
;
RUN ;
DATA work.agences ;
	INPUT idAgence $ x y ;
CARDS ;
A 20 20
B 38 12
C 100 45
;
RUN ;
PROC SQL ;
	CREATE VIEW work.distances AS
		SELECT *,
			   (x-xcl)**2+(y-ycl)**2 AS d2
		FROM work.clients,
			 work.agences
/*		WHERE CALCULATED d2 < 5000  */
		ORDER BY idCli, d2
	;
QUIT ;
DATA work.distances2 ;
	SET work.distances ;
	BY idCli ;
	IF FIRST.idCli THEN rang=0 ;
	rang+1 ;
	IF rang <= 2 THEN OUTPUT ;
RUN ;

On peut chercher des solutions optimisées par des index (je pense qu'indexer les variables de coordonnées géographiques ne doit pas faire de mal, quelle que soit la manière de programmer), avec un double SET aussi (qui permet de limiter par un WHERE la consultation des agences se trouvant dans un carré autour des coordonnées du client)... Les solutions sont nombreuses, reste juste à trouver le meilleur compromis complexité du code / rapidité d'exécution.
Olivier

[doudoubapt]

Merci pour cette solution, ca me semble tres interessant. je viens de regarder sur un petit echantillon, et le resultat est celui attendu. maintenant, je vais essayer plus tard (certainement pendant la nuit pour eviter de surcharger le serveur) sur la base entiere. j'ai simplement peur que l'espace memoire sature si toutes les combinaisons entre les deux tables sont tentées. je vous recontacterais sur ce point.
bonne journee.

[doudoubapt]

J'ai vu mon N+1 qui a apprecié la reponse que vous avez donné. merci pour l'aide.

[green_fr]

C'est assez étrange comme idée de chercher une agence la plus proche par des coordonnées géographiques. Sauf si on parles des agences pour les oiseaux...

Pour mieux expliquer ce que je voulais dire, prenons le cas des liaisons maritimes. Par la différence des coordonnées Odessa - Riga ne fait que 1300 km, i.e. Riga est beaucoup plus proche de Odessa que, disons, Porto (3300 km). Or, si on regarde la globe terrestre, on voit que le chemin Odessa - Riga passe bien à côté du Porto.

Pour les agences ça peut être pareil : une agence à 200 mètres sur une autre rive de la Seine est beaucoup plus loin qu'une autre, qui est à 600 mètres, mais sur la bonne rive.

[steelspirit]

Bonjour à tous,

Green a raison il ne faut pas oublier les autres paramètres géographiques ... ceci complexifie énormément l'algorithme ... on passe d'une recherche des plus proches voisins à de la recherche de chemin le plus court avec des paramètres de pondérations

Par ailleurs le produit cartésien proposé ci-dessus risque de prendre énormément de temps car on multiplie le nombre d'observations des 2 tables (5000*1000000) !

Je pense qu'il y a d'autres outils qui doivent faire ça tres bien comme Google Map ou ArcGis ???

[doudoubapt]

Effectivement, ca peut sembler bizare, mais dans l'ensemble, il s'agit simplement de dire :
Cher(e) monsieur (madame), c'est le le magasin de telle ou telle ville qui est le plus proche de chez vous!
Donc tant qu'il n'y a pas deux magasins dans la meme ville, ce n'est pas tres important. Ce que je ne veux surtout pas, c'est qu'on prospecte un marseillais en lui disant venez voir mon magasin de Nantes!
Un detail supplementaire, il y adeja suffisamnt de personnes dans la base (donc de calculs à effectuer), il serrait difficile de multiplier les temps de calcul en inserant les coordonnées routieres.
Neanmoins, merci pour la remarque.

[fafabzh6]

Green a raison il ne faut pas oublier les autres paramètres géographiques ... ceci complexifie énormément l'algorithme ... on passe d'une recherche des plus proches voisins à de la recherche de chemin le plus court avec des paramètres de pondérations

Pour cette question la Recherche Opérationnelle apporte de très bonnes solutions.

[green_fr]

Oui, effectivement, s'il s'agit de la France (suffisamment petite pour être considérée comme plate) au niveau nationale (suffisamment grande pour laisser tomber les particularités du réseau routier) ça peut marcher.

Sinon, on peut juste sortir la liste des magasins par département. Et s'il n'y a pas de magasin dans un des départements - renseigner manuellement le magasin "le plus proche pour tout le département". La précision reste à peu près la même, mais le temps de calculs est quasi nul.

Mais c'est vrai qu'on est éloigné du sujet de SAS :-)

[doudoubapt]

la question ne se pose pas toujours pour des magasins. En general, il s'agit surtout de determiner la localité la plus proche, mais dans un grand nombre de cas, que l'on a, il y a des problematiques où les personnes d'un departement sont plus proches d'un point d'acceuil situé dans un autre departement
et effectivement, on est eloigné de sas, mais ca replace le contexte