Facility Location Problem over Continuous Space

Question

I am reviewing the facility location problem (FLP) literature. Here, Daskin and Dean (2004) provided a short literature on discrete space FLPs, which was useful to distinguish different types of models with varying objectives. Chopra and Meindl (2013) showed a small example of an FLP over continuous space with a single facility selection, which they called gravity location model, in the book titled: "Supply chain management: strategy, planning, and operation."

I am in search of a review paper or select papers that formulated FLP over continuous space with multiple facility selections. Also, the problem was formulated with a nonlinear model in Chopra and Meindl (2013) because they considered Euclidean distance between a demand node and possible facility coordinates. Have you ever encountered a paper formulating the problem with a linear model? Is this even possible?

To better describe the problem, assume there is a polynomially-sized set of demand nodes and we would like to locate facilities to completely meet the demand while minimizing costs of facilities and services. Each facility has a circular service range, and facility cost is the same across locations. Since facilities are not capacity constrained and there is no incentive of meeting a portion of the demand by another facility, we can assume each demand node will be fully-served by the closest facility, and finding the ramifications is not at interest. We can further assume that the Euclidean distance is the prevailing driver of the service cost calculation.

I am also interested in the discretely-spaced facility version of the above described problem. In particular, I am looking for algorithms that can handle covering up to 2 millions of demand nodes in a reasonable amount of computational time, say less than a day. Otherwise, models presented in Daskin and Dean (2004) provide a reasonable sketch to build on.

Answer 1

The type of location problems you are looking for are planar location problems where the Weber problem and the multi-Weber problems are among the most well known (and simplest). Drezner gives a nice overview of the problem and a solution procedure called "Weizfeld's procedure". For the multi-Weber problem theres a simple and rather famous heuristic called "Cooper's location-allocation heuristic" (or something along those lines) .

I know that you can formulate the multi-Weber problem as both a non-linear mixed integer program and as a difference of convex optimization problem. But you cannot formulate it as a linear program (unless $\mathcal{P=NP}$) as it is an $\mathcal{NP}$-hard optimization problem.

Answer 2

If I understand correctly, you are given a set of demand nodes, and you want to locate a finite number of facilities, anywhere in the plane, so as to minimize the sum of distances between each demand node and its assigned facility?

Beyond the literature on facility location problems, you may find some useful tools in clustering methods (e.g., the K-means algorithm and alikes), as well as Steiner tree problems.

The K-means algorithm compute clusters, where each cluster's centroid is located so as to minimize the sum of squared distances to points in the cluster. A similar version with non-squared distances is the p-median problem. Some column generation-based approaches have been proposed for both, see, e.g., this paper.

The Euclidean Steiner tree problem is not exactly the problem you are mentioning, but there may be some useful modeling tricks from this literature, for instance this paper.