Optimal continuous location in the geographic and perceptual space using attractiveness and market share.

The location and/or positioning of an offer point, is a generic marketing problem in need for suited models and decision support.

The problem is conceptually the same whether it deals with the geographic space of distribution outlet locations or with the perceptual space in which brands are positioned.

Carpenter, (1989, p. 1031) argues that “representing brands in a two-dimensional perceptual space, is both common and well accepted (e.g. Johnson 1971; Urban and Hauser 1980; Wind 1982), as are psychometric methods for constructing these spaces and computing brand positions (e.g. Cooper 1983; DeSarbo and Rao 1986; Green and Rao 1972). Summarising buyer preferences by unimodal distributions of individual-level ideal points is also common and well accepted (e.g. Cooper 1983, Green, Carmone, Smith 1989). They describe the distribution of consumer tastes over the product space. DeSarbo, Kim, Choi and Spaulding (2002) suggest a spatial methodology that incorporates brand positioning and attraction as well as consumer ideal points and mass via a spatial gravity model of consumer utility.

Location theory is a vast field in Operations Research. For recent views on the state of art and the future trends in Locational Analysis one may refer to Giannikos and Nickel (Eds., 1996) or Scaparra and Scutella (2001). An extensive bibliography on location analysis is provided by Travor Hale. It contains a listing of over 3400 references on location science and related subjects. A large variety of location problems has been identified. These problems vary on the number of facilities to be located, on the type of location problem: whether continuous, network or discrete, on the distance measure used or on the kind and number of the objective functions and restrictions. Several classification schemes based on these or similar criteria have been suggested. For a more detailed discussion on this subject on may refer to Hamacher, Nickel and Schneider (1996)

The problem we are dealing with in this paper looks for the optimal location of new facilities with respect of existing ones and/or users. The new facilities can be distribution facilities in the geographic space or brands, products or services in the perceptual space.

In order to solve this problem we adapt a solution that was suggested by Drezner (1994) for the (two-dimensional) geographic space. The model that is being operationalised indicates the optimum location of a new offer point (be it a product, a service or a distribution outlet) in a competitional space. It takes into account the company’s existing offer and the offer of its competitors as well as the spatial distribution of demand.

Besides the optimum location, the model also indicates the market share that the own distribution network  (or product set) is obtaining following the introduction of the new point of offer.

An extension of Drezner’s (1994) solution to the multidimensional space is presented based upon the conceptual similarity between the geographic and perceptual space.

Recognising the embarrassing tendency of the algorithm used in the original paper, to converge towards local optima, several procedures are suggested in order to search for the global optimum location, and adapted to the two-, three- et multidimensional space.

The same convergence tendency is finally exploited in order to find some efficient procedures that are able to identify all or most local optima.

Drezner’s (1994) method uses Huff’s (1966) or Nakanishi and Cooper’s (1974) formulation of the market share and attractiveness of a new facility, and adapts it to allow some facilities to be part of one’s own chain. Using a series of algebraic transformations he reduces the location problem of a new facility to a situation where market share optimisation depends uniquely on the position of that facility and a series of constant values and uses a procedure designed to solve the minimisation of weighted Euclidian distances that was developed long before by Weiszfeld (1937).

The formulas used in the original paper can be adjusted in order to give better managerial insight to the problem and to its solution. Better managerial understanding can facilitate model adoption and encourage further solution developments. It is well known that the feeble adoption rate of marketing research results in general (Myers, Gryser and Massy, 1979; Monroe 1986) and of models in particular is due to poor communication from analysts who are too "techno-centric" [1] instead of being "problem-centric" (Geoffrion, 1987). For this reason a problem centric translation of the model’s original formulations is given here. It insists on distinguishing attraction of the new facility from the one of other facilities in the own set and from the one of units in the competitors’ set.

The computations follow several steps:

1) First constant elements in market share are computed for each demand point i, ignoring the new facility position and size [2] . They represent the attractiveness of the competitors’ network (product line, portfolio) in a demand point i.

a_i =              (1)

and the attractiveness of the whole offer in the demand point i.

b_i =            (2)

where

S_j = attractiveness of unit j, d_ij = distance between i and unit j, l = elasticity to la distance, m = number of units belonging to the own network and n = total number of units in the territory (m<n).

2) Depending on the position of the new facility and its size, cs_i the competitors’ share in demand point i can be computed. It logically represents the fraction between competitors attractiveness and total attractiveness in a given demand point i.

cs_i = them/(new + us + them) or otherwise

cs_i = a_i/(n_i + b_i)= a_i/ ( + b_i)

where

n_i = attraction of the new outlet point on demand point i (n_i = ),  S_n = attractiveness (size) of the new outlet, d_in = distance between i and the new outlet, it is a function of x and y coordinates of the new point.

this can be expressed algebraically by the following simple formula :

cs_i = a_i*(d_in^l/S_n)/(1+b_i*(d_in^l/S_n))         or otherwise

cs_i = a_i*d_in^l/(S_n + b_i*d_in^l)        (4)

3) The optimising algorithm must find the position of the new outlet that minimizes the  demand covered by the competing network and implicitly maximizes the demand served by the own network [3] .

Min { F(x, y) = S D_i cs_i (x,y)}

where

D_i = Demand in point i

For a given size (attractiveness) of the new facility, F depends only on the distance of that new point of offer compared to all existing demand points, which in a two dimensional space depends on the horizontal x coordinates and vertical y coordinates of that point.

So minimizing F(d_i) can be progressively achieved by equating to zero the partial derivatives of F by x and separately by y.

  =   =  =  =0    (5)

This can be reduced to the following weighted sum equations:

=0; =0;       (6)

where

w_i(x,y) =   (7)

and d_i = f(x,y)

the l from equation 5 could be cancelled in equation 6.

Formula 7 can also be expressed :

w_i(x,y) = = = ns_i cs_i  (7)

where ns_i is the new points share on demand point i.

The x and y are implicitly solved in Equation 6 yielding:

x = ;    y =   (8)

From a given starting point, the partial derivatives identify the nearest  optima on the two horizontal dimensions. As shown later, conjointly they indicate the best descending step towards the nearest local minimum.

This problem is similar to the more general minisum location problem, also referred to as the Fermat-Weber problem. It finds the new facility location that minimises the sum of weighted distances to a set of demand points. In real world problems, weighted distances can be seen as costs, so that minimising the sum of weighted distances is equivalent to minimising the total cost (Brimberg and Love, 1993).

While the objective function in the Fermat-Weber problem is a convex function (as it is a weighted sum of convex distance functions), in Drezner’s problem the objective function is not convex, because the “weights” are not constant values as they also depend on the new facility’s position. This means that the surface of the solution space is a combination of concave and convex shapes (“hills” and “valleys”) whose tops are local maximums and whose bottoms are local minima. The global optimum will be found among the local minima when minimisation is demanded and among local maximums in the alternate case. Technically and for analogy with the well-studied Fermat-Weber problem, Drezner’s problem is expressed as the minimisation of the sum of competitors’ market shares. In managerial terms the complementary interpretation as the maximisation of the company’s own market share is probably more convenient. This  corresponds to a reversal of the solution space, meaning that a valley descending optimum point search method in original space can be seen as a hill climbing procedure in the reversed space.

The optimisation method suggested by Drezner (1994) applies Weiszfeld’s (1937) minimisation of weighted Euclidian distances procedure [4] .

The optimisation algorithm is straightforward it uses a arbitrary starting point (x⁽⁰⁾, y⁽⁰⁾) in order to iteratively calculate formula (9) which is the recurrent interpretation of formula (8)

x^(r+1) = ;    y^(r+1) =     (9)

This iterative process continues until a local optimum is found.

In fact this algorithm first finds the nearest point in a valley that leads to a local minimum, and then advances towards that minimum by finding a lower better point in the same or in a nearby valley until it reaches that minimum. The particularity of this algorithm is that the length and the direction of the advancing step strictly depends on the current position.

This solution is similar to the more general method of the gradient that is used in non-linear optimisation problems.

can be seen as the gradient for x and the gradient for y.

The difference in gradient-based optimisation algorithms is that the gradient is only used to indicate the next step’s direction. Weiszfeld’s algorithm taking advantage of the particular case of minimising weighted distances uses the gradient also for computing the size of the next step. This has advantages and disadvantages. It somehow avoids omitting local optima but also makes finding the global optimum more difficult. The gradient’s advantage is that it dynamically fits the next step’s length allowing for overshooting local optima in search for a better solution [5] .

In order to compare the results of the two algorithms Drezner’s original data are used. They consist of seven existing facilities each with attractiveness (area, or MCI product) S_j = 1 and 100 demand points arranged on a grid with buying power B_i = 1. None of the facilities is assumed to belong to one’s chain. The power l=2 is used to raise the distance. Drezner’s example is a rather particular case in which demand is uniformly sized and distributed and the offer follows a somehow “hemispheric” distribution that gives a rather smooth landscape of the results space with small differences between local optima and the global one like in Figure 1. a.  It shows market shares that result when locations of the new facility are systematically and equally distributed. A real market situation can offer a much rougher (less uniform) landscape like in figure 3.

Figure 1. Results space in Drezner’s problem

A zoomed view of the same result space (Fig. 1 b) gives a clearer view on the eleven local optima that are listed in table 1.

In order to compare the performance of the two algorithms are compared using Drezner’s original data.

Table 1 – Comparing two optimal location algorithms

The first four columns in table 1 reflect the first experiment done by the original author, in which he generates 100 random starting points and counts the number of times the Weiszfeld procedure converges towards each of the eleven local optima. We repeated the same experiment using a grid of 100 starting points with X₁(0,5; 0,5) to X₁₀₀ (9,5; 9,5) and applying both Weiszfeld and Gradient algorithms to the same data. The results showed that the gradient algorithm performs much better in finding the global optimum by succeeding 43 times out of 100, while Weiszfeld succeeded only 14 times out of 100. Also the systematic, grid based, starting point generation gave slightly different results than the original experiment with random starting points. Of course these results are context specific and should not be interpreted as generalisations.

The only generalisation that might be drawn from this experiment is that the Weiszfeld procedure unlike the Gradient seems to converge systematically towards the starting point’s nearest local optimum.

In order to visually verify Weiszfeld’s nearest optimum convergence behaviour, we mapped all starting points to the local optima they produce using Weiszfeld's procedure. We progressively increased the number of starting points from 100 to 400 and then to 1600, applied the algorithm with each of them and recorded the optimum location towards which each converged.

Figure 2 – Illustration of the systematic convergence of Weiszfeld’s procedure towards the nearest local optimum

In figure 2, 400 starting points are labelled with the number of the optimum point to which the procedure starting there from converged. One may clearly see that each starting point seems to “patronise” the “nearest” local optimum in terms of Manhattan distances [6] . This is an interesting finding that might be used for further developments.

Also the increased density of starting points (1600) revealed two additional local optima that hadn’t appeared while applying sparser (100 point  and 400 point ) grids.

The existing algorithms don’t provide exact optimum solutions and most of the provided optimal solutions are only local optima. Finding the global optimum needs additional heuristics. Heuristic methods are used to find satisfactory solution that could deviate from the real optimal solution of the given problem. The term “heuristic” derives form the Greek “heuriskein” meaning to find or to discover. A heuristic algorithm can be defined as follows :

“A heuristic is a technique which seeks good (i.e. near-optimal) solutions at a reasonable computational cost without being able to guarantee either feasibility or optimality, or even in many cases to state how close to optimality a particular solution is”. (Reeves 1993)

In this section we suggest some heuristic methods in order to look for the global optimum for the problem being solved.

The most natural solutions would be to find some way to generate starting points for Weiszfeld’s algorithm that would cover the entire surface in some systematic way. This could be done by using fixed step starting point advancing procedure or by repeat random generation of starting point. During the procedure the best solution should be memorised…

These methods although easy to implement are not very efficient. Therefore a different solution is tested here first in the two dimensional space and then adapted for the three dimensional situations

A triangle object retains its state, the three peaks, their coordinates and values (the value of the objective function, here the market share) and its performance that can be the maximum value or the mean value of its edges. The performance is used as a criterion in eliminating triangles from the population like in a biological renewal process.

The triangle population is a FIFO buffer like collection of triangles with a given maximum capacity that keeps track of its actual size. When the maximum size is reached the collection is automatically cleaned for renewal by eliminating a given proportion of less well performing triangles.

While adding a triangle the population actualises the overall best performance value and the coordinates of the responsible edge, which is the moments global optimum.

The algorithm mimics a biological reproduction and selection process. The initial population consists of two triangles each covering half of the given market area. During each run the buffer’s top triangle is extracted in order to generate four child triangles that are pushed at the end of the buffer. This process continues during a given number of runs.

The results from an application to a small perceptual map positioning problem (figure 3) can be seen in figure 4.

Figure 3. A market situation and its market share result space

Figure 3 shows a perceptual map with 7 existing brands one of them belonging to one’s product line together with the new brand to be placed. The demand points are four segment ideal points. Again brands have equal attractiveness and segments have equal buying power. Both are arbitrarily fixed to 1000.

Figure 4. Triangles population to find the global optimum

The triangle generation and elimination procedure using the biological metaphor described before succeeds in progressively reducing the surface of the triangle population and orients its positional focus on higher reaching peaks.

We compared the results of our triangulation method with 250 runs to 1000 runs random Weiszfeld and the results and the time used were systematically better for our method.

The same algorithm has also been adapted for three dimensional location/positioning problems. The initial population consists of two tetrahedrons each covering half of the given market space cube. During each run the buffer’s top tetrahedron is extracted in order to generate four child tetrahedrons that are pushed at the end of the buffer. This process continues during a given number of runs.

Figure 7. – Finding the global optimum positioning of a new brand in a 3D perceptual space

The options can be extended to get a 3D view of other geometric spatial decomposition methods that will be subsequently tested.

What initially was presented as a troublesome property of Weiszfeld’s procedure, its convergence towards the nearest local optimum, may turn into an advantage

This algorithm’s problem is not only to find the global optimum but also to record all or most local optima. It helps identify these optima and provides decision support for optimal location under constraints. This is useful for example in positioning problems where the starting or actual position of a point (outlet, brand) is given in advance and reaching an optimal position demands a cost that depends upon the distance between the actual location and the targeted location. Under such circumstances some cost/benefit judgement is needed in order to evaluate the tradeoffs between gains and costs among the existing optimal locations.

Figure 8. Decreasing local convergence rate of Weiszfeld’s algorithm

The suggested method combines the spatial decomposition procedures used in the previous section with the quickly advancing steps in Weiszfeld’s algorithm.

Figure 9 - Selection criteria for moving triangles using Weiszfeld iterations

There are two elimination criteria after each Weiszfeld iteration:

1. Increased surface (figure 9a), means that  vertexes move in diverging directions. The triangle is at the intersection of two of more convergence (attraction) areas. 

2. If triangle is not increasing but moving with such a pace that for example its new barycenter gets outside its original surface (contour), this means that all vertexes move in the same direction within an convergence area, but are still far from circumscribing the local optimum (figure 9b).

The remaining triangles either circumscribe a local optimum as in figure 9 (c) or are close to it.

This algorithm seems very efficient compared to the repeat random generation of starting points for complete Weiszfeld  search procedure. A complete Weiszfeld search procedure finds a local optimum in let’s say 10 to 20 runs and the random generation of the starting point should be repeated 100 times in order to obtain a poor coverage of the analysed situation, meaning 2000 Weiszfeld iterations. The simultaneous triangles elimination procedure can start by covering the solution space with 200 triangles which is equivalent to about 200 vertex. After the first stem consuming one Weiszfeld iteration per vertex and using the criteria above more than 60% of the triangles are eliminated.

Observing the progressive convergence of equally distributed starting points towards local optima, another potentially efficient algorithm for recording local optima has been imagined.

It uses a grid of ordered and equally distributed starting points covering the solution surface and each of them undergo a Weiszfeld iteration. The distance for every two points sequence is compared to a flexible limit and if inferior, the two points are merged into one. The limit distance is initially fixed to the step size used to generate the points.  Subsequently it is increased at a given rate (say 1.2) if during the last iteration the point population hasn’t been reduced and decreased otherwise. At the end the point population should contain only local optima.

In this paper a new facility location problem is presented and extended to the multidimensional space based upon the conceptual similarity between the geographic and perceptual space in marketing. This problem and a solution using Weiszfeld (1937) algorithm has been suggested by Drezner(1994).

We first suggested a problem centric reformulation of the original method in order to give better managerial insight to the problem and to its solution.

We then showed that the algorithm, that has been used, systematically converges towards local optima. Recognising the similarity of this algorithm to the more general gradient method, a gradient formulation for Drezner’s problem has been given. Tests have been performed running the two algorithms and comparing their performance. The gradient method appeared to be much better in finding the global optimum, but it is still far from finding it systematically.

In order to avoid this embarrassing tendency of existing algorithms, alternative solutions have been looked for. Several procedures have been suggested that search for the global optimum location in the two-, three- et multidimensional space. All cover the given space with populations of geometric objects and use some biological metaphor to guide reproduction and selection processes in the two and three-dimensional space.

Finally we used Weiszfeld's algorithm property to converge toward the “nearest” local optimum in order to suggest procedures aimed to simultaneously retrieve all local optima.

Brimberg J. and R.F. Love (1992) Local Convergence in a Generalized Fermat-Weber Problem. Anns. Opns. Res. 67, 287-294.

Brimberg J. and R.F. Love (1993) Global Convergence of a Generalized Iterative Procedure for the Minisum Location Problem with l_p Distances. Operations Research, 41, 6, 1153-1163.

Chen P.-C., Hansen P., Jaumard B. and Tuy H. (1998) Solution of the multisource Weber and conditional Weber problems by D.-C. programming, Operations Research. Linthicum: 46, 4; 548-562

Carpenter G.S, (1989) “Perceptual Position and Competitive Brand Strategy in a Two-Dimensional, Two-Brand Market”, Management Science, 35,9, 1029-1044.

Cooper L. (1963) Location-Allocation Problems. Operations Research, 11, 37-52.

Cooper L.G. (1983) “A Review of Multidimension Scaling in Marketing Research,” Appl. Psychological Measurement, 7, Fall, 427-450.

DeSarbo W., Kim J., Choi S.C. and Spaulding M. (2002) “A Gravity-Based Multidimensional Scaling Model for Deriving Spatial Structures Underlying Consumer Preferece/Choice Judgements,” Journal of Consumer Research, June, 29, 1, 91-100.

DeSarbo W. and Rao V. (1986) “A Constrained Unfolding Methodology for Product Positioning,” Marketing Science, 5, 1-19.

Ehrenberg, A.S.C., (1994) "Commentary to Marketing Models: Past, Present and Future by G. Lilien", en Research Traditions in Marketing G.Laurent, G.L. Lilien, B. Pras, Boston, Kluwer Academic Publishers, 24-25.

Geoffrion A.M. (1987) "An introduction to structured modeling," Management Science, 33, 5, 547-589.

Green P.E., Carmone F.J.Jr and Smith S.M. (1989) Multidimensiona Scaling. Concepts and Applications, Allyn and Bacon, Boston.

Green P.E. and Rao V. (1972) Applied Multidimensional Scaling, Holt, Rinehart and Winston, Inc., New York.

Hale Trevor , Trevor Hale’s Location Science References. Available at the adress :  http://www.ent.ohiou.edu/~thale/thlocation.html

Hamacher H.W., S.Nickel and A.Schneider, Classification of location problems, Tech. Report, University of Kaiserslautern, Department of Mathematics, 1996, Report in Wissenschaftsmathematik No. 19

Johnson R.M. (1971) “Market Segmentation: A Strategic Management Tool,” Journal of Marketing Research, 8, February, 13-18.

Katz I.N., (1974) Local Convergence in Fermat’s Problem. Math. Prog. 6, 89-104.

Kuhn H., (1973) A Note on Fermat’s Problem. Math. Prog. 4, 98-107.

Kuhn H. and Kuenne R.E. (1962) "An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics," J. of Regional Science, 4, 2,21 -33.

Le Moigne, J-L., (1990) La modélisation des systèmes complexes, Dunod, Paris.

Miehle W. (1958) “Link-Length Minimization in Networks,” Operations Research, 6, 232-243.

Monroe, Kent B. (1986) "A Summary of Task Force's Current and Future Activities," dans Marketing Education Knowledge Development, Dissemination and Utilisation, D. Achabal and J. Guiltinan, Eds. Chicago: American Marketing Association.

Myers, John G., Stephen A. Greyser, and William F. Massy (1979) "The Effectiveness of Marketing's 'R&D' for Marketing Management: An Assessment," Journal of Marketing, 43, January, 17-29.

Reeves C.R. (1993)  Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications. Oxford. Great Britain

Scaparra M.P. and M.G. Scutellà (2001) "Facilities, Locations, Customers: Building blocks of location models. A survey", TR 01-18, Dipartimento di Informatica, Università di Pisa

Urban, G.L., J. R. Hauser (1980), Design and marketing of New Products, Englewood Cliffs, N.J.: Prentice Hall

Weiszfeld E. (1937) Sur le Point Leque la Somme des Distances de n Points donnés est Minimum. Tohoku Mathematical J., 43, 355-386.

Wind Y.J. (1982) Produce Policy: concepts, Methods and Strategy, Addison-Wesley, Reading, MA.