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

Question

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

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

寻找最小仓库及其位置的例子

Answer 1

这属于设施位置问题的范畴。关于这些问题有相当丰富的文献。 p-center 问题接近您想要的。

一些注意事项:

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

参见 here了解更多详情。

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

1. 模型 1 找到所需的仓库数量(根据最大距离限制最小化数量)
2. 模型 2 找到仓库的最佳位置(总距离最小化)

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

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