5

我有一份我想买的物品清单。这些商品由不同的商店和不同的价格提供。商店有单独的送货费用。我正在寻找一种最佳的购物策略（以及支持它的 java 库）以最低的总价购买所有商品。

例子：

  • 商品 1 在 Shop1 的售价为 100 美元，在 Shop2 的售价为 111 美元。
  • Item2 在 Shop1 的售价为 90 美元，在 Shop2 的售价为 85 美元。
  • Shop1的运费：如果总订单<$150，则为$10；$0 否则
  • Shop2的运费：如果总订单<50美元，则为5美元；$0 否则
  • 如果我在 Shop1 购买商品 1 和商品 2，总成本为 100 美元 + 90 美元 + 0 美元 = 190 美元。
  • 如果我在 Shop2 购买项目 1 和项目 2，总成本为 111 美元 + 85 美元 + 0 美元 = 196 美元。
  • 如果我在 Shop1 购买商品 1，在 Shop2 购买商品 2，总成本为 100 美元 + 10 美元 + 85 美元 + 0 美元 = 195。

如果我在 Shop1 订购商品 1 和商品 2，我将获得最低价格：190 美元

到目前为止我尝试了什么

在此之前我问了另一个问题，这使我进入了约束编程领域。我看了cream和choco，但我不知道如何创建一个模型来解决我的问题。

         | shop1 | shop2 | shop3 | ...
-----------------------------------------
item1    | p11   | p12   | p13   |
item2    | p21   | p22   | p23   |
 .       |       |       |       |
 .       |       |       |       |
-----------------------------------------
shipping | s1    | s2    | s3    |
limit    | l1    | l2    | l3    |
-----------------------------------------
total    | t1    | t2    | t3    |
-----------------------------------------

我的想法是定义这些约束：

  • 每个价格“p xy ”在域 (0, c) 中定义，其中c是该商店中商品的价格
  • 一行中只有一个价格不应该为零
  • 如果从一家商店购买一件或多件商品并且价格总和低于限额，则将运费添加到总成本中
  • 商店总成本是商店中所有商品价格的总和
  • 总成本是所有商店总和的总和

目标是“总成本”。我想尽量减少这种情况。

在奶油中，我无法表达有条件运输成本的“如果那么”约束。

在 choco 中存在这些限制，但即使对于 5 件商品和 10 家商店，该程序也运行了 10 分钟而没有找到解决方案。

问题

我应该如何表达我的约束以使这个问题对于约束编程求解器可以解决？

4

3 回答 3

4

我已经在MiniZinc（一种高级约束编程语言）中实现了这个问题：shopping_basket.mzn。它非常先进，也许可以用作您的 Java 模型的模型。

对于 Choco 模型，您是否尝试过不同的搜索策略？不同的策略可能会更快。

顺便说一句，您可能想要查看的另一个 Java 约束编程求解器是JaCoP。

于 2010-05-12T20:20:10.980 回答
3

您要问的本质上是k-knapsack问题。我喜欢的维基百科页面有丰富的解决方案资源。然而，问题是 NP-Complete 可以完全解决，因此您可能希望做的是通过模拟退火或其他形式寻找接近最佳的解决方案，以搜索问题空间。

首先要记住的是，在约束问题中，您最终可能会花费大量时间来生成解决方案。在您之前的示例中，虽然 5 件商品和 10 家商店看起来很小，但实际上会产生很大的问题空间（大约 1e5 不包括进一步引起问题的附加条件定价的复杂性）。

该问题的限制是您购买每件商品中的一件。目标是最低价格。我认为您所拥有的相当不错，尽管我不太确定要点一和二。

  • 每个价格“p xy”在域 (0, c) 中定义，其中 c 是该商店中商品的价格
  • 一行中只有一个价格不应该为零

    • 我会考虑将运费摊销到所购买物品的成本上，而不是在计算时将其作为总价值添加。

    于 2010-05-12T19:29:56.750 回答
    1

    我不太确定这是一个 k-knapsack 问题。该问题确实提到了“购物篮”一词，但没有具体说明任何给定货物的容量。如果您指定了最大装运尺寸，那么问题开始看起来更像是一个背包问题。

    这个问题实际上只是一个基本的网络流问题，弧上的运输成本和起点的成本。因为您有一个明确的目标函数 - 最小化运输 + 产品成本，并且因为可能只有一种解决方案，所以 CP 可能不是最好的方法。

    考虑作为线性规划问题求解：

    最低：运输+产品成本

    ST：总出货量 >= 需求量（每个产品）

    您可能需要为运输成本开发一些分段线性方程，但这应该不是问题。

    于 2010-05-20T20:25:19.030 回答