时间戳

首页 > 解决方案 > 使用 OptaPlanner 通过取货和交货解决多个订单

optaplanner - 使用 OptaPlanner 通过取货和交货解决多个订单

问题描述

你好 optaplanner 社区。问候并始终感谢您的回答。

我有一个 VRP 问题，我有一个车队和访问列表。每次访问都有一个交货点（D delivery）和一个拣货点（Ppicking）。限制是每次访问只有一辆车参加，车辆必须先到取货点装载访问所需的东西，然后再去交付。如果交货点的需求大于容量，则不得将其分解为行程。如果没有其他容量更大的车辆能够支持此次访问，则必须忽略此计划中的访问。最重要的是，因为有些访问的需求无法分割，因此车辆必须在同一行程中运输。

1-我想知道我遇到的这个问题是否可以建模为 VRPPD，即使每辆车只能去一次交货点？我理解虽然每辆车只能到一个送货点一次，但两次访问之间必须有订单，并且每个取货点必须在送货点之前完成。据我了解，每次访问都没有多选，因为车辆只开一次，但整个路线确实有多个接送。

2-我做了一些假设来解决我的问题。你有什么建议我可以为它建模吗？我的假设正确吗？我是 Optaplanner 的新手，任何建议都会非常有用。

我分析过，也许我可以通过将所有点注册为访问来解决我的 VRPPPD，其中访问的交付点和取件点将在同一位置。每次访问都会有一个类型来知道哪个是拣货（P），哪个是交付（D）。它必须管理一个影子变量来更新车辆的容量，因为在每个 P 中容量都会增加，而在 D 中容量会减小。我的硬性限制是容量限制，一个限制是让每个 P 和 D 拥有相同的车辆，另一个限制是每个 P 在 D 之前完成。

3- 另一方面，我想使用 Geoffrey 的示例“optaplanner-mixedvrp-experiment”？我知道这个例子是针对多次旅行，其中车辆将到客户的旅行分成多次旅行，所以我理解车辆多次前往客户，所以我理解我必须进行一些修改。

我可以在此示例“optaplanner-mixedvrp-experiment”中进行哪些更改以混合取货和交付，但绝不来自同一客户。这正是我的要求。

应用这个例子是否可以解决 4 和 5？

4- 我该如何管理，当附近的收集点有访问时，我可能会先去几个收集点，然后再进行交货。

(P1 P2 D1 D2 P3 D3) P1和P2在附近，先提货再发货

5-我如何管理当有相同交货点的访问时，车辆可以同时加载这些访问所要求的内容，从而不必返回相同的点？由于我了解访问之间的距离和时间不应加倍，因为尽管它们是不同的访问，但它们具有相同的位置。

(P1 D1 D2 P3 D3) 其中 D1 和 D2 具有相同的上车点 (P1) 并且车辆有足够的容量来加载 P1 点 D1 和 D2 的需求。

6- 如何让车辆以零载客量离开车厂，直接前往第一个上车点？

标签： optaplanner

解决方案

我不熟悉 Geoffrey 的 PDVRP 实验，但这就是我的处理方式（请注意，我将使用图形术语）：

  • 如果您只希望一辆车去拜访，您的问题中必须只有一个节点（计划变量）。Optaplanner 会将这个节点分配给一个链，更准确地说是分配给计划开始旅程的前一个节点。如果它只有一个节点，它本质上将是一次访问。
  • 如果您希望 Optaplanner 在其需求不适合车辆的情况下忽略访问，您必须进行访问nullable（请参阅此问题）。这意味着 Optaplanner 不会将其分配给资源。请注意，Optaplanner 不支持链变量上的这一点，但您可以使用虚拟车辆解决该问题。
  • 对于您的问题，您希望满足提货和交货限制。您可以使用自定义移动来强制执行此操作（例如，链式移动同时移动取货节点和交付节点，而不是单个节点），或者您可以使用约束来惩罚任何违反此约束的行为（即每次违规的硬分 -1 ）。这只是一个猜测，但我认为使用自定义动作更有效。Optaplanner 没有开箱即用地配置来支持这个用例，并且由于内置链移动的性质，将花费更多时间探索不可行的解决方案空间。无论哪种方式，您都必须知道在任何给定时间您正在处理什么对象，因此您可以创建一个类，例如Visit（或可能Job），带有子类PickupVisit和DeliveryVisit. 或者，您可以将类型存储为字段，但这是您需要考虑的设计决策。我建议无论您选择哪种方式，您都可以轻松检索同级任务，即相应的取货或交付任务，因为您在计算中将需要它。

如何管理当有相同交货点的访问时，车辆可以同时加载这些访问所需的内容，从而不必返回相同的点？

有几个选项：

  1. 您可以将它们预处理为单个作业
  2. 您可以使用目标值来强制执行此行为（例如，最小化对某个位置的唯一访问的目标）。你有充分的灵活性，你把它放在哪里。

如何管理当有相同交货点的访问时，车辆可以同时加载这些访问所需的内容，从而不必返回相同的点？因为我知道访问之间的距离和时间不应该加倍，因为尽管它们是不同的访问，但它们具有相同的位置

通过使用目标。这听起来像是期望的行为，而不是必需的行为。所以我会输入一个最大化访问次数或最小化总距离的分数。你必须玩它，因为没有简单的答案。

如何让车辆以零载客量离开站点，直接前往第一个上车点？你需要实现一个分数计算器，所以你会在那里做。例如，在一个简单的分数计算器中，您只需从第一份工作开始累积，这样您就可以从0. 其他分数计算器会稍微复杂一些，但 Optaplanner 存储库中有一些很好的例子。

我希望这能回答你的大部分问题。

推荐阅读