Comparative error bound theory for three location models: continuous demand versus discrete demand

Abstract

We develop a unified error bound theory to compare a given p-median, p-center or covering location model with continuously distributed demand points in R ⁿ to a corresponding given original model of the same type having a finite collection of demand points in R ⁿ. We give ways to construct either a continuous or finite demand point model from the other model and also control the error bound. Our work uses Voronoi tilings extensively, and is related to earlier error bound theory for aggregating finitely many demand points.

Appendix: Unifying SAND theory for error bound analysis

Here we adapt some of the theory used in Francis et al. (2000) considering certain functions called “SAND” functionals. In particular, we exploit the ideas of subadditivity and monotonicity (nondecreasingness), defined below. The basic difference between that work and ours is that previously the SAND function domain was a class of finite-dimensional, nonnegative vectors; in what follows, the domain is a class of “infinite,” nonnegative functions. Apart from providing the basis for our error bound theory, we believe this approach, since it suppresses much of the notation needed for the three specific location models, is more transparent than an approach with model-specific notation; it is also more general. Our purpose here is to establish Theorem A.1, and then indicate how to use it to obtain Theorem 2.1.

Let T be a compact subset of R ⁿ, while T _i is part of a tiling of T. Let I(T) be the set of all Lebesgue-integrable and nonnegative-valued functions defined on T, and bounded above on T.

For any two functions φ ₁,φ ₂∈I(T), we define φ ₁≤φ ₂ to mean φ ₁(u)≤φ ₂(u) for all u∈T.

We have a given, nonnegative-valued weight function w, a member of I(T). S(wφ) is a nonnegative-valued functional defined for all functions φ∈I(T) on the product function w(u)φ(u), u∈T. Hence S is a function from I(T) into the nonnegative reals. To restrict the domain of S to I(T _i ) for some tile T _i , we use the notation S(⋅:T _i ); if the function φ is identically 1, we write S(w:T _i ).

We make the following two basic SAND assumptions about S.

Subadditive (SA) assumption :

For any φ ₁,φ ₂∈I(T), we have S(w(φ ₁+φ ₂))≤S(wφ ₁)+S(wφ ₂).

Nondecreasing (ND) assumption :

For any φ ₁,φ ₂∈I(T) with φ ₁≤φ ₂, we have S(wφ ₁)≤S(wφ ₂).

The integral functional, S(wφ)=∫ _u∈T w(u)φ(u) du, and supremum functional, S(wφ)=sup{w(u)φ(u):u∈T}, are versions of S that satisfy both these assumptions, and are the principal SAND functionals of interest.

The above two basic assumptions immediately imply the following for any SAND functional S with domain I(T). Refer to Sects. 2 and 3 for assumptions about w(u) for the integral and supremum case, respectively.

SAND property :

Let φ ₁,φ ₂,φ ₃∈I(T). If φ ₁≤φ ₂+φ ₃, then S(wφ ₁)≤S(wφ ₂)+S(wφ ₃). Equality holds if and only if S(wφ ₁)=S(w(φ ₂+φ ₃))=S(wφ ₂)+S(wφ ₃).

Definition :

A SAND functional S with domain I(T) is positively homogeneous if, for any positive constant c, and φ∈I(T), S(cwφ)=cS(wφ); it is positively subhomogeneous if S(cwφ)≤cS(wφ).

Both the integral and sup-functionals are positively homogeneous.

Notation :

With w=w(u) for all u∈T, for all X⊂FS, for all u∈T _i of any given tiling of T, and for all i∈M, define the following:

$$\begin{aligned}[t]&\varphi _{1X}(u) = D(X,u),\qquad k_{iX} = D(X,a_{i});\qquad \varphi _{2i}(u) = d(u,a_{i}),\qquad \\&c(T_{i}) = S(w\varphi _{2i}:T_{i}),\qquad w'_{i} = S(w:T_{i}).\end{aligned}$$

Theorem A.1

Let S be any positively subhomogeneous SAND functional on I(T). Also, suppose $|w_{i}' - w_{i}|\leq \varepsilon_{i}$, i∈M.

• (a) For all X⊂FS, we have

  $$S(w \varphi _{1 X}: T_{i}) \leq w_{i} D(X,a_{i}) +b_{i} \varepsilon _{i} + c(T_{i}).$$

• (b) For all X⊂FS, we have

  $$w_{i} D(X,a_{i}) = w_{i} k_{iX} \leq S(w\varphi _{1X}:T_{i}) + b_{i} \varepsilon _{i} +c(T_{i}).$$

Proof

(a) We have, using the triangle inequality and the nonnegativity of the function w,

Using the fact that S is SAND, positively subhomogeneous, and the definitions, now gives

(b) We have, since $|w_{i}' - w_{i}| \leq \varepsilon_{i}$,

$$w_{i} - w_{i}' \leq \varepsilon_{i} \Leftrightarrow w_{i} \leq \varepsilon_{i} + w_{i}'.$$

Thus

$$w_{i} k_{iX} \leq \varepsilon_{i} k_{iX} +w_{i}' k_{iX} \leq \varepsilon_{i} b_{i} +w_{i}' k_{iX} \leq \varepsilon_{i} b_{i} + S(wk_{iX}: T_{i}).$$

Also, wk _iX ≤wφ _1X +wφ _2i by the triangle inequality and positivity of w, so, since S is SAND,

$$S(w k_{iX}) \leq S(w \varphi _{1X}:T_{i}) + S(w\varphi _{2i}: T_{i}),$$

giving

$$w_{i} k_{iX} \leq \varepsilon b_{i} + S(w\varphi _{1X}:T_{i}) + S(w \varphi _{2i}: T_{i}) = S(w\varphi _{1X}:T_{i}) + b_{i} \varepsilon _{i} +c(T_{i}).$$

 □

The inequalities used in the proofs of (a) and (b) are: the triangle inequality, the SAND inequality property, D(X,a _i )≤b _i for all X⊂FS, $|w_{i}'- w_{i}| \leq \varepsilon_{i}$, and positive subhomogeneity.

Equality holds in claim (a) or (b) if and only if each inequality in the proof of (a) or (b) holds as an equality. One can build on these equality observations to obtain necessary and sufficient conditions for each of the PCM, PMM, and CLM error bounds to be tight.

Remark

(a) If S is the integral functional, then, for all i∈M, $S(w \varphi _{1 X}: T_{i}) =\int_{u \in T_{i}}w( u )D( X,u ) \,du$,

$$\begin{aligned}[t]&c(T_{i}) = S(w\varphi _{2i}: T_{i}) =\int_{u \in T_{i}} w( u)d(u,a_{i}) \,du ;\qquad \\&w_{i}' = S(w: T_{i}) =\int_{u \in T_{i}} w(u )\,du\quad \mbox{(see Theorem~2.1(a))}.\end{aligned}$$

(b) If S is the supremum functional, then, for all i∈M, S(wφ _1X :T _i )=sup{w(u)D(X,u):u∈T _i }, c(T _i )=S(wφ _2i :T _i )=sup{w(u)d(u,a _i ):u∈T _i }; $w_{i}' = S(w: T_{i}) =\sup\{w(u): u \in T_{i}\}$ (see Theorem 2.1(b)).

Sections 2, 3 and 4 discuss uses of Theorem A.1, including Theorem 2.1.

We remark that our error bound results are not limited to the PMM, PCM, or LCM. For example, we can obtain an error bound for finite and infinite DP set versions of the “cent-dian” model of Halpern (1978), called the medi-center model by Handler (1985).