Main menu 
PSTT
·
·
·
Editorial staff
·
·
Articles
·
Others
·
·
·
·
·



 Artykuły :: Transport :: Conference papersThe medical emergency service system design Jaroslav JANĂÄEK  20070605 15:36:38 
1. INTRODUCTION Needs and requirements of human society or particular social groups form various demands, which are usually spread over a geographical area. An effective satisfaction of the demands is possible only if the corresponding service provider concentrates its sources at several places of the served area and provides the service in or from these places only. To denote source of a service, we shall use the term “facility”, which is mend to include a broad set of entities such as transportation terminals, schools, hospitals, daycare centres, public administration offices and others. An addressee of the service will be denoted by the term “customer”, even if he has hardly anything common with this term in a market sense. Within frame of this paper we restrict ourselves on the problem, in which a medical emergency service system is designed. This system design belongs to the family of location problems, in which it must be decided on centre locations, where ambulance vehicles should be placed.
In contrast to the private service systems, the objective of this sort of public service system must stress equity of a ”customer” in access to the provided services and comply with associated lows. That is why the facility location is not mater of the private firms, which provides the medical service in particular districts, but it is regulated by the public health agency in the frame of the whole region.
The studied problem arose from the necessity to locate approximate 250 depots of the ambulance vehicles in towns of the Slovak Republic so that each dwelling place of this region is accessible in fifteen minutes.
Such concisely formulated task evokes an idea that a feasible solution of a covering problem is searched for. But, more detailed observation of this vague formulation brings the notion that the feasibility or infeasibility of a particular solution for a real road network depends on speed, with which the ambulance vehicle can traverse the links of the network. The speed along an individual link is influenced by many factors (e.g. weather, traffic volume etc.), which are changing in time. Considering this speed variability, it can be asserted that no solution can be declared as feasible in all cases. That is why we suggested several criteria, how to quantify the quality of a vehicle allocation. Having completed the criteria, it is possible to raise a question about the best design of the medical emergency service system. That is for; we established the associated models and designed a suitable solving method.
2. QUALITY CRITERIA OF THE DEPOT LOCATION The question, which must be answered first, is: “How to estimate the time of access to a customer?” Let j be customer’s location and i be a centre of the service provider. Both the locations are nodes of a road network, which consists of links and nodes. Based on link quality, each link belongs to a class from a finite classification system. In accordance to this system, an average speed is assigned to each link. This way, an estimation of the necessary traversing time for each link can be obtained from the link length and the average speed corresponding with the link class. Using this time instead of the link length, the accessibility time t_{ij} can be enumerated as the time length of the shortest path in the network connecting i and j. Time t_{ij}(v) is a function of vector v=_{r}> of the speeds, which corresponds to the particular link classes.
The original requirement of the concerned public is that each inhabited place must be reachable within time T^{max} from at least one service centre placed in a location from set I of feasible centre locations. Design of this public system is equivalent to determination of a feasible solution of the maximum distance problem [8] under assumption that a number of possible service centres is given. The public system design can be reformulated as an optimization problem, if the number of located centres should be minimized subject to the abovementioned condition of the accessibility. Nevertheless, the average speeds are not constant, but they depend on weather, traffic volume and other dynamically changing conditions. Considering this condition variability, no system design ensures full satisfaction of the original time accessibility constraint and that is for a measure of the design quality must be derived. The first rough measure of the design quality can be established as the size of the part of population, which is out of the time limit T^{max} considering the time nearest service centre. This criterion does not take into account the size of affliction of an individual inhabitant, which is out of the time limit. There is a substantial difference between the case, when an inhabitant is about one minute or one hour out of the limit. Considering this disadvantage of the first criterion, we suggest the second one, where the affliction of an inhabitant is measured by the difference between the shortest time of accessibility and the time limit. Let us denote b_{j} the number of inhabitants of dwelling place j and let i(v, j) represent the located centre, which is the timenearest one to j considering the link speeds given by v. Then, expression (1) describes the first criterion and (2) describes the second one. The lower is the associated value the better is quality of the design.
 (1)   (2) 
The next generalization of these criteria may issue from observation of possible scenarios of the vehicle speeds. The family of the scenarios constitutes finite set V of possible speed vectors v^{q}, q=1, …, m and each scenario may be weighted by coefficient h_{q}. The weights can be set proportionally to the empirical frequencies or arbitrary else to reflect the necessity to keep the accessibility condition at a sensible speed. The composed criterion can be designed in the form of expression (3).  (3)

3. EMERGENCY DEPOT LOCATION PROBLEM AND A SOLVING TECHNIQUE Having suggested the quality criteria, an optimization problem can be formulated to decide about location of p emergency centres at some places from set I of possible centre locations so that the value of chosen criterion is minimal. To described this problem by means of mathematical programming, we evaluate price c_{ij} of the jth dwelling place assignment to possible location i accordingly to (1), (2) and (3). We obtain if and otherwise; if and otherwise and Coefficient c_{ij} used in the following text corresponds to one of these coefficients.
The decision on centre location at place iŃI will be modelled by zeroone variable y_{i}Ń{0,1}, which takes value 1 if a centre should be located at i and it takes value 0 otherwise. To form a model of this problem, auxiliary variables z_{ij}Ń{0,1} for each iŃI and jŃJ are introduced to assign dwelling place j to possible location i. The model has the following form: The decision on centre location at place iŃI will be modelled by zeroone variable y_{i}Ń{0,1}, which takes value 1 if a centre should be located at i and it takes value 0 otherwise. To form a model of this problem, auxiliaryvariables z_{ij}Ń{0,1} for each iŃI and jŃJ are introduced to assign dwelling place j to possible location i. The model has the following form:
Minimize    (4)  Subject to   for jŃJ
 (5)    for iŃI and jŃJ
 (6)     (7) 
The associated problem can be solved by the approach reported in [5], where Lagrangean multiplier f is introduced for constraint (7), which should be relaxed. Then the problem (4)(7) can be reformulated this way: Find f >= 0, so that values of variables y_{i} , iŃI of the optimal solution of problem (8), (5), (6) meet constraint (7) as equality. The considered objective function is  (8) 
If f is fixed, then problem (8), (5), (6) constitutes an uncapacitated location problem. To solve the problem for nonnegative values of f and {cij}, procedure BBDual [6] was designed and implemented based on [3]. Being tested during computational experiments with large networks, the procedure proved to be able to solve large size problems quickly enough to be used repeatedly in more complicated algorithms.
To find demanded value f, an algorithm was completed [5], in which function Q(f,c) gives number of variables y_{i} which value is equal to one in the optimal solution of problem (8), (5), (6) for given f, c.
It is necessary to remark that the optimal solution of problem (8), (5), (6) for resulting f need not necessarily meet constraint (7) as equality [5].
4. PRELIMINARY EXPERIMENTS To verify the suggested criteria and the proposed optimization approach, we made use of the formal proposal of the medical emergency system of the Slovak Republic and analysed it from the point of the abovementioned criteria. We employed the electronic road map of the Slovak Republic, in which set of towns and villages forms a part of the set of nodes. Numbers of inhabitants of the dwelling places were given together with other attributes of the nodes. As concerns the links of the road network we were given by the link lengths and class of each link. The road network contains 2906 dwelling places. The discussed original proposal of the medical emergency vehicle location consists of 259 places, but 46 of them duplicate or triplicate locations at some bigger cities and they have no influence on the studied accessibility considering the fact that these towns are represented by one node each.
That is why the 213 points (locations) were taken into consideration as concerns the original proposal. These data enable to enumerate criteria (1) and (2) for each scenario of the vehicle speeds connected with the individual link classes. The used scenarios and connected values of (1) and (2) are plotted in Table 1, where the speeds of a particular scenario are given in kilometre per hour.
Table 1. Speed scenarios and criterion evaluation
Speed0 is assumed for highways, speed1, 2 and 3 for the roads of the first, second and third class and speed4 is considered at the local roads. Scenario “St” corresponds to a standard speed spectrum, which was used for the enumeration of the common accessibility. Scenario “Vz” and “Zk” correspond to situations, which may occur at very bed weather conditions or by a big traffic volume. The scenarios “Op” and “So” correspond to good and optimal traffic conditions. Criterion1 is number of inhabitants, which are out of the accessibility limit of 15 minutes and Criterion2 is given in minutes and its value represents sum of the surplus accessibility times of individual inhabitants, which are not accessible in the given limit.
To establish proper instances of the optimization problems, we have performed an analysis of town and villages population. First, we have studied the distribution of the population on the set of the original emergency vehicle locations and in addition we have performed it on the set of all towns and villages of the Slovak Republic. The result of this study is shown in Table 2.
Table 2. Distribution of the population over sets of towns and villages In the first row, there are reported upper bounds on the numbers of inhabitants of the classes. The numbers of locations, which belong to the individual classes, are plotted in the row “Proposal” and the numbers of towns and villages of the whole area are placed in the row “Region”. Issuing from this analysis, we have decided to form the set of all possible locations from all towns and villages of the region, which have more than 2000 inhabitants and we have included into this set all locations from the original proposal. This way, a set of 449 possible locations was obtained. The problem (4) – (7) was solved for the five instances described in Table 1 with p=213. The results are plotted in Table 3, where the column denotations have the following meaning. Optimum1 and Optimum2 denote optimal values of the objective functions created accordingly to (1) and (2) respectively for the corresponding speed scenario. Corresponding values are given in the same units as Criterion1 and Criterion2 in table 1. Symbol “No.Loc.” denotes number of emergency vehicle locations, which were suggested in the frame of the optimal solution. Column “Time [s]” denotes computational time of the solving algorithm in seconds, which was necessary for obtaining the optimal solution.
Table 3. Results of optimization in accordance to both criteria 5. CONCLUSIONS Several interesting observations can be done comparing columns “Criterion” and “Optimum” in tables 1 and 3 respectively. The first finding is that it is impossible to serve all dwelling places in the given time limit, even if the best conditions are considered. The second finding concerns the quality of the original proposal. It can be found that quality of the system can be improved at least by one third using the optimization technique. The third finding is that the full number of the vehicle location is not necessary to ensure the given quality of the solution under good traffic conditions. Great surprise for us constitutes the computational times for the individual instants, which vary from a negligible time to the huge value of several tens of hours. This disproportion is a challenge for a future research in the field of integer programming algorithms.
Acknowledgment: This work was supported by grant VEGA 1/3375/06.
BIBLIOGRAPHY [1] BUZNA, L.: NĂĄvrh ĹĄtruktĂşry distribuÄného systému pomocou spojitej aproximĂĄcie a diskrétneho programovania. PhD thesis, Faculty of Management Science and Informatics, University of Ĺ˝ilina, Ĺ˝ilina, 2003, 90 p, (in Slovak) [2] CURRENT, J.; DASKIN, M.; SCHILLING, D.: Discrete network location models. In: Drezner, Zvi (ed.) et al. Facility location. Applications and theory. Berlin: Springer, 2002, pp 81118 [3] ERLENKOTTER D.: A DualBased Procedure for Uncapacitated Facility Location. Operations Research, Vol. 26, No 6, 1978, pp 9921009 [4] JANĂÄEK, J.: Service System Design in the Public and Private Sectors. In: Proceeding of the International Conference „Quantitative Methods in Economics (Multiple Criteria Decision Making XII)“, June 2. – 4. 2004, Virt, ISBN 8080780129, pp 101108 [5] JANĂÄEK, J.: Transportoptimal Partitioning of a Region. In: Communications – Scientific Letters of the University of Ĺ˝ilina, Vol. 2, No. 4, 2000, pp. 3542 [6] JANĂÄEK, J., KOVAÄIKOVĂ, J. (1997) Exact Solution Techniques for Large Location Problems. In: Proceedings of the Math. Methods in Economics, Ostrava, Sept. 911.,1997, pp 8084 [7] JANĂÄEK, J., BUZNA L.: A Comparison Continuous Approximation with Mathematical Programming Approach to Location Problems. Central European Journal of Operations Research, Vol. 12, No 3, Sept. 2004, pp 295305 [8] MARIANOV, V.; SERRA, D.: Location problems in the public sector. In: Drezner, Zvi (ed.) et al. Facility location. Applications and theory. Berlin: Springer, 2002, pp 119150 Jaroslav JANĂÄEK Faculty of Management Science and Informatics, University of Ĺ˝ilina


