I'm struggling with a facility location problem.
In its original form the problem is quite straightforward: Given a matrix of distances between cities, I have to pick a minimal number of centers from them and create districts, such that no city in a district is farther from the center than a predefined distance parameter. This is a set covering problem that can be formulated as a binary integer program which I can solve with MATLAB's bintprog()
. The solution vector gives me the list of cities that are selected as centers, after which I can establish districts by assigning each city to the closest center, and that's OK.
But I would also like to solve a specialized version of the problem, and this is where it gets ugly and I get stuck:
Let's assume we also know the population of each city and want to minimize the amount of people who have to commute to the district center, and also the distance they have to do. So we would like to prefer solutions where the cost
$$ C =\sum_{v \in V}P_v \times d_{vc} $$
is minimal ($v \in V$ are the cities in the district, $P_v$ is the population of $v$, and $d_{vc}$ is the distance to the center).
My problem is that I cannot think of a way to incorporate these constraints into the binary integer program, because computing these costs require the districts to be already established, which right now only happens after bintprog()
has returned.
I suspect this problem might not even be formulated as a linear program at all, but I'm yet to find another way to solve it, so any help would be much appreciated. Thanks.