The first contact between patients and the healthcare system often occurs through prehospital care, administered by emergency medical services (EMS). However, these services are inherently costly, and costs increase significantly with the number of ambulances, staff, and depots (or stations). Further, achieving fairness goals set for EMS response times remains critical. These goals typically vary between different types of incidents (acute versus urgent) and different types of regions of a country (rural versus urban). This study formulates fairness as explicit objectives within a multi-objective optimization framework. We leverage single- and multi-objective metaheuristic optimization algorithms to identify efficient and fair ambulance allocation strategies. Our empirical study, which is based on an incident data set provided by the Emergency Medical Communication Center (EMCC) of Oslo University Hospital (OUH) and the Norwegian National Advisory Unit for Prehospital Emergency Medicine (NAKOS), demonstrates the benefit of multi-objective formulation relative to the alternatives. On high-demand days, multi-objective adaptive ambulance allocations reduce response time violations by up to 31.4%. Key contributions include: (1) Formulating ambulance allocation as a multi-objective problem balancing fairness and efficiency; (2) Demonstrating the benefits of time segmentation, where reallocations at optimal intervals significantly improve compliance rates; and (3) Showing that NSGA-II consistently outperforms a traditional genetic algorithm in minimizing response time violations, particularly under high-demand scenarios.