基于改進的鄰域搜索算法對立庫貨位分配優(yōu)化的研究

王毅，王浩，李翀，郭榮坤，楊媛媛，楊華

（1 國網(wǎng)電力河北省分公司， 石家莊 050000； 2 武漢輕工大學 數(shù)學與計算機科學學院， 武漢 430023）

自動化立體倉庫具有存取自動化和操作簡便等特點，符合當前數(shù)字化技術發(fā)展需求［1］.目前，在倉庫操作智能化、無人化的立庫貨位分配應用研究中，已經(jīng)產(chǎn)生了大量研究成果［2］.越來越多企業(yè)采用數(shù)字孿生技術，利用該技術可以實時映射出物理實體的真實狀態(tài)［3］，構建虛擬立庫，對立庫運行情況進行實時監(jiān)控.本文研究的主要內容為：在立庫貨位調動前得出貨位分配方案預案，將方案預案提供給堆垛機進行調度，完成貨位優(yōu)化分配.

自動化立庫研究中，貨位分配效率是影響系統(tǒng)整體性能與工業(yè)生產(chǎn)效率的一個關鍵因素.李鵬飛等以出入庫效率和貨架穩(wěn)定性為優(yōu)化因素，建立相應的貨位優(yōu)化模型，設計病毒協(xié)同遺傳算法對模型進行求解［4］.李敬波等從提升貨品出入效率和貨架穩(wěn)定性與貨品的擺放為優(yōu)化因素建立數(shù)學模型，利用遺傳算法對模型進行求解［5］.徐偉華等利用遺傳算法對密集型自動化立體倉庫貨位進行優(yōu)化［6］.劉凱文等針對入庫作業(yè)操作最大完工時間與堆垛機能耗之間關系構建相應的懲罰函數(shù)，并應用于灰狼算法，實現(xiàn)帶有截止時間約束的自動化立體倉庫堆垛機能耗調度優(yōu)化算法［7］.董海等從運行時間、堆垛機利用率均衡化、貨架穩(wěn)定性、對產(chǎn)品質量影響程度四個角度出發(fā)構建多目標調度優(yōu)化模型，提出一種基于權值策略及非均勻概率分布的情緒化細菌覓食算法對立庫進行集成優(yōu)化［8］.彭小利等針對多品種智能倉庫的貨位分配問題，建立了考慮多規(guī)則約束的多目標智能倉庫貨位分配模型，提出了一種模型求解的改進遺傳算法［9］.焦玉玲等以資產(chǎn)出入庫作業(yè)時間、貨架整體等效重心和關聯(lián)產(chǎn)品間相對聚集程度為目標函數(shù)，構建了多目標貨位分配優(yōu)化數(shù)學模型［10］.

上述文獻對自動化立體倉庫貨位分配的研究較為豐富，考慮了不同分配原則，設計了不同優(yōu)化算法.但存在缺少分配后貨位整體分布的優(yōu)化，算法收斂速度較慢等不足，根據(jù)現(xiàn)存的問題對貨位不同狀態(tài)進行編碼，以提高貨位分配效率為目標，設計貨位分配優(yōu)化模型，并利用Optimizing Tabu搜索算法對模型進行求解［11］.在Tabu搜索算法中，對鄰域搜索過程融入概率分配機制，提升算法的尋優(yōu)能力，對比實驗分析結果表明，改進后的Optimizing Tabu搜索算法在保證最優(yōu)解的前提下能夠顯著提升算法的收斂速度.

1 立庫貨位分配優(yōu)化問題

自動化立體倉庫［12］包括高層貨架、堆垛機、傳送帶等.資產(chǎn)以托盤為單位存儲在高層貨架，傳送帶連接工作區(qū)與倉儲區(qū)，輸送需裝卸的資產(chǎn)；資產(chǎn)的上架存儲與分揀，均由堆垛機完成，堆垛機在收到指令后，對資產(chǎn)進行操作.

為便于問題研究，進行如下設定：（1）立庫每排貨架僅一個資產(chǎn)入口，資產(chǎn)出口與資產(chǎn)檢測出入口；（2）貨位只存儲同一種商品，其數(shù)量、體積有限；（3）不考慮傳送帶與堆垛機交接時間以及取、放資產(chǎn)操作時間；（4）資產(chǎn)存入貨架為入庫，資產(chǎn)從貨架的出口運出為出庫.

2 貨位優(yōu)選模型構建與算法設計

2.1 問題模型構建

模型所涉及的參數(shù)及其定義如表1所示.

表1 模型參數(shù)定義Tab.1 Definition of model parameters

（1） 貨位狀態(tài)隨著堆垛機對資產(chǎn)的不同作用而不斷轉變，轉變規(guī)則為：R→S；S→R；H→C；C→H.即原本是入庫的貨位，在資產(chǎn)進入該貨位后，貨位變?yōu)樗蜋z貨位，該資產(chǎn)的下一步操作為送檢操作，完成送檢操作即將資產(chǎn)送至檢測位置，貨位又變?yōu)槿霂熵浳坏却Y產(chǎn)送入；原本是接受檢定完成資產(chǎn)回庫的貨位，在資產(chǎn)進入該貨位后，貨位變?yōu)槌鰩熵浳?，該資產(chǎn)的下一步操作為出庫操作，完成出庫操作即將資產(chǎn)送至出貨口位置，貨位又變?yōu)闄z定完成資產(chǎn)回庫的貨位等待資產(chǎn)送入.（本文將立庫中的每排貨架分上下兩個部分，上層貨位為入庫與送檢貨位，下層為檢定完回庫與出庫.每一層貨位的轉換是獨立不影響資產(chǎn)的流動.當上層的送檢貨位將資產(chǎn)送出，會被下層的回庫貨位接受）.

堆垛機可以同時沿水平和豎直方向移動，每次堆垛機移動的時間為堆垛機水平方向的時間與豎直方向移動的時間的最大值，且不同狀態(tài)的貨位使得堆垛機移動的最終位置不同，每種操作分別是：1）入庫操作：堆垛機當前位置→入口→指定貨位；2）送檢操作：堆垛機當前位置→指定貨位→檢測入口；3）回庫操作：堆垛機當前位置→檢測出口→指定貨位；4）出庫操作：堆垛機當前位置→指定貨位→出庫位置.

設（ms，ms）為堆垛機當前坐標，（ne，ne）為堆垛機目標位置坐標.Ts→e為堆垛機當前位置到目標位置的時間Lx，Ly，分別是貨架中貨位水平與豎直的距離（ms，ms）∈｛（xstacker，ystacker），（xenter，yenter），（xexport，yexport），（xtest，ytest）｝，（ne，ne）∈｛（xi，yi）｝；

堆垛機每次移動的時間如式（1）：

完成入庫，送檢，回庫，出庫操作的時間分別如式（2）、式（3）、式（4）、式（5）所示，Dstaker為堆垛機當前位置.

（2） 自動化立體倉庫中有多臺堆垛機并行工作，降低所有堆垛機的最大工作時間作為優(yōu)化目標（j為每臺堆垛機的序號）：

（3） 整體上也要降低所有堆垛機工作的時間總和：

（4） 根據(jù)（6）（7）目標分析，優(yōu)化立庫工作主要任務是減少立庫任務的完成時間，以此為目標，將降低所有堆垛機工作的時間總和作為優(yōu)化目標的一定約束.本文取T1Ttotal的比例為1000∶1（n取1000，為了將T1作為第一優(yōu)化目標）.

（5） 約束條件：

2.2 Tabu搜索算法描述

Tabu搜索算法［13］通過對人類搜索信息的記憶特征進行模擬，能夠有效降低算法陷入局部最優(yōu)的可能性.將Optimizing Tabu搜索算法流程與原算法相同，如圖1所示.

圖1 Tabu搜索算法流程圖Fig.1 Tabu search flow chart

Tabu搜索算法的步驟如下：

（1） 設計算法的初始參數(shù)并隨機產(chǎn)生相應的初始解，將禁忌表置為空；

（2） 判斷產(chǎn)生解是否滿足算法終止條件？如果滿足，算法運行結束否則執(zhí)行一下步驟；

（3） 對當前解進行鄰域搜索產(chǎn)生鄰域解，在新產(chǎn)生的鄰域解中確定候選解；

（4） 判斷確定候選解是否滿足特赦要求？滿足則使用候選解替換當前解成為新的當前解，并將候選解寫入禁忌表中執(zhí)行步驟（2）；否則執(zhí)行下列步驟；

（5） 判斷候選解是否處于禁忌狀態(tài)，在選擇候選解時選擇處于非禁忌狀態(tài)的最優(yōu)解作為新的當前解，并且將新的當前解更新進入禁忌表中；

（6） 執(zhí)行步驟（2）.

2.3 Optimizing Tabu搜索算法的求解

利用傳統(tǒng)的Tabu搜索算法解決立庫中貨位選擇的問題，搜索的最終結果在一定程度上依賴于初始解的選取.雖然Tabu搜索算法的特性在一定程度上可以避免陷入局部最優(yōu)的情況［14］，但是Tabu搜索算法在執(zhí)行時，需要迭代次數(shù)足夠充分才可以達到最優(yōu)，因此會耗用大量時間，本文針對此問題，在鄰域搜索過程中對不同的貨位設置不同的搜索概率值.對能使解更優(yōu)的貨位給予一個大的搜索概率，反之則給予一個相對較小的搜索概率值，從而在整體上提高了鄰域搜索過程中貨位選擇的效率，顯著地提升了算法的尋優(yōu)性能.

2.3.1 初始貨位分布以及解的表達方式

每排貨架上初始貨位分布遵循如下準則：本文立庫12排貨架每排貨架有26層，1-13層為R狀態(tài)與S狀態(tài)；14-26層為H狀態(tài)與C狀態(tài).本文初始貨位分布采用隨機策略，1-13層中每個貨位分配給R或S的概率均為50%，14-26層同理.這樣分配可以使每種貨位均有足夠的數(shù)量在后續(xù)的仿真中能夠表現(xiàn)出一定規(guī)律.貨位狀態(tài)有四種，形態(tài)分為兩種：滿貨位（有資產(chǎn)存放的貨位S，C兩種狀態(tài)）與空貨位（沒有資產(chǎn)存放的貨位R，H兩種狀態(tài)）.該類貨位都具有一個入庫的時間標簽，本文中的時間標簽，時間標簽為1-30越少入庫時間越靠前，且生成初始貨位分布時對該類貨位隨機生成一個入庫時間標簽.

根據(jù)本文限定場景的情況，貨位的選擇包括已經(jīng)被選擇的貨位以及符合條件但是未被選中的貨位，因此算法鄰域搜索過程中需要對這兩部分進行搜索得出最優(yōu)解.

本文初始解包含兩方面，第一方面是選擇了哪些貨位，以及貨位選擇的分布情況，第二方面是貨位的順序.貨位的順序指堆垛機操作資產(chǎn)的先后順序，確定立庫工作的時間，根據(jù)實時情況的貨位選擇的初始解遵循如下準則：R與H型貨位，隨機在該類型貨位中選擇.S與C型貨位根據(jù)入庫時間的先后排序，選擇時間標簽小的貨位.

2.3.2 結合線性概率分配機制的鄰域搜索過程

一個合理的鄰域搜索方式有助于算法快速地搜索得到更優(yōu)的解［13］，鄰域搜索也是整個Tabu搜索算法過程中最為重要的部分，決定著算法的優(yōu)劣性，本文針對傳統(tǒng)鄰域搜索策略做出一定改進，經(jīng)過實驗驗證能提升搜索效率.

針對本文實際情況，將搜索分為外部搜索與內部搜索兩種情況.外部搜索：將符合條件但未被選中的貨位與已被選中的貨位進行逐個交換，挑出貨位選擇的最優(yōu)方案.內部搜索：在已經(jīng)確定選擇的貨位中不斷交換，在交換中尋得最優(yōu)路徑使運作時間達到最短，在進行外部搜索過程中給每一個貨位一個搜索概率且按照不同位置進行概率分配.貨位搜索概率分布遵循按貨位坐標與對應的傳送口位置坐標的遠近進行計算，每個貨位被搜索到的概率P(x，y)如下式：（xtarget， ytarge）t當前貨位對應出入口位置的坐標，貨架貨位數(shù)量為26 × 26.

搜索概率的計算方式為，貨架行列數(shù)的最大值+1減去貨位坐標與目標位置橫（縱）坐標差的最大值，除以貨架行列數(shù)最大值，將商記為概率P(x，y)，貨架行列數(shù)的最大值+1可以提高在目標位置搜索附近搜索的概率）：

2.3.3 禁忌表與禁忌對象以及候選解的確定

本文將貨位的交換操作作為禁忌對象，在算法的若干次迭代中禁止交換過的貨位再次進行交換.禁忌表長度：禁忌表長度是禁忌對象在不考慮特赦準則的情況下不允許被選取的最大次數(shù)，禁忌長度的選取與解決的問題和經(jīng)驗有關，本文選取禁忌表的長度為20，本文根據(jù)實際情況從鄰域中搜索出1000個解，取最優(yōu)的10個解，作為候選解集，在候選解的集合中選取最優(yōu)的候選解.

2.3.4 特赦條件

在Tabu搜索算法過程中，會出現(xiàn)選取的候選解全部被禁忌的情況［15］，特赦條件是指當所有候選解中選擇最優(yōu)的解，且必須優(yōu)于當前解，則可以忽略禁忌準則，解禁該候選解，并替換當前解更新禁忌表.

為了能夠更進一步避免算法陷入局部最優(yōu)，在候選解替換當前解時遵循如下準則（設CS為當前解，OS為候選解中準備替換CS的解）：當OS優(yōu)于CS的1%時正常替換，否則對是否替換加入一個較小的概率，本文中如果OS優(yōu)于CS小于1%，存在1%的可能忽略替換操作繼續(xù)運行算法［16］.

3 仿真數(shù)據(jù)與實驗仿真

3.1 仿真數(shù)據(jù)

本文以河北檢定中心自動化立體倉庫為例，立庫中存在12排貨架，每排貨架有52列26層，六臺堆垛機并行工作，每臺堆垛機均固定操作指定的兩排貨架，堆垛機每次水平搬運兩垛相同類型資產(chǎn)，因此根據(jù)這一特性可以將貨架原本的52列貨位在編碼時轉換成26列進行編碼，編碼時每個貨架對應貨位數(shù)量：26 × 26.堆垛機水平對應兩個貨架為一個整體，需要操作某種貨位時根據(jù)每個堆垛機操作該類型貨位狀態(tài)數(shù)量的比例來進行分配，每排貨架中坐標（1，1）距入貨口最近；坐標（1，13）距離檢測出入口最近；坐標（26，13）距離出貨口最近，堆垛機速度與貨位規(guī)格參數(shù)見表2.

表2 相關參數(shù)設定Tab.2 Setting of relevant parameters

使用c語言實現(xiàn)貨位分配優(yōu)化算法并進行實驗仿真，已知初始貨位分布，模擬設定需求下的貨位分配，已知程序編碼中單個堆垛機對應兩排貨架共1352個貨位，整個立庫共有8112個貨位，每排貨架中的編碼貨位為676個，對以下情況進行實驗：某時刻需要對立庫的貨位進行分配，需要分配相同數(shù)量的四類貨位數(shù)量，每類貨位數(shù)量需求為720個.由于在生成初始貨位時，每種類型貨位生成的概率均為50%，平均每個貨架每種貨位的分配數(shù)量約為60個，隨機選取一個貨架分析相關規(guī)律.

3.2 實驗結果與分析

3.2.1 對貨位分配后結果的分析

通過大量的實驗仿真，得出解的貨位分布如圖2.（從左到右依次是初始貨位分布，初始解的分布，優(yōu)化后解的分布，改進后優(yōu)化解的分布.）

圖2 貨位分布Fig.2 Location distribution

經(jīng)過對實驗結果的分析，改進前后解在分布上的表現(xiàn)接近完全相同，說明兩種搜索方式均可以達到相同效果，因此本文接下來將會對改進前后的搜索方式在算法中的迭代效果進行對比，以及對程序收斂性的影響進行分析.

對比初始解的分布與優(yōu)化后解的分布，入庫資產(chǎn)貨位的選擇整體上全部集中在入貨口的位置，回庫貨位的選擇也是整體上集中于回庫口的位置，分析可知，由于這兩類貨位屬于空貨位是不受入庫時間所約束，因此整體上都較為靠近與之關聯(lián)的庫位.

由于送檢與出庫貨位分布優(yōu)化后依然呈現(xiàn)得十分散亂，因此隨機挑選部分入庫貨位與送檢貨位的入庫時間進行分析，入庫時間信息如表3所示.

表3 部分貨位入庫時間信息Tab.3 Storage time information of some storage locations

觀察送檢貨位與出庫貨位的選擇中部分散亂貨位的入庫時間，分布結果十分散亂，但是入庫時間均十分靠前，符合算法先考慮時間，再考慮距離的原則，符合貨位選取的目標且可以有效地避免貨位長期在立庫中堆積.

3.2.2 迭代次數(shù)與立庫工作時分析

每種搜索方式的迭代次數(shù)與立庫執(zhí)行時間如表4所示，t1表示改進前算法的最優(yōu)解，t2表示改進后算法的最優(yōu)解，即公式（8）的目標函數(shù)值，該函數(shù)值是將最大工作時間與每臺堆垛機工作時間的和按一定比例結合，因此實際時間會略大.

表4 迭代次數(shù)與立庫工作時間表Tab.4 Number of iterations and work schedule of Warehouse Establishment

從表4得出：改進后的Tabu搜索算法與原算法相比，在迭代前期最優(yōu)解優(yōu)化概率明顯具有優(yōu)勢且收斂速度也明顯快于改進前，將改進后的Tabu搜索算法與原算法收斂效果進行對比如圖3所示.

圖3 迭代次數(shù)與時間分析圖Fig.3 Analysis of iteration times and time

由圖3可得：改進后的Tabu搜索算法收斂效果明顯優(yōu)于原算法，改進后的Tabu搜索算法可以減少迭代次數(shù)達到相同甚至更優(yōu)的解，提升了算法的效率，在一定程度上減弱了Tabu搜索算法對初始解的依賴程度.

3.2.4 算法性能分析

為了對算法的性能進行分析，只研究一臺堆垛機的生產(chǎn)流程，選取貨位總數(shù)為80，四種貨位選取概率相同.選取單一貨架貨位分布如圖4.（從左到右依次是初始貨位分布，初始解的分布，改進后優(yōu)化解的分布.）

圖4 貨位分布Fig.4 Location distribution

為驗證算法的優(yōu)越性，計算每次貨位規(guī)劃的迭代次數(shù).通過優(yōu)化貨位的分配，優(yōu)化前后結果如表5所示，time1，time2為程序運行時間單位均為/s.

表5 收斂次數(shù)與工作時間表Tab.5 Convergence times and working time

由表5可得，算法在相同的收斂次數(shù)下，本文算法收斂提升接近60%.算法核心是提升搜索過程中的尋優(yōu)能力，減少需要收斂的次數(shù)，且計算能控制在1 min左右，能夠滿足現(xiàn)場實時性的要求，與文獻［17］中采用遺傳算法進行優(yōu)化相比，在優(yōu)化效率上具有更加優(yōu)越的表現(xiàn).

4 總結

經(jīng)過對實驗結果的分析，本文結論如下：

（1） 結合概率機制后的Tabu搜索算法，相比傳統(tǒng)的Tabu搜索算法，具有更快的收斂速度，能夠避免傳統(tǒng)方式陷入局部最優(yōu)解的缺陷，從而提高了自動化立庫中貨位優(yōu)化的水平.

（2） 改進Tabu搜索算法優(yōu)化后，提高了自動化立體倉庫貨位搬運效率.能夠減少資產(chǎn)流動過程中所消耗的時間.

綜上所述，通過加入概率機制的Tabu搜索算法能夠優(yōu)化自動化立體倉庫的貨位分配，提高資產(chǎn)流動效率，從而減少資產(chǎn)的堆積，提高生產(chǎn)效率.