Vector Assignment Ordered Median Problem

Abstract

The vector assignment p-median problem (VAPMP) and the ordered p-median problem (OMP) are important extensions of the classic p-median problem. The VAPMP extends the p-median problem by allowing assignment of a demand to multiple facilities, and a wide variety of multi-assignment and backup location problems are special cases of this problem. The OMP optimizes a weighted sum of service distances according to their relative ranks among all demands. The OMP is well known as it represents a generalization of both the p-median and the p-center problems. In this article, a new model is developed which extends both the VAPMP and OMP problems. In addition, beyond median, center, and vector assignment, this new model can resolve problems where the system objective involves maximizing distance. The new model also gives rise to meaningful special-case problems, such as a “reliable p-center” problem. Different integer linear programming (ILP) formulations of the new problem are presented and tested. It is demonstrated that an efficient formulation for a special case of the VAOMP problem can solve medium sized problems optimally in a reasonable amount of time.

Keywords

location models optimization ordered median closest assignment vector assignment multi-assignment

Introduction

Location analysis has been an area of active research over the past four decades. Powered by the development in optimization techniques, mathematical programming, computational theory, algorithms, and computer hardware, the domain of location analysis has been greatly expanded. A large number of models and problems involving different criteria and constraints have been developed, in an attempt to capture to a greater extent the complexity of the real world. There is a general consensus in the location science literature (see e.g., reviews by Brandeau and Chiu 1989; Owen and Daskin 1998; ReVelle and Eiselt 2005; Daskin 2008) that there are four basic types of models, namely, the p-median problem, the simple plant location problem (SPLP), the p-center problem and covering problems (including the location set covering problem (LSCP) and the maximal covering location problem [MCLP]). There are other location problems that have appeared in the literature that are distinctively different from the four basic models in terms of their objectives and structures. These include, for example, undesirable or obnoxious facility location, facility dispersion, facility interdiction problems, location with backup service, unreliable facility location, and the hub location problem. Moreover, there are many extensions of location models in the sense that they can be added to a basic location model as the specific application context requires. A well-known example is the addition of capacity conditions to the SPLP. Another fundamental yet often neglected example is the protocol or rule for assigning individual demands to routes or service facilities in location analysis. A common protocol, called the closest assignment (CA) condition, is that each demand will be assigned to the closest facility or least cost route for service from the facility. Whether this condition is incorporated into a modeling framework or not largely distinguishes the purpose between user-oriented models and system optimal models.

Despite the multitude of location problems and extensions that have been developed, it is possible, in some occasions to unify basic location problems that appear to be drastically different. Even though it may be impossible to devise one problem to model the infinite complexity of the real world, the unification of different location models is important because (1) it helps in the classification and the understanding of the connections between different problems and (2) it often provides a means to identify and construct new models to meet the needs of analysis. In certain occasions, it is even possible to develop a unified means for solving a variety of related problems in a relatively efficient manner.

One of the earliest examples of model unification in location analysis is the work of Church and ReVelle (1976) in which the authors identified theoretical and computational links between the p-median problem and covering problems. In a similar vein, Hillsman (1984) proposed to use the p-median structure to solve a variety of location problems by appropriately modifying the distance or cost matrix. Weaver and Church (1985) developed the Vector Assignment p-median problem (VAPMP) which allowed split and multiple assignments. The weight values for making assignments to different facilities are based upon the relative closeness of the facilities for a given demand. Further, Church and Weaver (1986) showed that the VAPMP can be used to structure a variety of expected coverage and multilevel covering problems. In essence, it was shown that a number of single-level and multilevel cover models were special cases of the VAPMP.

A prominent recent development is the Ordered Median Problem (OMP; Nickel and Puerto 1999), which is well known for its ability to generalize the p-median and p-center problems as well as define new problems based on the order of the demands in terms of their closest service distance or lowest cost.¹ Whereas the VAPMP is based upon modeling the order of facility closeness for each demand, the OMP problem is based upon ordering demand in terms of service by their respective closest facility. At first this distinction appears to be quite subtle, but a closer look will reveal that these two model approaches are quite different; while the OMP deals with the single level CA, the VAPMP deals with multilevel CA for each demand.

The goal of this article is to introduce a new location model called the Vector Assignment Ordered Median Problem (VAOMP). VAOMP generalizes both the VAPMP and the OMP. Moreover, it is designed to be sensitive to distance in terms of facility or route choice. Consequently, problems such as obnoxious facility location and facility interdiction can be posed in terms of the new model, when negative weights are used. The new model not only subsumes some of the recently developed location models as special case problems but helps identify new location problems. For example, it is possible to formulate a “reliable p-center problem” using the VAOMP structure.

The rest of this article is organized as follows. The next section reviews the VAPMP and the OMP as well as past work to provide motivation for developing the VAOMP. Then, a subsequent section presents several alternative integer linear programming (ILP) formulations of the VAOMP. Following that, we provide specific examples of meaningful special case problems of the new VAOMP model. The experiments section presents computational results using two different data sets. Finally, we conclude with a summary of findings and needed future work.

Background and Motivation

Historically, research in location modeling was inspired by private sector applications with the Weber problem and its extensions, and the SPLP (Manne 1964; Balinski 1965). As pointed out by ReVelle, Marks, and Liebman (1970), location analysis in the public sector involves the added complexity that objectives and constraints are not as easily quantified or defined. They classified public location sector problems into two categories, ordinary and emergency services. In the former case, average travel time or distance in being served by the closest facility is often used as a surrogate or substitute measure for utility. In the latter, a maximum acceptable travel distance or time is often used as standard for service. Depending on whether the maximum distance is minimized or used as a fixed upper-bound or distance standard, two additional problems types can be defined, namely, center location problems and the covering location problems (including the LSCP [Toregas et al. 1971] and the MCLP [Church and ReVelle 1974]). These two problem types plus the p-median and the SPLP problem constitute what is generally recognized as the four fundamental problems in the location science literature. Based on these fundamental location problems, various extended problems have been developed, as will be discussed later in this section.

It is somewhat surprising that even the basic location problems can be related to each other structurally. One of the earliest efforts in identifying such connections is the work of Church and ReVelle (1976) who showed a relationship between covering and median problems. A more recent example is the OMP (Nickel and Puerto 1999) which provided a general structure to unify the p-median and p-center problems.

Church and ReVelle (1976) established that covering location problems such as the MCLP can be posed as a p-median problem via the following transformation of the distance or cost matrix:

d_{i j}^{'} = \{\begin{matrix} 0 i f d_{i j} \leq S \\ 1 i f d_{i j} > S \end{matrix}

where i is an index of demand, j is an index of facility sites, $d_{i j}$ is the shortest distance between demand $i$ and site $j$ , and ${d_{i j}^{'}}^{}$ is the transformed distance. In this transformation, S is the distance standard for coverage, and a demand i is considered covered if it is within distance S from a facility. The transformation defines a modified (binary) distance measure $d_{i j}^{'}$ from the original distance measure $d_{i j}$ . If one defines a p-median problem based on this modified distance, it is clear that this p-median problem will minimize the total demand that is served beyond the coverage distance S. This means that the sum of covered demands will be maximized. Church and ReVelle further stated that, “. . . an even more important view is the idea that the methodologies for solving the p-median problem are general enough to solve other kinds of location problems . . . by a pre-editing of the input data”. Hillsman (1984) further showed that a wider range of location problems can be structured as a p-median problem if the input data are edited appropriately. This included the LSCP (Toregas et al. 1971), the MCLP and some of its variants defined in Church (1974), and the SPLP, among others. For example, the SPLP can be structured as a p-median problem via the following transformation:

d_{i j}^{'} = \{\begin{matrix} a_{i} d_{i j} w h e n i \neq j \\ a_{i} d_{i j} + f_{j} w h e n i = j \end{matrix},

where $f_{j}$ is the fixed cost to open a facility at site j and $a_{i}$ is the demand at location $i$ . In addition, the p-facility constraint needs to be relaxed and changed to the following form:

\sum_{j \in J} y_{j} \leq p_{1},

where $y_{j}$ is the location variable which equals 1 if a facility is sited at location $j$ , and 0 otherwise. The value of $p_{1}$ can be defined arbitrarily large when solving the SPLP as a p-median problem. One notable extension of the p-median problem is the development of the VAPMP by Weaver and Church (1985). The VAPMP is different from the p-median problem in that it allows a demand to be assigned to multiple facilities. The weights or value of assignment to different facilities are based on their relative closeness for a given demand. For example, it may be that a demand can be served 70 percent of the time by its closest server and 30 percent of the time by its second closest server. Church and Weaver (1986) showed that multiple coverage models such as the Maximum Expected Coverage Location Problem (MECLP [Daskin 1983]) and the Backup Coverage Problem (BACOP [Hogan and ReVelle 1986]) can be posed as a VAPMP problem. Lei (2010) further has shown that the VAPMP problem can be used to formulate reliable location problems (Snyder and Daskin 2005) and fault-tolerant location problems (Swamy and Shmoys 2008), which involve assignment to multiple backup or redundant facilities. Recent applications of the VAPMP can be found in Lei and Church (2011a; 2011b) in the contexts of analyzing critical infrastructure and management of marine container transport in unreliable environments, respectively.

Another major generalization of the p-median location problem is the OMP (Nickel and Puerto 1999; Kalcsics et al. 2002; Domínguez-Marín et al. 2005; Nickel and Puerto 2005; Puerto and Tamir 2005; Boland et al. 2006; Stanimirović, Kratica, and Dugošija 2007; Marín et al. 2009). The main advantage of the OMP is that it is a general structure that can unify the p-median problem and the p-center problem, as well as represent intermediate hybrid problems between median and center problems. This is achieved by putting a vector $λ$ of weight values on the demands according to their ranked distances to their closest facilities. Since the p-center problem measures the worst case service distance and the p-median problem measures the sum of the service distances, they can both be treated as a special case OMP with an appropriately defined $λ$ vector. To understand the OMP and the nature of the $λ$ vector, we need to introduce the following additional notation:

$I$ is the set of demands, and $|I| = n$

$J$ is the set of candidate sites for facilities, and $| J | = m$

$a_{i} =$ the amount of demand at $i$ where $i \in I$

$k = 1, 2, \dots, n$ is an index for the relative rank of service distance, one assigned to each demand.

$λ_{k} =$ the weight on the $k t h$ rank of service

$z_{i j}^{k}$ = 1 if demand $i \in I$ assigns to candidate site $j \in J$ , and the assignment distance $d_{i j}$ is the $k t h$ smallest among all demands.

An ILP formulation of the OMP (due to Boland et al. [2006]) can be given as follows:

M i n i m i z e Z = \sum_{i \in I} \sum_{j \in J} \sum_{k = 1}^{n} λ_{k} a_{i} d_{i j} z_{i j}^{k},

s.t.

\sum_{i \in I} \sum_{j \in J} z_{i j}^{k} = 1 f o r e a c h k = 1, 2, \dots, n

\sum_{k = 1}^{n} \sum_{j \in J} z_{i j}^{k} = 1 f o r e a c h i \in I

\sum_{k = 1}^{n} \sum_{i \in I} d_{i j} z_{i j}^{k} \leq \sum_{k = 1}^{n} \sum_{i \in I} d_{i j} z_{i j}^{k + 1} f o r e a c h k = 1, 2, . . ., n - 1

\sum_{j \in J} y_{j} = p

\sum_{i \in I} z_{i j}^{k} \leq y_{j} f o r e a c h j \in J, k = 1, 2, . . ., n

In this formulation, objective (4) minimizes the sum of weighted distances (product of demand times distance), each further weighted by the λ vector according to their relative service ranks. Constraint (5) maintains that, at each service rank k, only one demand assignment can be made. Constraint (6) requires that each demand i is assigned exactly one service rank as well as assigned to only one facility. Constraints (5) and (6) together maintain that each demand assigns once to a facility, there is only one demand assigned to a given service rank, and all demands are assigned a service rank. Constraint (7) maintains the order of the service ranks based upon the distance associated with the assignment. For example, if a demand i is assigned a rank of 4 at a distance of 100, then the demand which is assigned a rank of 5 must have a distance that equals or exceeds 100. Constraint (8) establishes that exactly p-facilities will be located. Constraint (9) is an expanded form of a Balinski style constraint that maintains that assignment for any service rank cannot be made to a site unless that site has been selected for a facility. When all $λ_{k} = 1$ , then the OMP represents a simple p-median problem as the weights on service for all demand are considered equal. When all $λ_{k} = 0$ for $k = 1, 2, 3, . . ., n - 1$ , $λ_{n} = 1$ , and all $a_{i} = 1$ then the OMP represents the p-center problem. Other forms have been suggested, like the trimmed median problem, all based upon selected values of the λ vector.

Extending the work of Nickel and Puerto (1999), Kalcsics et al.(2002) identified finite optimality sets for the single facility problem involving different sets of weight vectors λ and derived results on computational complexity. Puerto and Tamir (2005) considered a variant of OMP for locating tree-shaped facilities on a tree network. Drezner and Nickel (2009a, 2009b) developed solution procedures for solving the single facility OMP on the continuous plane. Heuristic procedures for the OMP, such as genetic algorithms and variable neighborhood search, were investigated by Domínguez-Marín, et al.(2005) and Stanimirović, Kratica, and Dugošija (2007). Boland et al.(2006) investigated exact solution procedures for solving the discrete OMP as well as developed branch and bound procedures for solving the discrete OMP. They suggested alternative ILP formulations for the OMP problem and tested different measures for improving the formulation, such as using externally determined bounds, variable fixing as well as adding valid inequalities. Marín et al. (2009) presented an alternative formulation of the OMP (based on pre-sorted distances) as well as a specialized branch and cut procedure. For a systematic treatment of the OMP, the reader is referred to a book by Nickel and Puerto (2005) and a book by Domínguez-Marín (2003).

One of the potential issues of OMP formulations such as (4) through (9) pertains to the protocol for assigning demands to facilities. Normally, the λ vector is nonnegative, which makes the OMP “distance minimizing” just as the classic p-median problem. One can potentially set the λ vector to negative values to model obnoxious facility location or hostile interdiction of facilities. In a model for locating obnoxious facilities, the system will try to maximize the distance from each demand to its closest facility. The facility interdiction problem (Church, Scaparra, and Middleton 2004) aims at identifying critical facilities which, if removed, will result in maximizing total distance traveled by the demands. In both occasions, despite the fact the system objective is “distance maximizing,” each demand should still be assigned to its closest facility. This assignment protocol is called CA and it will be violated unless explicit constraints are imposed.

With the above discussion in mind, the goal of this article is to develop a new unified median location problem which we call the VAOMP. It is a generalization of both the VAPMP and the OMP, and therefore generalizes a multitude of classic location problems each of them generalizes. In addition, the new model allows one to define new location constructs such as a “reliable” p-center problem, which will be discussed in a subsequent section. Furthermore, the new model is formulated with explicit CA conditions. This makes the new model suitable for locating obnoxious facilities, something not possible with existing formulations of the OMP.

Formulating VAOMP

This section presents several ILP formulations of the VAOMP. The Vector Assignment Median problem involves assigning a demand to its first closest facility for some fraction of its needs, a second closest facility for an additional fraction of its need, and so on, whereas the OMP assigns each demand to its closest facility, but keeps track of which demand gets the closest or best service, which demand gets the second best service, and so on. In combining these two constructs, we need to allow multiple assignments for each demand as well as rank the level of combined service, in terms of which demand receives the best combined level of service, which demand receives the next best level of combined service, and so on. The generalized model will then minimize the weighted combined service levels, based upon the weight vector λ. To formulate this model, we need to introduce or refine the definitions of the following terms:

$a_{i}$ = the demand at location i.

$d_{i j} =$ the distance (or generalized cost) between $i \in I$ and $j \in J$ .

$L =$ the maximum number of levels of closeness being considered in the model for any demand

$θ_{i l} =$ the fraction of the time demand at $i$ is served by its lth closest facility

$p_{1} =$ the maximum number of open facilities

$p_{2} =$ the minimum number of open facilities

$C_{i j} = {q \in J | d_{i q} < d_{i j} o r d_{i q} = d_{i j} w h e n q < j}$ , is the set of facility sites that are closer to demand $i$ than facility $j$ is or are equidistant to $i$ with facility $j$ but having a lower site index than $j$ .

To describe the VAOMP objective, we need to describe for each demand i, the (weighted) partial sum of service distances (to its closest L facilities). We call this a weighted partial sum, as it is a sum of distances to only the L closest facilities, each weighted by the service fraction (or service weight) to that facility. Then, the (weighted) sum of the partial sums defines the VAOMP objective. Recall that index k defines an ordering among the costs for serving the demands, whereas index l is used to identify the ordering of the facilities in terms of distance to a specific demand i. A straightforward formulation of the VAOMP can be written in terms of the following assignment variable:

X_{i j}^{k l} = {\begin{matrix} \begin{array}{l} 1, if facility j is the l th closest todemand i and if the partial sum for i is the \\ the k th smallest partial sum out of all K partial sums of service distances \end{array} \\ 0, otherwise \end{matrix}

Other necessary decision variables are:

u_{i}^{k} = {\begin{matrix} 1, if demand i generates the k th partial sum \\ 0, otherwise \end{matrix}

Z_{i}^{k} = {\begin{matrix} \begin{array}{l} the weighted partial sum of costs for demand i, if i ranks as the k th \\ in all partial sums \end{array} \\ 0, if i does not generate the k th smallest partial sum \end{matrix}

x_{i j}^{l} = {\begin{matrix} 1, if demand i assigns to facility j as the l th closest open facility \\ 0, otherwise \end{matrix}

With the above notation, the VAOMP can be formulated as follows (which we call VAOMP_A to indicate the fact that this formulation uses assignment variables):

VAOMP_A:

M i n i m i z e Z = \sum_{i} \sum_{k = 1}^{n} λ_{k} Z_{i}^{k}

s.t.

Z_{i}^{k} = \sum_{j \in J} \sum_{l = 1}^{L} a_{i} θ_{i l} d_{i j} X_{i j}^{k l} f o r e a c h i \in I, k = 1, 2, . . ., n

\sum_{j \in J} \sum_{l = 1}^{L} X_{i j}^{k l} = L \cdot u_{i}^{k} f o r e a c h i \in I, k = 1, 2, . . ., n

\sum_{k = 1}^{n} u_{i}^{k} = 1 f o r e a c h i \in I

\sum_{i \in I} u_{i}^{k} = 1 f o r e a c h k = 1, 2, . . ., n

\sum_{i \in I} Z_{i}^{k} \leq \sum_{i \in I} Z_{i}^{k + 1} f o r e a c h k = 1, 2, . . ., n - 1

\sum_{k = 1}^{n} X_{i j}^{k l} = x_{i j}^{l} f o r e a c h i \in I, j \in J, l = 1, 2, . . ., L

\sum_{j \in J} x_{i j}^{l} = 1 f o r e a c h i \in I, l = 1, 2, . . ., L

\sum_{l = 1}^{L} x_{i j}^{l} \leq y_{j} f o r e a c h i \in I, j \in J

\sum_{q \in C_{i j}} x_{i q}^{l} + \sum_{s = 1}^{l} x_{i j}^{s} \geq y_{j} f o r e a c h i \in I, j \in J, l = 1, 2, . . ., L

p_{2} \leq \sum_{j \in J} y_{j} \leq p_{1}

0 \leq X_{i j}^{k l} \leq 1, 0 \leq X_{i j}^{l} \leq 1, a n d y_{j}, u_{i}^{k} \in {0, 1} f o r a l l a p p r o p r i a t e i n d e x e s

In this formulation, constraint (11) defines the weighted partial sum of distances for each demand i, in terms of assignment variables $X_{i j}^{k l}$ and assignment vector $θ_{i l}$ . This partial sum value is conditional and it is nonzero only when the partial sum generated by i is the kth smallest partial sum among all demands. The objective function (10) minimizes the sum of the weighted partial sums (weighted by order k with $λ_{k}$ ). Constraints (13) and (14) define a permutation or one-to-one correspondence between each partial sum and its rank, that is, each partial sum should be assigned only one rank and each rank should be assigned to only one partial sum. Constraint (12) establishes the link between the assignment variables, $X_{i j}^{k l}$ , and the rank variables, $u_{i}^{k}$ . Constraint (15) maintains that partial sum of the kth rank should be less than or equal to the partial sum at the next rank, and they will be referred to as the rank constraints. Altogether, constraints (12) through (15) ensure that the partial sums generated at demand points are correctly ranked. Constraint (16) defines a version of the assignment variable which does not have the rank index k. It is convenient to define such a variable because the rank of demand i is not important in describing the relative closeness of facilities for i. We have used this construct for ease of presentation as the elements of this model are somewhat complicated. Constraint (17) is a generalized assignment constraint, ensuring that each demand assigns to a facility as its lth closest. Constraint (18) is Balinski-like constraint where an assignment to a site at $j$ can be made only if that site has been selected for a facility. Additionally, it restricts assignment of demand $i$ to at most one level of closeness for any given site.

Constraints (19) ensure that a given demand $i$ assigns to facility $j$ as the lth closest facility (i.e., $x_{i j}^{l} = 1$ ), when $j$ is actually the lth closest facility to $i$ . It maintains that if no other facility located closer than $j$ is the lth closest (i.e., $\sum_{q \in C_{i j}} x_{i q}^{l} = 0$ ), then $j$ must be the lth closest or even closer (i.e., $\sum_{s = 1}^{l} x_{i j}^{s} \geq y_{j}$ ). Constraint form (19) is the so called multilevel closest assignment (MLCA) constraint which was developed recently in Lei and Church (2011a). In that article, a detailed description of six MLCA constraint forms is provided with a demonstration of the efficacy of the forms (19). Constraints (17)–(19) collectively maintain that each demand assignment is restricted to only those sites where facilities have been located, that a demand must assign for each level of closeness, and that the order of assignment closeness is based upon the relative closeness of the sites with respect to that demand. Constraint (20) maintains that the number of open facilities should be in the range from p ₂ to p ₁.

Constraint (21) defines the appropriate ranges and restrictions for the decision variables. Note that the binary requirement of the assignment variables can be relaxed because when appropriate forms of MLCA such as (19) are used, the assignment variables will be forced to integer values even if they are defined as continuous variables. A more detailed discussion of this property can be found in Lei and Church (2011a).

The VAOMP_A formulation uses an assignment variable $X_{i j}^{k l}$ with four indexes. Overall, there are $L \cdot n^{2} \cdot m$ such assignment variables, which can make VAOMP_A computationally challenging for ILP software. To reduce the number of variables, VAOMP can be formulated in terms of $x_{i j}^{l}$ variables as follows (which we call VAOMP_H).

VAOMP_H:

M i n i m i z e Z = \sum_{i \in I} \sum_{k = 1}^{n} λ_{k} Z_{i}^{k}

s.t.

z_{i} = \sum_{j \in J} \sum_{l = 1}^{L} a_{i} θ_{i l} d_{i j} \cdot x_{i j}^{l} f o r e a c h i \in I

\sum_{k = 1}^{n} Z_{i}^{k} = z_{i} f o r e a c h i \in I

Z_{i}^{k} \leq M \cdot u_{i}^{k} f o r e a c h i \in I, k = 1, 2, . . ., n

\sum_{k = 1}^{n} u_{i}^{k} = 1 f o r e a c h i \in I

\sum_{i \in I} u_{i}^{k} = 1 f o r e a c h k = 1, 2, . . ., n

\sum_{i \in I} Z_{i}^{k} \leq \sum_{i \in I} Z_{i}^{k + 1} f o r e a c h k = 1, 2, . . ., n - 1

\sum_{j \in J} x_{i j}^{l} = 1 f o r e a c h i \in I, l = 1, 2, . . ., L

\sum_{l = 1}^{L} x_{i j}^{l} \leq y_{j} f o r e a c h i \in I, j \in J

\sum_{q \in C_{i j}} x_{i q}^{l} + \sum_{s = 1}^{l} x_{i j}^{s} \geq y_{j} f o r e a c h i \in I, j \in J, l = 1, 2, . . ., L

p_{2} \leq \sum_{j \in J} y_{j} \leq p_{1}

0 \leq x_{i j}^{l} \leq 1, a n d y_{j}, u_{i}^{k} \in {0, 1} f o r a l l a p p r o p r i a t e i n d e x e s .

The VAOMP_H formulation is similar in structure to VAOMP_A. In fact, constraints (26) through (32) are the same with constraints (13), (14), (15), (17), (18), (19), and (20). What is different from the VAOMP_A formulation is that constraint (23) defines the partial sum at demand $i$ without reference to the service ranks $k$ . Constraint (24) maintains that sum of conditional partial sums $Z_{i}^{k}$ should be equal to the “unconditional” partial sum. Constraints (23) and (24) can be combined into one constraint, without loss of generality. Constraint (25) establishes that a conditional partial sum $Z_{i}^{k}$ should be zero unless the partial sum for demand $i$ is the kth smallest. The parameter M in (25) must be a sufficiently large number. It should be noted that this constraint assumes that $Z_{i}^{k}$ is nonnegative. If $Z_{i}^{k}$ can be negative (e.g., when the assignment vector (or the λ vector) contains negative values), then this constraint form should be replaced by the following form:

- M \cdot u_{i}^{k} \leq Z_{i}^{k} \leq M \cdot u_{i}^{k} f o r e a c h i \in I, k = 1, 2, . . ., n

Compared with VAOMP_A, the VAOMP_H formulation has a significantly reduced number of variables and constraints. This is achieved by structuring constraints (23), (24) and (25) based on “unconditional” partial sums at each demand $i$ . Alternatively, a second formulation (labeled as VAOMP_H2) can be developed by structuring constraints based on “unconditional” partial sums at each service rank $k$ . This formulation bears some resemblance to one of the OMP formulations (LDOMP₂) in Boland et al. (2006). This second reformulation rests on the use of a new variable, $w_{k}$ , which is defined as follows:

\begin{aligned} w_{k} = t h e c o s t o f s u p p l y i n g (f r o m m u l t i p l e f a c i l i t i e s) t h a t d e m a n d w i t h t h e k t h s m a l l e s t \\ combined cost of supply (that is, it is the demand with combined service cost rank k) \end{aligned}

VAOMP_H2:

M i n i m i z e Z = \sum_{k = 1}^{n} λ_{k} w_{k}

s.t.

\sum_{k = 1}^{n} w_{k} = \sum_{i \in I} \sum_{j \in J} \sum_{l = 1}^{L} a_{i} θ_{i l} d_{i j} \cdot x_{i j}^{l}

w_{k} \geq \sum_{j \in J} \sum_{l = 1}^{L} a_{i} θ_{i l} d_{i j} \cdot x_{i j}^{l} - M \cdot (1 - u_{i}^{k}) f o r e a c h i \in I, k = 1, 2, . . ., n

\sum_{k = 1}^{n} u_{i}^{k} = 1 f o r e a c h i \in I

\sum_{i \in I} u_{i}^{k} = 1 f o r e a c h k = 1, 2, . . ., n

w_{k} \leq w_{k + 1} f o r e a c h k = 1, 2, . . ., n - 1

\sum_{j \in J} x_{i j}^{l} \leq y_{j} f o r e a c h i \in I, l = 1, 2, . . ., L

\sum_{l = 1}^{L} x_{i j}^{l} \leq y_{j} f o r e a c h i \in I, j \in J

\sum_{q \in C_{i j}} x_{i q}^{l} + \sum_{s = 1}^{l} x_{i j}^{s} \geq y_{j} f o r e a c h i \in I, j \in J, l = 1, 2, . . ., L

p_{2} \leq \sum_{j \in J} y_{j} \leq p_{1}

0 \leq x_{i j}^{l} \leq 1, w_{k} \geq 0, y_{j}, u_{i}^{k} \in {0, 1} f o r a l l a p p r o p r i a t e i n d e x e s

In this formulation, constraint (36) is written in terms of the unconditional partial sum $w_{k}$ at each service rank k. Constraint (37) also requires the use of a large coefficient value, M; these constraints establish that when i has the kth smallest partial sum, the unconditional partial sum should be equal to the actual partial sum of the distances (associated with multilevel assignment). It is necessary to ensure that each $w_{k}$ value is associated with at least one binding constraint (37). This is ensured by constraint (36). Constraint (37) requires a modification if the assignment vector or the λ vector contains negative values. Constraints (38) through (45) are essentially the same as constraints (26) through (33).

It is worthy to note that some constraints in the above VAOMP formulations can be omitted when the parameters of the problem meet certain conditions. First of all, if $λ_{k}$ is non-increasing (on k), then the rank constraint (15) can be omitted. Proofs of this fact for the OMP can be found in Nickel and Puerto (1999, 2005) and Boland et al. (2006). An alternative proof can also be given using the Hardy-Littlewood-Pólya inequality (Hardy, Littlewood, and Pólya 1952). This inequality states that for two non-decreasing sequences $a_{1} \leq a_{2} \leq . . . \leq a_{n}$ , $b_{1} \leq b_{2} \leq . . . \leq b_{n}$ and any permutation π of the indices $1, 2, . . ., n$ , we have:

\sum_{i = 1}^{n} a_{i} b_{n - i + 1} \leq \sum_{i = 1}^{n} a_{i} b_{π (i)} \leq \sum_{i = 1}^{n} a_{i} b_{i} .

Basically, this inequality means that for all possible permutations of two sequences, the inner product of the two permutations will be the smallest when they have opposite orders and will be the greatest if they have the same order. Applying this to the VAOMP objective function (10), we can see that if $λ_{k}$ is non-increasing, the minimization of the product of { $λ_{k}$ } and { $\sum_{i} Z_{i}^{k}$ } can only be achieved when $\sum_{i} Z_{i}^{k} \leq \sum_{i} Z_{i}^{k + 1}$ . Therefore, constraint (15) is in this case optional.

Second, when the assignment vector θ has non-increasing entries and the λ vector is nonnegative, the (multilevel) CA constraint (19) is optional. This can be proved using a similar argument using the Hardy-Littlewood-Pólya inequality. The above two properties hold regardless of whether $λ_{k}$ and $θ_{i l}$ are negative or not.

Finally, if the ranking vector λ is non-decreasing, that is, $λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}$ , then an efficient special-case formulation is possible. Let

{\overset{ˉ}{λ}}_{k} = λ_{k} - λ_{k - 1}, f o r k = 1, 2, \dots, n, a s s u m i n g λ_{0} = 0.

The special-case formulation which we call VAOMP_C is as follows:

VAOMP_C:

m i n i m i z e \sum_{k = 1}^{n} {\overset{ˉ}{λ}}_{n - k + 1} \cdot (k \cdot t_{k} + \sum_{i \in I} u_{k i})

s . t .

t_{k} + u_{k i} \geq Z_{i} f o r a l l i \in I, k = 1, 2, \dots, n

Z_{i} = \sum_{j \in J} \sum_{l = 1}^{L} a_{i} \cdot θ_{i l} \cdot d_{i j} \cdot x_{i j}^{l} f o r a l l i \in I

\sum_{j \in J} x_{i j}^{l} = 1 f o r a l l i \in I, l = 1, 2, \dots, L

\sum_{l = 1}^{L} x_{i j}^{l} \leq y_{j} f o r a l l i \in I, j \in J

\sum_{q \in C_{i j}} x_{i q}^{l} + \sum_{s = 1}^{l} x_{i j}^{s} \geq y_{j} f o r a l l i \in I, j \in J, l = 1, 2, \dots, L

\sum_{j \in J} y_{j} = p

0 \leq x_{i j}^{l} \leq 1, y_{j} \in {0, 1} f o r a l l a p p r o p r i a t e i n d e x e s .

The above formulation makes use of the linear programming formulation of Ogryczak and Tamir (2003) to minimize the sum of the k largest numbers in an array. Their article showed that the sum of the k largest numbers in an array ${q_{i}}, i = 1, 2, . . ., n$ can be found by solving the following linear program with continuous decision variables $t$ and $u_{i}$ :

m i n i m i z e k \cdot t + \sum_{i = 1}^{n} u_{i}

s . t .

t + u_{i} \geq q_{i} f o r a l l i = 1, 2, \dots, n

u_{i} \geq 0 f o r a l l i = 1, 2, \dots, n

A formal proof can be found in Ogryczak and Tamir’s paper. Intuitively, the validity of this program can be verified by the following reasoning. Let $q^{(s)}$ be the sth largest member of ${q_{i}}$ and $π (s)$ be the index of $q^{(s)}$ . Then, by inequality (56), what the objective (55) minimizes is the quantity $k \cdot t + \sum_{i = 1}^{n} u_{i} \geq k \cdot t + \sum_{s = 1}^{k} u_{π (s)} = \sum_{s = 1}^{k} q^{(s)}$ . Thus, any feasible objective function value will be greater than or equal to the k largest elements of ${q_{i}}$ . On the other hand, when the “base value” $t$ is set to $q^{(k)}$ , one can clearly set $u_{π (s)} = 0, f o r s \geq k$ and $u_{π (s)} = q_{π (s)} - t, f o r s \geq k$ , to achieve the lower bound value. Therefore, the optimal objective value of (55) is equal to the k largest elements.

Using a similar argument as Ogryczak and Tamir (2003), but with slightly different notation, let the k largest elements of an array $q$ be

P_{k} (q) = \sum_{s = 1}^{k} q^{(s)}, t h e n q^{(k)} = P_{k} (q) - P_{k - 1} (q) .

The VAOMP objective (47) can be rewritten as

\begin{aligned} m i n i m i z e \sum_{k = 1}^{n} λ_{n - k + 1} (P_{k} (Z) - P_{k - 1} (Z)) \\ = \sum_{k = 1}^{n} (λ_{n - k + 1} - λ_{n - k}) \cdot P_{k} (Z) = \sum_{k = 1}^{n} {\overset{ˉ}{λ}}_{n - k + 1} \cdot P_{k} (Z) . \end{aligned}

Using (55) through (57), we have:

P_{k} (Z) = m i n i m i z e k \cdot t_{k} + \sum_{i} u_{k i} g i v e n t_{k} + u_{k i} \geq Z_{i}, u_{k i} \geq 0

We can substitute (59) into (58). When ${\overset{ˉ}{λ}}_{k}$ is positive for all k, the minimization operator within $P_{k} (Z)$ can be exchanged with the scalar multiplication ${\overset{ˉ}{λ}}_{k} \cdot (\cdot)$ , and with the summation sign, so that we can derive the VAOMP objective form (47). It is important to note that the above simplification works only when all of the ${\overset{ˉ}{λ}}_{k}$ ’s are positive. Otherwise, the minimization operator will become a maximization at some point when exchanged with the scalar multiplication. In addition, ${\overset{ˉ}{λ}}_{k}$ must be nonnegative since λ₀ equals zero by definition. In summary, we have the following observation:

Observation

The VAOMP_C formulation (47) through (54) is a valid formulation of VAOMP when the rank vector λ is nonnegative and weakly increasing.

Applications and special cases of VAOMP

The previous section presented several formulations for the VAOMP problem. In this section, we provide some examples of location problems for which the VAOMP problem can be used as a unified model. Before we discuss specific cases, there are several general issues that are important to mention. First, although the assignment vector in the original VAPMP problem was meant to represent the portions or probabilities of a demand being served by multiple facilities, they can in general represent any meaningful weight values associated with assignment at each level of closeness. For example, this was used in Church and Weaver (1986) to formulate the BACOP (Hogan and ReVelle 1986) in which each demand is required to be covered by different facilities a given number of times. As another example, the assignment vector can represent a combination of probability and a penalty for a demand in using backup facilities or backup routes. As pointed out by Snyder and Daskin (2005), the transportation cost for using backup facilities can be higher than the normal cost. For a risk aversive management strategy, it may be necessary to put a high penalty on using backup facilities.

Second, we note that negative weights in the objective (i.e., the assignment vector or the rank vector) can be used in certain applications when the system objective is “distance maximizing.” For one example, the location of obnoxious facilities (Church and Garfinkel 1978) can involve placing undesirable facilities as far away from population centers as possible. In this occasion, explicit constraints for CA are needed because it is the closest undesirable facility that gives the most negative impact for a given demand. As another example, facility interdiction problems (Church, Scaparra, and Middleton 2004) involve optimally removing a subset of existing facilities so that the total transportation cost is maximized after interdiction. Since the system objective involves maximizing the effects of facility interdiction, explicit CA constraints are needed to ensure that each demand assigns to the closest facility that remains open after the interdiction. In both the examples, interdiction and obnoxious location, MLCA constraints are necessary because of the sense of the objective function. Finally, it should be noted that in other applications, whether the CA constraint should be used or not depends on the modeling context. For example, in the SPLP if one central entity is in charge of system operation, then CA does not necessarily have to be respected and CA constraints can be eliminated.

There are a number of potential special-case problems of the VAOMP model. For the remainder of this section, we describe a number of such cases.

The p-median problem: The VAOMP problem is equivalent to the p-median problem when $λ_{1} = λ_{2} = \dots = λ_{n} = 1$ , and the assignment vector is trivial, that is, when $θ = [1.0]$ with the number of levels of assignment equal to one. In addition, we should choose $p_{1} = p_{2} = p$ in constraint (20). The p-median problem is one of the few location models that will automatically enforce CA. Correspondingly, it is not difficult to see that explicit CA/MLCA constraints are not necessary in each of the VAOMP formulations presented in this article in solving a p-median problem.

The p-center problem: The VAOMP is equivalent to the p-center problem when $λ_{1} = λ_{2} = \dots = λ_{n - 1} = 0$ , and $λ_{n} = 1$ . The assignment vector is also trivial, that is, $θ = [1.0]$ with the number of levels of assignment equal to one. In the formulation section, we have proved that when the assignment vector is non-increasing, MLCA constraints are optional. This applies to the trivial assignment vector $θ = [1.0]$ . Therefore, CA/MLCA constraints can also be omitted from the VAOMP formulation in expressing the p-center problem.

The OMP: The previous two results should come as no surprise since the OMP can be viewed as a VAOMP problem with a trivial assignment vector $θ = [1.0]$ with the number of levels of assignment equal to one. However, if negative weights (either λ or θ) are used in the objective function, whether MLCA constraints should be imposed needs to be carefully analyzed, based upon our discussion at the beginning of this section.

The VAPMP: Just as the p-median problem is a special case of the OMP, the VAPMP can be viewed as an VAOMP with a uniform rank vector $λ = [1, 1, \dots 1]$ .

The SPLP: As mentioned earlier, the SPLP can be structured as a VAOMP problem using a modified definition of distance (2), as well as setting $p_{1} = m$ and $p_{2} = 0$ in (20). In this case, $λ_{1} = λ_{2} = . . . = λ_{n} = 1$ and $θ = [1.0]$ with one level of assignment.

The MLCP: The MLCP can be structured via the binary distance transformation (1) introduced in Church and ReVelle (1976). The rank vector and the assignment vector are $λ_{1} = λ_{2} = . . . = λ_{n} = 1$ and $θ = [1.0]$ , respectively. The MECLP of Daskin (1983) can be structured as a VAOMP where the fraction of assignment for level $l$ is related to the combined probabilities of not being served by the first closest $l - 1$ facilities. For example, if the failure probability of facilities is q, then $1 - q$ percent of the time, a demand i will be served (or covered) by its closest facility, q percent of the time, the demand will be covered by non-closest facilities. That is, the assignment vector is $[1 - q, q]$ . When more than one facility covers a demand, we can always assume that it is the closest facility that is providing the service. In general, the assignment fraction/probability that a demand is served by the lth closest facility is $(1 - q) q^{l - 1}$ . At level L, the assignment fraction can be computed as $q^{L - 1}$ if we ignore the small chance event that all the L closest facilities fail simultaneously.

The r-interdiction median (RIM) problem: The RIM problem (Church, Scaparra, and Middleton 2004) is a recent model for identifying critical facilities in service systems. From the point of view of an interdictor or attacker, the model identifies a subset of $r$ facilities (out of p existing facilities) which, if removed, will lead to the maximum total travel distance. The RIM problem can be viewed as a special-case VAOMP problem by the following transformation. First, we can use a negative assignment vector $θ = [- 1.0]$ , which means that the value of travel distance is maximized (from the point of an attacker). Secondly, since $r$ facilities are interdicted, $p - r$ facilities should be left open. Therefore, the decision to remove $r$ facilities is equivalent to a decision to “locate” or select $p - r$ facilities that are left open after the interdiction. In this sense, the set of $p$ existing facilities corresponds to the set of candidate sites in a typical median problem. It should be noted that since the (hostile) system objective tries to maximize total distance, explicit CA constraints must be used to reflect the fact that each demand will use the closest remaining facility after interdiction.

Vector Assignment p-center problem or Reliable p-center problem: The VAPMP can be used to formulate many so-called reliable median and coverage location problems. The basic reasoning is that if the central facilities are subject to random failure, and a demand’s service will fall back to a farther facility when its closest fails, then the expected transportation can be calculated and expressed in terms of an assignment vector in the final form. Within the context of the VAOMP we can pose an interesting question as to what if the system objective in the context of reliable facility location is not the summed average distance but rather the worst case average distance. To address this problem, a Vector Assignment (or reliable) p-Center Problem can be formulated. Even though a direct formulation of the reliable p-center problem is possible, the VAOMP formulations presented in the previous section, especially the VAOMP_C formulation may be used instead. As will be shown in the computations section, the VAOMP_C can be used to solve medium-sized problems optimally in a reasonable amount of computation time. For now, it suffices to note that the Vector Assignment p-center problem can be derived from the VAOMP problem by choosing the rank vector to be $λ = [0, 0, \dots, 0, 1]$ . Also, conventionally, center problems are unweighted and each demand is treated equally (i.e., the weights are $a_{1} = a_{2} = . . . = a_{n} = 1$ ).

Computational Experiments

The ILP formulations of VAOMP_A, VAOMP_H, VAOMP_H2, and VAOMP_C were implemented using IBM ILOG OPL 6.3 and solved using IBM ILOG CPLEX 12.2 on a machine with dual 2.4 GHz Xeon CPUs with 24 Gigabytes of memory. The formulations were tested on three different data sets. The first one is a 12-node data set of large airports in the United States based on Lei (2010). Their standard airport codes are shown in Table 1. Distances between airports (as shown in Table A1) were calculated from the latitude and longitude using great circle arc distance and expressed in kilometers. This first data set is of a size that is comparable to that used in previous work testing OMP formulations. The second data set is the Swain (1971) 55-node data set widely used in the location science literature. A third data set of 100 US Cities (Daskin 1995) is also used to test the VAOMP_C formulation. During the computation, the parallel mode for the CPLEX engine was disabled in order to make comparisons, without including possible impacts of the parallel code. In most of the experiments, a 3-hr time limit was imposed, and if a model was not solved to optimality within this limit, we report the resulting optimality gap.

Table 1.

The 12-Node Airport Data Set.

ID	1	2	3	4	5	6
Code	ATL	DEN	DFW	JFK	LAX	MIA
ID	7	8	9	10	11	12
Code	MSP	ORD	PHX	SEA	SFO	STL

Among the many possible combinations of parameter settings, we tested eighteen combinations as shown in Table 2. The first column shows the name of the problem specification. The second and third column shows the assignment vector θ and the rank vector λ, respectively. For all problems, we restricted the number of assignment levels to at most two. The last column indicates the equivalent special case problems if applicable, as discussed earlier. In the experiment, we have mainly focused on the hybrid center-median problems (which the OMP is first shown to generalize) as well as their multi-assignment extensions that are possible using the new VAOMP framework.

Table 2.

Tested Problem Data for the VAOMP Problem.

Problem specification name	θ	λ	Note
D1	[1.0 0.0]	[0 … 0 1]	p-center
D2	[1.0 0.0]	[0 … 0 1 1]	k-centrum
D3	[1.0 0.0]	[0 … 0 1 1 1]	k-centrum
D4	[1.0 0.0]	[0 … 0 1 2 3]	center-dian
D5	[1.0 0.0]	[1 … 1 1]	p-median
D6	[1.0 0.0]	[1 … 1 3 6]	center-dian
D7	[0.7 0.3]	[0 … 0 1]	VA-p-center
D8	[0.7 0.3]	[0 … 0 1 1]
D9	[0.7 0.3]	[0 … 0 1 1 1]
D10	[0.7 0.3]	[0 … 0 1 2 3]
D11	[0.7 0.3]	[1 … 1 1]	VAPMP
D12	[0.7 0.3]	[1 … 1 3 6]
D13	[0.4 0.6]	[0 … 0 1]	VA-p-center
D14	[0.4 0.6]	[0 … 0 1 1]
D15	[0.4 0.6]	[0 … 0 1 1 1]
D16	[0.4 0.6]	[0 … 0 1 2 3]
D17	[0.4 0.6]	[1 … 1 1]	VAPMP
D18	[0.4 0.6]	[1 … 1 3 6]

Table 3 presents computational results for the VAOMP_H formulation applied to the 12-node problem for the different problem specifications (i.e., assignment vectors θ and service rank vectors λ) specified in Table 2. In the table, the best objective values, the computation time (in seconds), the solution site patterns and optimality gap are shown in columns 2, 3, 6 and 7, respectively. Columns 4 and 5 show the number of iterations and the number of nodes expanded as reported by the CPLEX solver. The number of facilities being located was fixed at p = 5. We tested three different assignment vectors of [1 0] (D1 through D6), [0.7 0.3] (D7 through D12), and [0.4 0.6] (D13 through D18). The assignment vector [1 0] represents single-level assignment models; [0.7 0.3] can represent a reliability location problem and [0.4 0.6] represents models with assignment vectors that are not non-increasing. Six different rank vectors (λ) were tested.

Table 3.

VAOMP_H Results for VAOMP_H on the 12-Node Data Set (p = 5).

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
D1	1188	10802	3026752	53542	[1 2 5 8 10]	58.68
D2	2190	10805	4918950	100162	[1 2 10 11 12]	50.96
D3	2900.0	10814	11811706	298266	[4 5 6 10 12]	38.45
D4	5960	3055	71379172	1738310	[4 6 9 10 12]	0
D5	5175	2.5	36191	497	[4 5 6 10 12]	0
D6	12576	1122	19907846	705456	[4 6 9 10 12]	0
D7	1285	10828	63377469	648271	[1 3 10 11 12]	22.58
D8	2108.5	7637	115981251	1210327	[4 6 9 10 12]	0
D9	3146.9	10852	88086835	1225902	[4 6 9 10 12]	0.89
D10	6315.5	9478	156809355	2176629	[4 6 9 10 12]	0
D11	7915.2	282.7	4380442	48270	[1 2 5 11 12]	0
D12	16346.4	7229	116788824	1944092	[4 6 9 10 12]	0
D13	1348	10883	156449439	1880529	[1 6 9 10 12]	17.93
D14	2786.2	10839	70430693	980565	[1 8 9 10 11]	27.76
D15	3751.0	10872	138042627	1755382	[1 2 6 8 11]	14.58
D16	8952.2	10836	48284424	662642	[2 4 6 9 12]	31.89
D17	9498.8	495.4	7168320	94253	[1 5 8 11 12]	0
D18	19196.4	6359	74051327	1903294	[5 6 8 11 12]	0

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

First, we compare the objective values. For the problems with the same assignment vector, we can observe that the objective values increase when the number of nonzero entries in the rank vector λ increases. However, the average service level for each demand, which is measured by the objective value divided by the number of 1 entries in λ, decreases with an increasing number of 1 entries in λ. For example, when θ = [1 0], the average service rank for the rank vectors in D1, D2, D3, and D5 is 1188, 1095, 966.7, and 431.25, respectively. This is in accordance with the fact that this sequence of λ vectors correspond to a transition from a worst case analysis to an average case one. Similar trends can be observed for θ = [0.7 0.3] (D6 through D12) and θ = [0.4 0.6] (D13 through D18). Next, if we fix a rank vector λ, we can observe (e.g., by comparing D1, D7, and D13) that the objective values increase when the assignment vector has increasingly greater values on the second component. This can be explained by the fact that heavier weights on higher order components of an assignment vector incur greater assignment distances.

Second, we make some observations on computational time. From the third column, we can see that the computational times for all but three problem instances are very long. The three instances with short computational times are the ones that are equivalent to VAPMP instances. All other problem instances with complicated rank vectors take thousands of seconds to solve even for this 12-node data set, and more than half of the instances cannot be solved to optimality within the given time limit. This is indicative of the complexity associated with the minimax structure (and in this case, a mixed/vector assignment minimax structure).

We have also tested the VAOMP_A formulation, but they result in much longer solution times (often one magnitude longer than the corresponding VAOMP_H formulation). The longer computational times of the assignment formulation may be attributed to the large number of assignment variables. While the VAOMP_H formulation has O(Ln²) assignment variables, the VAOMP_A formulation has O(Ln³) of them.

To assess the impact of the multilevel CA constraints on the complexity of the formulation, we also tested a version VAOMP_H formulation in which the MLCA constraints are dropped. The results are shown in Table 4. Comparing Table 4 with Table 3, we can see that there is some improvement in computational times, for example, for the median type problems D5, D11, and D17. The optimality gap for those problem instances that did not solve to optimally also tends to be smaller. Another interesting observation is that for the θ = [0.4 0.6] (i.e., D17 and D18), the VAOMP_H formulation produces incorrect optimal objective values when the MLCA constraints are dropped. The optimal objective becomes lower than the true optimal. This shows the necessity of MLCA constraints whenever the assignment vector is not non-increasing.

Table 4.

VAOMP_H (Without Closest Assignment) on the 12-Node Data Set (p = 5).

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
D1	1046	11031	217388426	3930054	[1 4 9 10 12]	42.12
D2	2014	10939	68164847	2813393	[1 4 9 10 12]	40.31
D3	2900.0	11190	253812459	11053710	[4 5 6 10 12]	26.81
D4	5960	10962	144242620	3408593	[4 6 9 10 12]	40.1
D5	5175	3.35	27612	838	[4 5 6 10 12]	0
D6	12576	11025	173395470	5160093	[4 6 9 10 12]	6.64
D7	1060.1	11016	205334100	4050926	[4 6 9 10 12]	14.25
D8	2108.5	10882	71885241	2191593	[4 6 9 10 12]	20.64
D9	3146.9	10887	75273221	2527124	[4 6 9 10 12]	19.41
D10	6315.5	10985	119323443	3955832	[4 6 9 10 12]	11.66
D11	7915.2	47.3	614975	9023	[1 2 5 11 12]	0
D12	16346.4	10967	180223618	3978393	[4 6 9 10 12]	1.79
D13	1093.6	10940	82370126	2803993	[4 6 9 10 12]	14.68
D14	2182.8	10943	161743561	3887993	[4 6 9 10 12]	14.52
D15	3257.8	10959	138208477	4422490	[2 4 6 11 12]	13.03
D16	6534.4	11048	124808049	5033693	[4 6 9 10 12]	13.89
D17	8497.2	39.3	586211	10332	[1 5 8 11 12]	0
D18	17516.4	5445	75217068	2585309	[1 5 8 11 12]	0

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Table 5 presents computational results for the VAOMP_H2 formulation. From this table, we can observe that the VAOMP_H2 formulation is significantly slower than VAOMP_H. For one instance (D12), no feasible solution was found within 3 hr. With few exceptions, the VAOMP_H2 formulation either involves longer solution times or larger optimality gaps than the VAOMP_H formulation.

Table 5.

VAOMP_H2 Results on the 12-Node Data Set (p = 5).

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
D1	1093	10877	59479401	1842605	[1 3 4 7 11]	50.1
D2	2124	11000	174961220	4567301	[1 2 4 10 11]	50.44
D3	2900	11056	153767167	5949590	[4 6 9 10 12]	44.45
D4	6033	10844	17140367	1008885	[1 4 9 10 12]	50.01
D5	5175	572	10293009	366144	[4 5 6 10 12]	0
D6	12576	10997	60732545	4626605	[4 6 9 10 12]	23.73
D7	1770.5	10900	108672300	2441005	[3 4 8 9 11]	57.38
D8	2543.9	10916	110565517	2799805	[1 2 3 11 12]	42.62
D9	3626.7	10930	147687964	3078040	[1 2 4 5 11]	40.47
D10	7517.1	10843	53737441	1128205	[1 4 8 9 11]	43.85
D11	7915.2	430	9008983	264404	[1 2 5 11 12]	0
D12	n/a	11123	305115781	7873871	[]	n/a
D13	1602.4	11000	177644602	4101869	[1 2 5 6 7]	42.62
D14	2716.8	11028	164094244	4019705	[1 5 6 8 10]	29.95
D15	4109.4	11026	147492305	3806565	[1 2 4 5 11]	31.52
D16	7809.0	10986	149339908	3981405	[1 2 6 8 11]	26.68
D17	9498.8	683	12638487	404365	[1 5 8 11 12]	0
D18	20201.4	11002	172491620	4565005	[5 6 8 10 12]	14.21

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Overall, the computational experiments in this section show that the VAOMP problem has a very high complexity. Among the general formulations tested above, VAOMP_H outperforms the other two formulations. Next, we test the special-case formulation VAOMP_C, which is suitable for problem instances with non-decreasing rank vectors. It should be noted, however, that this special-case model covers the “distance minimizing” problems involving a combination of worst case and average case analysis, which probably represents what is more commonly used in location problems.

Table 6 presents computational results for running the VAOMP_C results on the 12-node data set. Comparing this table with Tables 3 and 4, we can see a significant improvement in computation times. All problem instances are solved to optimality within less than a second. Except for the “median” problem instances D5, the solution times for the VAOMP_C formulation are at least three orders of magnitudes lower than that of the VAOMP_H and VAOMP_H2 formulations. This is in accordance with findings in prior work (see e.g., Nickel and Puerto 2005) that such problems are easier to solve than the general OMP. The improved efficiency of the VAOMP_C formulation is also evident from the significantly lower numbers of iterations and expanded nodes.

Table 6.

VAOMP_C Results on the 12-Node Data Set (p = 5).

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites
D1	1046	0.40	1968	63	[4 6 9 10 12]
D2	2014	0.28	1987	62	[1 4 9 10 12]
D3	2900	0.36	2711	88	[4 5 6 10 12]
D4	5960	0.31	2888	78	[4 6 9 10 12]
D5	5175	0.06	134	0	[4 5 6 10 12]
D6	12576	0.14	1506	50	[4 6 9 10 12]
D7	1060.1	0.33	2094	69	[4 6 9 10 12]
D8	2108.5	0.28	2094	78	[4 6 9 10 12]
D9	3146.9	0.28	1813	73	[4 6 9 10 12]
D10	6315.5	0.37	2152	57	[4 6 9 10 12]
D11	7915.2	0.06	78	0	[1 2 5 11 12]
D12	16346.4	0.19	992	29	[4 6 9 10 12]
D13	1244.6	0.27	1827	68	[1 6 8 9 10]
D14	2470.2	0.28	1968	87	[4 6 9 10 12]
D15	3505.6	0.19	1730	63	[2 4 6 11 12]
D16	7380.0	0.30	2986	80	[4 6 9 10 12]
D17	9498.8	0.06	81	0	[1 5 8 11 12]
D18	19196.4	0.19	1578	58	[5 6 8 11 12]

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

We also tested the VAOMP_C formulation on the (unweighted) Swain 55 node data set which is widely used in location science for testing median, center, and other problems, and the results are presented in Table 7. We can see from this table that even for this medium sized data set, all problem instances from D1 through D18 can be solved to optimality within less than 45 min. Most instances can be solved in less than 15 min, with the exception of the center-type or center-like problems (D1, D2, and D7).

Table 7.

VAOMP_C Results on the Swain 55-node Data Set (p = 5).

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites
D1	13.6015	2624	3202520	3065	[18 22 49 53 55]
D2	26.7544	1132	1643325	2575	[18 22 49 53 55]
D3	39.7928	839	1566417	3386	[18 22 49 53 55]
D4	80.1487	1235	2138050	3263	[18 22 49 53 55]
D5	388.0351	0.936	5757	0	[5 19 20 36 38]
D6	513.1713	128.7	183039	661	[2 22 36 37 55]
D7	15.85676	1077	1831727	3366	[18 22 49 50 55]
D8	30.70615	726	1228912	2101	[18 22 49 53 55]
D9	45.39939	613	1045283	1552	[18 22 49 53 55]
D10	91.9623	798	1258651	1794	[18 22 49 53 55]
D11	498.7316	3.245	6809	0	[9 13 19 25 32]
D12	635.6589	65.0	60774	657	[9 19 25 32 44]
D13	17.5212	761	1281296	2806	[16 23 37 46 48]
D14	34.6753	658	1142222	2505	[23 27 37 46 48]
D15	51.2982	521	882595	1688	[16 23 37 46 48]
D16	103.6135	624	1147080	2190	[16 23 37 46 48]
D17	566.4123	56.6	73106	575	[5 9 25 32 33]
D18	716.1050	239.1	232090	982	[9 13 25 32 33]

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Since the p-median problem and many other location problems are often posed with population on the demands, we also tested the VAOMP_C formulation on the original Swain data set with the weight data in order to facilitate comparison with known results in the literature. The VAOMP_C results are presented in Table 8. We can see from this table that (at least for this data set) the computational times for the weighted problem are significantly less (by about one or two orders of magnitudes) than the unweighted case.

Table 8.

VAOMP_C Results on the Weighted Swain 55-Node Data Set (p = 5).

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites
D1	144.4992	87.0	122233	231	[1 2 3 22 41]
D2	284.2128	14.3	25335	134	[1 2 3 22 41]
D3	411.9567	18.5	33695	158	[1 2 3 12 41]
D4	841.0341	12.8	21560	111	[1 2 3 12 41]
D5	2950.4125	0.55	4144	0	[1 3 10 22 36]
D6	4057.0218	7.5	12152	24	[1 2 3 22 41]
D7	166.75699	20.4	32492	200	[2 3 5 12 23]
D8	329.61444	14.5	19824	102	[1 2 3 12 41]
D9	481.3722	14.4	24609	130	[1 2 3 12 41]
D10	986.979	25.0	30544	164	[1 2 3 12 41]
D11	3801.76775	1.1	6377	0	[1 3 4 22 41]
D12	5072.80343	8.7	11766	54	[1 2 3 12 41]
D13	183.19404	25.6	45098	141	[1 2 3 14 28]
D14	360.44148	23.3	41803	153	[1 2 3 14 23]
D15	534.2194	25.0	47580	154	[1 2 3 14 23]
D16	1077.85492	30.7	55681	145	[1 2 3 14 23]
D17	4434.8215	5.7	11809	48	[2 4 22 33 41]
D18	5800.53748	17.3	19527	119	[1 2 3 17 22]

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

We also used a larger US Cities 100 data set, which contains the first 100 cities from the US Cities data set in Daskin (1995), to test the performance of the VAOMP_C formulation. Weights on demands were again not used. The computational results are presented in Table 9. We can observe that the Vector Assignment-PMP and “center-dian” problems, namely, D5, D6, D11, D12, D17, and D18, can be solved optimally, with solution times ranging from a few seconds to 15 min. All other problem instances (i.e., the VA-center and k-centrum problems) could not be solved optimally within the 3-hr time limit. The optimality gaps ranged from 11 percent to 35 percent. As observed earlier, the CA constraints can be dropped when the assignment vector is non-increasing. Table 10 presents computational results for solving a variant of the VAOMP_C formulation which did not include CA constraints. We can observe that dropping CA constraints significantly improved the performance of the formulation. While only six of the eighteen problems in Table 9 could be solved optimally, fourteen of the eighteen problems in Table 10 could be solved. The maximum optimality gap was reduced from 35 percent to about 7 percent. Again, it is important to note that for problems D13 through D18, dropping CA conditions leads to incorrect solutions as the assignment vector is not non-increasing.

Table 9.

VAOMP_C Results on the US Cities 100 Data, p = 5.

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
D1	616	10801	4298975	2320	[10 24 29 31 56]	34.9
D2	1178	10800	4241145	1965	[49 57 91 92 93]	33.0
D3	1728	10801	5193778	3174	[10 31 56 91 98]	28.3
D4	3656	10800	5362608	2339	[28 41 70 77 92]	32.9
D5	26853	3.8	16700	0	[3 18 27 67 88 ]	0
D6	32304	446	335344	688	[3 18 27 37 88 ]	0
D7	679.4	10801	4909848	2922	[24 43 57 64 66]	17.2
D8	1336.6	10801	5228996	3018	[24 43 57 66 91]	15.1
D9	1984.6	10801	5098552	2754	[28 30 43 56 57]	15.1
D10	3985.6	10800	5295524	1739	[28 30 43 56 57]	16.1
D11	37107.8	6.7	6144	0	[25 64 65 68 75]	0
D12	42882	73	50826	0	[64 65 68 73 75]	0
D13	755.6	10801	5651418	5460	[3 61 76 81 93]	11.3
D14	1515.4	10801	5846075	5269	[19 61 76 81 93]	11.3
D15	2280.2	10801	5975315	5600	[32 71 74 82 93]	11.6
D16	4654	10801	6016673	3662	[6 17 28 39 57]	14.7
D17	43463	607	232528	1258	[29 54 65 78 91]	0
D18	49797.8	974	431605	1500	[8 29 63 65 91]	0

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Table 10.

VAOMP_C Results (Without Closest Assignment) on the US Cities 100 data, p = 5.

Problem specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
D1	590	10839	33030949	50060	[14 70 86 95 100]	7.12
D2	1177	10837	31597030	46374	[14 19 33 86 100]	6.12
D3	1728	10827	34279321	59459	[10 31 67 84 93]	1.91
D4	3519	10843	40876733	47633	[14 71 82 86 100]	7.08
D5	26853	0.56	5864	0	[3 18 27 67 88]	0
D6	32304.0	74	293094	762	[3 18 27 37 88]	0
D7	671.2	5175	20481676	51985	[28 30 38 48 92]	0
D8	1329.1	3982	15595507	34431	[28 30 43 56 57]	0
D9	1983.9	3758	14999401	33702	[14 28 30 31 33]	0
D10	3985.6	8009	30317574	40307	[14 28 30 43 57]	0
D11	37107.8	0.8	6901	0	[25 64 65 68 75]	0
D12	42882.0	2.3	14102	0	[64 65 68 73 75]	0
D13	691.2	3525	12835222	25736	[32 61 74 93 96]	0
D14	1367.8	1827	6326560	11380	[14 28 30 43 57]	0
D15	2032.8	1447	4777655	8238	[14 28 30 43 57]	0
D16	4100.8	4107	13370945	14443	[14 28 30 43 57]	0
D17	39586.6	0.9	7086	0	[37 53 65 75 91]	0
D18	45525.8	2.37	11677	3	[29 37 65 73 75]	0

Note: Facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Finally, we compare the performances of the VAOMP model to those of the formulations specifically designed to solve the special cases problems noted in Table 2, namely, the OMP, the VAPMP, and p-median problem and the p-center problem. The OMP is implemented according to an OMP formulation in Nickel and Puerto (2005, 421). The VAPMP formulation is implemented according to Weaver and Church (1985) except that MLCA constraints in Lei and Church (2011a) were added. The p-median problem and the p-center problems were implemented according to the formulations in ReVelle and Swain (1970) and Daskin (1995) respectively. Table 11 presents results for solving the special case problems on the unweighted Swain data set. Problem specific parameters and the corresponding VAOMP specification names were listed in columns 1 and 2, respectively.

Table 11.

Results for VAOMP Equivalent Problems on the Unweighted Swain Data, p = 5.

Parameters	VAOMP specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
OMP, $λ =$
[0 … 0 1]	D1	13.6015	66.2	590288	3497	[18 22 49 53 55]	0
[0 … 0 1 1]	D2	26.7544	48.97	440294	3038	[18 22 49 53 55]	0
[0 … 0 1 1 1]	D3	39.7928	43.7	399188	3114	[18 22 49 53 55]	0
[0 … 0 1 2 3]	D4	80.1487	64	590688	3225	[18 22 49 53 55]	0
[1 … 1 1]	D5	388.0351	0.13	657	0	[5 19 20 36 38]	0
[1 … 1 3 6]	D6	513.1713	2.73	13652	292	[2 22 36 37 55]	0
VAPMP, $θ$ =
[0.7 0.3]	D11	498.7316	0.85	1874	0	[9 13 19 25 32]	0
[0.4 0.6]	D17	566.4123	39.8	71905	575	[5 9 25 32 33]	0
p-median	D5	388.0351	0.06	572	0	[5 19 20 36 38]	0
p-center	D1	13.6015	120.6	738984	3900	[18 22 49 53 55 ]	0

Note: p-median formulation is per ReVelle and Swain (1970), p-center formulation is per Daskin (1995), VAPMP formulation is per Weaver and Church (1985), and OMP formulation is tested using LDOMP2 formulation in Nickel and Puerto (2005, 421); facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Comparing Table 11 with Table 7, we can observe that the formulations specifically designed for the special-case problems are faster than VAOMP_C. The OMP formulation is 8 to 50 times faster than VAOMP_C. The VAPMP formulation was slightly faster than VAOMP_C in solving equivalent problems. While it took VAOMP_C 3.2 and 57 s to solve D11 and D17 problems, the VAPMP formulation took only 0.9 and 40 s, respectively. This shows that the overhead of VAOMP_C over VAPMP is not large. By comparison, the p-median formulation is 10 times and 50 times faster than the VAPMP and VAOMP_C formulations, respectively. The p-center formulation is about 20 times faster than VAOMP_C. Table 12 shows a similar comparison of VAOMP_C and special case formulations for the weighted Swain data set. The OMP formulation is 5 to 50 times faster than VAOMP_C. The p-median formulation is about 10 times faster and the VAPMP formulation is slightly faster than VAOMP_C. This difference is hardly surprising because all tested special-case problems except the VAPMP requires CA constraints.

To summarize the computational experiments in this section, we can see that the VAOMP problem is a very difficult problem to solve in general. General formulations such as VAOMP_H involve long solution times even for a very small 12-node data set. On the other hand, the VAOMP_C formulation is suitable for a special-case (yet also very general) VAOMP problem, confirming prior results (see e.g., Nickel and Puerto 2005) about the effectiveness of similar formulations for the OMP. It can be solved within short computation times even for a median sized problem. The computation times for different special cases of VAOMP vary. In general, our results show that the center-type or center-like problems are clearly harder to solve, as what has been experienced in the literature.

Table 12.

Results for VAOMP Equivalent Problems on the Weighted Swain Data, p = 5.

Parameters	VAOMP specification name	Objective	Time(s)	Iterations	Nodes	Sites	Gap (%)
OMP, $λ =$
[0… 0 1]	D1	144.4992	2.0	13841	131	[1 2 3 22 41]	0
[0… 0 1 1]	D2	284.2128	0.86	4988	115	[1 2 3 22 41]	0
[0… 0 1 1 1]	D3	411.9567	0.96	6147	117	[1 2 3 12 41]	0
[0… 0 1 2 3]	D4	841.0341	2.3	13913	138	[1 2 3 12 41]	0
[1… 1 1]	D5	2950.4125	0.11	544	0	[1 3 10 22 36]	0
[1… 1 3 6]	D6	4057.0218	0.67	3021	35	[1 2 3 22 41]	0
VAPMP, θ =
[0.7 0.3]	D11	3801.76775	0.8	1441	0	[1 3 4 22 41]	0
[0.4 0.6]	D17	4434.8215	6.5	6335	39	[2 4 22 33 41]	0
p-median	D5	2950.4125	0.07	441	0	[1 3 10 22 36]	0

Note: The p-center problem has no equivalent in the weighted VAOMP. p-median formulation is per ReVelle and Swain (1970), VAPMP formulation is per Weaver and Church (1985), and OMP formulation is per Nickel and Puerto (2005), pp 421; facilities are indexed from 1 to n and configurations given in the table conform to this convention.

Conclusions

Past research work has proposed several generalized constructs; among these are the OMP and the VAPMP. In this article, we have proposed a general problem that subsumes both constructs into one general framework, called VAOMP (vector assignment ordered median problem). In this article, we have presented several formulations for VAOMP. These new models are sensitive to distance and integrate explicit constraints which can enforce CA under various special case conditions of the general problem. We have shown that VAOMP is a very general model structure that can subsume as special cases a large number of location-allocation problems including ordered median, reliability location problems, multilevel covering, fault-tolerant location, and interdiction.

The ILP formulations developed in this article can be solved directly by off-the-shelf solvers. We have also analyzed the VAOMP and identified the conditions under which certain constraint structures can be omitted from the formulation.

We tested four different formulations of the VAOMP problem. Our experiments show that it takes a significant amount of computation time in finding optimal solutions for the general form of the problem. However, in the special case where the rank vector λ is non-decreasing and non-negative, the VAOMP_C formulation can solve almost all the tested problem instances in a relatively short amount of time, even for a medium-sized problem. A number of research directions involving VAOMP are possible and may be quite fruitful. This includes, for example, the development of effective heuristic or approximate algorithms for the general VAOMP, the design of branch and bound algorithms, and using externally derived bounds to tighten the VAOMP formulations by fixing variables and adding valid inequalities.

Footnotes

Appendix A

Table A1.

Distance Matrix for the 12-Node Data Set.

ATL	DEN	DFW	JFK	LAX	MIA	MSP	ORD	PHX	SEA	SFO	STL
0	1926	1175	1222	3126	959	1459	976	2549	3505	3435	778
1926	0	1032	2609	1385	2748	1092	1426	968	1646	1553	1236
1175	1032	0	2235	1983	1802	1373	1291	1394	2668	2352	886
1222	2609	2235	0	3974	1757	1651	1188	3458	3887	4152	1432
3126	1385	1983	3974	0	3763	2468	2802	595	1537	543	2558
959	2748	1802	1757	3763	0	2418	1930	3168	4379	4154	1721
1459	1092	1373	1651	2468	2418	0	537	2052	2245	2552	722
976	1426	1291	1188	2802	1930	537	0	2313	2762	2964	415
2549	968	1394	3458	595	3168	2052	2313	0	1782	1046	2027
3505	1646	2668	3887	1537	4379	2245	2762	1782	0	1093	2745
3435	1553	2352	4152	543	4154	2552	2964	1046	1093	0	2787
778	1236	886	1432	2558	1721	722	415	2027	2745	2787	0

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

Note

References

Balinski

M. L.

1965. “Integer Programming: Methods, Uses, Computation.” Management Science 12:253–313.

Boland

Domínguez-Marín

Nickel

Puerto

. 2006. “Exact Procedures for Solving the Discrete Ordered Median Problem.” Computers and Operations Research 33:3270–300.

Brandeau

M. L.

Chiu

S. S.

. 1989. “An Overview of Representative Problems in Location Research.” Management Science 35:645–74.

Church

R. L.

1974. “Synthesis of a Class of Public Facilities Location Models.” PhD. Diss., The Johns Hopkins University, Baltimore, MD.

Church

R. L.

Garfinkel

R. S.

. 1978. “Locating an Obnoxious Facility on a Network.” Transportation Science 12:107–18.

Church

R. L.

ReVelle

. 1974. “The Maximal Covering Location Problem.” Papers of the Regional Science Association 32:101–18.

Church

R. L.

ReVelle

C. S.

. 1976. “Theoretical and Computational Links between the P-median, Location Set-covering, and the Maximal Covering Location Problem.” Geographical Analysis 8:407–15.

Church

R. L.

Scaparra

M. P.

Middleton

R. S.

. 2004. “Identifying Critical Infrastructure: The Median and Covering Facility Interdiction Problems.” Annals of the Association of American Geographers 94:491–502.

Church

R. L.

Weaver

J. R.

. 1986. “Theoretical Links between Median and Coverage Location Problems.” Annals of Operations Research 6:1–19.

10.

Daskin

M. S

. 1995. Network and Discrete Location: Models, Algorithms and Applications. New York: John Wiley & Sons.

11.

Daskin

M. S

1983. “A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution.” Transportation Science 17:48–70.

12.

Daskin

M. S

2008. “What you Should Know about Location Modeling.” Naval Research Logistics 55:283–94.

13.

Domínguez-Marín

2003. The Discrete Ordered Median Problem: Models and Solution Methods. Norwell, MA: Kluver Academic Publishers.

14.

Domínguez-Marín

Nickel

Hansen

Mladenović

. 2005. “Heuristic Procedures for Solving the Discrete Ordered Median Problem.” Annals of Operations Research 136:145–73.

15.

Drezner

Nickel

. 2009a. “Constructing a DC Decomposition for Ordered Median Problems.” Journal of global optimization 45:187–201.

16.

Drezner

Nickel

2009b. “Solving the Ordered One-median Problem in the Plane.” European Journal of Operational Research 195:46–61.

17.

Hardy

G. H.

Littlewood

J. E.

Pólya

. 1952. Inequalities. Cambridge, MA: Cambridge University Press.

18.

Hillsman

E. L.

1984. “The p-median Structure as a Unified Linear Model for Location-allocation Analysis.” Environment and Planning A 16:305–18.

19.

Hogan

ReVelle

. 1986. “Concepts and Applications of Backup Coverage.” Management Science 32:1434–44.

20.

Kalcsics

Nickel

Puerto

Tamir

. 2002. “Algorithmic Results for Ordered Median Problems.” Operations Research Letters 30:149–58.

21.

Lei

T. L.

2010. “Location Modeling Utilizing Closest and Generalized Closest Transport/Interaction Assignment Constructs.” PhD. Diss., University of California, Santa Barbara.

22.

Lei

T. L.

Church

R. L.

. 2011a. “Constructs for Multi-level Closest Assignment in Location Modeling.” International Regional Science Review 34:339–67.

23.

Lei

T. L.

Church

R. L.

. 2011b. “Locating short-term empty-container storage facilities to support port operations: A user optimal approach.” Transportation Research Part E: Logistics and Transportation Review 47:738–754.

24.

Manne

A. S.

1964. “Plant Location under Economies-of-scale-decentralization and Computation.” Management Science 11:213–35.

25.

Marín

A. S.

Nickel

J. P.

Puerto

Velten

. 2009. “A Flexible Model and Efficient Solution Strategies for Discrete Location Problems.” Discrete Applied Mathematics 157:1128–45.

26.

Nickel

Puerto

. 1999. “A Unified Approach to Network Location Problems.” Networks 34:283–90.

27.

Nickel

Puerto

. 2005. Location Theory: A Unified Approach. Berlin and Heidelberg: Springer Verlag.

28.

Ogryczak

Tamir

. 2003. “Minimizing the Sum of the k Largest Functions in Linear Time.” Information Processing Letters 85:117–22.

29.

Owen

S. H.

Daskin

M. S.

. 1998. “Strategic Facility Location: A review.” European Journal of Operational Research 111:423–47.

30.

Puerto

Tamir

. 2005. “Locating Tree-shaped Facilities using the Ordered Median Objective.” Mathematical Programming 102:313–38.

31.

ReVelle

C. S.

Eiselt

H. A.

. 2005. “Location Analysis: A Synthesis and Survey.” European Journal of Operational Research 165:1–19.

32.

ReVelle

C. S.

Marks

Liebman

J. C.

. 1970. “An Analysis of Private and Public Sector Location Models.” Management Science 16:692–707.

33.

ReVelle

C. S.

Swain

R. W.

. 1970. “Central Facilities Location.” Geographical Analysis 2:30–42.

34.

Snyder

L. V.

Daskin

M. S.

. 2005. “Reliability Models for Facility Location: The Expected Failure Cost Case.” Transportation Science 39:400–16.

35.

Stanimirović

Kratica

Dugošija

. 2007. “Genetic Algorithms for Solving the Discrete Ordered Median Problem.” European Journal of Operational Research 182:983–1001.

36.

Swain

R. W.

1971. A Decomposition Algorithm for a Class of Facility Location Problems. Ithaca, NY: Cornell University.

37.

Swamy

Shmoys

D. B.

. 2008. “Fault-tolerant Facility Location.” ACM Transactions on Algorithms (TALG) 4:51:51:1–51:27.

38.

Toregas

Swain

ReVelle

Bergman

. 1971. “The Location of Emergency Service Facilities.” Operations Research 19:1363–73.

39.

Weaver

J. R.

Church

R. L.

. 1985. “A Median Location Model with Non-closest Facility Service.” Transportation Science 19:58–74.