|
Article Excerpt
1. Introduction
The fundamental problem facing emergency system planners can be described as follows. Customers residing at the nodes of a transportation network generate stochastic streams of service calls. These calls are served by mobile servers housed at a number of facilities. In emergency settings, calls must be handled promptly--which means that only a server located within a certain coverage radius of the customer may provide service. Moreover, since servers may be unavailable due to congestion, it is important to ensure that an incoming call finds a free server with a sufficiently high probability. Given the high cost of maintaining each additional server (a single police car staffed around the clock costs over one million dollar per year--see, e.g., Larson (1975), inflation adjusted), a service system planner must balance the service levels achieved with the cost incurred. This paper deals with two of the most critical strategic decisions for such systems: location of facilities and allocation of server capacity.
This problem belongs to the general class of Location Problems with Stochastic Demands and Congestion (LPSDC) reviewed in Berman and Krass (2002). One of the most important applications for mobile-server LPSDC models is the location of emergency service facilities such as ambulance, police and fire stations. The ability to quickly respond to a service call is particularly important in such problems. Potential applications also exist in other areas, including the location of service centers, sales offices, and cars by car sharing services (e.g., Zipcar.com).
Most mobile-server LPSDC problems combine aspects of classical location problems with the dynamics of spatially distributed queueing systems (Larson and Odoni, 1981) and are analytically intractable. Thus, a number of simplifying assumptions are usually made to obtain tractable models. Standard assumptions are that call arrival processes are Poisson and call service times are exponentially distributed. Even under these conditions, no analytical expressions exist for expected system performance measures such as server availability at a given customer node ("node availability"). This has led to the development of several models that employ various estimates of node availability in order to enforce the service level constraints. Our paper includes an examination of several best-known models in this area. We show that the availability estimates used in these models may result in systems that significantly underachieve the desired availability levels--i.e., these models fail to obtain feasible solutions. Through a series of computational experiments we demonstrate that this phenomenon is not uncommon--the vast majority of instances we generated had at least one demand-generating node where the desired availability was not met.
The LPSDC models we consider belong to the class of location set-covering problems, where the objective is to minimize the total number of servers required to provide adequate service (see Berman and Krass (2002) for an overview of the other main direction in LPSDC research--the median-type problems where the objective is to minimize the total response time).
The stochastic elements in set-covering models were introduced by Daskin (1983). Daskin makes the following three simplifying assumptions.
1. Servers operate independently of one another--thus the busy fraction of a server (the probability of finding a particular server busy at any time) is independent of that of other servers.
2. The busy fraction is identical for all servers.
3. The busy fraction is irrespective of allocation decisions.
The servers' busy fraction, p, is treated as an external parameter. Indeed, the congestion aspect of the underlying system is not explicitly captured in Daskin's model, however, this model has led to several models that integrate congestion and seek to relax some of the basic assumptions made listed above.
Batta et al. (1989) attempt to relax the assumption that the busy fraction of different servers are independent. Following Larson (1975), they introduce an adjustment factor to account for interdependence between servers. However, they still treat p as an external parameter. The first model to make the busy fraction p an endogenous parameter was developed by ReVelle and Hogan (1989a, 1989b), who use region-based estimates of p, but still retain Daskin's assumption that servers within each region are independent. The next significant step in set-covering LPSDC model development was taken by Marianov and ReVelle (1994, 1996) who represent each region as a multi-server Markovian queue and use queueing-based formulas to estimate node availability. While they use an M/M/k/k loss system representation, assuming that any call that cannot find a free server is routed to a back-up system, their approach easily extends to M/M/k systems (where incoming calls are queued) or other standard queueing models. Their model inherits ReVelle and Hogan's assumption that the probability of a server being busy is region-specific and is identical for all servers in each region. As discussed in Section 3 below, neither the Revelle-Hogan nor Marianov-Revelle models guarantee the availability requirements in the underlying system.
Ball and Lin (1993) developed the first model that ensures system feasibility, but under fairly stringent assumptions. In particular, they assume that service times are deterministic and equal to T > and derive facility-specific lower bounds for server availability. Their approach also extends to the case where service times are stochastic and bounded above by T, however, in this case the availability estimate becomes loose, which may lead to solutions that require an unrealistic number of servers. The approach does not easily extend to the case where service times are stochastic and unbounded (e.g., exponential). Further discussion of this model is provided in Section 3.
Borras and Pastor (2002) provide the ex-post evaluation of the availability level of several known models (including the ones listed above) by simulation, observing that desired availability is often not met. We note that their simulation operates as a loss system--i.e., any incoming call that cannot find a free server is dropped; in our simulation experiments, all calls are queued. They also suggest a new model formulated similar to the Ball-Lin model, but incorporating the estimate for the busy fraction of the ReVelle-Hogan model. While their model behaves well in computational experiments, it still does not guarantee a feasible solution. As mentioned earlier, our approach focuses on deriving provably feasible models via the analysis of the underlying queuing network.
The key contribution of this paper is the development of lower bounds for the node availability of the underlying systems. These bounds allow us to develop location models that guarantee feasibility with an increase of at most 20-30% in the total number of servers in comparison to the ReVelle-Hogan and Marianov-Revelle models, which as shown in Section 6 are often infeasible.
The plan for the remainder of the paper is as follows. In the next section we formulate the LPSDC model considered in the paper. Section 3 reviews three main models from the literature and demonstrates that their solutions may be infeasible. In Section 4 we analyze the underlying queuing network, representing it as a partially-accessible queueing system and deriving easily-verifiable stability conditions and lower bounds on system availability. In Section 5 these bounds are used to derive two new location models. In Section 6 we briefly discuss the issues involved in extending the two models to more general queueing systems. Section 7 presents the results of a series of computational experiments that use simulation to evaluate the performance of the existing and new models. Section 8 contains concluding remarks and directions for future research.
2. The set-covering LPSDC and mobile servers
2.1. Basic definitions
We consider an undirected network G = (N, L), where N is the node set and L is the link set. For i, j [member of] N, d(i, j) denotes the shortest distance between i and j on G. The set-covering-type LPSDC is defined by the following elements: demand points (nodes), facilities, servers, buffers and service discipline. Each of these elements are discussed below.
2.1.1. Demand points
We assume that customers are located at the nodes of the network, the demand process for each node i [member of] N is an independent Poisson process with rate [[lambda].sub.i] and a call at node i can be served only by servers within a prespecified distance [delta] > from node i; [delta] is the coverage radius of the system.
The node subset [N.sub.i] = {j [member of] N|d(i,j) [less than or equal to] [delta]} is called region [N.sub.i]. It represents the set of nodes that can be covered by a service facility at i. We also refer to node i as the center of region [N.sub.i] and all the other nodes in [N.sub.i] as the peripheral nodes of [N.sub.i].
For a subset V [subset] N, we denote the set of nodes accessible from V to be [[union].sub.j[member of]V][N.sub.j] (this is the set of potential facility locations that may serve at least one call from V). Region [N.sub.i] is said to be "isolated" if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] overlapping" otherwise. Calls from an isolated region have to be served within the region, while those from an overlapping region may be served from outside the region.
For a subset V [subset] N of nodes, we denote the total rate at which demand calls originate from V by [lambda](V) = [[SIGMA].sub.n[member of]V] [[lambda].sub.n] We illustrate the definitions above with the following example, which will be used throughout the paper:
Example 1. (A three-node path example.)
Consider a three-node path: N = {1, 2, 3}, d(1,2) = 1.9 and d(2, 3) = 2. Suppose that [[lambda].sub.1] = 2, [[lambda].sub.2] = 1, [[lambda].sub.3] = 2 and [delta] = 2. The network is illustrated in Fig. 1.
[FIGURE 1 OMITTED]
There are three regions: [N.sub.1] = {1,2}, [N.sub.2] = {1,2,3} and [N.sub.3] = {2, 3}. Observe that node 2 is the center of [N.sub.2] and the two peripheral nodes (1 and 3) in [N.sub.2] are not within the coverage radius from each other. Note that regions [N.sub.1] and [N.sub.3] are overlapping and that region [N.sub.2] is isolated.
The demand rates for the three regions are [lambda]([N.sub.1]) = [[lambda].sub.1] + [[lambda].sub.2] = 3,[lambda]([N.sub.2]) = [[lambda].sub.1] + [[lambda].sub.2] + [[lambda].sub.3] = 5 and [lambda]([N.sub.3]) = [[lambda].sub.2] + [[lambda].sub.3] = 3.
2.1.2. Facilities
We assume that the set of potential facility locations (or sites) consists of the node set N. We note that this assumption can be made without loss of generality. This is so because N can be extended to be the finite dominating set (see Berman et al. (1985) for details). We also note that all the results in the paper continue to hold if the set of potential locations consists of some subset of N (i.e., if some nodes cannot be used as facility locations).
The number of servers x(j) [greater than or equal to] to be placed at site j [member of] N is a decision variable. We denote an allocation vector by x = (x(l), ..., x([absolute value of (N)])). If a facility is located at site j, x(j) >0, 0, otherwise x(j) = 0. Let X = {j [member of] N|x(j) > 0} be the set of facility nodes, [absolute value of (X)] be the number of facility nodes and [X.sub.i] = {j: x(j) > 0, j [member of] [N.sub.i]} = X [intersection] [N.sub.i] be the set of facility nodes within region [N.sub.i]...
|
