Optimization of ambulance services sequencing and scheduling daily decisions with minimizing delay

Ambulances, one of the essential resources in the emergency medical service (EMS), are crucial in transporting patients to hospitals and saving lives. This research addresses the ambulance service scheduling problem (ASSP) for daily planning decisions by minimizing total weighted tardiness. A mixed integer linear mathematical model for the research problem is developed. Since the research problem is shown to be NP-hard, two population-based genetic algorithm (GA) and particle swarm optimization (PSO), and two solution-based, simulated annealing (SA) and tabu search (TS) meta-heuristics are proposed to solve this problem. In addition, the Lagrangian relaxation (LR) and Benders decomposition methods are employed to find effective lower bounds. Random test problems with small, medium, and large sizes are generated and solved by the proposed algorithms to evaluate their performance. Numerical results show that the LR and Benders decomposition can find efficient lower bounds with approximately 4 % and 6 % gap rates, respectively. Furthermore, ANOVA and Tukey’s HSD tests indicate that the GA, PSO, and SA algorithms perform better in small-, medium-, and large-size problems, respectively. It is noticeable that the best-obtained meta-heuristic solutions have a gap rate of approximately 6.21 %, with the best-obtained lower bounds. Moreover, due to the ASSP problem’s stochastic nature, we develop a two-stage stochastic programming model by considering each mission’s weight and time under uncertainty. Additionally, considering enough scenarios, which in our research is 40, the optimal value can be closely approximated. The outputs of this research are employed for a real-world case study as well. Finally, some managerial and practical insights are discussed based on the results.