In this study, the problem of optimal location decision of Emergency Service (ES) vehicles such as ambulances, fire trucks and patrols as a server-to-customer service is discussed. Hypercube queueing model (HQM) are employed to achieve performance measures that are sig- nificant to the location decision of ES vehicles. As an extension of this model, Spatial Queueing Model (SQM) is introduced for spatial networks. This study proposes a generalization of SQM for complete networks. Districting of the demand regions with respect to the travel times is used to approximate the service and the interarrival times in Approximate Queueing Model. Service times for the calls are differen- tiated for every demand call regarding the location of the responding vehicle and the demand call. The approximations in SQM is ques- tioned in terms of quality regarding the districting levels, and results are reported against various network parameters such as traffic inten- sity or distribution of demand regions over the area. The number of servers located in a single location is taken unrestricted. The effect of allowing multiple servers in a location is reported. A genetic algorithm is proposed to solve the model for which no closed-form expression exists and its performance is reported.