在接触所有客户的同时，尽量减少店铺数量。

Question

在这个特殊的问题上，我有一个想象中的城市，分为几个方块--基本上是一个。MxN 覆盖城市的方格网。M 和 N 可以是比较大的，所以我有的案例整体有4万多平方的小区。

我有一些客户 Z 在这个网格中，有些单元格会有很多客户，而有些单元格则是空的。我想找到一种方法来放置这些客户。最低 店的数量(每个小区只能有一个)，以便能够为所有客户提供服务，但限制是所有客户必须 "触及 "一个商店，并且...。都 客户需要包括在内。

作为一个额外的几个转折，我有这些约束issues。

1. 有一个最大的距离，一个客户可以旅行 - 如果商店在一个单元格太远， 那么客户不能与该商店相关联。编辑：这不是真正的距离，而是衡量顾客到达店铺的难易程度，所以我不能用圆圈......
2. 在尊重上述条件(1)的前提下，同一个顾客很可能会有多家店铺的距离。在这种情况下，距离最近的店铺应该胜出。

目前我试图忽略成本的问题--许多顾客意味着更大的商店和更大的成本--但也许在某些时候我也会考虑这个问题。问题是，我不知道我正在研究的问题的名称，也不知道它可能的算法解决方案：这可以作为线性编程问题来解决吗？

我通常用Python编码，所以如果有任何关于可能的算法方法和或一些代码库来解决它的建议，我将非常感激。

先谢谢你。

编辑我发现我可以用MINLP的 "无容量设施问题 "来解决这个问题，但我找到的所有信息都太复杂了：我并不关心哪个顾客是由哪个商店服务的，我只关心是否有商店以及在哪里建商店。我有一个次要的方法--作为后期处理--将客户关联到最合适的店铺。

我找到的所有代码都设置了这个畸形的线性系统，将每个顾客每个店铺的约束关联起来（如这里的 "解释"。https:/en.m.wikipedia.orgwikiFacility_location_problem#Uncapacitated_facility_location#。)，所以在像我这样的情况下，我可以很容易地最终得到一个有数百万行和列的线性系统，而对于整数二进制变量，它将需要大约宇宙的年龄来解决。

一定有更简单的方法来处理这个问题......

Answer 1

我认为这可以表述为 掩盖问题 联系.

你说：

像我这样的情况，我可以很容易地得到一个有数百万行和列的线性系统， 如果使用整数二进制变量，它将需要大约宇宙的年龄来解决。

那么，让我们来看看这是不是真的。

第一步：生成一些数据

我生成了一个200×200的网格，得出40000个单元格。我随机放置M=500个客户。这看起来像。

----     22 PARAMETER cloc  customer locations

                  x           y

cust1            35          75
cust2           169          84
cust3           111          18
cust4            61         163
cust5            59         102
...
cust497         196         148
cust498         115         136
cust499          63         101
cust500          92          87

第二步： 计算每个客户的覆盖率

下一步是为每个客户c确定允许到达的地点（i,j）。我创建了一个 稀疏布尔矩阵 reach(c,i,j) 为此。我使用的规则是：如果曼哈顿距离是

  |i-cloc(c,'x')|+|j-cloc(c,'y')| <= 10

那么位于(i,j)的商店就可以为客户c提供服务，我的数据是这样的。

(不存零). 这个数据结构有106k个元素。

第三步：形成MIP模型

我们形成一个简单的MIP模型。

不平等的约束条件是：我们需要至少有一家店是每个顾客都能到达的。这是一个非常简单的模型，制定和实现都很简单。

第四步：求解

这是一个大而简单的MIP。它有40000个二进制变量。它的解算速度非常快。在我的笔记本上，用商业解算器只花了不到1秒（用开源解算器CBC花了3秒）。

解决方案看起来像。

----     47 VARIABLE numStores.L           =          113  number of stores

----     47 VARIABLE placeStore.L  store locations

              j1          j6          j7          j8          j9         j15         j16         j17         j18

i4                                                                                                             1
i18                                                            1
i40                                                                                    1
i70            1
i79                                                                                                1
i80                        1
i107                                                                                   1
i118                                   1
i136                                                                       1
i157                                               1
i167                                                                       1
i193                                               1

   +         j21         j23         j26         j28         j29         j31         j32         j36         j38

i10                                    1
i28                                                                        1
i54                                                            1
i72                                                                                    1
i96                                                1
i113                       1
i147                                                           1
i158                                                                                                           1
i179                                                                                               1
i184                       1
i198           1

   +         j39         j44         j45         j46         j49         j50         j56         j58         j59

i5                                                                                                             1
i18                                                1
i39            1
i62                                                            1
i85                        1
i102                                                                       1
i104                                   1
i133                                               1
i166                                                                                               1
i195                                                                                   1

   +         j62         j66         j67         j68         j69         j73         j74         j76         j80

i11                                                                                                1
i16                                                1
i36                                                            1
i61                                                                                    1
i76                                                                        1
i105                                                                       1
i112           1
i117                                                                                                           1
i128                                   1
i146                                               1
i190                       1

   +         j82         j84         j85         j88         j90         j92         j95         j96         j97

i17                                    1
i26            1
i35                                                                                                1
i48                                    1
i68                                                                        1
i79                                                                                                            1
i97            1
i136                       1
i156                                               1
i170                                   1
i183                                                                                   1
i191                                                           1

   +         j98        j102        j107        j111        j112        j114        j115        j116        j118

i4                                                                         1
i22                                                                                    1
i36                                                            1
i56                        1
i63                                                1
i68                                                                                                            1
i88                                                                                                1
i100                                                                                   1
i101           1
i111                                                                                                           1
i129                                                           1
i140                                   1

   +        j119        j121        j126        j127        j132        j133        j134        j136        j139

i11                                                            1
i30                                    1
i53                                                1
i72                                                                                                1
i111                                                                                                           1
i129                                                                                   1
i144                                                                       1
i159           1
i183                                                                                               1
i191                       1

   +        j140        j147        j149        j150        j152        j153        j154        j156        j158

i14                                                            1
i35                        1
i48                                                                        1
i83                                                                                                1
i98                                                1
i117                                                                                                           1
i158                                                                                   1
i174                                   1
i194           1

   +        j161        j162        j163        j164        j166        j170        j172        j174        j175

i5                                                                         1
i32            1
i42                                                                                                1
i61                                                                                    1
i69                                                                        1
i103                                                           1
i143                                   1
i145                                                                                                           1
i158                                                                                               1
i192                       1
i198                                               1

   +        j176        j178        j179        j180        j182        j183        j184        j188        j191

i6                                                                         1
i13                                                                                                            1
i23                                                1
i47                                                                                                            1
i61                                                                                    1
i81                        1
i93            1
i103                                                                                                           1
i125                                   1
i182                                                           1
i193                                                                                               1

   +        j192        j193        j196

i73                                    1
i120           1
i138           1
i167                       1

我想我们已经推翻了你的说法，即MIP模型不是解决这个问题的可行方法。

请注意，宇宙的年龄是137亿年或4.3e17秒。所以我们已经实现了大约1e17的加速。这对我来说是一个记录。

请注意，这个模型并没有找到商店的最佳位置，而只是找到了一个配置，使服务所有顾客所需的商店数量最小化。从这个意义上说，它是最优的。但这个解决方案不会使顾客和商店之间的距离最小化。