Facility location problem (P-median)

alt_text

1. Dataset

To download the data for this example and the trial version of XLOPTIM, please click on the links below:

Download the data for the facility location problem

Download the trial version

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

    alt_text

  • 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.

    alt_text

  • 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: alt_text

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.

alt_text

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:

alt_text

Specifying the constraint of the problem:

alt_text

Defining the goal (to minimize the total distance):

alt_text

Once the model is parametrized, click on Launch.

After solving, the solver returns a feasible solution that corresponds to the optimal one.

alt_text

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:

alt_text

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.

5. Conclusion

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