推动板条箱时最大化距离

Question

我正在努力为这个问题编写一个算法。

问题

有一家叫CratePushers的公司，它的员工愿意推箱子换钱。他们的员工具有某些属性：

• 每个员工都以一定的速度推动板条箱。例如，Alice 可能会以每美元 3 英尺的价格推箱子，而 Bob 可能会以每美元 2 英尺的价格推箱子
• 每个员工都有一组他们能够推送的特定的板条箱类型。例如，Alice 可能只能推送标有 A、B 或 C 的板条箱，而 Bob 可能只能推送标有 A 或 D 的板条箱
• 每个员工可能对他们愿意推送的板条箱总数有限制。例如，尽管 Alice 有能力推动板条箱 A、B 或 C，但她可能有一项政策，规定每次工作分配最多只能推动 2 个板条箱
• 每位员工愿意接受的美元数量也可能受到限制。例如，Alice 可能有一项政策，规定她每次工作分配最多只能接受 35 美元。 （忽略此属性的解决方案仍然非常有帮助。）

现在假设我想获得他们的服务。我的后院有几个板条箱，每个板条箱都有一定的预算。例如，假设我有 5 个板条箱，标记为 A 到 E，我愿意在每个板条箱上花费 20 美元，但我对每个板条箱的预算只能用于推送一个特定的板条箱。我的目标是“最大化所有板条箱推动距离的总和”。问题是：我如何最佳地分配我的钱？也就是说，我付钱给谁来推动哪些板条箱，以及多少钱？ 输入

员工列表及其属性，例如

[
  {
    name: 'Alice',
    capableOfPushing: ['A', 'B', 'C'],
    paymentLimit: 35,
    crateLimit: 2,
    efficiency: 3, // Feet per dollar
  },
  {
    name: 'Bob',
    capableOfPushing: ['A', 'D'],
    paymentLimit: null,
    crateLimit: null,
    efficiency: 2,
  }
]

以及我的每箱预算，例如

[
  {
    crate: 'A',
    budget: 20,
  },
  {
    crate: 'B',
    budget: 20
  },
  {
    crate: 'C',
    budget: 20
  },
  {
    crate: 'D',
    budget: 20
  },
  {
    crate: 'E',
    budget: 20
  },
]

输出任何最优解都是可以接受的。上述示例的一种解决方案是：

[
  {
    employee: 'Alice',
    crate: 'B',
    amountPaid: 20,
  },
  {
    employee: 'Alice',
    crate: 'C',
    amountPaid: 15,
  },
  {
    employee: 'Bob',
    crate: 'A',
    amountPaid: 20,
  },
  {
    employee: 'Bob',
    crate: 'D',
    amountPaid: 20,
  }
]

（没有人可以推动板条箱 E，所以我的 20 美元预算仍然留在我的口袋里。）如果我对板条箱 B 的预算少于 5 美元，那么最佳解决方案是向 Alice 支付 15 美元购买板条箱 A，支付 20 美元购买板条箱 C，并向鲍勃支付 5 美元购买板条箱 A，支付 20 美元购买板条箱 D。这意味着我们“我们让板条箱 B 保持不变，但在考虑所有板条箱时，我们仍然最大化推动距离的总和。

我考虑过的事情

有一个蛮力解决方案，我们创建所有可能的推箱子组合。例如，我们考虑 Alice 推送 (A,B)、(A,C)、(B,C) 的所有 3 个场景。该解决方案效率太低，因为当多个员工有板条箱限制时，或者即使单个员工的属性数量较大时，它也会失控。就像如果 Alice 可以推送最多 30 个 crate 类型并且 crate 限制为 10 个，那么场景的数量已经达到数千万。

我觉得动态编程可以工作，但同样是板条箱限制导致了在了解每个点的最佳解决方案方面出现问题。

我在 LeetCode 上寻找过类似的问题，但尚未找到足够相关的问题。

这个问题有点类似于

背包问题

，但不太合适。

它也类似于多商品最大流量问题，但也不太适合？我正在努力找出一种可行的方法来将员工表示为图表，而且板条箱限制确实存在问题。但这似乎是最有希望的方向。

感谢@nneonneo 推荐 MILP！这是一个很好的解决方案。

Answer 1

示例问题可以这样表述，它提供了正确的答案：

import gurobipy as gp
from gurobipy import GRB

model = gp.Model("Pushing crates")

a_distance = model.addVar(vtype=GRB.CONTINUOUS, name="a_distance")
b_distance = model.addVar(vtype=GRB.CONTINUOUS, name="b_distance")
c_distance = model.addVar(vtype=GRB.CONTINUOUS, name="c_distance")
d_distance = model.addVar(vtype=GRB.CONTINUOUS, name="d_distance")
e_distance = model.addVar(vtype=GRB.CONTINUOUS, name="e_distance")

model.setObjective(a_distance + b_distance + c_distance + d_distance, GRB.MAXIMIZE)

alice_efficiency = 3
alice_payment_limit = 35
alice_crate_limit = 2

bob_efficiency = 2

budget_for_a = 20
budget_for_b = 20
budget_for_c = 20
budget_for_d = 20
budget_for_e = 20

dollars_to_alice_for_a = model.addVar(vtype=GRB.INTEGER, name="dollars_to_alice_for_a", lb=0, ub=budget_for_a)
dollars_to_alice_for_b = model.addVar(vtype=GRB.INTEGER, name="dollars_to_alice_for_b", lb=0, ub=budget_for_b)
dollars_to_alice_for_c = model.addVar(vtype=GRB.INTEGER, name="dollars_to_alice_for_c", lb=0, ub=budget_for_c)
dollars_to_bob_for_a = model.addVar(vtype=GRB.INTEGER, name="dollars_to_bob_for_a", lb=0, ub=budget_for_a)
dollars_to_bob_for_d = model.addVar(vtype=GRB.INTEGER, name="dollars_to_bob_for_d", lb=0, ub=budget_for_d)
dollars_for_e = model.addVar(vtype=GRB.INTEGER, name="dollars_for_e", lb=0, ub=budget_for_e)

value_1_for_alice_crate_limit = model.addVar(vtype=GRB.INTEGER, name="value_1_for_alice_crate_limit", lb=0, ub=1)
value_2_for_alice_crate_limit = model.addVar(vtype=GRB.INTEGER, name="value_2_for_alice_crate_limit", lb=0, ub=1)
value_3_for_alice_crate_limit = model.addVar(vtype=GRB.INTEGER, name="value_3_for_alice_crate_limit", lb=0, ub=1)

model.addConstr(dollars_to_alice_for_a + dollars_to_bob_for_a <= budget_for_a)
model.addConstr(dollars_to_alice_for_a + dollars_to_alice_for_b + dollars_to_alice_for_c <= alice_payment_limit)
model.addConstr(value_1_for_alice_crate_limit + value_2_for_alice_crate_limit + value_3_for_alice_crate_limit <= alice_crate_limit)

model.addConstr(a_distance <= alice_efficiency * dollars_to_alice_for_a * value_1_for_alice_crate_limit + bob_efficiency * dollars_to_bob_for_a)
model.addConstr(b_distance <= alice_efficiency * dollars_to_alice_for_b * value_2_for_alice_crate_limit)
model.addConstr(c_distance <= alice_efficiency * dollars_to_alice_for_c * value_3_for_alice_crate_limit)
model.addConstr(d_distance <= bob_efficiency * dollars_to_bob_for_d)
model.addConstr(e_distance <= 0 * dollars_for_e)

model.optimize()

for var in model.getVars():
    print(f"{var.varName}: {var.x}")

print(model.ObjVal)

最后一步是将其概括以处理各种输入。