Track: Operations Research

Abstract

An important component in decision making for public sectors relates with siting of facilities to achieve full or maximal coverage across an area to serve. Given a region, optimal deployment of facilities is sought from potential points. The objective is to find the minimum number of facilities achieving complete coverage, or to find the maximum coverage constrained by a fixed number of facilities. They are dealt in a set covering context; the former is called the location set covering problem (LSCP), while the latter is known as the maximum covering location problem (MCLP). The shape of coverage by a single facility is typically circular, commonly with square, rectangular, and elliptic variations. Along with a geographical dataset, a demand region is given by a polygon or alternatively by segments or points. Potential facility sites are given by a set of points. The attribute of a facility siting is associated with a binary {0, 1} decision variable, and the associated problem is reduced to either an inter programming (IP) or a mixed integer programming (MIP).

This problem formalization is applicable to siting of infrastructure facilities such as fire stations, police stations, cell towers, warning sirens, airborne radars, precipitation monitoring sensors, and so on. This type of infrastructural system is forced to spend at least tens of thousands of dollars for the installation of a single facility, for which minimization of the number of facilities is paramount in the planning phase.

Meanwhile, another but similar type of infrastructural system is concerned with coverage of an entire region occasionally with a limited number of facility resources. A sited facility is capable of covering a region, typically regulated by distance of travel time, but all sited facilities cannot cover the entire region of interest at one time instant. Instead, a facility is mobile or capable of moving around, with which the entire region can be covered within a time standard. Security patrol, whether with a vehicle or feet, is a practical application; for example, multiple police officers patrol a town to ensure the entire region is “covered” (secure in practice), where the coverage is attained within a time slot, typically several hours. This kind of operation might be formalized as a sort of {0, 1} decision making problem, but no formalization of coverage accounting for both space and time exists to date.

Along these lines, this study models and formalizes a spatial-temporal set covering problem accounting for mobility of facilities. Any demand point must always be covered within a time standard, which is comprehended as an expiration time. The problem is formalized in an IP problem context. The optimal value relates with the minimum number of facilities, while the optimal solution reflects the optimal siting of facilities at each time instant, with which the routing of each facility can be identified as well.