Optimizing Location and Relocation of Response Units in Guarding Critical Facilities

Abstract

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.

Get full access to this article

View all access options for this article.

References

Gilbert

Isenberg

Baecher

Papay

Spielvogel

Woodard

and Badolato

Infrastructure Issues for Cities—Countering the Terrorist Threat. ASCE Journal of Infrastructure Systems, Vol. 9, No. 1 2003, pp. 44–54.

Gendreau

Laporte

and Semet

Solving an Ambulance Location Model by Tabu Search. Location Science, Vol. 5, No. 2 1997, pp. 75–88.

Deb

Agrawal

Pratap

and Meyarivan

A Fast Elitist Nondominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II. Proc., Parallel Problem Solving from Nature VI Conference, Paris, 2000, pp. 849–858.

Kolesar

and Walker

An Algorithm for the Dynamic Relocations of Fire Companies. Operations Research, Vol. 22, No. 2 1974, pp. 249–274.

Mirchandani

Analysis of Stochastic Networks in Emergency Service Systems. IRP-TR-15-75. Operations Research Centre, Massachusetts Institute of Technology, Cambridge, Mass., 1975.

Mirchandani

and Odoni

Locations of Medians on Stochastic Networks. Transportation Science, Vol. 13, 1979, pp. 85–97.

Berman

Dynamic Positioning of Mobile Servers on Networks. Technical Report 144. Operations Research Centre, Massachusetts Institute of Technology, Cambridge, Mass., 1978.

Berman

and Odoni

Locating Mobile Facilities on a Network with Markovian Properties. Networks, Vol. 12, 1982, pp. 73–86.

Berman

and Rahnama

Optimal Location-Relocation Decisions on Stochastic Networks. Transportation Science, Vol. 19, No. 3 1985, pp. 203–221.

10.

Berman

and LeBlanc

Location-Relocation of Mobile Facilities on a Stochastic Network. Transportation Science, Vol. 18, No. 4 1984, pp. 315–330.

11.

Gendreau

Laporte

and Semet

A Dynamic Model and Parallel Tabu Search Heuristic for Real-Time Ambulance Relocation. Parallel Computing, Vol. 27, 2001, pp. 1641–1653.

12.

Holland

Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, Mass., 1975.

13.

Goldberg

Genetic Algorithms in Search. Optimization and Machine Learning, Addison-Wesley, New York, 1989.

14.

Jaramillo

Bhadury

and Batta

On the Use of Genetic Algorithms to Solve Location Problems. Computers and Operations Research, Vol. 29, No. 6 2002, pp. 761–779.

15.

Aytug

and Saydam

Solving Large-Scale Maximum Expected Covering Location Problems by Genetic Algorithms: A Comparative Study. European Journal of Operational Research, Vol. 141, No. 3 2002, pp. 480–494.

16.

Srinivas

and Deb

Multiobjective Function Optimization Using Nondominated Sorting Genetic Algorithms. Evolutionary Computation Journal, Vol. 2, No. 3 1995, pp. 221–248.

17.

Reed

Minsker

and Goldberg

Designing a Competent Simple Genetic Algorithm for Search and Optimization. Water Resources Research, Vol. 36, No. 12 2000, pp. 3757–3761.