11 Models
This chapter deals with defining the mathematical models used in this project. The models are the multi facility location allocation problem (MFLA), the p-median and p-center problems.
All models have the objective to place p ambulances in the most optimal way. As discussed earlier one of the key problems is to define optimality. Three different models with three different objectives will be presented. In addition it will be discussed how these models can be combined with a variety of limitations, which may be of relevance to this and future projects.
The models can be divided into two categories, continuous and discrete models. The difference between the continuous model and the discrete model is that in the continuous model it is feasible to place an ambulance anywhere, it could be on a lake, in a forest, anywhere on the map so to speak, whereas the discrete model is given a set of possible locations, this could be the demand points or any other set of points.
The continuous model will have the objective to minimize the average weighted Euclidean distance. The discrete model will have the objectives of minimizing the average weighted travel time on the network and minimizing the maximum travel time on the network.
11.1 Continuous Model
In order to state the model in terms of math, a few definitions are needed:
Ambulances are considered to be facilities, represented with the letter i, customers are referred to as demand points (accidents) and are represented by the symbol j. The number of ambulances is p.
The following notation is used:
I: The set of all ambulances, with |I| = p.
i: A specific ambulance
fi: The coordinates for the i’th ambulance J: The set of all demand points
j: A specific demand point
aj: The coordinates for the j’th demand point.
Ji: The set of demand points allocated to the i’th ambulance
ωj: The weight associated with demand point j, i.e. the number of accidents assigned to that demand point.
d2(fi,aj): The Euclidean distance between the i’th ambulance and the j’th demand point
The single continuous model used in this project has the objective of locating the ambulances anywhere in continuous space, i.e. not necessarily on a road or even on land, such that the average weighted Euclidian distance to the demand points is minimized. The objective function
is actually a minimization of the total weighted Euclidean distance, but since the number of demand points (and weight, i.e. accidents) is a constant it corresponds to minimizing the average weighted Euclidean distance.
11.1.1 The Multi Facility Location Allocation Problem - MFLA
The formulation of the Multi Facility Location Allocation problem (MFLA) is partly adapted from lecture notes by Henrik Juel [HJ].
Minimize
∑ ∑
Equation (11.1.1) states that the sum of the weighted Euclidean distances between each ambulance and the demand points allocated to it, and then summed over all ambulances, should be minimized. Which in essence is the same as minimizing the average weighted Euclidean distance, since the number of demand points is fixed. The allocation of the demand points is defined in (11.1.2) or (11.1.3) and (11.1.4) and ensures that all demand points are included in the solution. (11.1.3) and (11.1.4) are actually just the definition of (11.1.2), but are included to emphasize what a partition is.The decisions to be made are the location of the ambulances, fi, for all i ∈ I. Each demand point is allocated to the nearest ambulance.
A practical experiment by Eilon, Watson-Gandy and Christofides showed that a problem with 50 customers (demand points) and 5 facilities (ambulances) had 61 local minima, the worst of which had a deviation of 41 % percent from the best solution. Megiddon and Supowit proved in 1984 that the problem is NP-hard. [FL p. 17].
The MFLA model lacks many vital elements. The most obvious one is the fact that an
ambulance can be located at any point, also at sea, in lakes, in the middle of a building, or in a forest. In most cases though, it would be expected still to be a good solution even if each ambulance is moved a little, i.e. to the nearest road. Furthermore, the Euclidean distance is a
rather rough estimate of the response time of an ambulance. The Euclidean distance and the response time are without doubt correlated since it takes more time to travel a longer distance at the same speed. However the model might allocate a demand point to the ambulance on one side of the river only 1 km away from the relevant place on the other side of the river, regardless that the nearest crossing is 30 km away. So despite a short Euclidean distance, the response time becomes tremendous. An example of this is shown in Figure 22.
Figure 22. Illustration of possible risk when using the Euclidean distance as a measure for response time The left picture shows allocation when mimimizing the average weighted Euclidean distance, while the right picture shows the result when minmizing the average weighted response time on the road network.
This is a contructed example.
The model could be expanded with elements such as barrier definitions, i.e. forbidden areas where the ambulances are prohibited, such as lakes and forests. This is an area in which the GIS features might prove useful, since it could easily be determined using GIS whether a solution is feasible or not.
Other likely additions to the model could be capacity constraints, i.e. limitation on the number of potential accidents that an ambulance is allowed to serve. Leaving capacity constraints out allows a single ambulance to cover a large amount of demand, like in Odense. On the other hand, when using capacity constraints demand points might not be allocated to the nearest ambulance, even though it is the closest ambulance, which will respond. A problem which makes the use of capacity constraints a little odd, although it might not prove all that important in a practical situation, since the number of demand points not allocated to the nearest ambulance is expected to be relatively small.
The mathematical expressions of the barrier definitions and the capacity constraints are not included, since it would require a complete redefinition of the entire model.