Solved – Constrained assignment problem (Linear Programming, Genetic Algorithm, etc…)

genetic algorithmslinearoperations researchoptimizationr

I'm looking for advice on how I should approach a specific problem. I have about 1000 shops that I have to assign to about 20 different supply centers out of a possible 28, and I'm trying to pick the best 20 (or less) centers that minimizes the overall distance between shops and supply centers.

I looked into the 'assignment problem' and how linear programming could help, but it seems this can only work if I have an equal number of shops and centers. I also looked into Genetic Algorithms and tried to code the algorithm to 1) ensure each shop is assigned to only one center and the center count must be no greater than 20, but results aren't that great (I can provide my R code if requested)

Should I continue trying to work with a Genetic Algorithm or can you folks suggest some other tool I should use or resource to look over? Thank you.

EDIT: Some nice user who's comment is now deleted suggested researching the Facility Location Problem. This seems more in line with what I'm looking for but most of the examples online cover single-facility problems, not multi-facility problems. Can anyone recommend a good resource for R or Python?

Best Answer

EDIT: Apparently, I should have posted my original recommendation about the facility location problem as a reply to your question, not as an answer. I am new to the forum, but I get it now.

Any way, I believe your problem can be formulated as follows.

Let $y_i$ = 1 if supply center i is opened and 0 otherwise

$x_i,_j$ = 1 if supply center i feeds shop j and 0 otherwise

$c_i,_j$ = distance from supply center i to shop j

Then you want to solve the following linear programming problem.

    minimize  $\sum_i\sum_jc_i,_jx_i,_j$

    subject to $\sum_ix_i,_j = 1$                j = 1,...,1000 (or the number of shops you have)

                    $\sum_jx_i,_j \le 1000y_i$      i = 1,...,28 (If you have a max capacity for each supply center, use that number instead of 1000; 1000 assumes there is no max capacity so one center could feasibly supply all shops)

                    $\sum_iy_i \le 20$                 (max of 20 supply centers chosen)

                    $x_i,_j$ = 0 or 1                  i=1,...,28; j =1,...,1000

                    $y_i$ = 0 or 1                     i=1,...,14

The Rsymphony package in R can solve this problem for you. You will need a vector of the distances $c_i,_j$ and 0's for each $y_i$ as well as a matrix to take care of the constraints (the three summations starting after "subject to"). If you aren't familiar with the constraint matrix, each column contains the coefficients for that variable. The help file for the Rsymphony package has a couple examples that should help with that. Don't forget to include columns for the $y_i$ in the matrix as well. You will also need to set the $x_i,_j$ and $y_i$ to be binary by using

    types = "B"

As an example, suppose we have 3 shops and 2 supply centers with distances between them as $x_1,_1$ = 2.8, $x_1,_2$ = 5.4, $x_1,_3$ = 1.4, $x_2,_1$ = 4.2, $x_2,_2$ = 3.0, $x_2,_3$ = 6.3. Then

    library(Rsymphony)
    obj <- c(2.8, 5.4, 1.4, 4.2, 3.0, 6.3, 0, 0)
    mat <- matrix(c(1,0,0,1,0,0,0,1,0,1,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0,0,0,0,-3,0,1,0,0,0,0,-3,1), nrow = 6)
    dir <- c("==", "==", "==", "<=", "<=", "<=")
    rhs <- c(1, 1, 1, 0, 0, 2)
    max <- FALSE
    types <- "B"
    fac.loc <- Rsymphony_solve_LP(obj, mat, dir, rhs, types = types, max = max, write_lp = TRUE)
fac.loc

tells us that we should open both supply centers and supply center 1 will supply shops 1 and 3 and supply center 2 will supply shop 2, for a total distance of 7.2.

I hope this helps.

Related Question