The ability to locate military units or equipment, police forces, and first responders optimally and to relocate idle units quickly in response to changing conditions is crucial to a country's ability to guard its critical facilities. Such facilities include vital components of the transportation infrastructure, government and monumental buildings, locations of large gatherings, emergency operations centers, and public and private utilities and communications facilities. In this paper, the problem of making optimal location and relocation decisions for a fixed fleet of response units in a transportation network, where travel conditions are uncertain, is addressed. A mixed integer linear program with multiple objectives (maximize secondary coverage and minimize cost) is presented. Because exact solution of such problems may require considerable computational effort, a metaheuristic based on the principles of genetic algorithms is proposed. The heuristic seeks the set of Pareto-optimal location and relocation decisions for each network state. All facilities of concern must be covered by at least one response unit. If the state of the network changes so that coverage is lost (e.g., travel times increase or a response unit is no longer available), one or more of the response units must be relocated. These relocation decisions are also addressed.
Abstract