11.2 Discrete Models
The discrete models only consider a certain fixed number of potential sites as possible
locations for ambulances, ambulance points. This could be any set of points, i.e. the demand points, the Falck stations or perhaps a set of predefined dispatcher points which are expected to be good strategic positions such as in the cities, near intersections on fast roads etc.
Two different objectives will be considered. The first is to minimize the average response time (i.e also total) from the ambulances to the demand points, the p-median problem. The second is to minimize the maximum response time, p-center problem.
The response time from ambulance point i and demand point j is defined as dij. The response time, dij, could be any number, any sort of cost or distance. In this project the travel time on the road network is used for dij.
11.2.1 p-median Problem
The symbols ωj, p, J, and j denote the same meaning as they did for the continuous model. I and i have changed their meaning slightly and two new definitions are added for xi and yij: I: Is the set of all ambulance points |I| ≥ p.
i: Is a specific ambulance point.
xi: Is 1 if an ambulance is placed at the i’th ambulance point and 0 if not.
yij: Is 1 if the demand point j is allocated to the ambulance at ambulance point i, and 0 if not.
Formulation partly taken from “Facility Location: Applications and Theory” [FL p. 90-91]
Minimize
∑∑
Equation (11.2.2) makes sure that exactly p ambulances are used, and (11.2.3) ensures that each customer is allocated to one ambulance. (11.2.4) Prohibits demand points from being assigned to ambulance points with no ambulance. The integer requirement on xj (11.2.5) defines that an ambulance can only be placed at one demand point, since it is not possible to place the one half of an ambulance at one demand point and the other half at a different demand point. (11.2.6) Ensures that the demand from one demand point is allocated to one and only one ambulance. If necessary (11.2.6) can be relaxed (removed), however many times when solving the problem it will be easier to just allocate one demand point to one
ambulance, and in an optimal solution a demand point will always allocate its entire weight to the nearest ambulance. If (11.2.6) is not meet it might also be difficult to visualize the result.
The decision to be made is at which ambulance points are the p ambulances placed. Each demand point allocated to the nearest ambulance (ambulance point with an ambulance on it).
It is also possible to expand this model. Adding constraints on the maximum allowed travel time, i.e. an ambulance cannot cover a demand point which is more than dmax minutes away etc. is fairly easy. Either all the yij with a corresponding dij > dmax are banned from the solution or all the dij > dmax are substituted with a number so large that they will not be part of the optimal solution.
It is also possible to add capacity constraints to the problem, i.e. setting an upper limit on the potential number of accidents covered by the ambulance. If the capacity for an ambulance is set to k then the constraints can be formulated as,
∑
∈it is of course required that
k
to ensure that the total demand to be met does not exceed the total capacity of the ambulances, in order to ensure a feasible solution. The capacity constraint for the p-median problem will have the same disadvantages as those for the MFLA.
11.2.2 p-center Problem
The p-center problem is a minimax covering problem, i.e. its objective is to minimize the maximum response time represented by the letter W. It is important to notice that the weights play no role for the basic formulation of this problem, since we are minimizing the maximum response time, not the maximum cost. However if capacity constraints were to be applied, the weight would play a role.
Minimize W (11.2.9)
The model is very similar to the one from the p-median problem. It only differs in the
objective function and the new constraint (11.2.13), which defines W as the maximum travel time between any of the demand points and the ambulance to which they are allocated. That W defines the maximum travel time can be seen by examining (11.2.13) more closely. If W is not the maximum travel time it means that there exists a Σdij⋅yij which is greater than W, hence there exists a travel time dij > W, since yij is either one or zero. Given that (11.2.13) must be met there cannot exist a dij > W, hence dij ≤ W. Because W is minimized (11.2.9) it will be equal to the largest dij, hence a minimization of the maximum distance.
Response time limits like (11.2.7) are obviously not relevant for this problem, since the maximum requirement will be met if W is low enough. Capacity constraints are the same as for the p-median problem.
11.2.3 Complexity of the p-median and p-center problems
The number of possible solutions can easily be found. If there are n demand points, n = |J|, and p ambulances is corresponds to the number of different ways which p ambulance can be placed on n locations. Which is the same as the number of possible combinations to pick p elements out of n elements:
)!
with 1000 demand points and 10 ambulances it would be
1023
and as mentioned in section 5.2.1: “Computational Complexity” it would take 8 million years, even if one billion solutions were tested every second, to check them all. Though solutions with fewer ambulance has less possible solutions, the number of solution increases almost by a 1000 (n) every time an ambulance is added to the problem, number for shown in Table 4, the “Solution time” is the amount of time it takes to check all solutions with the given number of solutions checked per second.
p Possible 8 2.41⋅1019 764 years 764 thousand years 764 million years 10 2.63⋅1023 8 million years 8 billion years 8 trillion years
Table 4. Number of possible solutions and the time it takes to check them all.
Despite the many number of possible solution, the p-center and p-median problems can be solved in polynomial time for fixed values of p which is relative easy to see since
np
p n ≤
though as seen in Table 4, even for small number of p it is practical impossible, even with extreme computing power. For varying number of p the problems are NP-hard (Garey and Johnson, 1979) [FL. p. 91].
12 Solution Methods
This chapter deals with the methods used for solving the models in Chapter 11: “Models”.
As mentioned in chapter on (OR) there are many different ways of solving optimization problems. For the three problems at hand:
• Multi facility location allocation problem with Euclidean distance
• p-center problem
• p-median problem
Heuristic methods will be applied to the problems in this project, because to the amount of demand points and ambulances in the problem. The reason for not applying exact solution methods is that the available exact methods are very time consuming, for large problems like those dealt with in this project.