無人倉庫，由于整個倉庫不需要人力勞動，照明系統(tǒng)可以長時間保持關閉為黑燈狀態(tài)，亦稱黑燈倉庫。無人倉庫主要依靠智能化物流系統(tǒng)的應用集成，物流系統(tǒng)可自動運轉(zhuǎn)，卸貨—存貨—提貨—分揀—貼標—裝貨等整套物流流程實現(xiàn)智能化、自動化、網(wǎng)絡化，同時，由于智能物流系統(tǒng)整個系統(tǒng)不需要人力勞動，可以避免貨物的破損、錯發(fā)等一系列人為錯誤。

起重機是無人倉庫應用最多的一種滿足搬運工藝使用的智能化物流裝備，應用在造紙、鋼鐵等眾多工業(yè)領域。鋼鐵工業(yè)中的工藝起重機通常用于謹慎且可靠地搬運鋼材等貨物。利用起重機實現(xiàn)的空中物流可以充分利用空間，無需在地面上規(guī)劃路徑。此外，起重機的工作效率高，可以直接集成到生產(chǎn)設施的整體物流中。

智能起重機系統(tǒng)是具有自動控制的操作和移動功能、可編程功能、人機交互功能和自診斷功能，能完成起重機各種任務的、具有高度靈活性的自動化機器系統(tǒng)。它具備一些與人或生物相似的智能能力，如感知能力、規(guī)劃能力、動作能力和協(xié)同能力。它是一個由機械、電力電子、液壓、信息、網(wǎng)絡等多個學科高度集成的系統(tǒng)。涉及到多剛體動力學、多變量多耦合非線性控制、大型鋼結(jié)構(gòu)動態(tài)分析、GPS、檢測、監(jiān)測和控制等多個學科。無人倉庫的工藝起重機就是一種智能起重機。

1. 起重機搬運貨物的路徑

為了提供完善的服務，開發(fā)合適的倉庫管理系統(tǒng)WMS (Warehouse Management System) 十分必要。文中介紹了一種采用基于云的倉庫管理解決方案，可以方便地對倉庫操作，包括對貨物或材料進、出庫的全過程進行控制和管理。倉庫操作包括庫存管理、分揀、質(zhì)量控制和審計，可隨時了解和掌握倉庫的實時狀態(tài)，有利于滿足不同情況下的不同需求，保持對庫存和營運資金的控制。該系統(tǒng)囊括整個物流過程，從收貨、中間商和運輸服務商，以及堆場管理的生產(chǎn)過程等?；谠茢?shù)據(jù)的科學管理，便于對每一次生產(chǎn)、每一次發(fā)貨和交貨，以及任何其他操作進行追蹤，登錄簡單容易而且可形成日志。實時而準確的庫存水平報告，有利于優(yōu)化鋼材的庫存，避免缺貨的情況發(fā)生。中央云管理系統(tǒng)可管理多個跨地區(qū)的倉庫，包括供應商管理的庫存、第三方倉庫和寄售庫存，與銷售、制造和采購訂單、運輸和收貨形成信息集成，實時更新庫存和預期庫存。倉庫里至少會配置一臺用于搬運裝卸鋼材起重機。假設倉庫有 p 個不同的區(qū)域或堆場用于存放鋼材，每個堆場可以是空的，或存放著一些某一種類型的鋼材，設計和規(guī)劃一個起重機搬運裝卸系統(tǒng)。

假設每個堆場存放鋼材的容量無限；起重機的搬運沒有延遲；起重機一次只能搬運一種鋼材，且只能搬運裝卸位于各堆場鋼材堆頂部的鋼材；每次必須對每個堆場鋼材堆頂部的鋼材進行重新定位（即重新排序）。最終目的是盡量減少起重機的搬運次數(shù)。

約束條件為起重機只能搬運各堆場鋼材堆頂部的鋼材；必須滿足發(fā)貨日期 R 和交貨日期 D；根據(jù)發(fā)貨日期R 和交貨日期 D 確定是否進行搬運裝卸，何時進行。從搬運起始堆場 o 到目的堆場 d 的搬運列表 M 可表示為

M = [(o1, d1),…,(ok, dk)]

0 ≤ oi ≤ p, 1 ≤ di ≤ p+1 （1）

式中，oi 為第 i 個搬運起始堆場；di 為第 i 個搬運目的堆場；p ∈ N，為倉庫的堆場數(shù)量；n ∈ N，為訂單的數(shù)量；Ri ∈ N, i=1,…,n，為發(fā)貨日期；Di ∈ N,i=1,…,n，為交貨日期。堆場 0 為鋼鐵廠，堆場 p+1 為用戶或運輸船。

最終目的是使起重機搬運的次數(shù)最?。创_定 M的最小值）。

圖 1 顯示了四種（件）鋼材 A、B、C、D 從鋼廠到倉庫，再從倉庫到用戶的過程和路徑，以及它們的搬運列表 M。（圖 1 a 為表示在鋼廠生產(chǎn)的順序；圖 1 e到圖 1 m 為倉庫堆場只能堆放 2 層貨物；圖 1 j 到圖 1m 為根據(jù)用戶要求將 B 和 C 取出并搬運、同時發(fā)貨給用戶的過程。）

圖 1 起重機搬運貨物路徑示例

2 基于 MIP 的起重機路徑規(guī)劃

MIP 問題即混合整數(shù)規(guī)劃問題。線性規(guī)劃問題指滿足目標函數(shù)是線性函數(shù)、約束條件是線性等式或不等式兩項的優(yōu)化問題。求最小化目標函數(shù)或最大化目標函數(shù)。若無特殊說明，文中涉及的線性規(guī)劃問題為最小化目標函數(shù)。最小化目標函數(shù)與最大化目標函數(shù)可以相互轉(zhuǎn)換，沒有實質(zhì)上的區(qū)別。

線性規(guī)劃問題包括整數(shù)規(guī)劃問題、0-1 問題和混合整數(shù)規(guī)劃問題。根據(jù)對變量的限制，線性規(guī)劃問題可以更細地區(qū)分出：

1）整數(shù)規(guī)劃問題 指變量為整數(shù)的線性規(guī)劃問題。該問題將連續(xù)的線性規(guī)劃跳轉(zhuǎn)到離散的整數(shù)規(guī)劃。求解整數(shù)規(guī)劃的難度比求解線性規(guī)劃的難度更大，當問題的規(guī)模較大時更為明顯。

2）0-1 規(guī)劃問題 指變量只能取值 0 或 1 的線性規(guī)劃問題，是整數(shù)規(guī)劃中特殊的一種。

3）混合整數(shù)規(guī)劃問題 指所有變量中有些變量可以取值連續(xù)，部分變量只能取整數(shù)值的線性規(guī)劃問題。根據(jù)定義，混合整數(shù)規(guī)劃問題可以概括出其一般形式

(P) min c T x

s.t. Ax ≥ b （2）

xj , integer j ∈ I

除少數(shù)整數(shù)規(guī)劃可以用線性規(guī)劃的單純形法直接求解外，一般整數(shù)規(guī)劃必需尋找新的求解方法。全整數(shù)規(guī)劃的分枝定界方法可以用于求解混合整數(shù)規(guī)劃問題和0-1 規(guī)劃問題。分支定界法（Branch and bound）是一種求解整數(shù)規(guī)劃問題的最常用算法，這是一種在問題的解空間樹上搜索與迭代進行求解的方法，選擇不同的分支變量和子問題進行分支。與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小耗費優(yōu)先的方法搜索解空間樹，并且，每一個活結(jié)點只有一次機會成為擴展結(jié)點。它不但可以求解純整數(shù)規(guī)劃，還可以求解混合整數(shù)規(guī)劃問題。

分支定界法步驟：1) 創(chuàng)建隊列 Q；2) 將根節(jié)點推入Q；3) 當 Q 不為 0 時，h ←從 Q 中取出一個節(jié)點，即某個堆場中空的位置；4) i 將貨物放置到下一個節(jié)點 h；5)i 都可以被堆放到每一個堆場 s；6) h‘ ←節(jié)點 μ 的副本；7) 將貨物 i 堆垛在堆場 s 的節(jié)點 h‘；8) 從堆有 h‘ 的堆場的頂部開始搬運進行交貨；9) 如果 h‘ 是一個葉節(jié)點，即沒有子節(jié)點的節(jié)點；10) 檢查是否 h‘ 有一個更好的解決方案；11) 把節(jié)點 h‘ 推入 Q。

通常，把全部可行解空間反復地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題），稱為定界。分枝定界法的主要思路為在每次分枝后，界限超出已知可行解集目標值的子集不再進一步分枝（許多子集可不予考慮，稱為剪枝）。將倉庫中的堆場區(qū)域等價于子集或分枝，將各堆場中的區(qū)域等價于分枝中的解集，就可以采用分支定界法對倉庫規(guī)劃問題進行求解優(yōu)化。這也是一個混合整數(shù)規(guī)劃 MIP 問題。采用分支定界算法確定解決方案。當某個訂單的貨物要發(fā)貨或更換堆場存放時，要先檢查所有堆場區(qū)域，選擇哪個堆場可以放置，并為它們分別確定一個備用堆場（創(chuàng)建一個分枝），以防當該訂單的貨物從堆場貨物頂部取出交付時，沒有備用堆場（分枝）暫存貨物。

離散事件仿真是用計算機對離散事件系統(tǒng)進行仿真實驗的方法，是一種在狀態(tài)變化的系統(tǒng)中使用的仿真方法，其運行成本低。每次仿真都與隨機性有關，每件貨物堆放的堆場均是從候選堆場列表中隨機選擇的。不同的運行產(chǎn)生不同的解決方案，需要大量搬運仿真才能獲得良好的結(jié)果，可以使用試探法對幾種堆垛策略進行測試，最后才能選擇出最優(yōu)的運行方案。

仿真過程為使用公式描述問題，創(chuàng)建模型，再讀取一個案例實例對模型進行修正，然后將它發(fā)送到解算器。仿真策略為采用啟發(fā)法為一種貨物選擇一個堆場，貨物到達時或把一件貨物從堆場頂部搬運到另一個貨位的下部時，要重新排序。交貨優(yōu)先于堆場發(fā)貨，同步發(fā)貨是通過反推交貨日期來實現(xiàn)的。同步交貨從堆場頂部到底部逐步進行。

定位啟發(fā)式過程為放置貨物時，根據(jù)某些規(guī)則為每個位置即堆場分配一個值；再根據(jù)最優(yōu)分類構(gòu)建一個候選貨位列表，仿真過程為使用公式描述問題，創(chuàng)建模型，再讀取一個案例實例對模型進行修正，然后將它發(fā)送到解算器。仿真策略是采用啟發(fā)法為一種貨物選擇一個堆場，貨物到達時或?qū)⒁患浳飶亩褕鲰敳堪徇\到另一個貨位的下部時，要重新排序。交貨優(yōu)先于堆場發(fā)貨，同步發(fā)貨是通過反推交貨日期來實現(xiàn)的。同步交貨從堆場頂部到底部逐步進行。

定位啟發(fā)式過程為放置貨物時，根據(jù)某些規(guī)則為每個位置即堆場分配一個值；再根據(jù)最優(yōu)分類構(gòu)建一個候選貨位列表，但這取決于采用哪一種的啟發(fā)法；從這個列表中，隨機選擇一個來堆放貨物。如圖 2 所示，要將堆場 1 和堆場 2 中的 B 和 E 取出交貨，采用以下表 1 中表示的兩種搬運規(guī)劃，可比較它們的搬運次數(shù)。

圖 2 搬運規(guī)劃對比示例圖

表 1 搬運規(guī)劃對比

3. 路徑優(yōu)化

不同的貨物在出入庫時，可遵循不同的出入庫原則，圖 3 顯示了“后入先出”、“先入先出”和“雙端隊列”的三種出入庫原則?？梢圆捎谩办`活性優(yōu)化”啟發(fā)法來對搬運活動進行規(guī)劃定位。定義貨位的靈活性為可以堆放的具有不同交貨日期的貨物的最大數(shù)量，且不能出現(xiàn)反向重復搬運。故為一個貨物選擇候選堆場應滿足以下條件：①最大限度地提高靈活性，不能出現(xiàn)反向重復搬運；②如果反向重復搬運是不可避免的，應盡量減少靈活性。采用基于仿真優(yōu)化的啟發(fā)法，運行N 次獨立的仿真模擬，選擇起重機搬運次數(shù)最少的那個方案。進行每一個N 次仿真時，對于每個貨物，根據(jù)所選的啟發(fā)法來選擇堆場，并繼續(xù)進行貨物的發(fā)貨和交貨，直到完成所有貨物的交貨，就確定了需要搬運的次數(shù)以及相應的搬運列表。

由于許多實際情況與仿真條件有差異，影響了仿真的結(jié)果，相關影響因素包括：

1）實際的堆場與建模的條件不同，如雙端隊列（見圖 4），即一個端點允許堆入和搬出，另一個端點只允許堆入。

2）起重機的搬運活動有限的（見圖 5），因此，從給定位置可以到達的堆場數(shù)量是有限的。即一個端點允許堆入和搬出，另一個端點只允許搬出。

3）貨物在某些堆場位置限制了起重機的搬運活動，即：當貨物堆放在某一位置后，搬運活動的路徑為動態(tài)變化的，此時就要對各種動態(tài)狀態(tài)進行對比優(yōu)化，以期獲得最優(yōu)的搬運方案。

4）如果起重機的搬運效率低，會導致搬運嚴重延遲，立即交貨的設想無法實現(xiàn)；

5）其他影響因素包括：裝車 / 船耗費的最少時間要求；貨物在車 / 船到達前可能需要在貨場重新定位；目標為裝車 / 船的搬運次數(shù)最少；由于某些因素影響，可能同時要搬運多件貨物等。

圖 3 出入庫原則圖示

圖 4 雙端隊列

圖 5 受限的搬運

4. 結(jié)論

1）決定或改變搬運路徑中的某一步，可能對后續(xù)的搬運過程造成不同影響；

2）應基于仿真進行路徑優(yōu)化；

3）可以采用不同的方法解決路徑規(guī)劃問題；

4）做出決定時，動態(tài)路徑的配置可能發(fā)生變化；

5）盡量采用形式化問題描述的語言建模。通過改進和應用倉庫智能起重機路徑規(guī)劃，能有效地提高倉庫的運營效率，可更好地滿足不同情況的需求。