成本与半径优化的设施选址问题

Facility Location Problem with Cost and Radius Optimization

成本与半径优化的服务设施选址问题(CROFL)广泛应用于应急服务、快递、维修网络等领域,其特点是考虑了响应速度与服务价格、成本之间的关系,根据净收益最大化或者成本最小化的原则自动判断是否将偏远的"需求点"纳入服务半径之内,实现服务成本与服务半径的双重优化。建立了CROFL的混合整数规划模型,构造了求解平面CROFL的7.853+ε-近似算法,并提供了求解一般CROFL的Benders分解算法,计算实验显示,Benders分解算法具有非常高的求解效率与求解质量。

The facility location problem with cost and radius optimization （FLCRO） has a wide range of applications in emergency response, logistics, maintenance service as well as express delivery. By considering the relationship of response time, service benefits and service costs, the problem seeks a decision on whether the distant customers are brought into the range of service radius or not. Both service cost and service radius are taken into consideration in the model. We construct a mixed 0-1 integer programming model for the problem and present a 7. 853 4＋ε-approximation algorithm for FLCRO on a plane. We also provided a heuristic algorithm based on benders＇ decomposition which is very effective in solving FLCRO.