Optimal planar facility location with dense demands along a curve
研究了平面上沿曲线连续分布需求的多设施选址问题，提出基于线段近似的精确算法和交替定位分配算法，实验表明直接处理连续需求比离散化更有效。
This paper studies a multi-facility location problem with demand distributed continuously along a curve (MFLCD) in a planar space. We first model a single facility location problem in this setting. When the curve is approximated by a collection of line segments, an exact algorithm is proposed to solve the problem. Then we extend the model to the multi-facility case and propose an “alternate location and allocation” (ALA) based algorithm. Extensive computational experiments are conducted to justify the proposed models and algorithms. We show that using the proposed model to deal with continuous demand directly is much more effective than using other models with discrete demand generated by demand aggregation. As a by-product, some sufficient conditions that ensure an error-free demand aggregation from continuous demand to discrete demand are provided. Computational results are in support of the solution quality and computational efficiency of the proposed ALA-based algorithm for solving MFLCD problems. Our sensitivity analysis also offers some insights and suggestions.