Covering Problem
In many covering problems, services that customers receive by facilities depend on the distance between the customer and facilities. In a covering problem the customer can receive service by each facility if the distance between the customer and facility
- PDF / 930,796 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 199 Views
Covering Problem Hamed Fallah, Ali NaimiSadigh, and Marjan Aslanzadeh
In many covering problems, services that customers receive by facilities depend on the distance between the customer and facilities. In a covering problem the customer can receive service by each facility if the distance between the customer and facility is equal or less than a predefined number. This critical value is called coverage distance or coverage radius and shown by Dc. Church and ReVelle (1974) modeled the maximization covering problem. Covering problems are divided into two branches; tree networks and general networks, according to their graph. In addition, these problems are divided into two problems: Total covering and partial covering problems, based on covering all or some demand points. The total covering problem is modeled by Toregas (1971). Up to the present time many developments have occurred about total covering and partial covering problems in solution technique and assumptions. Covering problem has many applications such as: designing of switching circuits, data retrieving, assembly line balancing, air line staff scheduling, locating defend networks (at war), distributing products, warehouse locating, location emergency service facility (Francis et al. 1992). Let us first introduce the concept of covering a demand point with an example. Consider the tree network Fig. 7.1: Demand points in this problem are A, B, C and D. The distance between each two demand points, is shown on their connecting arc. Consider that we want the demand of point A to be covered. Coverage distance is supposed to be 5. Thus in order to cover point A, we should locate at least one facility on the network (feasible space of problem), in a way that it’s distance from point A is equal or less than 5. Therefore, the demand point A will be covered if at least one facility is located on one of thick lines, in Fig. 7.2: Consider three candidate locating sites I, II and III (that III is conformed on demand point D). Among these three places only II can cover point A; it means that one facility is located in place II, the demand point A will be covered. Note that the coverage distance (Dc) can be a kind of time or cost. For example, if the walking time from a residential region to a store is equal or less than 5 min the demand of that region will be covered. 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 7,
145
146
H. Fallah et al.
Fig. 7.1 Covering a demand point
15
A
C
8 10
B
D
Fig. 7.2 The space that can cover A
I
5
A
C
5 5
II
B D III
7.1 Problem Formulation The covering problem is one of well known problems of binary programming. Feasible solution space of this problem is a network (graph). In all problems of this chapter, the capacity of facilities is considered to be unlimited. In addition, facilities are desirable; therefore, the nearness of them to the demand points is inte
Data Loading...
