The capacity deployment of emergency medical service systems has been studied over decades. The design problem is still challenging due to the long-term uncertainty like the change of demographics. A novel approach in the form of multi-stage stochastic programming that considers flexibility in engineering design could be a valuable alternative to EMS infrastructure systems design. This paper proposes a hybrid algorithm to the stochastic model to improve its computational efficiency. The new algorithm outperforms other alternative methods in the numerical analysis by 3-6% in terms of quality of the solution, and is at least four times faster than the default methods.