Facility location problem (P-median)
To download the data for this example and the trial version of XLOPTIM, please click on the links below:
2. Description of the facility location problem
The OptiScooter company has pre-selected 30 zones in town among the high-traffic ones to deploy electric scooters. Their aim is to select only 5 zones to deploy the scooters, these zones being the closest to the highest traffic ones.
The aim of this problem is to know in which zones the company can place their scooters to optimize their benefits. To do so, we will minimize the total distance between every geographical zone and the closest scooter rental zone thanks to the XLOPTIM software.
3. Modeling a facility location problem with XLOPTIM in Excel
What data do we have?
- the distances between the zones
- the number of locations that the company would like to select
- the maximum distance between zones
What variables do we have ?
In our problem, the variables are modelled by choosing a zone or not. In other words, for each zone i, we have an yi variable that takes the value 1 if and only if the corresponding zone is a scooter rental zone, and takes the value 0 otherwise.
What are the constraints ?
We have to select 5 zones. In other words, the sum of the yi variables must be equal to 5.
What is the goal function?
Since our aim is to minimize the distances between the highest-traffic zones and the scooter rental zones, we are going to start by calculating the distances depending on the yi variables (in other words, depending on whether a zone has been selected or not).
If zone i is selected, the variable yi takes the value 1 and the i column contains the real distances. Else, the i column contains only the maximum distance.
We have calculated those distances in the following table:
The colored cell represents the distance between scooter rental in zone 7 and zone 1.
For each zone, in order to know how far is the closest scooter rental zone situated, we have calculated the minimum distance in the table below.
Once we have specified the data and the different formulas related to the goal function and to the constraints, we can open the dialog box of our solver in order to model the problem.
4. Modeling with XLOPTIM
Defining the main decision variables:
Specifying the constraint of the problem:
Defining the goal (to minimize the total distance):
Once the model is parametrized, click on Launch.
After solving, the solver returns a feasible solution that corresponds to the optimal one.
This solution tells us that we have to deploy scooters in zones 7, 11, 15, 24 and 29. The goal function takes the following value:
By choosing this placement strategy, the total distance from the scooter rental zones to the other ones will be 1002. The displayed result is optimal and calculated in 5 seconds.
This case study has enabled us to discover an example of a facility location problem. This problem can also be applied to commercial locations, factories or workshops. The size and the hypotheses of the problem may vary in order to get different solutions. Do not hesitate to contact us if you have any questions after using our XLOPTIM® solver.
To download a trial version of our software, click here: Download the trial version