将任务转换为线性编程

Question

我在组织非自动化仓库(带叉车)时遇到了这样的问题.在一天开始时,仓库中的托盘货架上有一些货盘,白天有一些特定数量的货车进出仓库的货盘.而且我希望最大限度地减少白天叉车的行驶距离,并且(或)最大限度地减少处理即将卸货的卡车的等待时间(他们正在等待用托盘填充他们的货车).

我已经提出了一些非常直观的算法,但如果我将它们与最直观的方法进行比较,它们就不会产生好的效果 - 将进口托盘放到仓库中最近的免费机架上.我试图将这个问题转换为线性编程,但我没有成功 - 我知道如何为个别卡车找到最小化的叉车路径,但后来我不知道如何把它放在一起,因为每次卡车出口/进口一些托盘仓库状态是改变了(仓库中不同的托盘布局).我还尝试通过系统检查每种可能性来找到最佳结果的强力方法,但这并不是在合理的时间内产生结果......

有没有人有想法(关于将问题转换为线性编程)？

Answer 1

一些想法.

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

如果您想优化叉车的行驶距离,那么 - c是操作每个叉车的成本向量,A将是包含您能够计算的最佳距离的#lorries x #forklifts大小的矩阵,以及解决方案x将为每个叉车分配一部分工作.

您必须根据系统约束计算出矢量b,即b [i]可能是叉车根据其平均速度可以驱动的最大距离.

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

最后,如果在仓库中移动调色板会改变系统的成本,那么LP将不适用,您将不得不使用某种状态空间搜索(最佳,首先,A*或其他一些变体),其中国家的定义是调色板,叉车和货车的位置.