8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, I read Drezner's paper before. It provides a general form of the gravity location problem. Thanks for reminding the commonly-known name of the problem. I think, I will go with the discrete space option as I will need to throw in more constraints. Any paper suggestions on that side would be helpful! $\endgroup$ – Taner Cokyasar Aug 25 at 1:07
  • 1
    $\begingroup$ As a first entry I usually go to Klose and Drexl's survey paper (although it's and older paper now) doi.org/10.1016/j.ejor.2003.10.031 $\endgroup$ – Sune Aug 25 at 19:50
7
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Indeed, I also thought about the K-means. But, I just cannot add constraints there. Most K-means applications--I know--only considers the Euclidean distance and not more. In my case, demand nodes will also have weight and I may have some constraints like the max distance between a demand node and the cluster center cannot exceed a constant. $\endgroup$ – Taner Cokyasar Aug 25 at 1:10

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.