8
$\begingroup$

Considering a set of $m$ existing weighted demand points (very large) and $n$ different-sized facilities, what is the best approach for locating new facilities to maximise coverage? I have used the Weber problem, which is non-linear (quadratic). I used the $\ell_p$-metric method to measure distance but it is not accurate. (For example, where to locate a new police station to cover the demand points, or which of the existing facilities can be shifted to maximize the coverage).


Update: I found a very similar model to what do I mean here. Sorry if my question was not clear. So put simply, referring to the provided link my main questions are as below:

  1. How to solve such this model for large cases?
  2. This model is nonlinear. How to linearize it?
  3. What if there are already some facility established? How to locate the new facilities by considering them?
$\endgroup$
6
  • 2
    $\begingroup$ I noticed this is tagged with p-median but if you're maximising coverage I don't think this counts as the p-median? p-median minimises the distance from the demand points to the assigned facility but doesn't maximise coverage (incidentally we have an open source p-median solver available here, which can go up to a few thousand demand points as its heuristic based). $\endgroup$ – Open Door Logistics Jul 9 '19 at 7:15
  • $\begingroup$ @sean it would be helpful if you could give us more details, what exactly do you understand by "coverage"? what is "large"? ideally, you state your mathematical model and we are all on the same page, you can use LaTeX math mode for this! $\endgroup$ – Marco Lübbecke Jul 9 '19 at 8:59
  • $\begingroup$ Sounds like a Planar Maximum Coverage Location Problem. See optimization-online.org/DB_FILE/2017/09/6191.pdf for example. $\endgroup$ – Libra Jul 9 '19 at 9:16
  • 2
    $\begingroup$ @OpenDoorLogistics I agree; I removed the [p-median] tag. $\endgroup$ – LarrySnyder610 Jul 9 '19 at 11:57
  • $\begingroup$ @Sean are you interested in discrete or in continuous location problems? Since you mention the Weber problem I assumed the latter, but perhaps I am wrong. $\endgroup$ – Libra Jul 9 '19 at 12:29
11
$\begingroup$

You may have a look at our recent work based on Benders decomposition, for the discrete Maximum Coverage Facility Location problem. It works very well if the number of facilities is relatively small, but the number of customers can run in millions…

J.F. Cordeau, F. Furini, I. Ljubic: Benders Decomposition for Very Large Scale Partial Set Covering and Maximal Covering Problems, European Journal of Operational Research 275(3):882-896, 2019

You can donwload the preprint from here.

The code is open-source.

$\endgroup$
1
  • $\begingroup$ Thanks for providing the links. That's a bit different from what I meant. I have now updated my post. $\endgroup$ – Sean Jul 14 '19 at 10:00
9
$\begingroup$

It sounds like you are describing either the set covering location problem (SCLP) (Wikipedia entry; canonical citation) or the maximal coverage location problem (MCLP) (Wikipedia entry; canonical citation). The SCLP minimizes the number of facilities subject to a constraint that every demand node is covered; the MCLP maximizes the number of covered demands subject to a constraint on the number of facilities to be located.

Your question specifies weighted demand points, which suggests the MCLP to me, since the weights don't matter in the SCLP (you have to cover everyone). You also say different-sized facilities and I'm not sure what you mean by that. If you mean that the coverage radius is different for different facilities, that's an easy modification. If you mean that the facilities have capacities, and the capacity is different for each facility, that's harder. The SCLP and MCLP assume the facilities are uncapacitated. You could add capacity constraints, but depending on how you are solving the problem, it may add computational difficulties.

Standard MIP formulations of both the SCLP and MCLP usually have very tight LP relaxations, which means you can often just solve them with a commercial solver. Other good algorithms exist, for example using Lagrangian relaxation or metaheuristics.

I wrote a book chapter on covering problems a while back; maybe that will be useful.

To answer your main questions:

  1. The SCLP and MCLP can be solved for large instances using off-the-shelf MIP solvers. By large, I mean 1000s of nodes, at least. If you need larger, you may have to look at specialized algorithms, e.g., the one mentioned in @IvanaLjubic’s answer. But if $m$ is large and $n$ is not, you can often reduce the size simply by aggregating the demand nodes, e.g., by postal code or some other grouping.

  2. The SCLP and MCLP are linear. The p-center problem is also linear, although the variant of it in the answer you linked to happens to be nonlinear.

  3. Easy, just set their fixed cost to 0, either in the objective function of the SCLP, or don’t include it in the LHS of the “open p facilities” constraint of the MCLP.

$\endgroup$
1
  • $\begingroup$ Thanks for the nice job. Soffy for confusion in my question. I have now provided more information in my post. $\endgroup$ – Sean Jul 14 '19 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.