Adding robustness to the objective function of the facility location problem

Question

Let us first define a simplified facility location problem as follows:

$$\min \sum_{i=1}^{n}\sum_{j=1}^{m}d(i,j)x_{i.j}$$

subjected to:

$$\sum_{i=1}^{n} x_{i,j}\geq1, \forall j$$ (Every customer should be served by at least one facility)

$$x_{i,j} \leq y_{j}, \forall i,j$$ (If a customer is assigned to a facility, then the facility should be open)

$$\sum_{j} y_{j} \leq 5$$ (Maximum number of facilities that can be opened should be less than $5$)

$$x_{i,j} \in \{0,1\}$$ $$y_{j} \in \{0,1\}$$

where $x_{i,j}=1$ if and only if customer $j$ is served by facility $i$ and $y_{i}=1$ if and only if facility $i$ is open.

The problem that I am having is actually how to define the objective function to make it more "robust". Obviously this objective function takes into account every customer and weights it as equally important. However, what I would like is to define the objective function such that customers that are very far from other customers should be weighted a bit less important. We can do this in several ways:

1. Define the function $d(i,j)$ such that customers living more than $50$km from the facility location have really low weights. But the $50$km is just an arbitrary number. The problem with this method is actually determining the arbritrary number of $50$km. What would be a good number / how would we get a good number?
2. Similary to solution 1, we can also weigh the customers, but I am not sure how we should assign the weights.
3. Instead of calculating the total distance, we can also compute the average distance as the objective function. Following along this idea, we can also use the median. However, I am not sure whether commercial solvers like CPLEX or Gurobi can handle a median.

My question is therefore, how can we formulate the objective function such that it is more robust to customers living really far away? What would be the best approach?

Answer 1

First off, you notion of "far" is unavoidably subjective, so I don't think you are going to find a totally objective approach.

Your solution 1 really looks at whether customers are far from their assigned facilities, not far from other customers. If you are going to go that route, you might consider basing it on distance to the nearest possible facility ($\min_j d(i,j)$) rather than distance to any specific facility.

One possibility for looking at customers' distances to other customers would be to simply compute the distance from each customer to the closest other customer, then reduce objective weights for customers far from their nearest neighbors.

Another would be to cluster your customers into as many clusters as the maximum number of facilities (so 5 in this case), and then compute for each customer $i$ the ratio $\rho_i$ of its distance from the cluster center to the mean or median distance from center of all customers in the cluster. If $\rho_i \le 1$, leave the coefficients of $x_{i,\cdot}$ alone. If $\rho_i > 1$, divide $d(i,j)$ by $\rho_i$ for all $j$. You could also use the standard deviation of distances to cluster center, penalizing customers more than 1.5 or 2 (or whatever) standard deviations from the cluster center.

Whatever route you take, you can do a kind of sensitivity analysis by gradually reducing objective weights for customers that meet your remoteness criterion until the number of open facilities decreases. Then you can compute the original (unweighted) distance functions for the solutions and present some options, where "you save the cost of this facility by tolerating this much more distance, absorbed mostly by customers who are 'remote' from other customers" (or from the nearest facility if you go the first route).

Answer 2

I agree with @prubin's suggestions. I would also add that there are already facility location models that try to do things similar to what you are describing. For example, "coverage"-based models (set covering location problem, maximal coverage location problem) define a customer as "covered" if it is within some radius of an open facility. It's not quite the same as what you are describing, but it is similar enough that you might want to check it out.

When you say "customers that are very far from other customers" do you really mean "customers that are very far away from their assigned facilities"? The two might be related in many cases (both will mean "remote" customers), but you will have to pick one approach or the other for your model.

In any case, you are going to have to make some arbitrary choices—the coverage radius, the weight threshold (e.g., 50 km), etc.—and there is probably no scientific way to choose these numbers. I agree with @prubin's suggestion to rely on sensitivity analysis to deal with that issue.