A New Approach Based On the Hybridization of Simulated Annealing Algorithm and Tabu Search to Solve the Static Ambulance Routing Problem

The paper describes a new approach based on the hybridization of Simulated Annealing algorithm and Tabu Search (SA-TS) to solve the Ambulance Routing Problem (ARP).In this research, we present a mathematical model for the addressed problem (ARP) based on the Vehicle Routing Problem (VRP) formulation. In this work, we aim to offer an efficient routing solution to the ambulance vehicles for emergency demands when a disaster or more than accidents occur at the same time. Our proposed approach solves this problem with the application of the cluster-first route-second method to a standard VRP. We propose the k-Means algorithm for the cluster phase and a hybrid meta-heuristic Simulated Annealing-Tabu Search (SA-TS) for the routing phase of the problem. Our approach (k-Means) gives cultures very close to the exact solution and better than the Petal algorithm. Also for the routing phase, experimental results show competitive solutions compared with recent literature review approaches using Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) approaches on Augerat et al (1995) benchmark datasets while improving processing times.