A cover-based competitive location model

Abstract

In this paper we propose a new approach to estimating market share captured by competing facilities. The approach is based on cover location models. Each competing facility has a ‘sphere of influence’ determined by its attractiveness level. More attractive facilities have a larger radius of the sphere of influence. The buying power of a customer within the sphere of influence of several facilities is equally divided among the competing facilities. The buying power of a customer within the sphere of influence of no facility is lost. Assuming the presence of competition in the area, the objective is to add a number of new facilities to a chain of existing facilities in such a way that the increase of market share captured by the chain is maximized. The model is formulated and analysed. Optimal and heuristic solution algorithms are designed. Computational experiments demonstrate the effectiveness of the proposed algorithms.

Appendix

A.1 First upper bound (UB ₁)

Since ∑ _j=1 ^N a _ij x _j ⩾0,

where with the provision that if F _i +C _i =0, substitute C _i =1 (and F _i =0).

The following knapsack problem yields an upper bound for the solution of (4) or (6):

subject to:

The solution to this knapsack problem, UB ₁, is the sum of the p largest values of γ _j .

A.2 Second upper bound (UB ₂)

As the arithmetic mean is greater than or equal to the geometric mean:

with the rule when F _i +C _i =0.

Consider the following identity:

It can be written as with the rule that when F _i +C _i =0, C _i =0, in the first term and C _i =1 in the second term.

By the Schwartz inequality (Hardy et al, 1952) ({∑ _i=1 ⁿ a _i b _i }²⩽∑ _i=1 ⁿ a _i ²∑ _i=1 ⁿ b _i ²):

with the rule that when F _i +C _i =0,

To implement UB ₂ (A.4) in conjunction with UB ₁, that is to use as an upper bound min{UB ₁,UB ₂}, calculate: UB ₁ and If ¼K<UB ₁ use as upper bound otherwise, use UB ₁ as the upper bound.

A.3 Third upper bound (UB ₃)

In developing UB ₂ we used inequalities based on a base of ‘2’, that is, the arithmetic mean is greater than or equal to the geometric mean and the Schwartz inequality. We can develop formulas based on a base of θ>1 (not necessarily integer), which reduces to UB ₂ when θ=2 is used. Once the best value of θ is found, UB ₃ must be better than UB ₂ (or equal to UB ₂ when the best θ is equal to 2). To construct UB ₃ we need the following lemma.

Lemma 1

• For θ⩾1, a,b>0: which reduces to for θ=2.

Proof

• Since the log function is concave, for x,y>0 and 0⩽λ⩽1: log(λ x+(1−λ)y)⩾λlogx+(1−λ)logy. Thus, λ x+(1−λ)y⩾x ^λ y ^1−λ. Substituting a=λ x and b=(1−λ)y yields

  

  Substituting □

By Lemma 1, when , which reduces to the property that the arithmetic mean is greater than or equal to the geometric mean when θ=2 is used. When F _i +C _i =0, because the sum is integer. This inequality leads to:

with the agreement that if F _i +C _i =0 then in the first term and in the second term.

We now replace the Schwartz inequality with the Holder inequality (Hardy et al, 1952)

which reduces to the Schwartz inequality for θ=2. This yields:

which reduces to UB ₂ when θ=2. When F _i +C _i =0 then substitute

Define

then UB ₃=min _θ⩾1{F(θ)}.

To simplify the calculation let F(θ)=λ(θ)UB ₁; define μ; where

then UB ₃=λ UB ₁ where λ=min _θ⩾1{λ(θ)}. The θ that minimizes λ(θ) is denoted by θ ^*.

By substitution

Also,

The derivative of ln λ(θ) following some algebraic manipulation is:

Lemma 2

• .

Proof

• Let Then □

Lemma 3

• lim _{θ → 1} λ(θ)=1 where λ(θ) is defined by (A.7) .

Proof

• When β>0 the result is trivial by Lemma 2. When β=0, it is easily verified by (A.8) that the limit of ln λ(θ) is zero. □

We distinguish between three cases:

Case 1 :

β=0. Equating the derivative of ln λ(θ) to zero by (A.9) yields

Therefore, and Consequently,

Case 2 :

β⩾1. By (A.9): Therefore, lnλ(θ) is monotonically increasing for θ⩾1. Therefore, θ ^*=1, thus λ(θ ^*)=1 and UB ₃=UB ₁.

Case 3 :

0<β<1.

Theorem 4

• θ ^* satisfies the equation .

Proof

• By equating the derivative of (A.9) to zero: