Positioning of Emergency Facilities in an Obstructed Traffic Grid

Student Co-author

HMC Undergraduate

Document Type



Mathematics (HMC)

Publication Date



We developed algorithms to determine the optimal location of emergency service centers in a given city. We give consideration both to the peculiarities of a particular town, Rio Rancho, and to the procedure by which problems of this nature can be solved in general. The streets of Rio Rancho are laid out in a uniform grid, except for two obstacles through which there are no streets. We are given data for the demand for emergency service at each block in the grid. We developed algorithms to find the transit times between any two points on the grid for Rio Rancho. To do this, we calculated a distance on a grid with no obstacles, then adjusted for the particular obstructions. We first assumed that demand was concentrated at the center of each block and that stations were located at street intersections. Under these assumptions, the problem is amenable to an exhaustive trial of all possibilities. We then made the more sophisticated assumption that the distribution of demand is continuous, and that the emergency facilities could be located anywhere on the streets. We prove two results which greatly reduce this problem: (1) it is necessary that the location of such emergency station be at an intersection; and (2) it is an equivalent problem to consider the demand to be located discretely at the center of each block, rather than being continuously distributed over the block. Due to these results, it is possible to run an exhaustive case study in this case as well. Statistical distributions were calculated to provide a means of comparison of the optimal result with the average result. We studied the stability of the solution with respect to the demand distribution and obstacle configuration and found it to be very stable in the first case, and reasonably stable in the latter. Finally, we discuss how similar problems would be approached, and in particular, how an approximation scheme could be implemented if the large number of possibilities prohibits an exhaustive analysis.

Rights Information

© 1986 Published by Elsevier B.V.