The outbreak of the COVID-19 epidemic has had a significant impact in increasing the number of emergency calls, which causes significant problems to emergency medical services centers (EMS) in many countries around the world, such as Saudi Arabia, which attracts a huge number of pilgrims during pilgrimage seasons. Among these issues, we address real-time ambulance dispatching and relocation problems (real-time ADRP). This paper proposes an improved MOEA/D algorithm using Simulated Annealing (G-MOEA/D-SA) to handle the real-time ADRP issue. The simulated annealing (SA) seeks to obtain optimal routes for ambulances to cover all emergency COVID-19 calls through the implementation of convergence indicator based dominance relation (CDR). To prevent the loss of good solutions once they are found in the G-MOEA/D-SA algorithm, we employ an external archive population to store the non-dominated solutions using the epsilon dominance relationship. Several experiments are conducted on real data collected from Saudi Arabia during the Covid-19 pandemic to compare our algorithm with three relevant state-of-art algorithms including MOEA/D, MOEA/D-M2M and NSGA-II. Statistical analysis of the comparative results obtained using ANOVA and Wilcoxon test demonstrate the merits and the outperformance of our G-MOEA/D-SA algorithm.