现有的调度问题算法？

Question

假设我想构建一个函数,该函数可以在一周内正确安排三个总线驱动程序,并具有以下约束条件:

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

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

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

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

坦率地说,这些对我来说都是"文化冲击",因为我过去从未学过任何类型的线性编程.我想知道两件事:

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

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

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

Answer 1

首先，这是一个离散优化问题，因此线性规划可能不是一个好主意（因为它用于连续优化）。您仍然可以使用线性编程来解决这个问题（它将成为整数或混合整数程序），但是这是指数级听到的（如果您的输入大小很小，那么就可以了）。

现在回到比较：

1. 蛮力：最糟糕。

2. 遗传：不能保证最优性。该算法可能无法解决问题。

3. 约束编程：在这种情况下（以及在许多离散优化问题中）绝对是最好的。IBM ILOG CPLEX 求解器中有一个超级高效的实现（但它不是免费的，但对于学术界或测试来说是免费的）。