java - 调度问题的现有算法？

Question

假设我想构建一个函数来正确安排三名公交车司机在一周内开车，但有以下限制:

• 每位司机每周不得驾驶超过五次
• 每天必须有两个司机开车
• 他们每周休息一天(不会与其他司机的休息日冲突)

什么样的算法可以用来解决这样的问题？

我浏览了几个网站，发现了这些:

1) Backtracking algorithm (brute force)
2) Genetic algorithm
3) Constraint programming

坦率地说，这些对我来说都是“文化冲击”，因为我过去从未学过任何一种线性规划。我想知道两件事:

1) 哪种算法最适合上述情况？

2) 解决这个问题最简单的算法是什么？

3) 请建议我可以研究的任何其他算法来解决上述问题。

Answer 1

1) 我同意蛮力是不好的。

2) 你的问题是一个整数问题。不过，它们可以用线性规划来解决。

3) 您可以区分两种不同的方法:启发式方法和精确方法。启发式在合理的计算时间内提供了很好的解决方案。当对计算时间有严格要求或问题太难计算最优解时使用它们。遗传算法是一种启发式算法。

由于您的问题相对简单，您可能会采用精确的方法。

4) 准确解决这个问题的标准方法是在分支定界搜索树中嵌入一个线性规划。有很多关于它的文献。该过程可概述如下:

1. 用单纯形算法求解线性规划
2. 找到用于分支的小数变量。 IE。 x=1.5
3. 新建两个节点，分别添加约束x<=1和x>=2
4. 进入一个节点(通过某种策略选择)
5. 转到第 1 点

此外，在树中的每个节点上，在点 1 之后，算法会检查是否可以修剪节点。这意味着停止从该节点开始“更深入”地搜索，因为

a) 问题变得不可行了，

b) 已经有更好的解决方案，

c) 找到一个整数解。此解决方案的目标值用于确定点 b。

当所有节点都被修剪时，该过程结束。

幸运的是，正如 Nicolas 所说，有免费的实现可以做到这一点。您所要做的就是创建模型。在某种工具中编写其目标和约束条件并让它求解。