设施位置 - 最小化为有距离限制的客户提供服务的设施的算法

Question

例如，我有 1000 个客户位于欧洲，不同纬度和经度。我想找到可以为所有客户提供服务的最少设施数量，受限于必须在 24 小时交付内为每个客户提供服务（这里我使用从设施到客户的最大允许运输距离作为确保 24 小时交付的约束）服务（距离是两个位置之间的直线，根据欧几里德距离/直线计算）。

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

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

Answer 1

这属于设施位置问题的范畴。关于这些问题有相当丰富的文献。在对中心问题是接近你想要什么。

一些注意事项：

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

通过 1000 个随机客户位置，我可以找到一个经过验证的最佳解决方案：

    ----     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 找到仓库的最佳位置（最小化总距离）

解决模型 1 后，我们看到（对于 50 个客户的随机问题）： 我们需要三个仓库。尽管没有链接超过最大距离约束，但这不是最佳放置。求解模型 2 后，我们看到： 现在通过最小化链接长度的总和来最佳地放置三个仓库。准确地说，我最小化了平方长度的总和。摆脱平方根让我可以使用二次求解器。

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