6

我在这里的第一篇文章——希望你能帮助我设计一个我已经考虑了一段时间的算法——不确定要采取什么方法（VRPTW 或资源调度或其他完全的东西！？）

用一个真实的例子来说，我们在少数几个地方（通常少于 5 个）有大量的花园垃圾。必须在给定的时间范围内将废物全部运送到其他地点。为了移动花园垃圾，我们有拖车，必须用汽车牵引。花园垃圾只能在特定时间（时间窗口）丢弃在垃圾场。在某些地方，我们可以将拖车放下，由那里的人来装满或清空，但在其他地方，汽车司机必须自己做，汽车必须留在那儿。可以计算所有时间（即装载/卸载时间、运输时间等）。汽车可以在没有拖车的情况下在站点之间移动，拖车可以拖空，但拖车不能在地点之间移动。

我们的目标是确保所有拖车装载的废物在运输的同时

  • 尽量减少使用中的拖车和汽车的数量
  • 满足所有丢弃废物的时间窗口
  • “平衡”拖车 - 即在一天结束时，我们在每个位置的拖车数量与一天开始时一样多

我曾想过将其作为一种资源调度算法，但我不确定如何处理预告片的“平衡”。

我考虑的另一种方法是首先考虑汽车。然后我可以选择最早的任务并在此之后构建所有可行任务的图表。如果我然后选择通过图表的最长路径将服务于最大数量的拖车负载。然后我可以从任务列表中删除这些任务并重复，直到所有任务都得到服务。然后我需要遍历这些拖车负载列表来计算所需的拖车数量。

任何有关方法的想法将不胜感激！

4

5 回答 5

4

我们肯定在这里讨论的是一个 NP 完全算法，除了一些汽车和拖车之外，这不会是一项任务，您可以从所有可能的解决方案中获得最佳解决方案，然后能够丢弃它并再次避免你建议的最长路径。如果你以这种方式设计你的算法，很可能有一天你会添加更多的汽车和拖车，它永远不会完成计算解决方案。

您可能希望使用可以合理快速地生成足够好的问题解决方案的算法。确保您为解决方案的质量创建了一个度量标准，您获得了一种评估理想解决方案的度量值的好方法，然后为自己设置了一些百分比，您希望您的解决方案在该百分比范围内来自理想解决方案，并且简单地取第一个度量在范围内的解决方案。这有一个额外的好处，如果这个算法的计算时间太长并且你中止它，你仍然可以使用具有最低计算度量的解决方案，即使它不在你的预期范围内。

我不确定采取什么方法来解决问题本身。我建议在acm 门户上搜索后阅读几篇文章。我认为 UPS 和 Fedex 可能有类似的问题，如果您将它们作为关键字添加到谷歌搜索中，您可以获得一些更有用的结果。

于 2009-12-18T05:38:13.993 回答
4

我同意 Jiri 的观点……您需要一种启发式算法，该算法可以快速接近可接受的解决方案，然后从那里进行改进。

我之前曾在拥有交付路由软件的公司工作，他们采用的方法是使用遗传算法来解决非常相似但规模更大的问题。如果您不熟悉该方法，请查看此处。从那个网站：

  1. [开始] 生成n条染色体的随机种群（问题的合适解决方案）
  2. 【适应度】评估种群中每条染色体x的适应度f(x)

  3. [新建种群] 重复以下步骤创建一个新种群，直到完成新种群

    【选择】根据适应度从种群中选择两条亲本染色体（适应度越好，被选中的机会越大）

    [交叉] 以交叉概率交叉父母，形成新的后代（子代）。如果没有进行交叉，后代是父母的精确副本。

    [突变] 以突变概率在每个基因座（染色体中的位置）突变新的后代。

    [接受] 将新的后代放入新的种群中

  4. [替换] 使用新生成的种群进一步运行算法
  5. 【测试】如果满足结束条件，停止，返回当前种群中的最优解
  6. [循环] 转到第 2 步

诀窍是将您的约束编码为“染色体”并编写“适应度”函数。适应度函数必须输入一个潜在解决方案的结果，并给出一个解决方案有多好的分数，或者如果它违反任何约束则将其丢弃。

正如 Jiri 所提到的，这个解决方案的优点是它提出了一个可行的，虽然可能不是最好的，但很快的答案，你让它运行的时间越长，解决方案就越好。

于 2009-12-18T11:54:58.490 回答
1

我倾向于同意罗伯特的观点。在我看来，这听起来像是他描述的遗传算法实现等进化优化技术的绝佳候选者。

我在粒子群优化 (PSO) 的某些问题上也取得了很好的成功。基本上，您可以将每个基因组视为某个多维空间中的一个粒子。粒子的坐标是您计算的参数（适应度函数）。每个粒子以随机速度随机开始。对于模拟的每次迭代，您使用当前行进向量更新每个粒子的位置，然后添加其他向量的分量，例如：到目前最好的粒子的方向、到有史以来最好的粒子的方向、到局部组的方向最好的等等...

起初实现 GA 或 PSO 似乎相当令人生畏，但我向您保证，编写一个从您尝试优化的实际问题域中抽象出算法 (GA/PSO) 的小型框架很容易。您可以随时返回 Wikipedia 了解算法的详细信息。

一旦我有了一个框架，我通常会从一个 2 参数问题开始（可能是您的问题的简化，或者图像上的 X 和 Y 位置），这样我就可以轻松地可视化和调整算法，从而获得良好的集群行为。然后我将它放大到更多维度。

我喜欢这种方法，因为它使我可以轻松地针对与实际问题陈述（如汽车和拖车）具有相当复杂和复杂部分的问题进行优化。

此外，进化技术之所以有吸引力，是因为您可以将固定部分的时间用于模拟，并在您决定停止时获得迄今为止的最佳答案。

以我的经验，你倾向于花尽可能多的时间来调整 GA 或 PSO 的参数（一旦你有一个实现），就像你编写一个硬编码的启发式解决方案一样，但好处是通常可以改变寻找解决方案的策略只需要更改参数或将定义明确的算法换成另一种实现，而不是编写完全不同的策略来从头开始启发式地解决问题。

如果您需要有关为这两种算法中的任何一种设计通用框架的指导，请给我留言。我必须指出，您也可以获得几个不错的免费 3rd 方框架。有时我喜欢自己编写代码，因为那时我了解算法的各个方面，并且知道可以在哪里调整策略。

于 2009-12-19T09:07:04.143 回答
1

一般的做法：

由于问题很小，我建议您添加汽车和拖车，直到找到可行的解决方案，而不是尝试最小化汽车和拖车。

解决：

我在具有约束的 GA 上取得的成功较少，而在具有整数变量约束的 GA 上（例如，一个位置的拖车数量）的成功率更低。约束规划可能是一种更好的方法，因为您只想为给定数量的汽车和拖车生成可行的解决方案，而不是试图最小化行驶距离。

观察：

您正在解决网络上的问题，其中最后一步可能是重新定位空拖车。

祝你好运 ！

于 2009-12-30T18:47:25.313 回答
1

局部搜索是遗传算法的替代方案。在2007 年国际时间表竞赛中，本地搜索算法（例如禁忌搜索和模拟退火）明显击败了遗传算法条目（在大约 80 名参赛者 IIRC 中，LS 获得第 1 至第 4 名，而 GA 在第 1 轨道中获得第 5 名）。

另外，看看那里的一些库，例如OptaPlanner（禁忌搜索、模拟退火、延迟验收、开源、java）、JGap（遗传算法、开源、java）、OpenTS（禁忌搜索、.. .

于 2011-01-16T16:25:35.187 回答