CODEWITHSUNDEEP
rconstraintsmathematical-optimizationgenetic-algorithm
gtnbz2nyt
gtnbz2nyt

Reputation: 1535

'At least one choice' Genetic Algorithm Constraint

I just started learning genetic algorithms in R using this example and I've run into an interesting problem trying to apply it. I have a dataset of shops, supply centers, and distance (miles) between shops and supply centers in the data frame dataset:

Shop    Center    Distance  DistanceSave
A       1         700       300
A       2         200       800
A       3         300       700
B       1         400       600
B       2         100       900
B       3         150       850
C       1         600       400
C       2         500       500
C       3         200       800

I'm trying to minimize Distance (or maximize DistanceSave which is 1000 minus Distance) subject to the constraint that each shop must be tied to a Center and I'm having trouble coding that last part:

#Generate Evaluation Function
library(genalg)
evalFunc <- function(x) {
    current_solution_savings <- x %*% dataset$DistanceSave
    current_solution_shop <- length(unique(dataset$shop[x==1]))

    #Set Conditions in Function
    if (current_solution_shop != length(unique(dataset$Shop)))
        return(0) else return(-current_solution_savings)
}

#Run GA Algorithm with 100 iterations
iter = 100
GAmodel <- rbga.bin(size = genes, popSize = 200, iters = iter, mutationChance = 0.01, 
                    elitism = T, evalFunc = evalFunc)
cat(summary.rbga(GAmodel))

I thought the current_solution_shop != length(unique(dataset$Shop)) condition would be enough but unfortunately it's not, sometimes it still assigns the same restaurant twice.

EDIT: It looks like the Facility Location Problem is what I need to research, but can anyone recommend a multi-facility approach for R or Python?

Upvotes: 1

Views: 199

Answers (1)

josliber
josliber

Reputation: 44309

If you're trying to assign each shop to exactly one center and aren't allowed to assign multiple shops to a particular center then this is called the assignment problem, and can be solved exactly in an efficient manner using linear programming.

Here's an approach using the lp.assign function from the lpSolve package:

# Cost matrix (shops as rows, centers as columns)
(dist.mat <- matrix(dat$Distance, nrow=3))
#      [,1] [,2] [,3]
# [1,]  700  400  600
# [2,]  200  100  500
# [3,]  300  150  200

# Solve the assignment problem
library(lpSolve)
sol <- lp.assign(dist.mat, "min")
sol$solution
#      [,1] [,2] [,3]
# [1,]    0    1    0
# [2,]    1    0    0
# [3,]    0    0    1
sol$objval
# [1] 800

The optimal solution assigns store A to center 2, store B to center 1, and store C to center 3, with cost 800.

Upvotes: 1

Related Questions