1. Introduction
This topic of Emergency Medical Services (EMS) has been intensively studied since the 1970s. Taiwan, from around 1995, modern concepts of the EMS were imported and supported by legislation [1]. Emergency Medical Services (EMS) is considered a critical component of the health system. It is responsible for the pre-hospital, which start from the arrival of an emergency call to the reach of the patient’s destination. The goal of EMS is to enhance survival rate, control morbidity, and prevent disability by providing rapid assessment, timely provision of appropriate interventions, prompt transportation to the nearest suitable health facility [2]. Consequently, the researchers are dedicated to accurately forecasting demands, rigorously measuring performance, strategically selecting ambulance station locations, and effectively allocating ambulance resources [3].
In the pursuit of enhancing survival rates in both urban and rural contexts, our research aligns with the operational research perspective in selecting optimal ambulance locations. A recent review classified the decision problems related to operational EMS management into ambulance location problems and dispatching problems [4]. This deliberate approach ensures a holistic understanding and effective resolution of challenges within EMS management, contributing to the overarching goal of improving emergency medical care in diverse settings.
Numerous studies have achieved remarkable advances in urban areas, such as Taipei, Taiwan, Vienna, Austria, Niigata, Japan, Chicago, America, Porto, Portugal, Shanghai, China, and Trondheim and Malvik, Norway [5]-[11]. Meanwhile, only a few studies have worked on ambulance location problems in rural areas, such as Leon, Spain, Hanover, Germany, and South Dakota, America [12]-[14]. In terms of the objective of the ambulance location problem, it is generally maximizing the coverage of the prespecified zones. Recently, it has been suggested that equity be incorporated into the model by minimizing the number of uncovered zones or the average response time for uncovered calls [4], [15]-[17].
The ambulance location problem aims to determine the number of ambulances in potential sites while considering constraints, such as the types of vehicles, the ambulance fleet size, the response time, and the workload of medical personnel. Meanwhile, the ambulance dispatching problem aims to decide which vehicle to assign to an emergency call. EMS thus raises issues concerning how to simultaneously maximize the coverage and minimize the response time of uncovered zones. Also, the protection of EMS personnel from occupationally acquired infections due to the pandemic should be noted. Medical care providers are mandated to use appropriate personal protective equipment (PPE) before responding to an emergency call [18].
The EMS process is composed of eight stages, including getting emergency calls, dispatching available ambulance and trained personnel, enrouting from to the scene, arriving at the scene, contacting the patient, departure from the scene, appropriate destination, and returning to the responding unit as an available vehicle [14]. EMS thus raises issues concerning how to provide emergency medical care to all who need it within a short time. Kobusingye et al. [2] point out the key issues are surveillance and identification of acute events; trained personnel and equipment of on-site management; safe transportation, transportation equipment, and referral system; personnel, equipment, and services of health facility care. Later, Tucker [19] also presents the challenges of EMS, such as timely EMS response, the availability of functional emergency vehicles with functional preemption systems, and the adequate ratio of transport units to respond to citizens.
During the pandemic, it is essential to acknowledge the significance of safeguarding EMS personnel from infections acquired while on duty. Medical care providers must utilize suitable personal protective equipment (PPE) prior to attending to an emergency call [18]. The majority of these concerns pertain to metropolitan regions. However, the characteristics of urban areas include reduced transportation time and a concentrated population, which distinguishes them significantly from rural areas in terms of EMS operations. In rural areas, on the other hand, the characteristics of rural areas are a sparsely distributed population, a limited number of EMS stations, long travel distances, geographic barriers, lack of professional or trained personnel, aging or inadequate equipment, and absence of specialized EMS facilities [14], [20]. Additionally, the fatality rate is 2.6 times higher than in urban areas [20]. Therefore, determining and studying ambulance location problems in rural areas could be helpful to patients. The challenges in rural and wilderness EMS are time loss in response and transport, critical incident detection and reporting, EMS dispatching and arrival, provision of medical care, recruitment, training, and retention of trained EMS personnel [21].
In this work, we aim to tailor a genetic algorithm (GA) to optimize the proposed ambulance location problem, considering coverage, equity, practical concerns about COVID-19, and the situation in a rural area. Specifically, the objective function intends to maximize the number of demand zones to be covered and simultaneously minimize the travel time for uncovered demand zones. Also, to protect EMS personnel from COVID-19, the required time of putting on personal protective equipment is added into chute time if the demand is suspected. Furthermore, two types of EMS vehicles are widely used in Taiwan: basic life support (BLS) and advanced life support (ALS). This research aims to formulate an ambulance location problem for rural emergency medical services, taking into account not only coverage but also equity considerations. The model incorporates various types of ambulances and the chute time required for medical staff preparation to enhance practicality. This study introduces a tailored genetic algorithm for optimizing the challenging problem. The effectiveness and efficiency of the proposed algorithm will be verified by a set of experiments.
This study is organized as follows. The literature related to the problem under study is briefly reviewed in Sect. 2. The mathematical problem formulation and description are presented in Sect. 3. A tailored genetic algorithm to tackle the studied problem is proposed in Sect. 4, while Sect. 5 is devoted to the computational experiments. Lastly, Sect. 6 presents the conclusions reached.
2. Optimization of Ambulance Location
The ambulance location problem has received much attention since the 1970s [4] and [16]. This problem was first formulated by Toregas, Swain, ReVelle, and Bergman [22], named location set covering problem (LSCP), and the objective is to minimize the total number of ambulance locations such that all demand zones are adequately covered. However, in some practical contexts, it takes a significant number of vehicles to cover the demands thoroughly. Moreover, being a pivotal role in the chain of survival, it seeks to increase the usage of given ambulances. Therefore, the maximal covering location problem (MCLP) was formulated by Church and ReVelle [23], and the objective is to maximize the number of people covered within the desired service distance under the constraints of a given vehicle fleet.
This model was extended by Schilling et al. [24] with two types of vehicles named primary and special equipment, which is similar to the idea of contemporary types of ambulance named basic life support (BLS) and advanced life support (ALS) [25]. These seminal mathematical models of ambulance location problems are classified into three main categories by B\(\acute{\mathrm{e}}\)langer et al. [4] in chronological order, corresponding to single coverage deterministic models, multiple coverage deterministic models, and probabilistic and stochastic models. Single coverage deterministic models have led to a proliferation of research on ambulance location problems with relatively simple formulations. These models shared an assumption that ambulances are always available for emergency requests. Unfortunately, this assumption may not be robust enough in real life. For instance, two consecutive calls from the same demand zones cannot be covered with the same ambulance in a short time. Therefore, multiple coverage deterministic models are provided to be conducive to robustness by doubly covering the demands zones. Daskin and Stern [26] proposed that the hierarchy objective set covering problem (HOSC) was the first research to consider multiple coverages. The HOSC provides multiple coverage by minimizing the number of ambulances for singly covering and maximizing the number of additional ambulances available to an emergency call within a prespecified time. This very first research gave rise to the following variants that tend to escalate the multiple coverage by considering the demand of each additional ambulance [27], by covering demand zones twice within a given number of ambulances [28], or by integrating double coverage and two different coverage radiuses [29].
The double standard model (DMS) presented by Gendreau et al. [29] seeks to maximize the demand zones covered twice within a large radius while ensuring a proportion of the demand zones are covered once within a small radius. Researchers in many countries have widely adopted this model. Doerner et al. [30] applied the DSM in Austria and introduced a penalty term to prevent some ambulances from covering only a small demand. Laporte et al. [31] employed a dynamic version of DSM to cope with the ambulance location problem in Canada, Austria, and Belgium. They presented a busy fraction for each ambulance to indicate the probability of being unavailable. Liu et al. [25] introduced two types of ambulance and severity to the DSM to address the ambulance location problem in America, while Su et al. [32] refined the DSM with a different objective function in China. They aimed to minimize both the expected cost of delayed services and the operation cost of EMS under a limit on ambulance workload. Liu et al. [33] enhanced their previous work in America to a more efficient demand-responsive system by considering the availability of ambulance and service reliability requirements from competing demand zones.
Dibene et al. [34] reported a robust version of the DSM applied in Mexico. They classified the demand into scenarios and involved the following information for optimization, including potential base location, call demand and priority, demand scenarios, demand points, and average travel time. In all this research, practical concerns and empirical data are used to conduct computational experiments for ambulance location problems around the world. Alongside the progress on models for ambulance location problems, numerous studies have been dedicated to providing a more comprehensive perspective. Basar et al. [15] reported several constraints, including coverage, server capacity, the priority of different types of servers, the maximum number of servers at each location, maximum distance, and upper bound on the number of assigned servers. Aringhieri et al. [16] suggested incorporating equity and uncertainty, while B\(\acute{\mathrm{e}}\)langer et al. [4] recommended including real-time information, medical outcome, and equity. They also point out the need for the development of a more efficient solving method. Later, Tassone and Choudhury [17] summarized the techniques and models for ambulance location problems and emphasized the importance of achieving a unique and powerful method.
The solution techniques from an operational research perspective can be divided into optimal, heuristic, metaheuristic, and simulation [15]. Optimal methods are proposed to obtain exact solutions with brand-and-bound algorithms or optimizers such as CPLEX, Gurobi, Fico Xpress, and MOSEK [17]. Some researchers utilized these methods to tackle the variants of ambulance location problems [34], while others employed heuristics to obtain approximate solutions [32]. Meanwhile, more works have been reported on using metaheuristics to retrieve approximate solutions. Among those researchers, tabu search (TS) [12], [15], [29], [30] ant colony optimization (ACO) [30], genetic algorithm (GA) [35], particle swarm optimization (PSO) [36], and variable neighborhood search (VNS) [30] have received considerable attention. Lastly, some studies in the literature attack the ambulance location problem with simulation methods [37].
While Numerous studies have applied their ambulance location models using real data from urban areas [5]-[11], ambulance location problems in rural areas pose different challenges from those in urban areas. Recent research [38] explored the challenges in rural areas: longer transportation distances, patient transfer delays, limited resources, fickle weather and seasonal factors, and scarcity of skilled and trained emergency service providers. Few studies have worked on the ambulance location problems in rural areas. Through this literature review, we observe that the researchers studying rural area ambulance location problems are relatively insufficient. Moreover, most of these studies are dedicated to urban areas due to the complex geographical network, heavy traffic, dense population, and speedy road. However, rural areas have scarce resources, long travel distances, and sparsely distributed services that are crucial but rarely addressed. This raises the need to better investigate the ambulance location problem in rural areas and propose an efficient method to obtain effective solutions.
3. Problem Statement
To tackle the proposed ambulance location problem, we adopted the double standard model (DSM) introduced by Gendreau et al. [27] by adding two service coverage standards into the proposed model. The two service coverage standards ensure that a portion of demand zones is covered by EMS vehicles within the primary standard, and all demand zones must be covered within the secondary standard, which is a more extended time period than the primary standard. Moreover, considering the context of COVID-19 and the situation in Taiwan, three practical limitations have been considered, including suspected COVID-19 demands, two types of EMS vehicles, and chute time. A demand call with COVID-19 must be covered by a vehicle with personal protective equipment (PPE), and the travel time equals the sum of chute time and en-route time. Similar to the USA, there are two types of EMS vehicles in Taiwan: basic life support (BLS) and advanced life support (ALS). A demand call of higher severity is covered by an ALS ambulance, while BLS or ALS ambulances cover lower-severity demands. The proposed model aims to consider coverage and equity for a good and similar response to all the demands by maximizing the number of demand zones to be covered and minimizing the travel time for uncovered demand zones. Given a set of possible locations for ambulance stations with two types of EMS vehicles and a set of demand zones with or without COVID-19, the proposed model locates ambulance stations and allocates ambulances to these stations based on the objectives mentioned above and constraints. The parameters and their description are presented in Table 1, and the mathematical model is explained in the following section. Table 2 summarizes the decision variables and auxiliary variables, where the decision variables \(x_{ij}^{k}\) takes value 1 if the demand zone \(i\) is covered by type \(k\) ambulance from location \(j\), and 0 otherwise, while the auxiliary variables \(z_{i}^{k}\) takes 1 represent the demand zone \(i\) is covered by type \(k\) ambulance, \(\delta_{i_{j}}^{k}\) takes 1 represent the demand zone \(i\) is covered by type \(k\) ambulance from location \(j\) within primary coverage standard (\(r1\)), \(\theta_{ij}^{k}\) takes 1 represent the demand zone \(i\) is covered by type \(k\) ambulance from location \(j\) within secondary coverage standard (\(r2\)).
Table 1 Notations |
 |
Table 2 Decision variables and auxiliary variables |
 |
Maximize
| \[\begin{align} & F_{3}=\omega_{1}\ast \frac{F_{1}\!-\!F_{1}min}{F_{1}max \!-\! F_{1}min}+\omega_{2}\ast \frac{F_{2}\!-\!F_{2}min}{F_{2}max \!-\! F_{2}min} \tag{1} \\ & F_{2}=\frac{1}{R}=\frac{\sum\nolimits_{i=1}^n \sum\nolimits_{j=1}^m \sum\nolimits_{k=1}^q {D_{i}^{k}\left(1-x_{ij}^{k}\right)}}{\sum\nolimits_{i=1}^n \!\sum\nolimits_{j=1}^m \!\sum\nolimits_{k=1}^q \!D_{i}^{k}\!\left(\!1-x_{ij}^{k}\!\right)\!\min \left(t_{ij}\right)} \tag{2} \\ & F_{1}=C=\frac{\sum\nolimits_{i=1}^n \sum\nolimits_{j=1}^m \sum\nolimits_{k=1}^q {D_{i}^{k}x_{ij}^{k}}} {\sum\nolimits\nolimits_{i=1}^n \sum\nolimits_{j=1}^m \sum\nolimits_{k=1}^q D_{i}^{k}} \tag{3} \end{align}\] |
Subject to
| \[\begin{align} & D_{i}^{k}=\bar{d}_{i}^{k}+d_{i}^{k} \hskip3.5mm \forall i\in I,\forall k\in K \tag{4} \\ & \big(d_{i}^{k}-1\big)- z_{i}^{k}M<0 \hskip3.5mm \forall i\in I, \forall k\in K \tag{5} \\ & {\big(d}_{i}^{k}-1\big)+\big(1-z_{i}^{k}\big)M\geq0 \hskip3.5mm \forall i\in I, \forall k\in K \tag{6} \\ & t_{ij}^{k}=t_{ij}+ \bar{t}_{j}^{k}+ t_{j}^{k}z_{i}^{k} \hskip3.5mm\forall i\in I,\forall j\in L,\forall k\in K \tag{7} \\ & y_{j}^{k}=\sum\nolimits_{i=1}^n x_{ij}^{k} \hskip3.5mm \forall j\in L,\forall k\in K \tag{8} \\ & \sum\nolimits_{j=1}^m {y_{j}^{k}\leq}{p}^{k} \hskip3.5mm \forall k\in K \tag{9} \\ & \sum\nolimits_{k=1}^q {y_{j}^{k}\leq} p_{j} \hskip3.5mm\forall j\in L \tag{10} \\ & {\big(t}_{ij}^{k}-r1\big)x_{ij}^{k}+\delta_{ij}^{k}M\geq 0 \tag{11} \\ & \phantom{\big(}\forall i\in I,\forall j\in S,\forall k\in K\nonumber\\ & \big(t_{ij}^{k}-r1\big)x_{ij}^{k}-\big(1-\delta_{ij}^{k}\big)M<0 \tag{12} \\ & \phantom{\big(}\forall i\in I,\forall j\in S,\forall k\in K\nonumber\\ & \alpha D_{i}^{1}\leq\sum\nolimits_{j=1}^m \sum\nolimits_{k=1}^2 \delta_{ij}^{k} \hskip3.5mm \forall i\in I \tag{13} \\ & \alpha D_{i}^{2}\leq\sum\nolimits_{j=1}^m \delta_{i_{j}}^{2} \hskip3.5mm \forall i\in I \tag{14} \\ & {\big(t}_{ij}^{k}-r2\big)x_{ij}^{k}+\theta_{ij}^{k}M\geq 0 \tag{15} \\ & \phantom{\big(}\forall i\in I,\forall j\in L,\forall k\in K\nonumber\\ & {\big(t}_{ij}^{k}-r2\big)x_{ij}^{k}-\big(1-\theta_{ij}^{k}\big)M<0 \tag{16} \\ & \phantom{\big(}\forall i\in I,\forall j\in L,\forall k\in K\nonumber\\ & D_{i}^{1}\leq\sum\nolimits_{j=1}^m \sum\nolimits_{k=1}^2 {\theta_{ij}^{k}} \hskip3.5mm \forall i\in I \tag{17} \\ & D_{i}^{2}\leq\sum\nolimits_{j=1}^m \theta_{ij}^{k} \hskip3.5mm \forall i\in I \tag{18} \end{align}\] |
In the above formulation, we aim to maximize the EMS coverage and minimize the response time for uncovered demand zones by employing the weighted sum method to convert the multi-objective problem into a single objective function in Eq. (1) to normalize the different measurement scales. In order to ensure a balanced consideration of both EMS coverage maximization and response time minimization within our single aggregated objective function, two weights are added in Eq. (3), and the weights (\(w_{1}\) and \(w_{2}\)) are calibrated such that their sum equals 1. Specifically, the objective function F1 within Eq. (3) is designed to maximize the average EMS coverage across all demand zones, regardless of their association with suspected COVID-19 cases. Conversely, Eq. (2) focuses on minimizing the response time for those demand zones that remain uncovered.
Equation (4) indicates the number of demands at zone \(i\) of type k (\(D_{i}^{k}\)) equals to the number of demands at zone \(i\) of type k with (\(d_{i}^{k}\)) and without (\(\bar{d}_{i}^{k}\)) COVID-19 suspicions. Equation (5) and (6) denote the auxiliary variable \(z_{i}^{k}\) reveals whether there are demands at zone \(i\) for type \(k\) with COVID-19 suspected elor not. Equation (7) denotes the response time of demand zone \(i\) from location \(j\) by type \(k\) equals to the estimated enroute time, chute time, and chute time with the personal protective requirement (PPE). But, the chute time with the PPE will be added only if there are demands at zone \(i\) of type \(k\) with COVID-19 suspected. Equation (8) indicates the total number of demands covered by location \(j\) equals to the number of vehicles in location \(j\). Equation (9) ensure total number of vehicles of each type \(k\) does not exceed the give fleet size \(p^{k}\). Equation (10) ensure the total number of vehicles deployed at location \(j\) does not exceed its capacity \(p^{j}\). Equation (11) and (12) denote the auxiliary variable \(\delta_{ij}^{k}\) reveals whether demand zone \(i\) is covered by location \(j\) by type \(k\) vehicle within primary coverage standard (\(r1\)). Equation (13) and (14) restrict \(\alpha\) percent of the total number of demands of type 1 (\(k=1\)) can be covered within primary coverage standard (\(r1\)) by all types of vehicles (BLS and ALS), while \(k = 2\) can be covered only by type 2 (ALS). Equation (15) and (16) denote the auxiliary variable \(\theta_{ij}^{k}\) reveals whether demand zone \(i\) is covered by location j by type \(k\) vehicle within secondary coverage standard (\(r2\)). Equation (17) and (18) ensure all demand zone can be covered within secondary coverage standard (\(r2\)), while demands of type 1 (\(k= 1\)) can be covered by all types of vehicles and type 2 (\(k = 2\)) can be covered by only type 2 vehicles.
4. The Tailored Genetic Algorithm
4.1 Chromosome and Initial Population
According to the comprehensive analysis conducted by Katoch et al. [39] the established encoding schemas in the field of genetic algorithm encompass binary, octal, hexadecimal, permutation, value-based, and tree. For the purpose of this study, binary encoding has been chosen due to its extensive usage and ease of implementation, in order to address the stated problem that corresponds to binary encoding.
A chromosome is a collection of binary variables in which each binary variable indicates whether demand zone \(i\) is covered by type \(k\) from location \(j\), as illustrated in Fig. 1. These chromosomes, denoted as \(c\), are generated in a random manner, with the length of a chromosome denoted as \(CL\), the population size denoted as \(PS\) and the ith gene chromosome represented as \(G_{ij}^{k}\). If the value of \(G_{ij}^{k}\) is 1, it signifies that demand zone \(i\) is covered by type \(k\) from location \(j\). Conversely, if the value of \(G_{ij}^{k}\) is 0, it indicates that demand zone i is not covered by type \(k\) from location \(j\). However, to avoid infeasible initial solutions, the genes are randomly assigned a value of 1 when there are demands in zone \(i\), until the available number of ambulances for both types is depleted.
 |
Fig. 1 Chromosome encoding used in this study |
In the quest for a superior initial solution, we utilize a specifically designed greedy algorithm that is customized to tackle the proposed problem, as elucidated in Table 3. In order to introduce an element of chance, merely fifty percent of the population is produced utilizing the aforementioned greedy algorithm.
Table 3 Pseudo-code for greedy algorithm |
 |
4.2 Evaluation and Selection
The utilization of the fitness function aims to optimize the criteria for selecting solutions. The evaluation of more superior physical fitness solutions is performed through the utilization of Eq. (1). Drawing upon an extensive analysis carried out by Katoch et al. [39] in the year 2021, various well-established selection techniques were identified, such as roulette wheel selection, rank selection, tournament selection, Boltzmann selection, and stochastic universal sampling. The commonly employed method of selecting individuals for the roulette wheel is susceptible to premature convergence [40], thus leading to the proposal of incorporating rank-based selection and elitism selection in this context. These approaches aim to tackle this issue by assigning ranks to individuals based on their levels of fitness and guaranteeing the preservation of the highest-performing individual for the next generation. In order to mitigate the risk of prematurely converging the solution to a local optimum and to ensure the successful propagation of the elite chromosome to the subsequent generation, we have chosen to implement rank and elitism selection. The details of the selection operator are illustrated in Table 4. The elitist population is generated based on the rank of fitness value of each chromosome. This elitist population size is denoted as eps, while the fitness function is denoted as \(F(c)\). In all generations, where the chromosome proves infeasible, it will be eliminated, and all gene (\(G_{ij}^{k}\)) will be assigned a value of zero. This signifies that demand zone \(i\) will not receive coverage from ambulance type \(k\) originating from location \(j\). Furthermore, the chromosomes are arranged in descending order and subsequently incorporated into the privileged population until it reaches its maximum capacity.
Table 4 Pseudo-code for selection operator |
 |
4.3 Crossover and Mutation
Among the abundance of established crossover operator, such as single point, two-point, and uniform crossovers, the k-point crossover operator distinguishes itself due to its efficacy in our investigation. The integration of binary encoding into our genetic algorithm framework seamlessly aligns with the characteristics of the k-point crossover operator. By strategically selecting multiple crossover points along the binary strings, this operator not only facilitates the exchange of genetic information but also aids in the exploration of diverse solutions within the problem space. Importantly, the adoption of the k-point crossover operator fulfills the dual purpose of harnessing the advantages of binary encoding while mitigating the risk of infeasible solutions. This nuanced approach ensures the generation of offspring that complies with the constraints of the optimization problem, thus contributing to the effectiveness of our proposed methodology.
The preservation of genetic diversity in successive populations is of utmost importance for the effectiveness of genetic algorithms. In the midst of the various mutation operators available, such as displacement, simple inversion, and scramble mutation, our study strategically opts for the utilization of the inversion operator. This decision is justified by its compatibility with binary encoding and the inherent simplicity of its implementation. Binary encoding, being a fundamental choice within our genetic algorithm framework, seamlessly aligns with the characteristics of the inversion mutation operator. By selectively inverting segments of binary strings, this operator not only maintains genetic diversity but also facilitates the exploration of new and innovative solutions within the solution space. The deliberate selection of the inversion operator underscores our dedication to an efficient and streamlined implementation, which ultimately ensures the algorithm’s robust performance in optimizing complex problems.
The specificities of the crossover operator are delineated in Table 5. The \(k\)-points crossover operator commences by establishing the size of \(k\), indicated as \(ks\). Subsequently, the genetic material from parent 1 and parent 2 is replicated to generate offspring 1 and offspring 2, denoted as \(p_{1}\_G_{ij}^{k}\), \(p_{2}\_G_{ij}^{k}\), o\(_{1}\_{G}_{ij}^{k}\), and o\(_{2}\_{G}_{ij}^{k}\), respectively. Following this, a random selection is made from the total number of demand zones \(n\), the total number of locations \(m\), and the total number of types \(q\). The genes of offspring is then substituted with that of parent 2, and conversely, the genes of offspring 2 is substituted with that of parent 1.
Table 5 Pseudo-code for crossover operator |
 |
5. Results and Discussion
5.1 Experimental Setting
This study encompasses a comprehensive investigation of seven distinct parameter configurations (Group 1-7), in which each combination consists of three specific settings, details can be seen from Table 6. The primary goal is to systematically examine the impact of these variations in parameters on the performance of the evolutionary algorithm.
Table 6 Comprehensive matrix of experimental settings and hyperparameter combinations |
 |
The experimental instance for this study is divided into three distinct categories, namely small, medium, and large, which represent different levels of complexity suitable for optimization using genetic algorithms. For different instance sizes, the weights are set to 0.5 for \(w_{1}\) and \(w_{2}\). It is imperative to note that in our numerical experiments, we have assigned equal importance to both considered objectives to ensure a balanced influence on the combined objective function used in the optimization process. In the case of small instances, the number of demand locations (\(n\)) is varied among values of 10, 20, 30, 40, and 50, while the number of candidate locations (\(m\)) is fixed at 5 and the number of vehicle types (\(q\)) is set at 2. In the medium instance, the range of demand locations (\(n\)) extends from 100 to 500 with increments of 100 (i.e., 100, 200, 300, 400, 500). The number of candidate locations (\(m\)) is established at 10, while the number of vehicle types (\(q\)) remains constant at 2. In the case of the large dataset, the range of demand locations (\(n\)) also spans from 100 to 500 with increments of 100 (i.e., 100, 200, 300, 400, 500). However, the number of candidate locations (m) is increased to 30, while the number of vehicle types (\(q\)) remains constant at 2. This systematic categorization enables a comprehensive examination of the optimization performance of the genetic algorithm across different data scales, providing valuable insights for the optimization of complex problems through genetic algorithms.
5.2 Experimental Results
In this study, the tailored genetic algorithm was executed 100 times for each instance, spanning small, medium, and large scenarios. Additionally, for the small instances, the CPLEX optimization tool was employed to acquire the optimal solution. The inclusion of CPLEX results in these cases serves to validate that our genetic algorithm obtains optimal solutions, ensuring the efficacy and accuracy of our genetic algorithm in smaller-scale scenarios. The average processing times across 21 settings for small, medium, and large instances are detailed in Figs. 2, 4, and 6, respectively. Concurrently, Figs. 3 and 5 present the fitness values for medium and large instances. Owing to the consistent nature of all settings, the fitness values for small instances are omitted from the presentation. Furthermore, to validate the statical significance of the differences between the two settings, we conducted a T-test and the findings are displayed in Table 7.
 |
Fig. 2 The average processing time of settings for small instances |
 |
Fig. 3 The fitness of settings for medium instances |
 |
Fig. 4 The average processing time of settings for medium instances |
 |
Fig. 5 The fitness of settings for large instances |
 |
Fig. 6 The average processing time of settings for large instances |
Table 7 T-test analysis for settings across varied instance sizes |
 |
For small instances, the graphical representation in Fig. 2 clearly illustrates that the average processing times of groups 1 and 2 markedly differ from those of the remaining groups. Consider instance \(n=50\) as an example, where the average processing times for settings 1-6 (s1-s6) are 0.64, 2.53, 4.99, 0.62, 1.05, and 2.08 seconds, respectively. In contrast, the processing times for settings 7-21 are consistently less than 1 second, averaging around 0.64 seconds. It is evident from Table 6 that the average processing times of groups 1 and 2 exhibit statistically significant differences. This outcome aligns with the variations among settings, specifically regarding the number of generations and population size. Notably, the average processing times for settings 13-21 are comparatively small, with setting 20 achieving the optimal solution in the shortest time. The distinctions between settings 19, 20, and 21 are particularly noteworthy. Consequently, in small instances, setting 20 emerges as the most appropriate configuration.
Figure 3 presents the fitness values for various settings applied to medium instances. Observing the figure, minimal differences in objective values are apparent. However, a detailed examination of the fitness values in Table 6 for the medium dataset reveals noteworthy distinctions within group 2 between settings 4 and 6, showcasing average objective values of 0.346 and 0.348 across five datasets. Group 5 exhibits significant differences with Settings 13 and 15, displaying average objective values of 0.347 and 0.345, respectively. Group 7 demonstrates significant variations among Settings 19, 20, and 21, with average objective values of 0.346, 0.342, and 0.343, respectively.
Figure 4 illustrates marked disparities in processing times. A closer examination of Table 6’s test results highlights significant differences in processing times for Settings 1, 2, and 3 in the medium instance, recording average processing times of 0.646, 2.65, and 5.10 seconds, respectively. In Group 2, Settings 4, 5, and 6 display significant differences, recording average processing times of 0.65 seconds, 1.07 seconds, and 2.09 seconds, respectively. Similarly, Group 5 showcases significant differences with Settings 13, 14, and 15, presenting average processing times of 0.72, 0.64, and 0.63 seconds, respectively. Within Group 6, Settings 19, 20, and 21 also demonstrate significant differences, reflecting average processing times of 0.650, 0.57, and 0.58 seconds, respectively. Considering both processing times and objective values, it is evident that Setting 6 achieves the optimal objective value within an acceptable processing time. If prioritizing a shorter processing time, setting 13 represents the subsequent best parameter combination.
In Fig. 5, it is evident that there is minimal difference in the objective values. However, upon examining the fitness values for the large instance in Table 6, significant differences emerge in Group 2 between Settings 4 and 5, which significantly differ from Setting 6, with average objective values of 0.346, 0.346, and 0.349, respectively. Within Group 6, Settings 16 and 17 exhibit noteworthy differences from Setting 18, with average objective values of 0.345, 0.345, and 0.348, respectively. In Group 7, Setting 19 displays significant differences from Settings 20 and 21, with average objective values of 0.346, 0.343, and 0.342, respectively.
Figure 6 reveals substantial differences in processing times. Further scrutiny of the t-test results in Table 7 indicates notable distinctions in processing times for Group 1’s Settings 1, 2, and 3 in the large instance, with average processing times of 0.66, 2.65, and 5.13 seconds, respectively. For Group 2, Settings 4, 5, and 6 exhibit significant differences, with average processing times of 0.65, 1.05, and 2.14 seconds, respectively. In Group 5, Settings 13, 14, and 15 display marked differences, with average processing times of 0.74, 0.66, and 0.64 seconds, respectively. Within Group 6, Settings 16 and 18 exhibit noteworthy distinctions, with average processing times of 0.65 and 0.67 seconds, respectively. Finally, in Group 7, Settings 19, 20, and 21 show marked differences, with average processing times of 0.65, 0.57, and 0.59 seconds, respectively.
Considering both processing times and objective values, it is evident that Setting 6 attains a relatively better objective value within an acceptable processing time. Setting 18 represents the next best parameter combination if a shorter processing time is a priority.
Our experimental results offer nuanced observations on the effectiveness of various parameter configurations within an optimization framework across different instance sizes. For small instances, our analysis reveals significant differences in average processing times and objective values, focusing on the influential role played by the number of generations and population size. Notably, Configuration 20 emerges as the most prominent choice, achieving optimality in the shortest time frame, making it the preferable option for smaller instances. Moving on to medium-sized instances where marginal disparities in objective values are observed, a thorough examination uncovers notable distinctions within specific parameter groups. Setting 6 stands out as an excellent choice, displaying optimal objective values within an acceptable processing time. Importantly, Setting 13 proves to be the best parameter combination when prioritizing a more expedient processing time. Our investigation demonstrates substantial variations in objective values and processing times across different parameter settings when considering large instances. Remaining a robust choice, Configuration 6 consistently exhibits a superior objective value within an acceptable processing time, positioning it as a formidable candidate for larger-scale instances. Moreover, setting 18 emerges as the optimal parameter combination when a swift processing time takes precedence. In summary, our results highlight the critical significance of tailoring parameter configurations based on the specific characteristics of the problem instances. The consistent performance of setting 6 across diverse scenarios positions it as a robust and versatile choice.
6. Conclusions
In this research endeavor, we have embarked upon an exploration of the intricate challenges that arise in the optimization of emergency medical services (EMS). Additionally, we have presented a novel formulation of a mathematical problem specifically tailored to address the issue of ambulance location in rural areas. This unique problem formulation has been meticulously designed to prioritize coverage and equity, ensuring a fair and efficient response to all demands. The overarching objective is achieved by maximizing the coverage of demand zones while simultaneously minimizing the travel time for those zones that remain without coverage. In order to address the inherent complexity of the formulated problem, we have adapted a genetic algorithm (GA) to obtain acceptable solutions. This GA represents a key innovation, offering a versatile and effective approach to tackling the intricacies of optimizing rural EMS. Using a genetic algorithm is aligned with the dynamic nature of EMS challenges and the need for robust and adaptable solutions in various scenarios. Our experimental study, encompassing 21 distinct settings, serves as a testament to the efficacy and efficiency of our proposed approach. Notably, the comparison with CPLEX in small instances underscores the effectiveness of our method and demonstrates its competitive performance.
Furthermore, the efficiency of our approach is evident across various scales of instances, as we consistently obtain approximate solutions within a concise timeframe―less than 1 second. This efficiency is of paramount importance in the realm of emergency response, where swift decision-making plays a critical role in saving lives and mitigating adverse outcomes. In conclusion, our research not only provides a fresh perspective on the domain of EMS optimization but also introduces a tangible and practical solution that has been tailored to meet the unique challenges of rural areas. The novel mathematical formulation, in combination with the efficiency and effectiveness of the genetic algorithm, positions our approach as a significant advancement in the quest for improved emergency medical services. The implications of our findings extend beyond theoretical frameworks, as they offer a tangible impact on real-world emergency response strategies, particularly in rural communities. As we present our work to the scholarly community, we are optimistic that our contributions will catalyze further advancements in EMS optimization, ultimately fostering more resilient and responsive emergency healthcare systems.
References
[1] W.-C. Chiang, P.C.-I. Ko, H.-C. Wang, C.-W. Yang, F.-Y. Shih, K.-H. Hsiung, and M.H.-M. Ma, “EMS in Taiwan: Past, present, and future,” Resuscitation, vol.80, no.1, pp.9-13, Jan. 2009.
CrossRef
[2] O.C. Kobusingye, A.A. Hyder, D. Bishai, M. Joshipura, E.R. Hicks, and C. Mock, “Emergency Medical Services,” ed. D.T. Jamison, J.G. Breman, A.R. Measham, G. Alleyne, M. Claeson, D.B. Evans, P. Jha, A. Mills, and P. Musgrove, Disease Control Priorities in Developing Countries, 2nd ed., Washington (DC): The International Bank for Reconstruction and Development/The World Bank, http://www.ncbi.nlm.nih.gov/books/NBK11744/, 2006.
[3] A. Ingolfsson, “EMS planning and management,” Operations research and health care policy, vol.190, pp.105-128, Springer, 2013.
CrossRef
[4] V. Bélanger, A. Ruiz, and P. Soriano, “Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles,” Eur. J. Oper. Res., vol.272, no.1, pp.1-23, 2019.
CrossRef
[5] S. Su and C.-L. Shih, “Modeling an emergency medical services system using computer simulation,” Int. J. Med. Inf., vol.72, no.1-3, pp.57-72, 2003.
CrossRef
[6] V. Schmid and K.F. Doerner, “Ambulance location and relocation problems with time-dependent travel times,” Eur. J. Oper. Res., vol.207, no.3, pp.1293-1303, 2010.
CrossRef
[7] A.J. Comber, S. Sasaki, H. Suzuki, and C. Brunsdon, “A modified grouping genetic algorithm to select ambulance site locations,” Int. J. Geogr. Inf. Sci., vol.25, no.5, pp.807-823, 2011.
CrossRef
[8] Y. Liu, Z. Li, J. Liu, and H. Patel, “A double standard model for allocating limited emergency medical service vehicle resources ensuring service reliability,” Transp. Res. Part C Emerg. Technol., vol.69, pp.120-133, 2016.
CrossRef
[9] M. Amorim, S. Ferreira, and A. Couto, “Road safety and the urban emergency medical service (uEMS): Strategy station location,” J. Transp. Health, vol.6, pp.60-72, 2017.
CrossRef
[10] J. Song, X. Li, and J. Mango, “Location optimization of urban emergency medical service stations: a hierarchical multi-objective model with a new encoding method of genetic algorithm solution,” Web and Wireless Geographical Information Systems: 18th International Symposium, W2GIS 2020, Wuhan, China, Proceedings 18, vol.12473, pp.68-82, Springer, 2020.
CrossRef
[11] H. Andersson, T.A. Granberg, M. Christiansen, E.S. Aartun, and H. Leknes, “Using optimization to provide decision support for strategic emergency medical service planning - Three case studies,” Int. J. Med. Inf., vol.133, p.103975, 2020.
CrossRef
[12] B. Adenso-Díaz and F. Rodríguez, “A simple search heuristic for the MCLP: Application to the location of ambulance bases in a rural region,” Omega, vol.25, no.2, pp.181-187, 1997.
CrossRef
[13] S. Chanta, M.E. Mayorga, and L.A. McLay, “Improving emergency service in rural areas: a bi-objective covering location model for EMS systems,” Ann. Oper. Res., vol.221, pp.133-159, 2014.
CrossRef
[14] Z. He, X. Qin, Y. Xie, and J. Guo, “Service location optimization model for improving rural emergency medical services,” Transp. Res. Rec., vol.2672, no.32, pp.83-93, 2018.
CrossRef
[15] A. Başar, B. Çatay, and T. Ünlüyurt, “A multi-period double coverage approach for locating the emergency medical service stations in Istanbul,” J. Oper. Res. Soc., vol.62, no.4, pp.627-637, 2011.
CrossRef
[16] R. Aringhieri, M.E. Bruni, S. Khodaparasti, and J.T. van Essen, “Emergency medical services and beyond: Addressing new challenges through a wide literature review,” Comput. Oper. Res., vol.78, pp.349-368, 2017.
CrossRef
[17] J. Tassone and S. Choudhury, “Tabu search-based fleet scheduling of air ambulances for disaster response,” Array, vol.8, p.100047, 2020.
CrossRef
[18] C.M. Van Gelder, “Protection of EMS personnel from occupationally acquired infections,” Emerg. Med. Serv. Clin. Pract. Syst. Overs., vol.2, pp.86-95, 2021.
CrossRef
[19] E.T. Tucker, “An examination of public safety resources aiding the Houston Fire Departments response time to improve safety, standardization and sustainability of the Emergency Medical Service,” PhD Thesis, Texas Southern University, 2018.
[20] X. Qin, Z. He, and H. Samra, “Needs assessment of rural Emergency Medical Services,” Transp. Res. Rec., vol.2513, pp.30-39, 2015.
[21] J.E. Tintinalli, P. Cameron, and J. Holliman, EMS: A Practical Global Guidebook, PMPH-USA, 2010.
[22] C. Toregas, R. Swain, C. ReVelle, and L. Bergman, “The location of emergency service facilities,” Oper. Res., vol.19, no.6, pp.1363-1373, 1971.
CrossRef
[23] R. Church and C. ReVelle, “The maximal covering location problem,” Papers of the regional science association, vol.32, no.1, pp.101-118, Springer-Verlag Berlin/Heidelberg, 1974.
CrossRef
[24] D. Schilling, D.J. Elzinga, J. Cohon, R. Church, and C. ReVelle, “The TEAM/FLEET models for simultaneous facility and equipment siting,” Transp. Sci., vol.13, no.2, pp.163-175, 1979.
CrossRef
[25] Y. Liu, A.M. Roshandeh, Z. Li, K. Kepaptsoglou, H. Patel, and X. Lu, “Heuristic approach for optimizing emergency medical services in road safety within large urban networks,” J. Transp. Eng., vol.140, no.9, p.04014043, 2014.
CrossRef
[26] M.S. Daskin and E.H. Stern, “A hierarchical objective set covering model for emergency medical service vehicle deployment,” Transp. Sci., vol.15, no.2, pp.137-152, 1981.
CrossRef
[27] D.J. Eaton, H.ML. Sánchez U, R.R. Lantigua, and J. Morgan, “Determining ambulance deployment in santo domingo, dominican republic,” J. Oper. Res. Soc., vol.37, pp.113-126, 1986.
CrossRef
[28] K. Hogan and C. ReVelle, “Concepts and applications of backup coverage,” Manag. Sci., vol.32, no.11, pp.1434-1444, 1986.
CrossRef
[29] M. Gendreau, G. Laporte, and F. Semet, “Solving an ambulance location model by tabu search,” Locat. Sci., vol.5, no.2, pp.75-88, 1997.
CrossRef
[30] K.F. Doerner, W.J. Gutjahr, R.F. Hartl, M. Karall, and M. Reimann, “Heuristic solution of an extended double-coverage ambulance location problem for Austria,” Cent. Eur. J. Oper. Res., vol.13, no.4, pp.325-340, 2005.
[31] G. Laporte, F.V. Louveaux, F. Semet, and A. Thirion, “Application of the double standard model for ambulance location,” Innovations in distribution logistics, vol.619, pp.235-249, Springer, 2009.
CrossRef
[32] Q. Su, Q. Luo, and S.H. Huang, “Cost-effective analyses for emergency medical services deployment: A case study in Shanghai,” Int. J. Prod. Econ., vol.163, pp.112-123, 2015.
CrossRef
[33] Y. Liu, Z. Li, J. Liu, and H. Patel, “A double standard model for allocating limited emergency medical service vehicle resources ensuring service reliability,” Transp. Res. Part C Emerg. Technol., vol.69, pp.120-133, 2016.
CrossRef
[34] J.C. Dibene, Y. Maldonado, C. Vera, M. de Oliveira, L. Trujillo, and O. Schütze, “Optimizing the location of ambulances in Tijuana, Mexico,” Comput. Biol. Med., vol.80, pp.107-115, 2017.
CrossRef
[35] H. Jia, F. Ordonez, and M.M. Dessouky, “Solution approaches for facility location of medical supplies for large-scale emergencies,” Comput. Ind. Eng., vol.52, no.2, pp.257-276, 2007.
CrossRef
[36] W. Hatta, C.S. Lim, A.F.Z. Abidin, M.H. Azizan, and S.S. Teoh, “Solving maximal covering location with particle swarm optimization,” Int. J. Eng. Technol., vol.5, no.4, pp.3301-3306, 2013.
[37] J.A. Fitzsimmons and B.N. Srikar, “Emergency ambulance location using the contiguous zone search routine,” J. Oper. Manag., vol.2, no.4, pp.225-237, 1982.
CrossRef
[38] J.M. Morgan and P. Calleja, “Emergency trauma care in rural and remote settings: Challenges and patient outcomes,” Int. Emerg. Nurs., vol.51, p.100880, 2020.
CrossRef
[39] S. Katoch, S.S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed. Tools Appl., vol.80, no.5, pp.8091-8126, 2021.
CrossRef
[40] K. Jebari, M. Madiafi, and others, “Selection methods for genetic algorithms,” Int. J. Emerg. Sci., vol.3, no.4, pp.333-344, 2013.
Authors
National Dong Hwa University
is a Ph.D. student in the Department of Information Management, School of Management, and National Dong Hwa University, Hualien, Taiwan, R.O.C. His research interests are the philosophy of artificial intelligence, an epistemological analysis of the philosophy of artificial intelligence, and human-computer interaction.
 |
National Dong Hwa University
is an assistant professor of the Department of Information Management, National Dong Hwa University, Hualien, Taiwan, R.O.C. Professor Wu’s major research interests include combinatorial optimization, meta-heuristic, mathematical programming, computational intelligence, electronic commerce, and customer relationship management.
 |
