设施选址--在距离约束下最小化为客户服务的设施的算法

Question

例如，我有1000个客户位于欧洲不同的纬度和经度。我想找到能够为所有客户服务的最小设施数量，以必须在24小时送达内为每个客户提供服务为约束条件（这里我使用一个从设施到客户的最大允许运输距离作为确保24小时送达服务的约束条件（距离是两个地点之间的直线，基于欧几里德距离/直线计算）。

那么，每个仓库只能为一定距离（例如600公里）内的客户提供服务，有什么算法可以帮助我找到为所有客户提供服务所需的最小设备数量，以及它们各自的经纬度。下面附上的一张图片显示了一个例子。

查找最小仓库及其位置的示例

Answer 1

这属于设施选址问题的范畴。关于这些问题有相当丰富的文献。P中心问题接近你想要的。

一些注意事项：

1. 除了求解一个形式化的数学html" target="_blank">优化模型外，还经常使用启发式（和元启发式）。
2. 这些距离是真实旅行时间的粗略近似。这也意味着近似解可能足够好。
3. 除了找到为所有客户提供服务所需的最少设施数量外，我们还可以通过最小化距离来优化位置。
4. 将纯“最小化设施数”的数学规划模型表述为一个混合整数二次约束问题(MIQCP)。这可以用标准求解器（例如Cplex和Gurobi）来解决。下面是我拼凑的一个示例:

    ----     57 VARIABLE n.L                   =        4.000  number of open facilties

    ----     57 VARIABLE isopen.L  use facility

    facility1 1.000,    facility2 1.000,    facility3 1.000,    facility4 1.000


    ----     60 PARAMETER locations  

                        x           y

    facility1      26.707      31.796
    facility2      68.739      68.980
    facility3      28.044      67.880
    facility4      76.921      34.929

基本上我们解决了两个模型：

1. 模型1查找所需仓库的数量（在最大距离约束下最小化数量）
2. 模型2找到仓库的最优位置（最小化总距离）

这两个模型都属于凸混合整数二次约束问题类型(MIQCP)。我使用了一个现成的求解器来求解这些模型。