Heuristics for a continuous multi-facility location problem with demand regions

We propose mathematical programming formulations of the single and multiple facility versions of the problem considered. The single facility location problem is formulated as a second order cone programming (SOCP) problem, and hence is solvable in polynomial time. The multiple facility location problem is NP-hard in general and can be formulated as a mixed integer SOCP problem. This formulation is weak and does not even solve medium-size instances. To solve larger instances of the problem we propose three heuristics. When all the demand regions are rectangular regions with their sides parallel to the standard coordinate axes, a faster special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.

Citation Formats
D. Dinler, M. K. Tural, and C. İyigün, “Heuristics for a continuous multi-facility location problem with demand regions,” Computers & Operations Research, vol. 62, pp. 237–256, 2015, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/28541.