Localisation commerciale multiple: une application du traitement du signal et du modèle p-médian au développement d'un réseau de magasins de produits biologiques

IntroductionThe large-scale reorganization of distribution networks these last years and the fluctuating and unforeseeable economic situation reminds that even large companies is not fixed but remains subjected to the pitiless law of competition. Thus, dozens of large firms and hundreds of subsidiary companies were forced to restructure their production mode in industrial sectors and their distribution network for those whose activity is in the distribution of goods or services field. For companies managing several hundreds or even thousands of outlets, the reorganization of a network proves to be a hard task. Each store or agency must be observed with a magnifying glass, be compared in term of profitability, turnover and trade area to its closest commercial neighbors which were sometimes concurrents in the past but from now on partners of a same network. The precision of a network reorganization or construction is essential especially concerning the outlet location choice, but also a quick decision-making proves to be necessary. The purpose of our present paper is to show the feasibility of a new precise, fast and also conclusive decision tool to select the best commercial locations when planning to a reorganizate or create of a network of outlets. The direct solving of location-allocation models such as the p-median could be a way to discover optimal locations but their implementation generates a so significant number of mathematical operations that it requires powerful computers and huge computing times. This fact leads us to simplify the expression of the p-median model by introducing original methods of filtering and convolution intended to accelerate the geomarketing data processing, reliable methods which are already used in the field of " hard sciences ".Theory and practice of commercial location choixeThe search for a commercial location usually takes place after the company has determined on which market it wishes to establish and which number of outlets it plans to create depending on the market saturation for the distributed products or service and of the available financial capacities. A first category of theoretical model of location search is based on the gravitation analogy: one of the principal criteria of these models is the distance and one will thus seek to locate the outlets as nearest as possible to the customers so as to attract their greatest number. The central places theory of Christaller is one of these space interaction models : the Christaller 's theory assumes that geographical space understands a uniform distribution of identical customers: the optimal establishment is then at the center of a hexagon whose apices are occupied by six elementary stores. The method of the proximal sectors is a variation of the preceding theory which uses the principle of the Thiessen or Dirichlet polygons. Space interaction models also includes the law of Reilly which considers that the intermediate population I located between two city poles A and B will be attracted by each one of these poles proportionally to their size and in opposite proportion of the distance between the urban zone I and poles A and B . The model of Huff introduces into the preceding law the concept of the store sale area which according to him plays an important role in customers attraction. The MCI model or Interactive Model of Competition is a generalization of the Huff model which takes into account many other parameters related to attraction i.e. the price, the number of cash desks, the consumers perception in the case of the subjective MCI model.The search for locations uses a second category of model named location-allocation models which tries to find the closest to customers sites thanks to mathematical algorithms. A location-allocation model usually understands (1) an objective function quantifying the store distance to the customers or more generally measuring a commercial performance criterion linked to its location; (2) request points or request nodes representing the number of customers or their wish to buy specific products or services ; (3) potential sites nodes corresponding to possible sites for the outlets to be located; (4) a matrix of distance or time measuring the distances in kilometres or the travel time each of the request nodes and the potential sites nodes; (5) an allocation rule which specifies how the potential sites nodes will be allocated to the request nodes.The most used location-allocation model for optimized commercial locations search is the p-median model which has many applications field i.e. transport, distribution, banking services, insurance: its problems is to find the locations for a number of p activities having to provide some services or products to N customers in such a way that the sum of the distances separating each customer to the closest activity is minimal. Its mathematical formulation is the following one:Minimize ai dij xij represents the objective function, (1)with xij = 1,  i,ensure that all the customers are assigned to a single activity, (2)xij  yj,  i, jprevent from assigning a customer to an activity if it is not open,(3) yj = p,the total number of activities is p,(4)xij, yj  0,1,  i, jbinary nature of the variables xij, yj(5)whereai : the request at node i,di,j : the distance from node i to node j,p : the number of activities to be located,xi,j = 1, if the node i is assigned to the activity i and equals 0 if not,yj = 1, if the activity i is opened and 0 if not.The problem is that the p-median is considered to belong to the class of problems known as being NP-complete: its solving resulting from linear algorithms become insoluble as the number of variables (activities and customers) increases with an exponential progression of the problem size. There are nevertheless some heuristics to find acceptable solutions to the p-median problem despite the fact that all these solutions often converge to local optima and that it is not possible to know the optimality level of these solutions. The fundamental solving algorithms of the p-median problem are the fuzzy algorithm, the neighboorhood algorithm, the Lagrange multipliers algorithm, the genetic algorithm, substitution heuristics and ome of their alternatives . Generally speaking, heuristics line up in two classes: construction algorithms which seek locations with a small degree of optimality and the improvement algorithms which improve the results provided by the construction algorithms. Thus, the fuzzy algorithm is of the construction type just as the genetic and the Lagrange multipliers algorithm. The substitution and the neighboorhood algorithms are of the improvement type.The search for optimal locations in practiceIn practice, professionals use convincing simple statistical methods to choose some new commercial locations. amonh them, the market shares and surface areas method consists in evaluating the size of the trade area of possible locations and then to calculate the expected turnover after having compared this trade area compared to those of existing stores. The analogical method calculates first the expected average turnover per customer based on experience and extrapolates it to that of the possible site after having evaluated the number of potential customers in its surroundings. The multiple regression model seeks to correlate a performance measurement of a store (turnover, result) with various criteria like the households incomes in the area, the competition level, the market share... A general regression equation is then obtained and applied to the most interesting potential sites selected the one having the higher performance. The discriminant method is a variation of the regression model which separates thanks to a multidiscriminant analysis a set of stores in several groups according to their commercial results, in fact in a group comprising the stores having an acceptable performance and the remainders in the other group : one will then seek to locate new sites in places having the features of areas where the most performant stores are established. The method of the potential market is an application of the Reilly's law of retail gravitation: this mode of research minimizes by groping the distance from the future site to potential consumers and maximizes it compared to that of the competitors. Lastly, the p-median model is used to locate outlets by locating the geographical addresses or potential customers origins generally obtained by surveys. Initially, during the construction of the model, one seeks to assign each customer address of the database to a district or an urban sector so as to reduce the number of cells of analysis. Thus, it is often the gravity center of each one of these sectors which will be used as node of the p-median network. The number of nodes is then considerably reduced compared to the case one would have created for each customer a particular node. The problem is that this division in geographical sectors often corresponds much more to an administrative logic than to a commercial one. Moreover, this irrational extreme simplification procedure harms considerably the precision and even the reliability of the results obtained when solving the p-median model. In addition, all these methods usually call upon intuition, this fact having been shown by a certain number of works . That led us to propose a new, more reliable and faster method associating the p-median model with the signal processing theory. A new approach for the search of optimal locationsThe preceding limitations have been overcome by introducing a new approach using signal processing. Signal processing with algorithms are able to process data in dynamics provided by many applications very greedy in information and in computing time i.e. artificial vision (a technique complementary to robotics). Thus, we propose to uses the principles of signal processing associated with the p-median model to determine optimized commercial locations. The method is composed of four stages including (1) the geocoding and the cartographic representation of the locations of potential customers, (2) the delimitation of the trade area thanks to signal processing, (3) the calculation of the features of all the zones forming the trade area : these features will shape a network p-median with its nodes (the gravity centers of each zone) and its requests (the surface areas of the each zone) and finally (4) the solving of this simplified p-median network with classical heuristics. The same procedure can possibly after these steps focus at the level of each zone identified as an optimal location : the same algorithme can then be reused but on a finer geographical scale for better specifying the commercial locations.The following drawings summarize operation this new algorithm based on the delimitation of trade area.Stage 1 consists in codifying the potential customers addresses or locations in terms of geographical co-ordinates so as to get a map on which each customer is represented by a point. Stage 2 enables to outline trade area zones through signal processing techniques. One will calculate in stage 3 the co-ordinates of the gravity centers of outlined zone found in the preceding stage so as to model a p-median network: the nodes of this network will be represented by the gravity centers and its segments will be the road distances measured in time or in kilometers. Additional potential locations can be introduced as node even if they do not count customers. This network can, if necessary, be weighted and in this case, the weight will represent the commercial potential at each node.In stage 4, traditional algorithms will be used for for solving the p-median model and this will thus lead to the choice of some nodes for optimal locations. Feedback and scaling: after having identified the p optimal nodes the process can be reiterated in focusing oneself this time on each each optimal node. Thus, the central and innovative part of this method consists in the outlining of trade area zones (dense zones of customers) where it is possible to define gravity centers characterizing their location on space. These gravity centers will constitute the nodes of a p-median model. It is thus fundamental to define with enough precision the borders of these trade area zones: a coarse evaluation of the borders will necessarily induce a bad location of the gravity centers with consequences on the p locations results. The innovation in this kind of location allocation question comes then from the fact that the formulation of the problem is automatically done with a number of nodes reduced and a more simple network..Flow chart of the new method of search for location suggestedWe will now study each phase more in detail. Delimitation of the trade area zones by signal processingThe geocoding and the representation of the data geomarketing (stage 1) resulting generally from surveys do not generally pose any technical problems. The second stage of delimitation needs a thorough description. It is composed of a pretreatment of the data by a morphological transform named dilatation directly on the chart representing the location of the customers in order to accentuate the trade area borders. Dilatation has for effect to increase the total surface of shapes and tends to connect disjoined parts and to smooth contours.Example of a dilation:in hatchings, the original shape The original shapeThe dilated shape Many types of filtering exist like the filters sigma, Nagao or median already used by MKAY on cartographies of customers. Filtering on average is simplest of the filters: it consists in replacing each point of the chart by the average value of a small surface centered on this point and thus rebuilding all the chart. The median filter takes him to it median value of each small surface instead of the average value.Addresses customers associated with the frequentationsThe representation treated by 2 filters median The filter sigma studies the statistics of dispersion of the values in each point and generally takes as new value in each point the average of its neighbors in each small surface whose level belongs to the interval half-width 2 times the local variance. The Nagao filter is interesting for it preserves much better the form of contours of the objects of an image than the other filters: it amounts analyzing a certain number of special configurations (tangential, horizontal or vertical in the vicinity of each point) and retaining that which is adapted like new value of the swept point. Lastly, let us mention the transformation of dilation which consists in increasing the surface of each point by enlarging it (not representing each customer on the image) until those touch what makes it possible to fill the interstices: this pretreatment is fundamental to obtain a general representation of the trade area when customers or points are very separate from/to each other in geographical space and that it is then not possible to visually locate the forms full with the trade area. After having to improve the total aspect of the image representing the dispersion of the customers by accentuating contours of the trade area, one proceeds in the continuation of our method, with a delimitation of the trade area by a masking (a special standard of filtering) carried out thanks to a matric operation on the image, named convolution. Let us recall that the operation of convolution between two matrices, the image fi,j and filter it or mask hi,j, is defined by:gi,j = fi,j * hi,j = The most current masks to delimit the borders of the objects of an image are:- masks of Sobel represented by the two matrices:Sx = ;Sy = Stamp detection horizontal;and stamps detection vertical- masks of Prewitt who are one of the filters of the derivative type simplest:Px = ;Py = Detection HorizontalDetection Vertical- the Gradient represented by the matrices : or ; or Matrices of detection horizontal;and matrices of detection vertical- the Laplacian represented by the matrices: or ; or Matrices of detection horizontal;and matrices of detection verticalThus, the simple convolution of the image with these filters makes it possible to immediately obtain contours of the trade area.The representation treated by Sobel filtersCustomers adresses after 2 filters median (contours areassociated to the frequentationssuperimposed on the image filtered by 2 Nagao filters The third stage of our method consists in locating the co-ordinates of the gravity centers of the various surfaces constituting the trade area delimited beforehand and to calculate the surface of these surfaces so as to build a network p-median. For that, simplest is to sweep the image representing contours of the trade area with an algorithm of course which will follow the borders of each surface of the zone by noting the co-ordinates of each one of its points.Example of course of border of trade area using the algorithm : Then, it will be enough to take the average value of the co-ordinates of the points of borders to obtain the co-ordinates of the gravity center of the surface. If the border were described parallel in Northern term of orientation, Southern, Is, Western, the surface of the surface is given by the following algorithm:1) Au départ; u = 0 and t =02) For i = 1 To n DoA) If ai = NorthThent = t + 1Else Go To B)B) If ai = SouthThenu = u + t Else Go To C)C) If ai = WestThent = t - 1Else Go To D)D) If ai = EastThenu = u - t3) Sg = u x Swhere the value of the parameter U at the end of the procedure is the number of points contained in the trade area considered, T a parameter of counting and S the unit geographical surface of a point.The location of co-ordinates of the gravity centers corresponding to the futures nodes of the p-median model in our algorithm, will also give by a simple calculation length, the distances from each segment of the network what will enable us to obtain all the parameters of the network p-median.The p-median modelled after delimitation of the trade area and calculation of the gravity centers. It is enough for us thus in last stage to solve this p-median model made up of a limited number of points by the heuristic traditional ones (genetic algorithms, of substitution... to have the optimal locations. An optional stage is to reiterate the same process on the level of the surfaces underlined by this solving to refine the position of the optimal locations. Our method was used successfully to find the sites optimized of stores of products biological in the west of the Paris area.An application of the p-median model associated with signal processing in the field with the distribution with the products biologicalThe sale of biological products progresses to France and with the United States at the rate of 20 % per annum and the experts count that in the medium term, 5 % of the expenditure of French are devoted to the bio (either still a margin of progression of 400 %) what still leaves creation appropriatenesses of new trade selling this type of products. We got a database of addresses of 10 211 potential customers interested by the purchase of biological products in the cities of Boulogne-Billancourt, Issy -Les Moulineaux, the Neuilly-On-Seine, Paris 7th, Paris 15th, Paris 16th and Paris 17th. These data were geocoded and represented on a chart. The pretreatment constituted in a dilation of the points representing the customers addresses in manners to fill the vacuums in the dense zones of customers.Geocoding of 10 211 potential customersof west of ParisFiltering by dilation of point-customer The image thus treated then underwent a convolution by a Sobel filter so as to draw the borders from them from the trade area. The constitutive surfaces were then analyzed in terms of co-ordinates of their surface and gravity centers their so as to build the network p-median corresponding: each gravity center then constitutes the node network, the demand for each node having the value of the surface of the surface.Classification and location of the gravity center of the surfacesconstitutive of the trade area The solving of this model by the heuristic traditional ones (fuzzy algorithm, of vicinity, Lagrange multipliers and genetic algorithm) gives us the same results for the optimal locations (either surfaces 1 [ Paris 17th ], 10 [ Paris 15th ], 18 [ Boulogne-Billancourt ] forthree locations compared to the numbers of the surfaces mentioned on the figure above). We focused then ourselves on these three surfaces and reiterated the same procedure in their centre : the observation on the ground commercial distributing of the biological products led us to notice in an astonishing way that outlets of this type were already established with less than 150 meters of the recommendations calculated by our model in surfaces 10 and 1 of 15th and 17th districts of Paris. On the other hand, surface 18 correspondent with a district of Boulogne-Billancourt lets foresee a possibility of establishment not yet exploited to date. Theimplementation in parallel of a traditional method of use of the p-median model where the gravity centers of the Parisian districts and cities of periphery correspond to the nodes of a network leads on the contrary to too extravagant results to be taken into account.ConclusionOur method associating p-median model and signal processing comprising an integrated process of geocoding of the customers, of delimitation of the trade area zones and solving of a model of simplified location-allocation makes it possible to very quickly realize of the double use or not of certain outlets or well of the advisability of creating a store in certain lacunar zones forsaken by competition. In the tread, this method makes it possible to measure the potential of the sales of such or such area at the local, regional or national level according to the sector of analysis. Lastly, its implementation anticipates the stage of daily management of the outlet: the precise determination (on the level of the street) of the borders of the trade area will facilitate considerably the task of the Sales manager in the geographical ciblage of the promotion campaigns which these last take the shape of leaflets distributed in the letter-boxes, of sendings of enamel or billboards to place at the strategic places... One of the objectives of our future research is more generally to associate the signal processing with other location-allocation models such as p-centered or the problem of maximum cover so as to study the validity of such a method for problems of logistics (optimization of centers of delivery or of a network of emergency services, barracks of sapper-firemen).
IntroductionLes regroupements massifs des réseaux de distribution ces dernières années et la conjoncture fluctuante et imprévisible ont rappelé que leur organisation n'était jamais figée et restait soumis à la loi impitoyable de la concurrence. Des dizaines de grandes entreprises et des centaines de filiales se voient contraintes de restructurer leur mode de production dans les secteurs industriels et leur réseau de distribution pour celles dont l'activité se situe dans le domaine de la distribution des biens ou des services. Pour des entreprises comportant plusieurs centaines de points de vente ou même plusieurs milliers comme dans le cas des agences de compagnies d'assurance ou de banque, la réorganisation d'un réseau s'avère être une tâche colossale. Chaque point de vente ou agence doit être passé à la loupe, comparé en terme de rentabilité, de chiffre d'affaires et de zone de chalandise par rapport à ses plus proches voisins dans certains cas concurrents par le passé et désormais, partenaires d'un même réseau. La précision d'une réorganisation ou même de la construction d'un réseau est indispensable sur le plan de la localisation de ces éléments sur le terrain, mais aussi s'avère être nécessaire une certaine rapidité des prises de décision et de leur application dans ce domaine. Le but de notre présente démarche est de découvrir et démontrer la faisabilité d'un nouvel instrument de décision précis, rapide et également démonstratif pour sélectionner les meilleurs emplacements commerciaux dans l'optique d'une restructuration ou de la création d'un réseau de points de vente. La résolution des modèles de localisation-allocation tel que le p-médian aurait pu constituer une solution mais leur mise en œuvre engendre un nombre d'opérations mathématique si important qu'elle nécessite des ordinateurs puissants et des temps de calcul énormes. Ceci nous conduit tout naturellement à simplifier l'expression du modèle p-médian en introduisant des méthodes originales de filtrage et de convolution destinées à accélérer le traitement des données géomarketing, méthodes ayant déjà fait leurs preuves dans le domaine des "sciences dures".Enjeux et pratiques de la localisation commercialeLa zone de chalandise du point de vente et son appréciationLe choix d’une bonne localisation est sans doute l’une des décisions les plus importantes qu’un manager doive prendre car l’emplacement du point de vente est en effet un investissement fixé sur le long terme et son choix bon ou mauvais se ressentira sur la performance commerciale. Toute étude de localisation s'accompagne au préalable de l'identification et le repérage dans l'espace d'une clientèle potentielle qui constituera le fond de commerce du point de vente. En pratique, il s'agit de délimiter une aire géographique rassemblant l'essentiel de cette clientèle, dénommée zone de chalandise. Plusieurs méthodes ont été proposées par le passé pour apprécier au mieux la zone de chalandise dont les méthodes normatives théoriques et les méthodes subjectives qui se fondent sur l'expérience et la connaissance des consommateurs. La principale méthode subjective est représentée par la méthode du temps de conduite qui considère que les clients ne sont prêts à parcourir qu'une distance ou qu'un temps limite pour rejoindre le point de vente : la zone de chalandise comprend alors les aires pas trop éloignées du point de vente selon ce critère de distance limite souvent mesurée en temps de conduite. Les méthodes normatives rassemblent la méthode analogique qui sous-tend que deux magasins placés à deux emplacements identiques auront la même performance commerciale : la zone de chalandise est considérée comme étant le disque dont le rayon a une dimension telle qu'il concentre au minimum X % de la clientèle (X=80 % par exemple). Les autres méthodes normatives sont le modèle de régression qui cherche à mesurer un paramètre de performance commerciale en le corrélant avec des variables socio-économiques, environnementales et marketing ; la méthode par les surfaces enveloppantes qui consiste à représenter les taux de pénétration sur une carte quadrillée en zones de manière à obtenir un relief dont la surface est approximée par des courbes ou des plans et en particulier par des équations dont les coefficients sont déterminés grâce à un modèle de régression ; la méthode des nuées dynamiques qui con¬struit itérativement une classification d’un nuage de points. Malheureusement, toutes ces méthodes de description de la zone de chalandise, une phase primordiale dans la recherche d'une bonne localisation, sont compliquées, peu précises et réduisent le plus souvent la zone de chalandise à une aire compacte et centrée autour du magasin alors que cette dernière est généralement morcelée du fait des irrégularités géographiques, (barrières naturelles, infrastructures routières, séparation de la population en quartiers).Théorie et pratique de la localisation commercialeLa phase de recherche d'une localisation commerciale s'opère après que la société se soit attachée à déterminer sur quel marché elle souhaite s'implanter et en ayant à l'idée le nombre exact de point de vente à créer en fonction de la saturation du marché pour le produit ou le service proposé et des capacités financières disponibles. Une première catégorie de modèle de recherche théorique de localisation se fonde sur l'analogie gravitaire : l'un des critères principaux de ces modèles est la distance et l'on cherchera ainsi à se placer au plus proche de la masse des clients de manière à en attirer le plus grand nombre. Citons parmi ces modèles dits modèles d'interaction spatiale, la théorie des places centrales de Christaller qui considère l'espace géographique comme comprenant une répartition uniforme des clients ayant tous un comportement identique : selon cette théorie, l'implantation optimale se situe au centre d'un hexagone dont les sommets sont occupés par six magasins élémentaires. La méthode des secteurs proximaux est une variation de la théorie précédente qui utilise le principe des polygones de Thiessen ou de Dirichlet . Les modèles d'interaction spatiale comprennent également la loi de Reilly qui considère que la population intermédiaire I localisée entre deux pôles urbains A et B sera attirée par chacun de ces pôles proportionnellement à leur taille et en proportion inverse de la distance entre la zone I et les pôles urbains A et B . Le modèle de Huff introduit dans la loi précédente la notion de surface de vente du magasin qui selon lui joue un rôle tout aussi important dans son attractivité vis-à-vis des clients que sa proximité. Le modèle MCI ou Modèle Interactif de Concurrence est une généralisation du modèle de Huff qui tient compte encore d'autres paramètres d'attraction que la distance ou que la surface de vente comme le prix des articles, le nombre de caisse ou même de la perception des consommateurs dans le cas du MCI subjectif.La recherche de localisation utilise une deuxième catégorie de modèles nommés modèles de localisation-allocation qui tente de trouver les emplacements les plus proches des clients grâce à des algorithmes mathématiques. Tout modèle de localisation-allocation comprend (1) une fonction objectif quantifiant l'éloignement du magasin aux clients ou plus généralement mesurant un critère de performance du point de vente par rapport à sa localisation ; (2) des points de demande ou nœuds de demande représentant l'importance de la clientèle et de son désir d'acheter un produit ou un service particulier ; (3) les emplacements potentiels ou nœuds d'emplacement potentiel correspondant aux emplacements possibles du ou des points de vente à localiser ; (4) la matrice d'éloignement ou de temps mesurant les distances kilométriques ou temporelles entre les points de demande et les emplacements potentiels ; (5) la règle d'allocation qui spécifie de quelle manière les emplacements potentiels seront alloués aux points de demande.Le modèle de localisation-allocation le plus utilisé pour la recherche de localisations commerciales optimisées est le modèle p-médian dont les champs d'applications vont du transport à la grande distribution en passant par les services bancaires et l'assurance : sa problématique est de trouver les localisations pour un nombre p d'activités devant fournir une panoplie de services ou de produits à n clients de telle manière que la somme de l'ensemble des distances séparant chaque activité aux clients les plus proches soit minimale. Sa formulation mathématique est la suivante :Minimiser ai dij xij représente la fonction objectif, (1)avec xij = 1,  i,assure que tous les clients sont assignés à une activité et une seule, (2)xij  yj,  i, jempêche d'assigner un client à une activité si elle n'est pas ouverte,(3) yj = p,le nombre total d'activités est p,(4)xij, yj  0,1,  i, jnature binaire des variables xij, yj(5)oùai : la demande au nœud i,di,j : la distance du nœud i au nœud j,p : le nombre d'activités à localiser,xi,j = 1, si le nœud i est assigné à l'activité j et 0 autrement,yj = 1, si l'activité j est ouverte et 0 autrement.Le problème est que le p-médian est réputé appartenir à la classe des problèmes connus comme étant NP-complets : ses solutions issues d'algorithmes linéaires deviennent insolubles au fur et à mesure que le nombre des variables (activités et clients) augmente avec une progression exponentielle de la taille du problème. Il existe néanmoins un certain nombre d'heuristiques pour trouver une solution acceptable au problème p-médian malgré le fait que toutes ces solutions ne convergent que vers des optima locaux et non vers une solution globale et qu'il ne soit pas possible à priori de connaître le niveau d'optimalité de cette solution. Dans les algorithmes de résolution fondamentaux, on trouve l'algorithme flou, l'algorithme de recherche de voisinage, l'algorithme par les multiplicateurs de Lagrange, l'algorithme génétique, une heuristique de substitution et ses variantes . D'une façon générale, les heuristiques se rangent en deux classes : les algorithmes de construction qui permettent de rechercher des localisations avec un degré d'optimalité faible et les algorithmes d'amélioration destinés comme leur nom l'indique, à améliorer les résultats fournis par les algorithmes de construction. Ainsi l'algorithme flou est du type construction de même que l'algorithme génétique et par les multiplicateurs de Lagrange. L'heuristique de substitution et l'algorithme de recherche de voisinage ont une approche d'amélioration.La recherche de localisations optimales en pratiqueDans la pratique, les professionnels utilisent des méthodes statistiques démonstratives en général assez simples qui ont aussi le bénéfice de la rapidité. Citons parmi elles la méthode par les parts de marché et les surfaces de vente qui consiste à évaluer la taille de la zone de chalandise à l'emplacement pressenti puis à calculer le chiffre d'affaires escompté en pratiquant une règle de trois après avoir comparé cette zone de chalandise par rapport à celles de magasins existants. La méthode analogique consiste à calculer le chiffre d'affaires par client pour un magasin et à l'extrapoler à celui de l'emplacement prévu du nouveau point de vente après avoir évalué le nombre de clients potentiels sur lesquels il pourra compter. Le modèle de régression multiple cherche à corréler une mesure de la performance d'un magasin (chiffre d'affaires, résultat) avec divers critères comme le revenu des ménages dans la zone, le niveau de concurrence, la part de marché estimée,... Il s'agit ensuite de transposer l'équation de régression obtenue aux sites potentiellement intéressants pour retenir celui ayant la performance la plus élevée. La méthode du discriminant est une variation du modèle de régression qui sépare grâce à une analyse multidiscriminante un ensemble de magasins en plusieurs groupes selon leurs résultats commerciaux, en l'occurrence les magasins ayant une performance acceptable et les autres plutôt inacceptables : on recherchera ainsi ultérieurement à créer un nouvel établissement dans un endroit ayant les caractéristiques d'une zone où est implanté un magasin performant avec éventuellement les caractéristiques de ce type de magasins. La méthode du marché potentiel découle directement du principe de gravité du commerce de détail de Reilly : souvent utilisée par la grande distribution, ce mode de recherche par tâtonnements tente de minimiser la distance du futur emplacement aux consommateurs potentiels et la maximise par rapport à celle des concurrents. Enfin, le modèle p-médian lui-même, sert à localiser des points de vente en repérant les adresses ou les origines géographiques de clients potentiels le plus souvent par des enquêtes de terrain. Dans un premier temps, lors de la construction du modèle, on cherche à assigner chaque client de la base de données d'adresses à un quartier ou à un secteur urbain de manière à réduire le nombre de cellules d'analyse. Ainsi, c'est le centre de gravité de chacun de ces secteurs qui servira de nœud au réseau du modèle. Le nombre de nœuds correspond chacun à un secteur est alors considérablement réduit par rapport au cas où l'on aurait créé pour chaque client un nœud particulier. Le problème est que ce découpage en secteurs géographiques correspond plus à une logique administrative qu'à une logique commerciale et qu'une d'une manière générale, cette procédure de simplification à l'extrême de la réalité commerciale nuit considérablement à la précision et même à la fiabilité des résultats obtenus suite à la résolution du modèle. Il est vrai que l'ensemble des méthodes utilisées en pratique fait d'autre part largement appel à l'intuition, ce fait ayant été démontré par un certain nombre de travaux . Cela nous a conduit à proposer une nouvelle méthode plus fiable, plus rapide et facile d'utilisation qui fait appel au modèle p-médian et aux notions de traitement du signal.Une nouvelle approche pour la recherche de localisations optimalesLes limitations précédentes se devaient d'être surmontées en introduisant une nouvelle approche pour en premier lieu délimiter précisément les zones de chalandise ou même toute autre zone géographique possédant des caractéristiques commerciales, économiques, sociologiques propres puis rechercher des emplacements optimisés pour la création de points de vente. Cette nouvelle méthode devait à la fois être rapide, précise et pouvoir être convertie en algorithmes de manière à pouvoir être mise en application sur ordinateur et de préférence sur les calculateurs les plus courants du marché, c'est-à-dire les micro-ordinateurs.Le traitement du signal dont les algorithmes sont capables de traiter les informations en dynamique a fourni de nombreuses applications dont en particulier la plus élaborée, très gourmande en information et en temps de calcul, la vision artificielle, une technique complémentaire de la robotique.La nouvelle approche que nous proposons utilise les principes du traitement du signal associés au modèle p-médian pour déterminer des emplacements optimisés lors de la création de points de vente. Elle se compose de quatre phases dont (1) le géocodage et la représentation cartographique des localisations de clients potentiels, (2) la délimitation des zones de chalandise en utilisant les principes de traitement du signal, (3) le calcul des caractéristiques de chaque aire formant dans leur ensemble la zone de chalandise, ces caractéristiques formant un réseau p-médian avec ses nœuds (centres de gravité de chaque aire) et ses niveaux de demande (étendue des aires) et enfin (4) la résolution de ce réseau p-médian simplifié par les heuristiques traditionnelles. Eventuellement, on pourra ensuite se focaliser au niveau de chaque aire identifiée comme pouvant constituer une localisation optimale en effectuant la même procédure mais à une échelle plus fine pour encore mieux préciser la localisation commerciale. Les dessins suivants résument le fonctionnement ce nouvel algorithme fondé sur la délimitation de zones de chalandise.La phase 1 consiste à codifier les adresses de clients potentiels ou réels en termes de coordonnées géographiques, adresses tirées d'une base de données. On pourra alors obtenir une représentation cartographique des différentes localisations de la clientèle, chaque client étant représenté par un point.La phase 2 correspond à la délimitation des "paquets" de clients ou zones de chalandise. Nous utiliserons dans cette optique les techniques traitement du signal qui font aussi l'originalité de notre démarche.On calculera dans la phase 3 les coordonnées des centres de gravité de chaque zone délimitée dans la phase précédente de manière à modéliser un réseau: les nœuds du réseau seront représentés par les centres de gravité et les segments par les distances routières ou par un indicateur d'éloignement (temporel, kilométrique, généralisé...). Des localisations potentielles supplémentaires pourront d'autre part être introduites comme nœud même si elles ne comptent pas de clients. Ce réseau peut être, si nécessaire, pondéré et dans ce cas, à chaque nœud sera affecté un poids représentatif de l'importance de la clientèle ou de son potentiel. Dans la phase 4, le réseau sera résolu sur la base du modèle p-médian grâce aux algorithmes classiques de résolution et d'amélioration. On aboutira donc au choix de certains nœuds comme localisations optimales. Rétroaction et changement d'échelle: après avoir identifié les p nœuds optimaux par l'algorithme du p-médian, on pourra, si un degré de précision supplémentaire s'avère nécessaire, réitérer le processus en se focalisant cette fois au niveau de chaque nœud. L'examen de zones de plus en plus petites pour améliorer la finesse du choix de localisation pourra se faire autant de fois que souhaité sous réserve de l'existence d'un nombre suffisant de clients ou d'emplacements potentiels à cette échelle.Ainsi, la partie centrale et novatrice de cette méthode est constituée par la délimitation des zones de chalandise (zones denses de clientèle) au niveau desquelles il sera possible de définir un centre de gravité caractérisant la localisation spatiale de ladite zone. Ces centres de gravité constitueront les nœuds d'un modèle p-médian. Il est donc fondamental de définir avec précision les contours de ces zones de chalandise: une évaluation grossière des frontières induira nécessairement un repérage des centres de gravité entachés d'erreurs ce qui ne manquera pas de se répercuter sur le résultat final de localisation des p centres au niveau global et plus encore au niveau local.La deuxième innovation découle du fait que l'on simplifie le problème en l'appréhendant de manière globale grâce à l'identification de "paquets" de clients, et qu'ensuite seulement, on pousse l'analyse dans le détail en recherchant dans les zones intéressantes des emplacements plus précis toujours en utilisant la délimitation de zones de chalandise caractérisées par leurs centres de gravité et le modèle p-médian. Cette technique utilise à la fois des principes de la localisation discrète (à travers le modèle p-médian) et celles du modèle planaire (à travers le calcul de centres de gravité).Organigramme de la nouvelle méthode de recherche de localisation proposéeLa délimitation des zones de chalandise par traitement du signalLe géocodage et la représentation des données géomarketing (phase 1) issues le plus souvent d'enquêtes ne posent en général pas de problème. La deuxième phase de délimitation de la zone de chalandise mérite une description plus approfondie. Elle se compose d'un prétraitement des données par un filtrage directement sur la carte représentant la localisation des clients pour accentuer les contours de la zone de chalandise. De nombreux types de filtrage existent comme les filtres sigma, Nagao ou médian déjà utilisé par McKay sur des cartographies de clients. Le filtrage en moyenne est le plus simple des filtres : il consiste à remplacer chaque point de la carte par la valeur moyenne d'une petite aire centrée sur ce point et à reconstruire ainsi toute la carte. Le filtre médian prend lui la valeur médiane de chaque petite aire au lieu de la valeur moyenne.Adresses clients associées aux fréquentationsLa représentation traitée par 2 filtres médians Le filtre sigma étudie la statistique de dispersion des valeurs en chaque point et prend le plus souvent comme nouvelle valeur en chaque point la moyenne de ses voisins dans chaque petite aire dont le niveau appartient à l'intervalle de demi-largeur 2 fois la variance locale. Le filtre Nagao est intéressant car il conserve beaucoup mieux la forme des contours des objets d'une image que les autres filtres : il revient à analyser un certain nombre de configurations spéciales (tangentielles, horizontales ou verticales au voisinage de chaque point) et à retenir celle qui est la plus adaptée comme nouvelle valeur du point balayé. Enfin, mentionnons la transformation de dilatation qui consiste à augmenter la surface de chaque point en le grossissant (point représentant chaque client sur l'image) jusqu'à ce que ceux-ci se touchent ce qui permet de remplir les interstices : ce prétraitement est fondamental pour obtenir une représentation générale de la zone de chalandise lorsque les clients ou points sont très séparés les uns des autres dans l'espace géographique et qu'il n'est alors pas possible de repérer visuellement les formes pleines de la zone de chalandise.Après avoir améliorer l'aspect global de l'image représentant la dispersion des clients en accentuant les contours de la zone de chalandise, on procède dans la suite de notre méthode, à une délimitation de la zone de chalandise par un masquage (un type spécial de filtrage) réalisé grâce à une opération matricielle sur l'image, nommée convolution. Rappelons que l'opération de convolution entre deux matrices, l'image fi,j et le filtre ou masque hi,j , est définie par :gi,j = fi,j * hi,j = Les masques les plus courants pour délimiter les frontières des objets d'une image sont :- les masques de Sobel représentés par les deux matrices :Sx = ;Sy = Matrice de détection horizontale ;et matrice de détection verticale- les masques de Prewitt qui sont l'un des filtres du type dérivatif le plus simple :Px = ;Py = Détection HorizontaleDétection Verticale - le Gradient représenté par les matrices : ou ; ou Matrices de détection horizontale ;et matrices de détection verticale- le laplacien représenté par les matrices : ou ; ou Matrices de détection horizontale ;et matrices de détection verticaleAinsi, la simple convolution de l'image avec ces filtres permet d'obtenir immédiatement les contours de la zone de chalandise.La représentation traitée par filtres SobelAdresses clients après 2 filtres médian (les contours sont associées aux fréquentations superposés à l'image filtrée par 2 filtres Nagao La troisième phase de notre méthode consiste à repérer les coordonnées des centres de gravité des différentes aires constituant la zone de chalandise préalablement délimitée et de calculer la superficie de ces aires de manière à construire un réseau p-médian. Pour cela, le plus simple est de balayer l'image représentant les contours de la zone de chalandise avec un algorithme de parcours qui va suivre les frontières de chaque aire de la zone en notant les coordonnées de chacun de ses points.Exemple de parcours de frontière de zonede chalandise à l’aide de l’algorithme Ensuite, il suffira de prendre la valeur moyenne des coordonnées des points de frontières pour obtenir les coordonnées du centre de gravité de l'aire. Si la frontière a été décrite parallèle en terme d'orientation Nord, Sud, Est, Ouest, la superficie de l'aire est donnée par l'algorithme suivant :1) Au départ; u = 0 et t =02) De i = 1 à n FaireA) Si ai = NordAlorst = t + 1Sinon Aller en B)B) Si ai = SudAlorsu = u + t Sinon Aller en C)C) Si ai = OuestAlorst = t - 1Sinon Aller en D)D) Si ai = EstAlorsu = u - t3) Sg = u x Soù la valeur du paramètre u à la fin de la procédure est le nombre de points contenus dans la zone de chalandise considérée, t un paramètre de comptage et S la superficie géographique unitaire d'un point.Le repérage de coordonnées des centres de gravité correspondant aux futurs nœuds du modèle p-médian dans notre algorithme, donnera aussi par un simple calcul de longueur, les distances de chaque segment du réseau ce qui nous permettra d'obtenir tous les paramètres du réseau p-médian.Le p-médian modélisé après délimitation de la zone de chalandise et calcul des centres de gravité. Il nous suffit donc en dernière étape de résoudre ce modèle p-médian composé d'un nombre limité de points par les heuristiques classiques (algorithmes génétiques, de substitution,...) pour avoir les localisations optimales. Une étape facultative est de réitérer le même processus au niveau des aires mises en évidence par cette résolution pour affiner la position des localisations optimales. Notre méthode a été utilisée avec succès pour trouver les emplacements optimisés de magasins de produits biologiques dans l'ouest de la région parisienne. Une application du modèle p-médian associé au traitement du signal dans le domaine de la distribution des produits biologiquesLa vente de produits biologiques progresse en France et aux Etats-Unis au rythme de 20 % par an et les experts tablent qu'à moyen terme, 5 % des dépenses des français soient consacrés au bio (soit encore une marge de progression de 400 %) ce qui laisse encore des opportunités de création de nouveaux commerces vendant ce type de produits. Nous nous sommes procurés une base de données d'adresses de 10 211 clients potentiels intéressés par l'achat de produits biologiques dans les communes de Boulogne-Billancourt, Issy-Les Moulineaux, Neuilly-Sur-Seine, Paris 7ème, Paris 15ème, Paris 16ème et Paris 17ème. Ces données ont été géocodées et représentées sur une carte. Le prétraitement a constitué en une dilatation des points représentant les adresses des clients de manières à combler les vides dans les zones denses de clientèle.Géocodage des 10 211 clientspotentiels de l'ouest parisienFiltrage par dilatation de points-client L'image ainsi traitée a alors subi une convolution par un filtre Sobel de manière à en tirer les frontières de la zone de chalandise. Les aires constitutives ont ensuite été analysées en termes de coordonnées de leurs centres de gravité et de leurs superficies de manière à construire le réseau p-médian correspondant : chaque centre de gravité constitue alors le nœud du réseau, la demande en chaque nœud ayant la valeur de la superficie de l'aire.Numérotation et repérage du centre de gravité des aires constitutives de la zone de chalandise La résolution de ce modèle par les heuristiques classiques (algorithme flou, de voisinage, multiplicateurs de Lagrange et algorithme génétique) nous donne les mêmes résultats pour les localisations optimales (soit les aires 1 [Paris 17ième], 10 [Paris 15ième], 18 [Boulogne-Billancourt] pour trois localisations par rapport aux numéros des aires mentionnés sur la figure ci-dessus). Nous nous sommes ensuite focalisés sur ces trois aires et avons réitéré la même procédure en leur sein : l'observation sur le terrain des commerces distribuant des produits biologiques nous a conduit à remarquer de façon étonnante que des points de vente de ce type étaient déjà implantés à moins de 150 mètres des préconisations calculées par notre modèle dans les aires 10 et 1 des 15ième et 17ième arrondissements de Paris. En revanche, l'aire 18 correspondant à un quartier de Boulogne-Billancourt laisse entrevoir une possibilité d'implantation non encore exploitée à ce jour. La mise en oeuvre en parallèle d'une méthode classique d'utilisation du modèle p-médian où les centres de gravités des arrondissements parisiens et des communes de périphérie correspondent aux nœuds d'un réseau débouche au contraire sur des résultats trop extravagants pour être pris en compte.ConclusionNotre méthode associant modèle p-médian et traitement du signal comportant un processus intégré de géocodage des clients, de délimitation des zones de chalandise et de résolution d'un modèle de localisation-allocation simplifié permet de se rendre très rapidement compte du double emploi ou non de certains points de vente ou bien de l'opportunité de créer un magasin dans certaines zones lacunaires délaissées par la concurrence. Dans la foulée, cette méthode offre la possibilité de mesurer le potentiel des ventes de telle ou telle région au niveau local, régional ou national selon le secteur d'analyse. Enfin, sa mise en œuvre anticipe la phase de gestion quotidienne du point de vente : la détermination précise (au niveau de la rue) des frontières de la zone de chalandise facilitera considérablement la tâche du Directeur Commercial dans le ciblage géographique des campagnes de promotion que ces dernières prennent la forme de prospectus distribués dans les boîtes aux lettres, d'envois d'e-mail ou de panneaux publicitaires à placer aux endroits stratégiques,... L'un des objectifs de notre recherche future est d'associer le traitement du signal plus généralement à d'autres modèles de localisation-allocation tel que le p-centré ou le problème de couverture maximale de manière à étudier la validité d'une telle méthode pour des problématiques de logistiques (optimisation de centres de livraison ou d'un réseau de livraison) ou de création de services de proximité (hôpitaux, services d'urgence, caserne de sapeur-pompiers).