2

我们正在努力解决以下问题的某些方面：

  • 公共交通巴士时间表包括班次（〜轨道部分），每个班次都有固定的开始和结束时间

  • 公交车司机需要被分配到每个班次

  • [有问题的约束]法律规定要求每位公交车司机在驾驶 4 小时后（即轮班后）有30 分钟的休息时间

  • 换句话说，驾驶员在换班时累积的驾驶时间不得超过 4 小时，除非驾驶员休息 30 分钟，在这种情况下，累积的时间“重置为零”

总之，我们需要跟踪每个司机的累积驾驶时间，以抑制轮班分配以强制执行 30 分钟的休息时间。

潜在的问题似乎介于作业车间和分配问题之间：

  • 像工作车间问题一样，它有许多不重叠和优先约束的班次（或任务、工作）......

  • ...但是我们的轮班（~任务/工作）没有预先分配给司机；与作业车间问题相比，任务（~班次）需要在特定机器（~驱动程序）上执行，因此是预先分配的，因此分配它们不是问题的一部分

  • 就像分配任务一样，我们需要将轮班分配给尽可能少的司机......

  • ...但是我们还需要处理前面提到的无重叠和优先约束，在分配问题中没有考虑到这些约束

所以我的问题是，如何使用or-tools在约束问题中最好地模拟上述约束？

提前致谢！

4

1 回答 1

1

在约束编程中指定模式的一种通用技术是常规约束（在Gecode、Choco、MiniZinc等中，不确定 or-tools 的状态），其中变量的模式使用有限自动机（DFA 和 NFA）或常规表达式。

在您的情况下，假设您有一系列变量表示某个驱动程序在每个时间点所做的事情，那么指定一个自动机来接受不包含超过四个连续小时的任何值的序列是相当简单的。驾驶。这种自动机的草图：

状态：

  • 驾驶状态 Dn 代表 n 个时间单位驾驶（对于时间单位的某些分辨率），最多 n=4 小时。
  • 中断状态 DnBm 用于在 n 个时间单位行驶后的长度为 m 的中断，最多 m=30 分钟。
  • 起始状态为 D0。

过渡：

  • 驾驶：驾驶1个单位时间时，从状态Dn移动到D(n+1)，从DnBm短于30分钟的休息时间移动到D(n+1)。
  • 中断 1 个单位时间，从 DnBm 移动到 DnB(m+1)，除非已达到 30 分钟的中断时间，否则转换回到 D0。
  • 其他操作主要作为自循环处理，具体取决于所需的语义。

当然，细节会因您的特定用例而异。

于 2019-05-20T11:34:57.450 回答