將任務轉換爲線性編程

Question

組織非自動化倉庫（使用叉車）時存在這樣的問題。在一天的開始時，倉庫中的托盤架上有一些托盤，白天有一些特定數量的貨車將托盤導入托盤/從倉庫出口托盤。我希望儘量減少叉車在白天的行駛距離，並且（或）儘量減少正在處理即將交貨的貨車的等候時間（他們正在等待用貨盤填滿貨車）。

我建議了一些非常直觀的算法，但如果將它們與最直觀的方法進行比較，它們不會產生良好的結果 - 將進口托盤放入倉庫中最近的免費機架。我試圖將這個問題轉化爲線性編程，但是我沒有成功 - 我知道如何爲單個貨車找到最小化的叉車路徑，但是我不知道如何把它放在一起，因爲每次貨車出口/進口一些貨盤倉庫狀態是更改（倉庫中不同的托盤佈局）。我也嘗試通過系統檢查每種可能性來找到最佳結果的蠻力方法，但這不會在合理的時間內產生結果...

有沒有人有一些想法（關於將問題轉換爲線性編程）？

Answer 1

一些想法。

聽起來像你可能無法將此問題轉換爲LP規範形式。回想一下，一個LP的規範形式是

如果你想優化叉車的行駛距離，然後 - ç是用於操作每個叉車成本載體，一個會大小爲＃matrix＃#forklifts的矩陣包含您可以計算的最佳距離，解決方案x將爲每臺叉車分配一部分工作量。

您必須根據系統約束找出向量b，即b [i]可以是剷車可以基於其平均速度驅動的最大距離。

希望您可以將實數解轉化爲一些合理的整數解，否則您將需要使用整數線性規劃，這是一個非常困難的優化問題。

最後，如果在倉庫中移動調色板會改變系統的成本，那麼LP將不適用，您將不得不使用某種狀態空間搜索（最好優先，A *或某些其他變體），其中狀態由調色板，叉車和貨車的位置定義。