6. Covering Problems

The mail-order DVD rental company Netflix chooses distribution center locations so that most of its customers receive their DVDs within one business day via first-class U.S. Mail. Similarly, many municipalities aim to have fire crews reach 911 callers within a specified time, such as four minutes. Both of these are examples of the notion of coverage, a concept central to several classes of facility location models; it indicates whether a demand location is within a pre-specified radius (measured by distance, travel time, cost, or another metric) of its assigned facility. Homeowners are covered if they are within four minutes of the nearest fire station, and Netflix customers are covered if they are within one mailing day of a distribution center. Note that in the fire-station example, municipalities typically want to cover all residents (while minimizing the number of service stations to open), whereas Netflix wants to cover as many customers as possible (subject to a limit on the number of warehouses it may operate at any time, as specified by its capital budget). The fire-station problem is an example of the set covering location problem (SCLP), while Netflix’s problem is an example of the maximal covering location problem (MCLP). This chapter discusses both problems.