Robust optimization approach to emergency mobile facility routing

Abstract

Emergency events such as natural disasters, environmental events, sudden illness, and social security events pose tremendous threats to people’s lives and property security. In order to meet emergency service demands by rationally allocating mobile facilities, an emergency mobile facility routing model is proposed to maximize the total served demand by the available mobile facilities. Based on the uninterruptible feature of emergency services, the model abstracts emergency events act as a combination of multiple uncertain variables. To overcome the computational difficulty, a robust optimization approach and genetic algorithm are employed to obtain solutions. Illustrative examples show that it provides an effective method for solving the emergency mobile facility routing problem, and that the risk factor and penalty factor of the model can further guide decision-making.

Introduction

Mobile facility refers to public facilities designed and equipped for addressing emergency situations, with high mobility and service ability. They are widely used in public service fields such as disaster response, public security and medical treatment. The study on mobile facility planning is closely related to the dynamic facility location problem (DFLP), ¹ vehicle routing problem (VRP), ² and team orienteering problem (TOP). ³ Bespamyatnikh et al. ⁴ were the early ones to consider the mobile facility problem, and investigated the location of mobile facilities vis-a-vis the motion of clients. From the perspective of Steiner center, Durocher and Kirkpatrick ⁵ explored the stability and eccentricity of mobile services. However, their research focused mainly on the location of mobile facility. To solve the dynamic vehicle routing problem, Alessandro et al. ⁶ proposed a motion coordination strategy for minimizing the expected time between the appearance of a target point and the visit time. Zachary and Mohammad ⁷ and Sara et al. ⁸ studied the facility movement and the client assignment, respectively, with the objective to minimize the sum of the movement costs and the client-assignment costs. Based on previous researches, Halper and Raghavan ⁹ formally introduced the mobile facility routing problem (MFRP) with continuous-time planning horizon. Although the MFRP is NP-hard, three heuristics were put forward to route mobile facilities. Focusing on the MFRP under uncertain demand, Lei et al.^10,11 built a two-stage stochastic model and investigate the reasonable routes by the L-shaped method, which further reduced the movement cost of facilities. Based on prediction of accessibility to demand points, Sibel and Eda ¹² analyzed the objective to maximize the expected demand coverage. They studied the emergency facility location problem within a specified distance over all possible network realizations. It improved the practicability of the programming model. Observing that the MFRP can be decomposed into two polynomially solvable subproblems, Halper et al. ¹³ developed an integer programming formulation for the MFLP in a given set of facility destinations. Furthermore, Lei et al. ¹⁴ put forward a two-stage robust optimization approach to the mobile facility fleet sizing and routing problem under uncertainty. It was solved by a hybrid algorithm in the inner level that combined heuristic and exact methods. To realize the service-time-related demand rate, Qi et al. ¹⁵ constructed a mixed integer program and develop a variable neighborhood search meta-heuristic to solve the MFRP. All of these results provided much decision support for fleet sizing and routing of mobile facility. As for the emergency mobile facility routing problem (EMFRP), Mouhcine et al. ¹⁶ proposed a distributed solution to find the optimal path for a set of emergency vehicles. Vijayalakshmi and Anitha ¹⁷ designed an optimization routing model for developing flexible dispatching strategies in Emergency Medical Service System. They adopted optimization approach and established basic models for the EMFRP. In order to reduce the response time of emergency mobile facility, Ogunwolu et al. ¹⁸ discussed the issue of traffic route management for emergency service. Du and Zhou ¹⁹ proposed a chance-constrained and location-routing programming model under emergency with simultaneous relief materials delivery. The authors obtained the satisfactory solution of the EMFRP by using swarm intelligence algorithm. As effective distribution of relief goods and supplies plays an important role in rescue operation, Vahdani et al. ²⁰ put forward a two-stage multi-objective location-routing-inventory model for vehicle routing. It minimized the total cost and travel time while also increasing the reliability of the route. Recently, taking into consideration road capacity decline and other characteristics in a short time under sudden disasters, Zhao et al. ²¹ built a multi-objective route optimization model with connectivity reliability. Luan et al. ²² and Liu et al. ²³ separately presented location routing problem models to assist decision makers in emergency service. The models attempted to consider the delivery routes, the urgent window constraints, and multimodal relief delivery. From the perspective of demand area and the emergency service quality of emergency facilities, Yu et al. ²⁴ constructed a location-allocation optimization model of emergency facilities. The studies above attempt to construct effective models and strategies to improve the emergency vehicle servicem, etc. ²⁵ To evaluate the value of multiple response, Yoon and Albert. ²⁶ formulated a Markov decision process model that dynamically determined which type of mobile facility to dispatch. In addition, Mohammadi et al. ²⁷ proposed a new reliable optimization model to make a broad range of decisions, including reliable facility location-allocation, fair distribution of relief items, assignment of victims, and routing of trucks. Memari et al. ²⁸ presented a new bi-objective dynamic routing model with multi-medical servers. Singgih ²⁹ solved the routing problem of several mobile laboratories to maximize the total number of service ability. These existing studies provided instructive approach for anlysizing the uncertainty in emergency sevice, and improved the the applicability and feasibility of the model for the EMFRP.

In conclusion, the basic models for emergency mobile facility routing, location, and dispatch have been established from different perspectives. At the same time, heuristic, stochastic programming, and robust optimization were put forward to obtain solutions to these models. However, the existing studies focused largely on the common mobile facilities. The proposed models can’t be applied to mobile facilities for emergency event with uncertain characteristic of service time. Moreover, since they generally supposed that the service process was decomposable and the core objective was to minimize the cost of the mobile facility, their models were difficult to use in emergency events with lots of indeterminate scenarios. Besides, emergency events are commonly independent and impartible, so that the emergency service must be uninterruptible. Much more significantly, emergency services are required to undertake disaster relief without considering the movement costs of mobile facilities or the consumption of resources. Therefore, a more efficient objective function is to maximize the total served demand under rationally mobile facility routing. In this paper, an emergency mobile facility (EMF) routing model is presented based on an abstract description of emergency events to satisfy the need of uninterruptible service and the maximum of total served demand, with the constraint of service order and time requirement.

Emergency mobile facility routing model

Let $M=\{1,2,\dots ,m\}$ denote the set of EMFs and $U_m$ denote the total resources of the EMF $m$ . We define the emergency mobile facility routing problem in the directed network $G(L,D)$ with the planning horizon $[0,T]$ , and assume the following:

(I) All EMFs are homogeneous in system structure and service capability, but have different service resources. Furthermore, the EMFs need not cooperate with each other to provide emergency service.

(II) The set of the locations where EMFs can stop is defined as $L=\{1,2,...,l\}$ . And the set $D=\{D(l_i,l_j)\}$ is the distance between two locations $l_i,l_j\in L$ . Here, $D(l_i,l_j)$ is the shortest distance between $l_i$ and $l_j$ based on traffic congestion and road condition, satisfying the triangle inequality $D(l_i,l_j)+D(l_i,l_k)\le D(l_j,l_k)$ and the symmetry principle $D(l_i,l_j)=D(l_j,l_i)$ .

(III) In order to universally describe event information and obtain more reasonable path routing, we assume that $E=\{1,2,...,e\}$ is the set of all emergency events and that each emergency event $e$ is served by a separate EMF and has the attributes of $T_e^{\mathrm{B}},T_e^{\mathrm{W}},T_e^{\mathrm{D}},r_e,l_e$ .

As for any emergency event, the occurrence time $T_e^{\mathrm{B}}$ is abstracted as the time of the emergency event $e$ appears; the wait time $T_e^{\mathrm{W}}$ means how long the emergency event $e$ can wait until it is served; the service time $T_e^{\mathrm{D}}$ denotes the length of time that the emergency event $e$ requires; the demand quantity $r_e$ presents the quantity of demand that needs to be served per unit time, and the event location $l_e\in L$ is the nearest location where the emergency event $e$ is served. In this abstraction, the demand quantity $r_e$ is used to construct the objective function. And the total demand of emergency event $e$ is $r_e{T}_e^{\mathrm{D}}$ which lasts for $T_e^{\mathrm{D}}$ without interruption. If no EMF is available for the emergency event $e$ before the time $T_e^{\mathrm{B}}+T_e^{\mathrm{W}}$ , it will be labeled as unhandled event and can’t be served by other EMFs.

Depending on the assumption above, we define a decision variable $x_{\mathrm{me}}(t)$ that embeds the service location $l_e$ into the event information $e$ . If $x_{\mathrm{me}}(t)$ equals 1, it means that the EMF $m$ serves the emergency event $e$ at location $l_e$ and time $t$ , and otherwise $x_{\mathrm{me}}(t)$ equals 0. Consequently, let $O_m=\{e_i^m|e_i^m\in E\}$ denote the serving list of the EMF $m$ , where $e_i^m$ presents the $i$ th emergency event ordered by time, so the EMFRP is formulated as follows:

$$max\sum _{m\in M}\sum _{e\in E}{\int }_0^T{r}_e{x}_{\mathrm{me}}(t)\mathrm{dt}$$

(1)

$$\mathrm{s}.\mathrm{t}.\sum _{e\in O_m}{\int }_0^T{r}_e{x}_{\mathrm{me}}(t)\mathrm{dt}\le U_m$$

(2)

$$\begin{array}{c}\multicolumn{1}{c}{x_{\mathrm{me}}(t)\le x_{\mathrm{me}}(t\prime ),T_e^{\mathrm{B}}+T_e^{\mathrm{AW}}\le t\le T_e^{\mathrm{B}}+T_e^{\mathrm{AW}}}\\ +T_e^{\mathrm{D}},t<t\prime \le T_e^{\mathrm{B}}+T_e^{\mathrm{AW}}+T_e^{\mathrm{D}},T_e^{\mathrm{AW}}\in [0,T_e^{\mathrm{W}}]\hfill \end{array}$$

(3)

$$x_{\mathrm{me}}(t)+x_{\mathrm{me}\prime }(t\prime )\le 1,t<t\prime <t+D(l_e,l_{e\prime })$$

(4)

$$\begin{array}{c}\multicolumn{1}{c}{x_{{\mathrm{me}}_i^m}(t)+x_{{\mathrm{me}}_{i+1}^m}(t\prime )=2,T_{e_i^m}^{\mathrm{B}}+T_{e_i^m}^{\mathrm{AW}}\le t\le T_{e_i^m}^{\mathrm{B}}+T_{e_i^m}^{\mathrm{AW}}}\\ +T_{e_i^m}^{\mathrm{D}},\max (t+D(l_{e_i^m},l_{e_{i+1}^m}),T_{e_{i+1}^m}^{\mathrm{B}})\le t\prime \le T_{e_{i+1}^m}^{\mathrm{B}}+T_{e_{i+1}^m}^{\mathrm{W}}\hfill \end{array}$$

(5)

$$x_{\mathrm{me}}(t)+x_{m\prime e}(t\prime )\le 1,m\ne m\prime$$

(6)

$$x_{{\mathrm{me}}_1^m}(t)=1,max(T_{e_1^m}^{\mathrm{B}},D(l_m,l_{e_1^m}))\le t\le T_{e_1^m}^{\mathrm{B}}+T_{e_1^m}^{\mathrm{W}}$$

(7)

$$\begin{array}{c}0\le t\le T,0\le t\prime \le T,T_{e_i^m}^{\mathrm{AW}}\in [0,T_{e_i^m}^{\mathrm{W}}],l\in L,i\in \{1,2,...,|E|\},\hfill \\ m\in M,m\prime \in M,e\in E,e_i^m\in E,e_1^m\in E\hfill \end{array}$$

(8)

Objective (1) is an integral of a sectional-continuous function to maximize the total demand served by EMFs. Constraint (2) restricts that it is necessary for the total demand of $e\in O_m$ to be less than the resources in $m$ when the serving list of the EMF is $O_m$ . It indicates that if the resources left in the EMF are insufficient, the service will stop. Constraint (3) guarantees that each EMF must provide uninterrupted service during time $[T_e^{\mathrm{B}}+T_e^{\mathrm{AW}},T_e^{\mathrm{B}}+T_e^{\mathrm{AW}}+T_e^{\mathrm{D}}]$ and that the service must start at the time of $T_e^{\mathrm{B}}+T_e^{\mathrm{AW}}$ , where $T_e^{\mathrm{AW}}\in [0,T_e^{\mathrm{W}}]$ is the length of actual waiting time. If $x_{\mathrm{me}}(t)$ equals 0, which means that the EMF $m$ does not serve the emergency event $e$ at time $t$ , then the decision variable $x_{\mathrm{me}}(t\prime )$ can be 0 or 1. This indicates that the EMF $m$ may serve some other emergency events at time $t\prime$ . If $x_{\mathrm{me}}(t)$ equals 1, which means that the EMF $m$ does serve the emergency event $e$ at time $t$ and that the decision variable $x_{\mathrm{me}}(t\prime )$ is forced to be 1, then it is necessary for the EMF $m$ to continuously serve the emergency event $e$ until time $t\prime$ (time $t\prime$ is later than $t$ but earlier than service ending time). Constraint (4) stipulates that the EMF $m$ can’t simultaneously provide services for the emergency event $e\prime$ at location $l_{e\prime }$ and time $t+D(l_e,l_{e\prime })$ , when the EMF $m$ serves $e$ . This constraint will be invalid under the condition of $l_e=l_{e\prime }$ . Constraint (5) ensures that the travel time and wait time are taken into account when an EMF moves from location $l_{e_i^m}$ to location $l_{e_{i+1}^m}$ for serving the next emergency event $e_{i+1}^m$ . Constraint (6) points out that any emergency event can’t be served by two different EMFs. Constraint (7) requires that EMF $m$ has to move from $l_m$ to $l_{e_1^m}$ in its first service, where the emergency event $e_1^m$ is the first emergency event served by the EMF $m$ and $l_m$ is the initial location of the EMF $m$ . Constraint (8) states the corresponding bounds of each variable.

Robust optimization and model solution

In the EMFRP, the emergency event consisting of $T_e^{\mathrm{B}},T_e^{\mathrm{W}},T_e^{\mathrm{D}},r_e,l_e$ is uncertain within $[0,T]$ . Unfortunately, it is impossible to eliminate this uncertainty completely, so decision-makers often accept it first and then use the stochastic theory or probability theory to solve it. Especially in the case of many emergency scenarios, exact optimization methods are ineffective due to the extremely large computing scale of the model. The direct method or indirect method, such as Sequential Unconstrained Minimization Technique, Lagrangian Multiplier Method, Series Quadratic Programming, Feasible Direction Method, are all fail to obtain the solution of the EMFRP within finite time. Referencing the analysis result by Snyder, ³⁰ we adopt robust optimization to integrate the programming requirement and the uncertainty of scenarios, and use $\min (-G)$ equivalently replacing of $max(G)$ , where $G=\sum _{m\in M}\sum _{e\in E}{\int }_0^T{r}_e{x}_{\mathrm{me}}(t)\mathrm{dt}$ . The objective function of the EMFRP thus have the form:

$$\min \{-E(G)+\lambda \mathrm{Var}(G)+\omega (\mathrm{sum}\mathrm{of}\mathrm{squares}\mathrm{of}\mathrm{infeasibilities})\}.$$

(9)

Thereby, if the scenario set is $\mathrm{\Omega }=\{1,2,...,S\}$ and the occurrence probability of the scenario $s\in \mathrm{\Omega }$ is ${\phi }_s$ , the EMFRP in robust optimization will be presented as below:

$$min\left\{\begin{array}{c}-\sum _{s\in \mathrm{\Omega }}{\phi }_s\sum _{m\in M}\sum _{e\in E^s}{\int }_0^T{r}_e^s{x}_{\mathrm{me}}(t)\mathrm{dt}+\lambda \sum _{s\in \mathrm{\Omega }}{{\phi }_s(\sum _{m\in M}\sum _{e\in E^s}{\int }_0^T{r}_e^s{x}_{\mathrm{me}}(t)\mathrm{dt}-\sum _{s\in \mathrm{\Omega }}{\phi }_s\sum _{m\in M}\sum _{e\in E^s}{\int }_0^T{r}_e^s{x}_{\mathrm{me}}(t)\mathrm{dt})}^2+\hfill \\ \multicolumn{1}{c}{\omega \sum _{s\in \mathrm{\Omega }}{{\phi }_s\sum _{m\in M}(U_m^s-\sum _{e\in E^s}{\int }_0^T{r}_e^s{x}_{\mathrm{me}}(t)\mathrm{dt})}^2}\end{array}\right\}$$

(10)

$$\mathrm{s}.\mathrm{t}.\sum _{s\in \mathrm{\Omega }}\sum _{e\in O_m}{\int }_0^T{r}_e{x}_{\mathrm{me}}(t)\mathrm{dt}\le \sum _{s\in \mathrm{\Omega }}{U}_m^s$$

(11)

(3), (4), (5), (6), (7), (8)

The expectation and variance in objective function (10) generates more computational complexity, which makes it hard to solve by heuristics algorithm or software like LINDO. However, genetic algorithm performs global search effectively without many mathematical requirements for optimization problem, and provides great flexibility to mix and construct domain-independent heuristics. Therefore, the solution process of genetic algorithm does not need to explore the complex form of objective function and constraints, which is easy to set up a parallel computing method to get the optimal solution quickly. Taking account of this, we adopt genetic algorithm in light of its excellent intrinsic parallelism and global search ability. As for the EMFRP, the input comprises travel time matrix $D(i,j)$ , the number of EMFs $|M|$ , resources capacity $U_m^s$ , scenario set $\mathrm{\Omega }$ , scenario occurrence probability ${\phi }_s$ , and event information $T_e^S,T_e^W,T_e^D,r_e,l_e$ . Thus, with the risk factor, penalty factor and algorithm precision (minimum time interval), we takes six steps as below to solve the EMFRP by genetic algorithm.

Step 1: (Chromosome Coding) Since each emergency event is served by only one EMF, the service for emergency event $e$ is indirectly presented as a gene of $m_e,x_e,t_e$ , where $m_e$ is the EMF serving the emergency event $e$ , the decision variable $x_e$ equals $x_{\mathrm{me}}$ , indicating whether the EMF $m_e$ serves $e$ , and $t_e$ is the start time of the service. Here we use $m_e,x_e$ instead of $x_{\mathrm{me}}$ to simplify the description of a gene. On this basis, a chromosome is coded into $h$ genes, where $h=\sum _{s\in \mathrm{\Omega }}|E^s|$ is the number of all emergency events. That is to say a chromosome is denoted as $m_1,x_1,t_1,...,m_i,x_i,t_i,...,m_h,x_h,t_h$ in the time sequence of $t_e$ . Thus, a chromosome is a solution to the model, since it describes the EMF and the start time of the services for all emergency events. While we extract $O_m=\{e_i^m\}$ the emergency events served by a certain EMF $m$ from a chromosome, we will obtain the route of $m$ ordered by the location $l_{e_i^m}$ in light with $e_i^m$ .

Step 2: (Initial Population) We define the number of initial population as $h|M||L|$ according to the problem size. In terms of a single chromosome $m_1,x_1,t_1,...,m_i,x_i,t_i,...,m_h,x_h,t_h$ in the population, the $m_i$ and $x_i$ in a gene are randomly created from set $M$ and interval {0,1}, while $t_i$ is set as $T_e^{\mathrm{B}}$ . Then we check whether each gene satisfies all constraints. If not, the start time is adjusted by taking $\theta$ as time step till the constraints are met. If the constraints still can’t be satisfied when the time is more than $T_e^{\mathrm{B}}+T_e^{\mathrm{W}}$ , we set $x=0$ for this gene, namely the chromosomes with the gene is an inferior one. But it is not deleted from the initial population so as to maintain population diversity and representativeness, thereby obtaining better chromosomes from crossover and mutation operations.

Step 3: (Crossover operation) In order to ensure that each emergency event has the same opportunity of crossover, we define the crossover probability as $p^{\mathrm{C}}=1/\max (|E|)$ . With two chromosomes $A$ and $B$ selected from the initial population by the crossover probability, the EMF $m_i$ in the gene $m_i,x_i,t_i$ of chromosome $A$ is exchanged with corresponding $m_i$ of chromosome $B$ , where $i$ is a random gene position. Meanwhile, the decision variable $x_i$ is set to 1, and seek the minimum time of $t_i$ meeting all constraints. If a suitable $t_i$ within $[T_e^{\mathrm{B}},T_e^{\mathrm{B}}+T_e^{\mathrm{W}}]$ is found, we modify the time $t_i$ of the gene and recalculate $x_k$ , $t_k,i<k\le h|$ in the subsequent gene with the time step $\theta$ . Otherwise, if the constraints can’t be satisfied, $x_i$ is set back to 0.

Step 4: (Mutation Operation) Considering that the mutation operation mainly changes the EMF service for emergency events in scenarios, we choose a chromosome by the mutation probability $p^{\mathrm{V}}=1/(|M||\mathrm{\Omega }|)$ . Then, the EMF $m_j$ in the $j$ th gene $m_j,x_j,t_j$ of the chromosome is modified to $m_k\in M$ , where $j$ is a random gene position and $m_k$ is a random EMF. The start time $t_j$ and the decision variable $x_j$ are changed by the same way as that of crossover till they satisfy all constraints.

Step 5: (Selection Operation) According to the objective function, the formula (10) is took as the fitness function. After carrying out the crossover operation and the mutation operation in population, we sort them in ascending order with the fitness function. Thus, the top $h|M||L|$ chromosomes meeting all constraints is selected for the next iteration.

Step 6: (Terminal Condition) If the difference between two maximum fitness values is less than the minimum of the demand per unit $min(r_e^s)$ , or the number of iterations is more than the threshold value of $\Theta$ , the algorithm is terminated. At this time, the chromosomes with the maximum value of fitness function is the solution to the EMFRP.

Analysis of examples

In order to test the practicability of the method, we take the southeast district of Xi’an, China, as the research area. Figure 1 shows the 9 locations where EMFs can stop and the time distance between two different locations. The average travel time is 17 min. In the case of the earthquake event, we split the emergency events under 36 scenarios according to the plan horizon $T=24$  h. Each scenario has different numbers of emergency events. The maximum number of emergency events in scenarios $\max (|E|)$ is 18. The service time $T_e^{\mathrm{D}}$ of each emergency event is less than 60 min and the demand quantity $r_e$ is at most 6 units. The scenario 1 is as shown in Table 1. The probability of each scenario is illustrated in Table 2. Three EMFs is used to carry out emergency event services, and labeled as $m_1,m_2,m_3$ . They initially stop at densely populated locations $l_1$ , $l_4$ , and $l_6$ , and their capacities of emergency resources are 500, 500, and 450 units, respectively.

Figure 1.

Solution to the EMFRP.

Table 1.

Information on all events in scenario 1

$e$	$T_e^{\mathrm{B}}$	$T_e^{\mathrm{W}}$	$T_e^{\mathrm{D}}$	$r_e$	$l_e$	$e$	$T_e^{\mathrm{B}}$	$T_e^{\mathrm{W}}$	$T_e^{\mathrm{D}}$	$r_e$	$l_e$
1	20	15	15	4	9	9	151	11	30	3	3
2	32	10	30	2	9	10	162	25	30	1	3
3	44	12	15	5	5	11	188	10	15	4	7
4	65	38	45	3	6	12	190	10	15	1	1
5	105	10	15	1	2	13	206	18	30	3	1
6	120	8	30	4	8	14	206	15	25	3	6
7	132	6	30	1	4	15	220	12	15	1	9
8	136	18	45	3	2	16	239	24	45	3	7

Table 2.

Probability of each scenario.

$s$	1	2	3	4	5	6	7	8	9	10	11	12
${\phi }_s$	0.014	0.053	0.008	0.052	0.001	0.069	0.001	0.008	0.044	0.014	0.052	0.007
$s$	13	14	15	16	17	18	19	20	21	22	23	24
${\phi }_s$	0.022	0.043	0.013	0.019	0.038	0.013	0.004	0.033	0.069	0.019	0.013	0.032
$s$	25	26	27	28	29	30	31	32	33	34	35	36
${\phi }_s$	0.002	0.023	0.066	0.006	0.032	0.015	0.01	0.009	0.05	0.034	0.057	0.055

Given the accuracy of solution $\theta$ as 1 min, 17,496 initial populations is generated for the genetic algorithm according to the number of all emergency events, the number of EMFs and the number of locations where EMFs can stop. By observing the average fitness value of the population in relation to the maximum fitness value of the population, the crossover probability 0.056 and the mutation probability 0.009 is chosen according to literature. ³¹ The solution to the EMFRP is obtained after 1932 iterations (Figure 1). The green, crystal and yellow points are the stops of $m_1,m_2,m_3$ , respectively. The locations stopped by multiple EMFs are marked by a mixed color. According to the result, $m_1,m_2,m_3$ all pass through five locations. They cover all locations in the planning horizon. Furthermore, the location at a higher frequency of emergency events is visited by two routes, which ensures that emergency events on a large scale are timely coped with. If applying the route to Scenario 1, as shown in Figures 1 and 2, we can see that:

1. EMF $m_1$ arrives at location after serving emergency event $e_6$ , and EMF $m_2$ reaches $l_2$ after accomplishing the service for $e_5$ . It takes EMFs $m_1,m_2$ 14 min and 5 min, respectively to arrive at $l_4$ where $e_7$ occurs. They are both less than 18 min while $m_3$ spends in moving $l_4$ with the service for $e_4$ at $l_6$ made. However, the occurrence time of $e_7$ is 132 min and the wait time is only 6 min. Since the EMF $m_1,m_2$ have not completed their own tasks before 132 + 6 = 138 min, they can’t depart to $l_4$ under the fact that the principle of emergency service is uninterruptible. That is to say, EMF $m_3$ is assigned to serve $e_7$ , even though EMFs $m_1,m_2$ spend less time travelling to $l_4$ . These routes demonstrate that the model effectively schedules the service time of EMFs.

2. After dealing with $e_5$ , EMF $m_2$ stops at $l_2$ . In view of the emergency event $e_8$ occurring 16 min later, EMF $m_2$ is assigned to cope with $e_8$ . Moreover, EMF $m_1$ is located at $l_8$ with $e_6$ served and EMF $m_3$ at $l_4$ with $e_7$ served. In consideration of $e_9$ and $e_{10}$ occurring nearly simultaneously at $l_3$ , both EMFs $m_1$ and $m_3$ are sent for $l_3$ , while $m_2$ is still in a service task. The schedule shows that the model deals with multiple emergency events in time.

3. When EMFs $m_1,m_2,m_3$ finish the services for $e_9$ , $e_{11}$ , and $e_{10}$ , they stop at $l_3$ , $l_7$ , and $l_3$ at 186, 211, and 208 min. At this time, the emergency event $e_{12}$ occurs at $l_1$ , but the travel times of $D(l_3,l_1)$ and $D(l_7,l_1)$ are 27 min and 8 min. Consequently, EMFs $m_1,m_2,m_3$ reach $l_1$ at 213 min, 218 min, and 235 min, respectively, while $e_{12}$ waits for so long. As a result, the emergency event $e_{12}$ can’t be served by any of the EMFs. It demonstrates that the route maximizes the total served demand rather than the demand for a single emergency event.

4. The emergency events $e_{13}$ and $e_{14}$ appear at $l_1$ and $l_6$ respectively, while EMF $m_3$ still engages in a task and can’t deal with $e_{13}$ and $e_{14}$ . Accordingly, $m_1$ and $m_2$ are assigned to serve them. In addition, if EMF $m_2$ moves from $l_7$ to $l_6$ for coping with $e_{14}$ , a short travel time is only taken as 7 min. However, it forces $m_1$ to spend 27 min moving from $l_3$ to $l_1$ for serving $e_{13}$ . Therefore, EMF $m_1$ is scheduled from $l_3$ to $l_6$ and $m_2$ from $l_7$ to $l_1$ . This process shows that the model takes the requirement for the minimum wait time into account. With respect to the emergency event $e_{16}$ , EMFs $m_1$ and $m_2$ are the closest to $l_7$ after serving $e_{14}$ and $e_{13}$ . However, due to their insufficient medical resources, they can’t provide service for $e_{16}$ . Consequently, EMF $m_3$ is assigned to serve $e_{16}$ , which shows the genetic algorithm complying with all constraints of the EMFRP.

5. In summary, the emergency events, except $e_{12}$ , are all effectively served,. The total served demand is not increased even when other services are cancelled for coping with $e_{12}$ . Therefore, it is concluded that the total served demand is 1125 unit, which is a satisfactory solution to the EMFRP. Furthermore, with the step time being $\theta =1$ that exactly equals the precision of time, the wait time is minimized to some extent when the total served demand is maximized through proceeding stepwise.

6. The existing research largely concerned about the routing problem of relief distribution, victim evacuation and humanitarian logistics in emergency service. Since the model presented in this paper pays attention to the uncertain service process of emergency event, it is difficult to compare with the existing methods. In order to illustrate the solution quality of the proposed algorithm, two relevant approaches from the literature Luan et al. ²² and Yoon and Albert ²⁶ are selected for comparative analysis. Firstly, our model is converted to be solvable by the self-adaptive bat algorithm introduced in literature Luan et al. ²² When 36 scenarios are used in the model, the algorithm fails to obtain solution. The reason is that too much uncertainty information leads to more complex computation. While reducing to 12 scenarios, the solution to the EMFRP is obtained with the route of the three EMFs. But both $l_3$ and $l_9$ are visited three times in order to cover all emergency events occurred, which significantly increases the travel distance of EMFs. It take 288 min to complete the service of all emergency events compared with 248 min by the approach proposed in this paper. When the Markov decision process model described in literature Yoon and Albert ²⁶ is adopted, the routes of EMFs $m_1,m_2,m_3$ are acquired fairly quickly. However, not only the emergency event $e_{12}$ . but also $e_{11}$ is not served by any EMFs. And the load of EMFs are imbalance. One of the EMFs only visits three locations, while others visit more than seven locations.

Figure 2.

Service process in line with planned route in scenario 1.

Factor analysis

The illustrative examples demonstrate that the service plan of EMFs with event occurrence time and wait time et al. are uncertain. Nevertheless, except for the uncertain environmental influence on the programming model, the attitude of decision-makers to risks also affects the routing. Therefore, the risk factors of $\lambda$ and penalty factors of $\omega$ are analyzed in the RO model, so as to provide decision-makers with a more reasonable EMF routing with various risk control parameters.

Risk factor

The different values of risk factor $\lambda$ indicate the decision-makers’ varying attitudes towards risks. Aiming at analyzing the relationship between risk factors and the expectation of total served demand by EMFs, Fifteen risk factors are analyzed, as shown in Figure 3(a). It is suggested that the expectation fluctuates with risk factors, but the total demand tends to decrease. This is due to the quite large risk factor resulting in conservative decisions, which reduces the served demand loss under uncertainty. In this case, the EMFs mainly serve for the locations where emergency events frequently happen, rather than dealing with other emergency events that need a long travel time. Consequently, the EMFs are not available for a large number of events within $[T_e^{\mathrm{B}},T_e^{\mathrm{B}}+T_e^{\mathrm{W}}]$ . Moreover, the number of emergency events without service tends to become stable with the enlarging of risk factors. It shows that the expectation of total served demand is extremely little when $\lambda >5.5$ , being only 4.2% of the maximum expectation.

Figure 3.

Expectation of total served demand with different factors: (a) the influence of risk factor and (b) the influence of penalty factor.

Penalty factor

The penalty factor of $\omega$ is another type of risk control parameter for decision-makers. It indicates the penalty to the model objective with the degree of uncertainty. The more is the uncertainty in emergency events, the more is the infeasibility of providing emergency service. Therefore, taking $\omega =\beta max(\mathrm{Var}(T_e^{\mathrm{B}})\mathrm{Var}(T_e^{\mathrm{W}})\mathrm{Var}(T_e^{\mathrm{D}})\mathrm{Var}(l_e))$ as the penalty factor, the expectation of total served demand is analyzed under the different uncertainty degrees of multiple emergency events. Given the $\max (|E|)$ and $max(r_e)$ as constants, the penalty factors are almost positively correlated with the uncertainty of emergency events. Therefore, the influence posed by uncertainty on model objective is eliminated by penalty factors, with the expectation of the totally served demand hardly changing under different penalty factors. As shown in Figure 3(b), the expectation of the total served demand shows little change under various penalty factors and tends to be linear. Because the penalty factor $\omega =\beta max(\mathrm{Var}(T_e^{\mathrm{B}})\mathrm{Var}(T_e^{\mathrm{W}})\mathrm{Var}(T_e^{\mathrm{D}})\mathrm{Var}(l_e))$ related to the uncertainty of emergency events effectively prevents the risks of scenarios, the maximum difference between the expectations is only 2.4% of the maximum expectation. It demonstrates that penalty factors are selected in line with the uncertainty of emergency events.

Conclusion and recommendations

To solve the problem of EMF routing, this paper abstracts emergency events into a tuple comprising occurrence time, wait time, service time and demand quantity. In line with the uninterruptible service process, a robust optimization model of the EMFRP is presented for simultaneously determining the routing and service schedule for EMFs. The objective of the model is to maximize the total served demand while taking the uncertainty of emergency events into account. Instead of simply obtaining a feasible solution by applying the heuristics method, a genetic algorithm is developed with specific chromosome coding, crossover operation, and mutation operation. It is helpful to search for a satisfactory solution to the EMFRP. Meanwhile, the risk factors and penalty factors are analyzed to provide decision-makers with a control strategy for coping with the risk in uncertainty. However, in the model of the EMFRP, the severity of emergency and the initial locations of EMFs remain to be analyzed. Moreover, depending on the number of scenarios, the genetic algorithm only obtains satisfactory solution. The more scenarios, the more accurate solution of the problem. Particularly, the time-consuming of the methodology varies dramatically with the number of EMFs and locations, resulting in several hours of computation when the problem scale is too large. For future research, we will provide weights to different emergency events and improve the performance of the algorithm, so as to further guarantee the maximization of totally served demand and the minimization of total wait time.