Python（多背包）中使用 OR-Tools CP Solver 的包裹运输（包裹合并）

Question

我正在使用 OR-Tools CP Solver 实施包整合解决方案（基于护士问题解决方案）。

有一家工厂生产一些小包裹，需要 post 运送给客户。最好将一些 mini_Packages 合并成更大的包裹（例如，如果我们尊重总重量限制，我们可以将 3 灯 mini_Packages 合并成一个包裹，并支付一次运输费用而不是 3 次）。

Mini_Packages 在数据源中有一些重要的属性（固定目的地、重量、可接受的交货日期范围）。

我的主要 0-1 整数变量如下所示：

x[mini_package_source_number, destination, optimal_shipment_date, package_number]

它== 1 如果mini_package应该去某个目的地，在某个日期，合并到某个Package_number。

我已经成功构建了大部分模型，除了：

1.主要挑战
如何进行约束以确保当求解器分配最佳包裹编号时，它不能与任何其他目的地或 shipment_date 一起使用？（它实际上是一个合并的包裹去某个地方）

潜在代码：

for package_number in range(Packages):
  model.Add(sum(x[mini_package_source_number, destination, optimal_shipment_date, package_number] for ...) <= 1)

是错误的，因为分配的 Package_number 可以存在多次，合并多个 mini_Packages。它可以存在多次，但必须始终分配给相同的目的地和日期。

潜在的求解器解决方案：

x[1, Place67, 2019-01-01, 8] = 1
x[2, Place124, 2019-01-04, 119] = 1
x[3, Place124, 2019-01-04, 119] = 1

还可以，mini_Packages2 和 3 已合并到包裹 119 中，目的地相同（和日期）。

x[4, Place55, 2019-01-05, 119] = 1

是错误的，因为 mini_Package 4 也被合并到包 119 中，之前由求解程序决定去另一个目的地（和另一个日期）。

如何编码？我真的很感激任何解决方案的建议。

2。加法

@Stradivari 感觉（下面的回答）是准确的。很可能我使用了过多的变量。

3。冲突产品挑战

第 2-3 点移至：
https://or.stackexchange.com/questions/2786/shipments-consolidation-with-or-tools-cp-solver-in-python-multi-knapsack

Answer 1

为每个 [pkg, destination] 对创建一个 boolvar。

for package_number in range(Packages):
    for destination in destinations:
        model.AddBoolOr(v for k, v in x.items() if k[1] == destination and k[3] == package_number).OnlyEnforceIf(pkg_dest[package_number, destination])
        model.AddBoolAnd(v.Not() for k, v in x.items() if k[1] == destination and k[3] == package_number).OnlyEnforceIf(pkg_dest[package_number, destination].Not())
    model.Add(sum(pkg_dest[package_number, destination] for destination in destinations) == 1)

日期的逻辑相同。

顺便说一句，我觉得你可能用这个公式创建了很多无用的变量，你真的能决定一个迷你包目的地 and/or 日期吗？或者只是包裹，然后是每个包裹的目的地和日期？

Python（多背包）中使用 OR-Tools CP Solver 的包裹运输（包裹合并）

Packages shipment (packages consolidation) with OR-Tools CP Solver in Python (multi-knapsack)

python

scheduling

knapsack-problem

cp

or-tools