This thesis deals with the problem of locating emergency vehicles in an urban area. An optimization model is formulated that extends previous work by allowing stochastic travel times, unequal vehicle utilizations, and backup service. The heart of the model is a procedure similar to the Hypercube approximation model. Ten pair-wise interchange heuristics are developed and tested on 240 test problems. Demand and service time components of the test data have been generated using characteristics of the Tucson Emergency Medical System. Geographical components of the test data have been generated using actual city shapes as models. It is believed that these test problems are more indicative of actual emergency vehicle location problems than those previously presented in the literature.