optimization - 将任务转换为线性规划

Question

我在组织非自动化仓库（带叉车）时遇到了这样的问题。在一天开始时，仓库的托盘架上有一些托盘，白天有一些特定数量的卡车将托盘进出口到仓库。我想尽量减少白天叉车的行驶距离和（或）尽量减少正在处理外送货物的卡车的等待时间（他们正在等待用托盘装满卡车）。

我提出了一些非常直观的算法，但如果我将它们与最直观的方法进行比较，它们并没有产生好的结果——将进口托盘放在仓库中最近的空闲货架上。我试图将这个问题转换为线性规划，但我没有成功 - 我知道如何为单个货车找到最小化的叉车路径，但是我不知道如何将它们放在一起，因为每次货车导出/导入一些托盘时，仓库状态是改变（仓库中不同的托盘布局）。我还尝试了通过系统检查每种可能性来找到最佳结果的蛮力方法，但这并没有在合理的时间内产生结果......

有没有人有一些想法（关于将问题转换为线性规划）？

Answer 1

一些想法。

听起来您可能无法将此问题转换为 LP 规范形式。回想一下，LP 的规范形式是

如果您想优化叉车的行驶距离，则 - c是操作每辆叉车的成本向量，A将是大小为#lorries x #forklifts的矩阵，其中包含您能够计算的最佳距离，并且解决方案x会将一部分工作分配给每辆叉车。

您必须根据系统约束计算出向量b，即 b[i] 可能是叉车根据其平均速度可以行驶的最大距离。

希望您可以将实数解转换为一些合理的整数解，否则您将需要使用整数线性规划，这是一个更困难的优化问题。

最后，如果在仓库中移动调色板会改变系统的成本，那么 LP 将不适用，您将不得不使用某种状态空间搜索（最佳优先、A* 或其他变体），其中该州由调色板、叉车和卡车的位置定义。