algorithm - 基于时间间隔重叠，权重约束和距离最小化的组合分组优化问题

Question

让每个元素都是独立的假设一个个体被定义为每个个体都有一个时间范围、权重和位置。
目标是将时间范围重叠的个体分组，同时确保在组内，个体的权重之和不超过某个阈值同时，期望最小化组中个体之间的总距离。只要满足权重约束，就可以将尽可能多的个体放入一个组中。假设有N个个体（假设在实际实现中最多有5000个个体）。
目标是让尽可能多的个体分组（即最小配对），同时最小化组中个体之间的总距离。这个问题似乎是NP难的，所以我不是在寻找全局最小值，而是一个好的解决方案。
例如，考虑一个离散时间的例子，其中有十个时间间隔[1，2，3，4，5，6，7，8，9，10]权重阈值为4，个体的位置为一维整数线上的点。
假设我们有以下人员：

A: time range: [1, 2, 3] | weight: 1 | location: 1
B: time range: [2, 3, 4] | weight: 2 | location: 2
C: time range: [4, 5, 6] | weight: 2 | location: -3
D: time range: [4, 5, 6] | weight: 3 | location: -3

注：
A和C不能分组，因为它们没有重叠的时间范围。
将a和b组合在一起比将b和c组合在一起更可取，因为a和b更接近。
C和D不能分组，因为它们的权重之和超过4。
有没有人有推荐的算法来解决这样的问题？
我看过《计算智能研究666》（Studies in Computational Intelligence 666）中的例子，迈克尔·穆廷吉（Michael Mutingi），查尔斯·姆博瓦（Charles Mbohwa）（作者）——分组遗传算法进展与应用斯普林格国际出版（2017）然而，没有一种分组算法看起来非常合适。
理解/解释此问题的不同方法：
解读一：装箱问题
目标是找到个体的分区，以便在每个分区内，所有成员的时间范围重叠每个分区的总“权重”总和低于某个阈值（请注意，没有一个单独的分区超过权重阈值）。总“距离”和（通过对每个分区的距离求和计算）最小化因为只有一个单独的分区形成。
解释2：
见下文
我解决这个问题的不切实际的方法
步骤1：定义个人

Individual:
   Time Range: [2, 3, 4]
   Weight: 2
   Location: -3

第二步：寻找可能与时间相容的个体
假设一天24小时被定义为24个一小时垃圾箱。每个箱子代表一小时。例如，索引6处的bin表示6 am。我们把这称为时间表吧。
我们根据个人的时间范围将其放入这些容器中。例如，如果john的时间范围是[1，2]，wilson的时间范围是[2，3]，那么时间表将填充如下：

[ [] , [John] , [John, Wilson], [Wilson], [] , ... , [] ]

在这里，同一个容器中的个体可能被分组。
过时的
步骤3：基于权重约束生成可行组
让我们定义一个组的重量限制为4。
对于时间表中的每个箱子，我们生成满足权重的组
约束（个体权重之和小于4）。
注意，我们可以跳过一个或几个人的垃圾箱。在这里，
每组有以下特点：

Group:
   Individuals: [ Person1, Person2, ... ]
   Weight: INT (computed by summing weight of individuals)
   Distance: FLOAT (computed by finding distance sum between individuals)

我们将生成的所有组存储在
被称为可行的小组的名单。
第4步：找到最佳组集
我们通过寻找不相交集来优化组/分区
使总距离和最小化的组。
这种方法有问题
到了第3步，这种方法在计算上变得不可行，因为
通过枚举生成所有可能的组。
更新：
第一步：“个人”的新定义
一开始，每个个体都被视为一个单一的群体：

Group:
   members: [person1]
   time range: [0, 1, 2, 3, 4, 5]
   weight: 2
   location: -3

第二步：和以前一样
步骤3：按人口对时间箱排序
时间箱按该箱中单例组的数量降序排序。排序后，单件组数最多的时间段排名第一。
步骤4：合并组，直到无法合并为止
从第一个时间单元开始，构造一个图，使得节点是组，边表示两个组之间的距离只有当它们的加权和不超过最大容量时，才存在两个边之间的边。例如，将权重阈值设为4，并考虑以下单例组：

group1:
   members: [person1]
   time range: [0, 1, 2]
   weight: 1
   location: -3

group2:
   members: [person2]
   time range: [0, 1, 2, 3]
   weight: 2
   location: 0

group3:
   members: [person3]
   time range: [0, 1]
   weight: 3
   location: 1

注意，在3个可能的边缘中，存在以下边缘：

group1 -- 3 -- group2
group1 -- 4 -- group3

这是因为group2-group3超过了4的权重阈值。
现在我们找到值最小的边并合并两个端点节点合并后的两个节点，我们重新计算边缘的基础上的新节点可用的集合，我们重复，直到没有边缘存在。
在上面的例子中，我们将group1和group2合并得到：

group12:
   members: [person1, person2] (union of members)
   time range: [0, 1, 2] (intersection of time ranges)
   weight: 3 (sum of weights)
   location: 1.5 (center between two locations)

group3:
   members: [person3]
   time range: [0, 1]
   weight: 3
   location: -3

现在，如果我们重新计算边，我们看到没有边存在。这样，我们就完成了第一次的垃圾桶。
下一步，我们将删除所有单例组，这些单例组的成员与后续时间箱中的成员重叠例如，在本例中，如果在随后的操作中找到group1、group2或group3，则删除这些组。
我们重复我们在第一次箱子上执行的合并过程。
我们重复这个直到最后一次。
到目前为止，这是我的方法，我意识到这不是最有效的方法。有人有改进的建议吗如果解释不清楚，请在评论中告诉我！

Answer 1

目标是将尽可能多的个体分组（至少
（成对）尽可能减少
群体中的个体。
由于您的目标是将尽可能多的个体分组，因此在对距离进行任何进一步比较之前，您不必比较所有的组，而只需比较那些允许最多分组个体的组。
如果你把每个箱子作为一个集合，试着找到它们中最大的一个，并且有一个最大的，你现在可以检查它的可行性。如果不可行，你就得试试第二大的。
一个人的体重必须是一个或更高如果是这样，你知道你的体重限制，某些配对可能更具吸引力，如果你可以用一种更接近的方法，你可以对每一个容器应用贪婪算法（以适应最佳体重），然后应用贪婪来解决你的覆盖问题。
基本上，在选择了有效但可行的时隙分配后，您会尝试将多个个体分组，只有在有多个选项的情况下，您才会比较这些选项以获得更低的总距离。
[1]https://en.wikipedia.org/wiki/Maximum_coverage_problem