Center Problem
In the covering problems, the attempt is to determine the location of the minimum number of facilities necessary to cover all demand nodes. In this type of problems, the coverage distance is an exogenous data. But sometimes the number of facilities needed
- PDF / 964,881 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 23 Downloads / 234 Views
Center Problem Maryam Biazaran and Bahareh SeyediNezhad
In the covering problems, the attempt is to determine the location of the minimum number of facilities necessary to cover all demand nodes. In this type of problems, the coverage distance is an exogenous data. But sometimes the number of facilities needed to cover all demand nodes with a predefined coverage distance may be quite large. In order to overcome this, the maximum covering location problem has been discussed. In this model, the objective is to maximize the number of covered demand nodes with a fixed number of facilities. In other words, we relaxed the total coverage requirement (Daskin 1995). A different strategy is discussed in this chapter. Now, instead of asking the model to minimize the number of facilities with a given coverage distance, we will ask the model to minimize the coverage distance with a given number of facilities, while maintaining the coverage of all demand nodes. This model is introduced under the title of p-center problem which is in fact a minimax problem. In this model, the objective is to find locations of p facilities so that all demands are covered and the maximum distance between a demand node and the nearest facility (coverage distance) is minimized. It can be said that we have relaxed the coverage distance (Daskin 1995). In the p-center model, each demand point has a weight. These weights may have different interpretations such as time per unit distance, cost per unit distance or loss per unit distance (Daskin 1995). So the problem would be seeking a center to minimize a maximum time, cost or loss. In other words, the concern is about the worst case and we want to make it as good as possible (Francis et al. 1992). For example, assume that we need to establish a number of fire stations in a town. If the time to reach the scene from facility j to demand node i is dij , then this amount must not be greater than minutes. Therefore, we are looking to provide dij < for each node i and a closest facility j . If we are to cover all the points, we need certain number of facilities. To evaluate the number of facilities needed, one needs to solve a set covering problem. Now assume that there is a budget constraint and we can not establish enough fire stations, then there are two ways of approaching the problem. One is to cover maximum points; in this case you are facing a maximum covering problem. The second approach is to cover all of demand nodes, but through increasing the radius of coverage distance. Evaluation of the minimum increase in R.Z. Farahani and M. Hekmatfar (eds.), Facility Location: Concepts, Models, Algorithms and Case Studies, Contributions to Management Science, c Physica-Verlag Heidelberg 2009 DOI 10.1007/978-3-7908-2151-2 9,
193
194 Fig. 9.1 Example network illustrating suboptimality of nodal locations (Daskin 1995)
M. Biazaran and B. SeyediNezhad
A
8
B
the coverage distance with respect to the given number of facilities can be done with a p-center model. One should recognize the difference between pr
Data Loading...
