A Note on Solutions to the Ambulance Facility Real-Time Relocation Models

A Note on Solutions to the Ambulance Facility Real-Time Relocation Models

M. Sofyan, Cut Latifah, Dewi Suryani Hanum, Herman Mawengkang

Graduate School of Mathematics, University Sumatera Utara, Medan, Indonesia

Abstract Aiming to improve the efficiency and reliability of ambulance services, some allocation and location models has been developed in operations research literature. Coverage model for the locations to maximize the (deterministic or probabilistic) number of ambulance calls. This research will present a dynamic modeling in an ambulance emergency medical services system, where the research focus an emergency ambulance type. The main purpose of this relocation models is as an anticipation of the availability of ambulance vehicle to maximize the number of calls or covered demand of ambulance calls. This research represents the extended of MEXCLP model into linear programming with 0-1 constraint both of demand point of ambulance and allocation status any ambulance unit at location and obtained a model that can be used to determine departure and relocation of available ambulances at any demand location.

Keywords ambulance, Emergency Medical Service (EMS), relocation, dynamic modeling.

1. INTRODUCTION

   Ambulance is a component of Emergency Medical Services (EMS) facility that available 24 hours per day in a hospital. Erdojan et al. [1] considered that effectiveness of EMSs quality services component can be define into multiple criteria, including the average response time, type of EMS service of each hospital staff and the medical equipment that used. In this problem, the indicator that often used in determined the quality of EMS service is ratio between the total number of covered demand points in a given certain limit of time, eight to ten minutes. Thus, for planning model, the total demand points are given by using coverage concept where we assume that there is a demand point covered by ambulance only if the average response time has a given certain limit of time.

   Zaharudin et al. [2] affixed the rate of patients death risk is depend on response time to the demand of ambulance services. The response time is defined as a time where operator received a call for demand of ambulance services, so that the response time be a necessary component in determined the performance of EMS. The EMS components originally is a kind of out-of-hospital service and provides

   transportations for the patients that needs a medical treatment by the hospital.

   In developing the improvement of efficiency and reliability of ambulance services, several allocation models of ambulance services was developed in operation research literature, is coverage model and median model. Coverage model knows as a model that can be used to maximize total number of covered demand points of ambulance and well- oriented to deterministic or probabilistic model. Whereas the object of median model is to minimize total distance between ambulance to hospital and demand points. Then, this model gives the efficiency score of ambulance services as a solution [3].

   Several of these models were based on location problem under static and deterministic assumptions without considering any stochastic factors [4]. It is also explained the difference among EMS and others facility. Ambulance is allocated at a certain location such as parking lot by considering that ambulance is used periodically where the goal is to cover the total number of demand point at a certain location. Thus, this allocation problem need implementation of computation framework that helps in decision making process. There are three classification of relocation models that has been suggested: (i) the solution of real-time integer program to ambulance relocation decision making process (see Kolesar and Walker [5], Gendreau et al. [6], Brotcorne et al. [4], and Nair and Miller-Hooks [7]); (ii) the model helps in determine optimal location for ambulance in order to cover the total number of demand points by using integer program formula (see Gendreau et al. [8], Ingolfsson [9], and Goldberg [10]); and (iii) the model changes the random variable into explicit system.

   An estimated model have been developed to formulate ambulance relocation model as a Markov decision process and used to obtain an optimal solution by using a dynamic programming (see Berman [11] and Zhang et al. [12]). Another heuristic models also have been developed to determine relocation decision making process based on an approximation of a certain configuration system. Andersson

   1. and Andersson and Vaerband [14] proposed an estimated model of function of availability with the aim is to determine the capacity of a certain configuration so that the total number of demand points can be covered.

      Much of the research described above focused on

      M n

      yij aij xi 0

      (1.2)

      covering models where the demand points is considered to be covered if an ambulance is available within the given time. Daskins model of maximum expected coverage location problem (MEXCLP) was among the earliest to incorporate the probabilistic dimension of the ambulance

      i1

      i1

      n

      xi M

      i1

      (1.3)

      location scenario [15]. This paper propose a new model of ambulance relocation model based on extended of dynamic programming of MEXCLP model that combined with a real- time algorithm of relocation model. This paper is organized as follows. Section II we review some background information on the study area and outline that adopted the relocation model of EMS facility. The relocation model is proposed in Section III with a real-time algorithm of model is discussed in Section IV. Finally, the conclusion are provided in the last section.

2. RECENT DEVELOPMENTS IN RELOCATION MODELS

   Facility location problem is one of NP-complete problem with the solution space of m locations that allocated to n unit facilities, denoted by nm. Due to problem, some approximation solutions can be determined by using a metaheuristic methods such as tabu search, simulated annealing and evolutionary algorithms. Karaman [16] suggested two approximation method to determine location problem of EMS based on the objective, is (1) total of distances or times from or to ambulance location and (2) total of sum distances or times that must be passed through to reach the ambulance location. Mandell [17] considered that EMS facility was based on two kind of facility providers: Basic Life Support (BLS) units such as fire and police facility and Advanced Life Support (ALS) such as EMS components includes ambulance facility. Both of these facilities works in the same scope, life support, but with a differ standard time of each.

   Daskin [15] proposed the first ambulance facility location model by using a deterministic model and without considering the probability of the ambulance condition or the number of available ambulance that allocated in a certain region. The model used queueing theory under assumptions the probability of each ambulance that to be allocated in a certain region is q. If there are j demand points covered by k units ambulance, then the expectation score is pj(1-qk). Assume that K is being relocated to some of region. Thus, the total expected of demand points that can be covered in j is

   (MEXCLP)

   where = 0,1,2, , , ; = 0,1, , ; M is total maximum of ambulances that to be allocated; n is total number of demand points; xi is total number of available ambulances that allocated at i; and the decision making process

   {ij

   1; if j is covered by at least i ambulance

   y

   0; if j is covered by less than i ambulances

   with hj is total number of demand points at j. The objective function in Eq. (1.1) is to maximize the total number of covered demand points with constraint (1.2) to estimate demand rates at j location that covered in which based on decision variable yij to decision variables set, xi. Constraint (1.3) gives specification to total number of available ambulance that to be allocated where the model allows total of allocated ambulances in a certain region more than the expected.

   Goldberg et al. [18] suggested the relocation model that considered a given travel time as a parameter which defined in stochastic. The aim of this extended model is to maximize total number of covered demand points with a given standard time, eight minutes. In determining the solution, the probability is estimated from total demand points that covered by the ambulance under the assumptions as follows.

   • probability ambulances that allocated at k is covered the demand point in eight minutes;

   • probability that ambulance is available at a certain location;

   • probability ambulances that allocated at k-1 is unavailable

   Using data in Tucson, Arizona, the result show the increasing performance of ambulance facility at the location from 24% to 53.1%. Repede and Bernando [19] then extended this model with assumption the velocity of the ambulance to cover the demand points per day in Louisville, Kentucky. The main result from the model show the increasing performance of demand points within ten minutes from 84% to 95%, but decreasing of response time to 36%.

   s.t

   n M

   max (1 p) pi1hj yij

   j 1 i1

   (1.1)

3. MODELS

   This paper is based on the model simulation in emergency medic facility system by using a discrete-time system to emergency calls or demands as follows.

   1. assume that there is an emergency call;

   2. ambulance arrives at the location;

   3. medic team gives proceeds at the location;

   4. ambulance brings the patient to the hospital;

      Thus, our propose relocation model can be formulated as follows.

      i i jl

      n m p

   5. medic team bring the patient to the hospital to

      max x2 M t y jl

      (3.5)

      receive the medical treatment; and

   6. ambulance back to the source location

   i1

   m p

   j 1 i1

   In this simulation, two of random data are given, the total

   s.t

   ij y jl 1, vi V

   j 1 i1

   (3.6)

   number of demand points and the location of demand points

   n n

   1

   (3.7)

   in a certain time. In relocation problem, the decision maker choose the main location, relocation time and facility location that given in our models. In our simulation of

   i1

   m

   i xi

   p

   i

   i1

   1 2

   relocation models, we consider several components that influence the relocation models such as the source location of ambulances, hospital location, transportation network in a certain region, the location of demand points, scheduling and the status of the ambulance whether the ambulance is available to cover the emergency calls.

   Define the relocation problem of the ambulance facility by representing a graph G (V W , E) where

   ij y jl xi xi , vi V

   j 1 i1

   i i i

   x2 x1,v V

   m

   y jl 1,l 1,, p

   j 1

   p

   y jl p j ,v j W

   l 1

   x1 0 atau 1

   (3.8)

   (3.9)

   (3.10)

   (3.11)

   (3.12)

   i

   V {v1, v2 ,, vn} and W {vn1,, vnm} are two of i

   vertex sets that define the location of demand points and the potential location region, respectively. Then, assume that

   x2 0 atau 1

   y jl 0 atau 1

   (3.13)

   (3.14)

   E {(vi , v j ) : vi , v j V W ,i j} is set of edge in the

   graph. The location of demand points are given by a vertex, In our relocation model, constraint (3.6) and (3.7)

   i , where each edge is connected with the parameter of

   showed the covered demand rates by

   r2 . Constraint (3.8)

   travel time, tij . For vi V and v j V , given

   {1; tij r1

   (3.1)

   and (3.9) showed the relative needs of ambulance demand rates that can be covered where the proportion of the

   covered demand points. Eq. (3.10) is a binary variable where Eq. (3.11) showed an upper limit of the total number

   ij

   ij

   0; otherwise

   {

   1; tij r2

   0; otherwise

   (3.2)

   of the idle-time ambulance in a certain demand location. For some solutions, we use genetics algorithm concept that developed by Aytug and Saydam [20] as follows.

   M

   jl

   Given the total of available ambulances is p where p m, thus the total maximum number of idle-time status of ambulances is p j at v j W . Set t as a penalty

   coefficient that related to the relocation ambulance,

   l 1,, p from the current demand point in time t lo the other destination demand point, v j W . Clearly that the

   M

   jl

   coefficient t changes for each period t. Consequently,

   1. Average Response Time (ART)

      One of important parameter of EMS component is the average response time to the demand points of ambulance that defined as an interval time between the demand calls and time when the ambulance arrives at the demand location. As an illustration, assume that we have 3-months of period with total number of calls is 300. The total time, T

      = 4050 minutes, to cover all the demand points. Thus, the ART is

      is the proportion of the total number of demand points that needs to be cover by the allocated ambulance, r.

      ART =

      total number of calls 4050 13.5 minutes total time 300

      For the decision making process, we use a binary variable as follows.

      It means that the average response time to the demand calls of ambulance in 3-months of period is 13.5 minutes.

      y jl

      1; if and only if the ambulance l is allocated to v j W

      {

      0; otherwise

      (3.3)

   2. Coverage radius

      xk {1; if and only if vi is relocated k times

      (3.4)

      Assume that the first coverage radius, r1 , is calculated

      i 0; otherwise

      from the 3-month of period with ART is 13.5 minutes. The

      second coverage radius,

      r2 , will be based on the standard

      response time on the 10 minutes for all emergency calls. Step 4. If the current relocation point is the same demand

      Given the known allowable constant ambulance speed of

      V 40 km/h . For each r1 and r2 we determined

      V ART 4013.5

      location at interval [t j , tk ) , we calculate relocation ambulance that formulated by

      m

      C jk , cost of

      r1 60 60

      9 km

      C jk wijk d ( X jk , Pi )

      i1

      r V ART 4010 6.67 km

      2 60 60

      where d ( X jk , Pi ) is distance between optimal location and

   3. System-wide probability

   the new relocation of demand points i for [t j , tk )

   is calculated by Step 3.

   and

   X jk

   Based on the illustration above, the total period of 3- months is 300 days that converting to minutes and equal to 43400 minutes. Thus, the probability for each ambulance in this relocation model is

   Step 5. Then, we calculate the relocation ambulance in time

   t, based on Eq. (3.5) (3.14).

   V. CONCLUSIONS

   p T

   Dt NA

   4050

   300 450

   0.03

   In this paper we propose a new relocation model of ambulance by modifying the MEXCLP model. The model is formulated by considering the probability of each demand

   with assumption that Dt = 300 and NA = 450 is denoted as the given total number of available ambulance. It means the probability for each available number of ambulance is

   0.03 for the relocation in a certain ocation.

4. PROCEDURES OF ALGORITHM

points that covered by the ambulance facility. It also based on a simulation model of emergency medic facility system, that is total number of emergency calls and unit of available ambulances that have been located. Then, the extended MEXCLP represented into linear program with 0-1 constraint.

We used the procedures concepts of algorithm that suggested by Farahani et al. [21] in determining the relocation ambulance. This algorithm then we modified based on our model Eq. (3.5) (3.14) as follows.

Step 1. Set wi (t) as a time function based on the period. Set t1 0 and tn T as location-relocation points of n total of demand points. Calculate

t j1

wij wi (t) dt

t j

t

REFERENCES

1. Erdogan, G., Erkut, E., Ingolfsson, A. and Laporte, G. Scheduling ambulance crews for maximum coverage, Canadian Natural Sciences, and Engineering Research Council, (2008).

2. Zaharudin, Z.A, Shuib, A., Shahidin, A.M. and Nordin, N.A.

   A goal programming model for ambulance location problem

   – a preliminary study , Proceeding Seminar Kebangsaan Sains Matematika, Vol. 17 (2009), pp. 463-469.

3. Amponsah, S.K, Amoako, G., Darkwah, K.F. and Agyeman,

   E. Location of ambulance emergency medical service in the Kumasi metropolis, Ghana, African Journal of Mathematics and Computer Science Research, Vol. 41 (2010), pp. 18-26.

4. Brotocorne, L, Laporte, G. dan Semet, F. Ambulance location and relocation models. European Journal of Operational Research, Vol. 147 (2003), pp. 451-463.

5. Kolesar, P. and Walker, W.E. An algorithm for the dynamic relocation of fire companies, Operation Research, Vol. 22

   Step 2. Set

   wijk

   k

   wi (t) dt , j k . For each demand point

   t j

   (1974), pp. 249-274.

6. Gendreau, M. and Laporte, G. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation,

   i, calculate wijk for all j and k that integrated with the weight of the graph at i demand location in interval [t j , tk ) .

   Step 3. For each interval [bj , bk ) , calculate the optimal

   Parallel Computing, Vol. 27 (2001), pp. 1641-1653.

7. Nair, R. and Miller-Hooks, E. A case study of ambulance location and relocation, Presentation at 2006 INFORMS conference, (2006).

8. Gendreau, M. Laporte, G., and Semet, S. The maximal expected coverage relocation problem for emergency vehicles, Journal of the Operational Research Society, Vol.57

   score at facility (x

   jk , y jk )

   with

   wijk and coordinate of

   (2006), pp. 22-28.

9. Ingolfsson, A. The impact of ambulance system status

   ambulance location is (ai ,bi ) . Thus, we determine the optimal solution.

   management, Presentation at 2006 INFORMS conference, (2006)

10. Goldberg, J.B. Personal communication, (2007).

11. Berman, O. Dynamic repositioning of indistinguishable service units on transportation networks, Transportation Science, Vol. 15 (1981), pp. 115-136.

12. Zhang, O., Mason, A.J., Philpott, A.B. Simulation and optimization for ambulance logistics and relocation, Presentation at the INFORMS 2008 conference, (2008).

13. Andersson, T. Decision support tools for dynamic fleet management, PhD thesis, Department Science and Technology Linkoepings Universiteit, Norrkoeping, Sweden.

14. Andersson, T. and Vaerband, P. Decision support tools for ambulance dispatch and relocation, Journal of Operational Research Society, Vol. 58 (2007), pp. 195-201.

15. Daskin, M.S. A maximum expected location model: formulation, properties and heuristic location, Transportation Science, Vol. 7 (1983), pp. 48-70.

16. Karaman, M. A genetic algorithm for the multi-level maximal covering ambulance location problem, PhD thesis, Middle East Technical University (METU), Turkey, (2008).

17. Mandell, M.B. Covering models for two-tiered emergency medical service systems, Location Science, Vol. 6 (1998), pp.355-368.

18. Goldberg, J., Dietrich, R., Chen, J.M. and Mitwasi, M.G. Validating and applying a model for locationg emergency medical services in Tuscon, AZ, European Journal of Operational Research, Vol. 49 (1990), pp. 308-324.

19. Repede, J.F. and Bernando, J.J. Developing and validating a decision support system for location emergency medical vehicles in Louisville, Kentucky, European Journal of Operational Research, Vol. 75 (1994), pp. 567-581.

20. Aytug, H. and Saydam, C. Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study, European Journal of Operational Research, Vol. 141 (2002), pp. 480-494.

21. Farahani, R.Z. and Hekmatfar, M. Facility location: concepts, models, algorithms and case studies, Contribution to Management Science, Physica-Verlag Heidelberg, (2009).