algorithmoptimizationlogistics

Facility Location - Algorithm to Minimize facilities serving customers with distance constraint

I have for example, 1000 customers located in Europe with different latitude and longitude. I want to find the minimal number of facilities that can serve all customers, subject to the constraint that each customer must be served within 24hr delivery (here I use a maximum allowed transportation distance from a facility to a customer as the constraint for ensuring 24hr delivery service (distance is straight line between two locations, calculated based on Euclidean distance/straight line).

So, with each warehouse that can only serve the customers within certain distance e.g. 600 km, what is the algorithms that can help me to find the minimal number of facilities needed to service all customers, and their respective latitude and longitude. An example is shown in the attached pic below.

example of finding minimal warehouses and their locaitons

example of finding minimal warehouses and their locaitons

Solution

  • This falls in the category of facility location problems. There is quite a rich literature about these problems. The p-center problem is close to what you want.

    Some notes:

    1. Besides solving a formal mathematical optimization model, often heuristics (and meta-heuristics) are used.
    2. The distances are a rough approximation of real travel time. That also means approximate solutions are probably good enough.
    3. Besides just finding the minimum number of facilities needed to service all customers, we can refine the locations by minimizing the distances.
    4. A math programming model for the pure "minimize number of facilities" can be formulated as a Mixed Integer Quadratically Constrained problem (MIQCP). This can be solved with standard solvers (e.g. Cplex and Gurobi). Below is an example I cobbled together:

    enter image description here

    With 1000 random customer locations, I can find a proven optimal solution:

        ----     57 VARIABLE n.L                   =        4.000  number of open facilties

    ----     57 VARIABLE isopen.L  use facility

    facility1 1.000,    facility2 1.000,    facility3 1.000,    facility4 1.000


    ----     60 PARAMETER locations  

                        x           y

    facility1      26.707      31.796
    facility2      68.739      68.980
    facility3      28.044      67.880
    facility4      76.921      34.929

    See here for more details.

    Basically we solve two models:

    1. Model 1 finds the number of warehouses needed (minimize number subject to maximum distance constraint)
    2. Model 2 finds the optimal placement of the warehouses (minimize total distance)

    After solving model 1 we see (for a 50 customer random problem): enter image description here We need three warehouses. Although no link exceeds the maximum distance constraint, this is not an optimal placement. After solving model 2 we see: enter image description here This now optimally places the three warehouses by minimizing the sum of length of the links. To be precise I minimized the sum of the squared lengths. Getting rid of the square root allowed me to use a quadratic solver.

    Both models are of the convex Mixed Integer Quadratically Constrained Problem type (MIQCP). I used a readily available solver to solve these models.