...that new facility will have access to sufficient consumer demand to make it profitable. These considerations also apply to the multifacility case in which several new facilities are sited at once, possibly in addition to a set of already existing facilities owned by the same company. Strategically, a company moving into a new region may want to maximize the amount of potential demand that will be captured by its facilities; since this creates a barrier for entry by potential competitors.

Specifically, consider the situation in which customer demand is concentrated at discrete "demand points", and possibly there are a number of competitive facilities already located in the region under study. As a first step, such a company would usually undertake a study to measure the "available consumer demand". Suppose that the demand points are numbered from 1 to n, and for demand point i the amount of available consumer demand is estimated to be [w.sub.i]. We assume that this quantity represents the total amount of demand the company may expect to capture from location i provided that: (i) the new facility is located in close proximity to demand point i; and (ii) this new facility provides an adequate level of service. In the monopolistic case (i.e., when there are no competitive facilities on the network), [w.sub.i] may simply represent the total number of customers (or the total amount of consumer demand) available at demand point i. When competition is present, the quantities [w.sub.i] should also reflect the share of market i that the company can expect to capture provided assumptions (i) and (ii) are satisfied. It should normally be possible to estimate the values of [w.sub.i] for i = 1,..., n through a customer survey and/or statistical analysis of the past performance of the company's facilities.

It should be recognized that probably not all of the available consumer demand will be captured by the new facilities. In this paper we concentrate on two sources of the potential "loss" of demand:

1. Lack of coverage. This occurs when none of the facilities are close enough to the customer locations to provide a sufficient level of convenience.

2. Lack of service. This occurs when a customer decides to visit a facility, but is dissatisfied with the level of service she receives there. While there may be many reasons for the failure-of-service event to occur, one of the most common (and the one most closely related to location decisions) is congestion (overcrowding) at the facility. We primarily concentrate on this component of the lack-of-service demand loss in this paper, referring to it as the "loss due to congestion" rather than "lack of service" in the remainder of the paper.

The facility location model presented here will explicitly take these two sources of potential demand loss into account.

The standard way of modeling lack of coverage in the location literature is using a location-set-cover approach. In this approach, a certain radius of coverage is defined for each customer location (or "node"); the demand originating from this node is assumed to be covered (or captured) only if there is a facility within this coverage radius. Thus, a customer node is either covered completely or not at all. The study of maximum-coverage objectives in location models can be traced to Church and ReVelle (1974) (with extension in Church and Meadows (1979)), who introduced the Maximal Cover Location Problem (MCLP). In this model, each node has a certain amount ("weight") of associated customer demand. A node is "covered" if there exists a facility within a prespecified coverage radius. The objective is to locate m facilities so as to cover as much of the customer demand as possible. The MCLP is one of the classical models in locational analysis, with a large number of publications on both the theoretical and applied aspects of the model. We refer the reader to ReVelle and Williams (2002) for a recent review of related literature. A closely related problem, called the Location Set Covering Problem (LSCP), is to find the minimum number of facilities that cover all of the customer demands; this problem was originally stated in Toregas et al. (1971).

We consider the all-or-nothing approach to coverage utilized in the models above to be somewhat oversimplified, especially in the case of service and retail facilities. A more realistic representation should allow the degree of coverage to decline as a function of distance from the closest facility. The all-or-nothing assumption was relaxed in Berman and Krass (2002a), where the level of coverage provided by a facility was modeled as a step-function of the distance to the facility. We follow this approach in the current paper to model the demand loss due to lack of coverage.

Berman, Krass and Drezner (2003) further generalized this approach for network models by allowing for a general form of coverage-decay function. They showed that most of the theoretical properties of the MCLP can be extended to the gradual-coverage form of the model. We note that this approach mirrors the approach commonly used by practitioners to locate retail and service facilities. For example, primary and secondary trading areas (consisting of expanding radii) are usually identified for retail facilities, with the assumption that the customers in the primary trading area constitute the main demand base for the facility (i.e., are fully covered), whereas customers in secondary areas are expected to be only occasional shoppers (see, e.g., Jones and Simmons (1993)). This, of course, is an example of a gradual-coverage mechanism.

To model the demand lost due to congestion, we consider each facility as a Markovian queue with a given fixed capacity, and assume that customer demand arriving during the periods when this capacity is reached is lost to the system (that is, potential customers arriving when the system is full are blocked). This framework allows us to identify facility locations that may be swamped by excessive demand, and to select locations that control this effect.

The incorporation of stochastic aspects (involving potential congestion at the facilities) into coverage-type models originated with Maximal Expected Covering Location Problem of Daskin (1983); a significant number of other publications have followed. We refer the reader to Berman and Krass (2002b) for an overview of Location Problems with Stochastic Demands and Congestion (LPSDC). Of particular relevance to the current paper are LPSDC models with fixed servers in which customers travel to facilities to obtain service, and all customers residing at a certain node are assumed to patronize the same facility. This line of research was introduced by Marianov and Serra (1998) who assumed that: (i) the customer demands are generated by a Poisson process; (ii) the distribution of the service time is exponential; (iii) each facility acts as an M/M/1/a queuing system with finite capacity a; and (iv) all demands for service arriving while the system is full are assumed to be lost. Under this model, the customer demand may be lost because there is no facility within the coverage radius, or due to blockage at the facilities. The objective is to locate m facilities to capture as much demand as possible. Marianov and Rios (2000) applied this model to the location of ATM switches. The LSCP version of the model was developed in Marianov and Serra (2002), where the objective is to find the minimum number of facilities so that all customers have a facility within their coverage radius, and the bound on the maximum proportion of blocked demands (or on the maximum waiting time) is satisfied. We note that both Marianov-Serra models assume that customers can be assigned to any open facility within the coverage radius, rather then letting customers patronize the closest facility. Thus, they assume a directed-choice mechanism, rather than a customer-choice mechanism. Other features that distinguish their models from the one developed in this paper are the all-or-nothing coverage mechanism and the solution procedures (we note that in both of their studies Marianov and Serra limited themselves to developing integer programming formulations only).

The model that is perhaps closest to the one considered in the current paper was recently independently developed by Wang et al. (2002), where each customer is assumed to patronize the closest facility (however, the loss of demand due to coverage is not considered in this model). They also investigate a number of computational approaches, including developing an efficient Lagrangian relaxation procedure.

The goal of the location problem addressed in this paper is to identify locations of the new facilities to capture as much of the available demand as possible: i.e., to control the amount of demand lost due to lack of coverage and congestion.

An important feature of our model is that it assumes that each customer will tend to patronize the most convenient (i.e., closest) open facility. This is in contrast to a large number of models in the literature that assume that customers can be assigned to any open facility within the coverage radius. These assignments may result in a customer being routed to a distant facility (or not served at all) in spite of having an open facility nearby. Unless there is a mechanism to enforce such assignments (which is unlikely to exist in service or retail settings), these models may seriously underestimate the amount of traffic and congestion at certain centrally located facilities.

While a number of published studies have contained some of the elements described above, to the best of our knowledge, the model presented in this paper is the first one to combine all of these features. Another objective of this paper is to develop algorithmic approaches for this problem.

The remainder of the paper is organized as follows. Our model is formally introduced in Section 2. We note that there are several alternatives available to develop integer programming formulations, particularly when it comes to closest-assignment constraints that ensure that each customer is assigned to the closest facility. This matter is investigated in depth in Section 3, where we review the closest-assignment constraints previously available in the literature, and present a computational study that shows that the form of the constraints developed in this paper is competitive with the generally recommended form. In Section 4 we turn our attention to developing efficient computational procedures for our model. Due to the complexity of the model, the direct approach of applying commercial solvers to the integer programming formulation of Section 2 is not practical even for medium-sized problems. To overcome this difficulty we develop a number of heuristic algorithms, ranging from simple exchange heuristics, to metaheuristics (e.g., tabu search) to time-limited branch-and-bound procedures. Section 5 contains the results of an extensive set of computational experiments that compare the performance of the different solution procedures. Our results indicate that randomized...

NOTE: All illustrations and photos have been removed from this article.



Looking for additional articles?
Search our database of over 3 million articles.

Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication name or publication date.

About Goliath
Whether you're looking for sales prospects, competitive information, company analysis or best practices in managing your organization, Goliath can help you meet your business needs.

Our extensive business information databases empower business professionals with both the breadth and depth of credible, authoritative information they need to support their business goals. Whether it be strategic planning, sales prospecting, company research or defining management best practices - Goliath is your leading source for accurate information.