问题标签 [assignment-problem]

对于解决此问题的任何帮助，我将不胜感激。在这个双层分配问题 (BAP) 中，我们有 n 个起点和 n 个终点，领导者必须选择 k 个起点和 k 个终点，这样才能解决追随者的典型（最小化）分配问题（AP）（大小为 k ) 被最大化。那是：

最大化（大小为 k 的 AP 的解决方案）[领导者的目标函数 (OF)]

st 1.Leader选择k个起点和k个目的地

2. 大小为 k = minimum(sum(cij * xij) i= 1…k) 的 AP 的解（对于 k 个选定的起点和终点）[Follower's OF]

3. 英石。典型的 AP 约束。（xij 布尔值等）

我已经成功地实现了两个目标函数对齐的情况下的代码（例如两个最小化），因为我可以通过编写一次目标函数来做到这一点，因为它对于领导者和追随者来说是完全相同的。当我尝试解决上述公式时，我的问题出现了，其中我们有一个最大化的领导者和一个最小化的追随者。下面是适用于领导者和追随者都最小化的情况的代码。

对于 Leader 的最大化问题和 Follower 的最小化问题（我无法实现），输出解决方案将是：选择行（起点）1 和 2 以及列（目的地）1 和 3，以及解决方案值 11（所选行和列的 AP）。欢迎任何帮助解决这个问题:)

非常感谢！

如果需要，这里有作业问题的描述：https ://en.wikipedia.org/wiki/Assignment_problem

柯克曼的女学生问题旨在将三个女孩组成一组持续“n”天，这样任何一对女孩都不会在同一组中超过一次。为此，我与 9 个女孩一起工作，她们需要被分成三人一组，为期 4 天。

我对 Python 很陌生。我现在想避免花哨的模块，这样我就可以正确地掌握基础知识。

这是我的代码：

当我运行它时，内核没有响应，好像卡在某个无限循环中并且没有输出。

给定一个 NxM 正整数数组，如何选择整数，以便在每行最多有 x 个选择，每列最多有 y 个选择的情况下获得最大的值总和。这是我在制作 NCAA 游泳阵容时所面临的一个问题的抽象。每个游泳者在每个项目中都有一个时间，可以使用USA Swimming Power Points Calculator将其转换为整数，越高越好。一旦你转换了这些时间，我想为每个项目分配不超过 3 名游泳者，每个游泳者不超过 3 场比赛，以使力量得分的总和最大化。我认为这类似于武器瞄准分配问题但是这个问题允许一种武器类型多次攻击同一个目标（在我的情况下，允许一个游泳者参加同一个事件两次），这对我的用例不起作用。有人知道 wta 问题的这种变化被称为什么，如果知道的话，您知道我可以寻找的任何解决方案或资源吗？

问题设置

目前，我们正在为一家食品科技初创公司（电子杂货店）解决配送问题。我们有工作（要交付的订单）和工人（快递员/包装员/通用）问题是如何有效地将订单分配给工人。第一步，我们决定优化 CTE（点击即食 - 下订单和订单交付之间的时间）

问题本身

问题来自这样一个事实，即有时每个作业有 2 个工人而不是单个执行者是有效的，因为打包者可能知道商店“地图”，而快递员可能有自行车，与他们中的每一个相比，它们可以更快地执行作业，甚至计算订单转移成本。

我们研究了算法，发现我们的问题看起来像分配问题，并且有一个算法解决方案（匈牙利算法），但问题是经典问题要求“每个工作分配给一个工人，每个工人分配一份工作”，而在在我们的案例中，有时每份工作有 2 个工人是有效的。

到目前为止我们所做的尝试

1. 将（打包机 A +通用 B）组合插入成本矩阵，但在这种情况下，我们不能将 通用 B添加到矩阵中，因为结果我们可以得到通用 B将分配给 2 个工作（作为一个单独的单元和作为与封隔器 A组合的一部分）

2. 因此实施 2 种匈牙利算法：首先分配包装，然后分配交付。它在绝大多数情况下都有效，但有时会导致效率低下的解决方案。如果需要，我将添加一个示例。

问题本身

我用谷歌搜索了很多，但找不到任何可以指导我解决问题的方法。如果您有任何链接或想法可以用作解决方案的线索，我将很乐意检查它们。

编辑：我已经添加了我的问题的蛮力解决方案。希望这有助于更好地理解问题

我有N不同的工作。有些工作可以连续完成。

需要将连续的作业排列成作业序列，以使作业序列的数量M最少。

问题在于最大基数匹配的形式。

但是确定最大基数匹配时，作业序列的数量是最小的吗？

我正在寻找一种算法来解决它。

例子

N=6

可以从事以下工作：

然后，作业 1 可以转到作业 2、5。

然后作业 2 可以转到作业 3。

然后，作业 4 可以转到作业 2、5。

然后作业 5 可以转到作业 6。

执行工作分配，我们得到以下 2 个工作序列：

1-2-3

4-5-6

那么M=2。

这可以看作是找到完成所有航班（工作）的最少机组人员的问题。

WE are Designing a Solution for building delivery-Agent Task Assigment Tasks are Pickup Request, Drop Request

客户在家门口就组织提供的各种服务提出取货请求/丢弃请求。

基于以下标准

• 客户位置密码，
• 代理轮班时间表，
• 代理-客户位置匹配
• 代理评级必须自动分配

我们无法确定 [旅行或分支限制] 应在什么基础上计算成本。解决这个问题的方法是什么。

目前，我们正在尝试使用 Drools 来选择用于分配的活动代理，我们与 Opta Planner 合作，

有人可以提出一些解决方案和技术建议吗？

这是解决调度问题的尝试。目标是按顺序运行多次，以获得体育联盟的每周时间表，定义如下：

1. 有48个人，每个人都按技能顺序排列。
2. 每个人都被分配到一个团队。团队由 3 个人组成。
3. 排名前 12 的人不能与排名后的 12 人比赛。
4. 个人只能互相玩一次。
5. 个人之间的对抗不能超过两次（越少越好）。

*个人在代码中被标记为“Pods”，但等同于上述个人。

下面是我试图用来解决这个问题的 ortools 代码。我认为最难的部分是确保目标函数是正确的，并且我适当地构建了约束。

最后，我有一个列（个人）和行（团队）的矩阵。有 16 支球队，我已经构建了目标函数，使得奇数行播放下面的偶数行。目标是最小化每个团队中个人排名之和的差异的绝对值：minimize(sumOf(abs(home_i - away_i) for home/away in teams)). 我不确定我是否正确地将这个成对绝对差之和转换为线性约束。

我有几个主要问题：

1. 似乎成本总是1176。为什么会这样？对我来说，最佳解决方案似乎是：SUM(ABS(team1 - team2)) for all teams，并且由于团队的最小值/最大值相对接近，我预计成本会低得多，特别是考虑到我abs(team1 - team2) == 0从蛮力解决方案中获得了很多增量没有人与其他任何人一起玩过/对抗过其他任何人的初始运行。（我的运行解决方案如下所示）
2. 如果我尝试按顺序运行此程序（以利用所玩的/反对约束），我会在第二次运行时得出一个不可行的解决方案。我创建了一个纯粹的蛮力解决方案，现在是第 5 周，并且满足这些限制没有问题。蛮力解决方案的主要问题是它现在大约运行了 5-6 天并且没有完成。
3. 这段代码需要很长时间才能运行！我在它上面放了一个 5 分钟的计数器，因为无论运行 5 分钟还是 6 小时，它似乎都会产生相同的解决方案……而且它产生的解决方案只是在问题停止运行 6 小时后才产生的。我是否错误地指定了某些东西导致它运行这么长时间？
4. 从问题的描述中，代码是否看起来像我想要的那样。我知道代码审查可能超出了这个问题/答案格式的范围，但我想我会问，因为可能需要简短的审查来帮助回答我是否正确指定了目标函数。

谢谢！

一次运行后的收益：（我不知道为什么......我原以为成本会产生 Sum(abs(team0 - team1) + ... + abs(team14 - team15)) == (37 + 31 + 11 + 3 + 19 + 3 + 9 + 1) == 114：）

连续两次运行后的产量（错误），其中第一次运行的输出被缓存并且个人的队友/对手更新：生成一天的第一个时间表......总成本 = 1176.0

我正在尝试找到一种将资源类型分配给最佳项目的算法。例如，我有 3 种类型（A 型、B 型、C 型）和 25 种项目。每种类型都有一个容量。

此外，每个项目都有不同的成本来分配关于来自成本矩阵的类型的每种类型。

例子：

我正在等待您的建议以找到最佳方法。