Emergency medical service provides a variety of services for those in need of emergency care. One of the major challenges encountered by emergency service providers is selecting the appropriate locations for ambulance stations. Prior works measure spatial proximity under Euclidean space or static road network. In this paper, we focus on locating the ambulance stations by using the real traffic information so as to minimize the average travel-time to reach the emergency requests. To this end, we estimate the travel-time of road segments using real GPS trajectories and propose an efficient PAM-based refinement for the location problem. We conduct extensive experimental evaluations using real emergency requests collected from Tianjin, and the result shows that the proposed solution can reduce the travel-time to reach the emergency requests by 29.9% when compared to the original locations of ambulance stations.