Search publications, data, projects and authors
Optimization of commercial locations : an application of signal processing and p-median model

Free full text available



ID: <10670/1.3util0>


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).

Your Feedback

Please give us your feedback and help us make GoTriple better.
Fill in our satisfaction questionnaire and tell us what you like about GoTriple!