5

假设我想构建一个函数，可以在一周内正确安排三个公交车司机开车，并具有以下约束：

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

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

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

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

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

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

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

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

4

2 回答 2

3

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

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

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

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

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

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

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

a) 问题变得不可行，

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

c) 找到一个整数解。该解的这个目标值用于确定点 b。

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

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

于 2013-05-12T19:46:41.797 回答
2

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

现在回到比较：

  1. 蛮力：最差。

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

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

于 2013-05-03T01:40:54.343 回答