кластеризация с использованием некоторых ограничений

Question

Я пытаюсь сгруппировать / назначить несколько позиций (скажем, 200 пунктов назначения) некоторым менеджерам по продажам (скажем, 50 менеджерам по продажам), чтобы общее расстояние, которое должны пройти менеджеры, было наименьшим. Я использую K-средства кластеризации. Ответ, который я получаю, - это наименьшее расстояние, но количество назначенных пунктов назначения не очень равномерно. Один продавец получает 10 пунктов назначения, в то время как другой получает только 1, а другие между ними.

Поэтому я хочу добавить ограничение, согласно которому максимально допустимый пункт назначения должен быть равен 6, чтобы ни один менеджер по продажам не получил более 6 пунктов назначения. Любая помощь о том, как добавить это ограничение?

D1=read.xlsx("brisbane.xlsx")
km <- kmeans(cbind(D1$lat, D1$lng), centers = 50,iter.max = 100000)
    scluster<-km$cluster
    centers<-km$centers
out1 <- cbind(D1, clusterNum = scluster)
write.csv(out1,"brisbaneout.csv")
write.csv(centers,"brisbanecenters.csv")

Answer 1

Хорошо, вот решение подобной проблемы.В линейном программировании такая проблема называется проблемой «транспортировки».Трудно сказать, что единственный реальный способ решить эту проблему - это пройти через все возможные комбинации, но были эвристики, помогающие их решить.

Вот решение в R

library(lpSolveAPI)

# This is a random matrix of 50 salespeople over 200 locations
# This would really be your distance matrix for each person and town

locations <- matrix(runif(200*50, 1, 500), nrow = 50)

# For the row constraint you want each sales person to travel less than 600 miles
row.signs <- rep ("<", 50)
row.rhs <- rep(600, 50)

# You additionally want each site to be visited once
col.signs <- rep (">", 200)
col.rhs <- rep(1, 200)

# Now you can solve the problem and verify that it converged
# Here we are trying to minimize the distance traveled hence "min"
(result <- lp.transport (locations, "min", row.signs, 
                         row.rhs, col.signs, col.rhs))

# And the output is a matrix with a "1" for each salesperson to visit a specific city
solution <- result$solution

Вот как бы я это решил.