A facility location problem. Where is the optimal placing?
The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors’ facilities.
Consider the following scenario
A rural area of a country has decided to improve their health and medicine access. They decided to build a new hospital and a pharmacy but everyone argues about the optimal location of these facilities. Some argue about the population of the cities and others about the distance.
The first step is to create a model of the rural area so we can apply some logic. Using graph theory we will create a non-directed graph of the cities of our rural area. Each vertex will be a city/village and the edges are the connections between them. For example let’s take the following graph.
Before we try to find the optimal location of the hospital/pharmacy lets define some graph theory terms.
Eccentricity
Eccentricity is the maximum distance from vertex 𝑣 to any other vertex
𝑢 of the graph. e(v)= max{𝑑( v, u) | 𝑢 ∈ 𝑉(𝐺)}. For example the Eccentricity of the node 3 is 3 if we consider that every edge has a weight of 1.
The Center of the Graph
The subgraph of a graph 𝐺 induced by the vertices of 𝐺 with the minimum
eccentricity is called Center of graph G (denoted as center(𝐺)).
In our graph we can see clearly that the center of the graph is the node 3.
Vertex Distance
Vertex Distance is defined as the sum of the distances between a specific
vertex and all the vertices of the graph.
distance of 𝑣 = SUM (𝑑𝑖𝑠𝑡(𝑣, 𝑢)) for every 𝑢 ∈ 𝑉(𝐺)
The Median of the Graph
The subgraph of a graph 𝐺 induced by the vertices of 𝐺 with the minimum
distance is called Median of graph 𝐺 (denoted as median(𝐺)).
In our case the median of the graph is the node 6.
What about the hospital? what about the pharmacy? Where we should put them?
The hospital must be near the quickest routes. Take note that an ambulance has to make the same path twice, one dispatching the vehicle to the location and one returning the patient back to the hospital.
In the other hand the pharmacy just has to be accessible by the citizens.
The median of the graph can minimize the time because it has the minimum eccentricity. Thats where the hospital must be placed. As you imagined, the center of the graph can be used for the pharmacy because it’s more accessible by everyone.
Let’s code it.
First thing to do is to transfer the graph in some beep boop computer language. We will use Java.
We need to use the Dijkstra algorithm so we can find the all the shortests paths for every node.
These two helper functions will be used by the Dijkstra algorithm to find the minimum and maximum value of the array.
After getting the paths we can find the eccentricity the center and the median as follows
The main of the class will be as follows.
Conclusion
We checked a simplified version of a problem that can be very tedious if many factors are acknowledged and connected it with graph theory. At first we made a model of the rural cities with a graph. Using the center and the median of a graph we created an automated way of placing these two facilities in the optimal location. Graph theory helps us model and solve problems using existing theorems and applying everyday logic to them. Every application of the graph theory properties depends solely on the problem we’re facing, in our case the hospital and the pharmacy locations.
You can check the live demo of the code here
This blog post was made to feed and share our curiosity in collaboration with Nikos Pantelidis.
