基于小生境遺傳算法的倉庫揀貨-復核路徑規劃

蒲 晶，譚代倫,b，郭 瀟

（西華師范大學a.數學與信息學院；b.計算方法及應用軟件研究所，四川 南充 637000）

引 言

隨著近年來互聯網經濟的高速發展，淘寶、京東等互聯網購物平臺使用率飛快增長，對于其背后倉儲物流系統的要求也越來越高。在倉儲作業中，揀貨作業則是配送中心的一個重要的環節，其作業效率研究成為近年來的重點研究課題。

在現代物流企業中，較大型貨物倉庫通常放置有很多組相對獨立的貨架，它們的基本布局有矩形［1-3］排列，魚骨型［4-6］排列等形式。從存放貨物的貨架層數上，可以分為只考慮一層貨架的平面型倉庫和考慮多層貨架的立體型倉庫。從對揀貨前后的復核臺設置上，可以分為無復核臺、單復核臺和多復核臺等形式。在倉庫的日常揀貨過程中，揀貨員從復核臺獲取訂單，沿著通道揀選兩側貨架上的商品，當商品揀完后再返回復核臺檢驗，形成揀貨-復核路徑。因此，如何合理地給出它們的揀貨順序，使得揀貨-復核路徑盡可能短，對提高倉庫工作效率具有重要意義。

目前國內外學者針對各類型的倉庫揀貨作業進行了大量的分析和研究，包括使用不同存儲分配策略［7］、不同的倉庫布局［8］和訂單分批［9］等方法來優化倉庫的揀貨路徑。在倉庫布局方面，孫慧［10］在雙區型倉庫下建立了揀貨車容量受限的TSP 模型，設計出一種啟發式算法對揀貨路徑進行優化處理；陳榮［11］針對多區型倉庫人工揀貨路徑問題，提出了人工魚群算法優化策略，極大地縮短了揀貨路徑的距離。在路徑規劃方面，Chen 等［12］基于訂單采摘路線不確定揀選下的多訂單揀選機制，設計了一種蟻群算法，來避免揀貨通道的擁擠；Giannikas 等［13］設計了一種動態揀貨策略，在揀貨周期中更新訂單分配和揀貨路線；Kulak 等［14］采用基于聚類的禁忌搜索算法求解最佳揀選路徑；劉建勝［15］考慮揀貨小車載重約束條件，建立多車協同揀選調度優化模型，給出了一種混合粒子群算法；孫軍艷［16］以揀貨時間最短為目標函數構建數學模型，提出并設計了動態貨位調整與人工揀貨協同作業的動態揀貨策略。

物流倉庫的揀貨-復核作業過程具有明顯的旅行商問題（TSP）特征，因此將揀貨點（含復核臺）定義為TSP頂點，構建任意兩點間的距離計算公式，從而將該問題轉化為TSP 問題建模，然后選擇小生境遺傳算法[17]進行求解，進而為提高倉庫揀貨-復核作業效率提供更有效的解決方法。

1 倉庫布局及其路徑規劃模型

1.1 倉庫布局

選取貨柜按矩形排列、單復核臺、平面型的倉庫布局形式，計算路徑長度時要考慮貨格和通道的尺寸大小，整個倉庫平面布局如圖1所示。

在圖1中，每一個正方形小格子存放一類貨物，稱為一個貨格，所有貨格的尺寸都相同。一定數量的貨格并排組成一列貨架，每一列貨架的貨格數目相同，兩列貨架背靠背形成一個貨柜。所有貨柜以矩形排列構成整個倉庫，同一行或同一列的貨柜可稱為一個貨區。貨柜之間留有等間隔的通道，用于揀貨行走，倉庫的四周也是通道。復核臺設置在倉庫的左側邊線處，領單和交貨都要到復核臺處完成。

圖1 倉庫布局圖

為便于描述和計算，現以倉庫的左下角為坐標原點建立平面坐標系，向右為x軸正方向、向上為y軸正方向。

1.2 揀貨點及其坐標

設倉庫內共有K個貨格，矩形排列為M行N列，其中每一列貨架均由T個貨格構成。貨格尺寸均為a，通道寬度均為w。

所有貨格從左下角開始，按從左到右、從下向上統一依次編號。對每一個貨格，取其面向通道的邊中點處為揀貨點。任意第i(i= 1,2,…,K)個貨格的揀貨點記為vi，它在倉庫中從下向上的行號記為im、從左向右的列號記為in，則有：

其中：im= 1,2,…,M；in= 1,2,…,N；“mod”表示求余數。

于是第i個揀貨點vi的坐標可表示為vi(xin,yim)，其坐標計算公式為：

復核臺可視為一種特殊的揀貨點，它處于最左側通道的邊線處（圖1），不考慮本身的尺寸，取其與y軸重合的邊線中點處為領單或交貨復核點，記為v0(0,y0)。

1.3 任意兩點間的距離

倉庫內的揀貨點既有貨格，也有復核臺。從圖1可見，任意兩點之間的路徑，主要受行方向上的貨區位置關系影響，可分為兩種情形：一種情形是這兩點分別在不同行貨區中，另一種情形是這兩點都在同一行貨區內，如圖2所示。

圖2 任意兩點之間的路徑

設任意兩點為vi(xin,yim)和vj(xjn,yjm)，由圖2可知，這兩點的實際距離dij需要在曼哈頓距離的基礎上予以修正，以下分兩種情形討論。

（1）當這兩點在不同的行貨區時

如 圖2 中 的 路 徑：A0B1—A0B7，A1B1—A1B7，A2B1—A2B7，分析可知，若點vi在奇數列上，可將橫坐標左移半個通道寬度；若點vj在偶數列上，可將橫坐標右移半個通道寬度，通過平移后的兩個點的橫坐標分別為x′in和x′jn，則有：

經過坐標變換后，這兩點間的曼哈頓距離為：

（2）當這兩點在相同的行貨區時

如 圖2 中 的 路 徑：A0C1—A0C8，A1C1—A1C8，A2C1—A2C8，出現繞行到貨柜背后揀貨的情況，此時只需選取其中一個點。例如選vj點，作其關于相鄰行通道中間線的向上對稱點v′j(xjn,y′jm)和向下對稱點v″j(xjn,y″jm)，通過對稱映射，就將“在相同行貨區”變換為“在不同行貨區”的情形。其中，y′jm和y″jm分別為對稱映射后的兩個點的縱坐標，其計算公式為：

接下來只需分別計算出點vi與v′j之間的距離d′ij以及點vi與v″j之間的距離d″ij，并求其最小值，即為在相同行貨區 時 點vi與vj之間的距離。由于vi與v′j和v″j分別在不同行貨區內，因此仍要按照式(3)對x坐標進行變換得x′in和x′jn，于是有：

式（6）中，dij為相同行貨區內兩點之間的距離。

1.4 揀貨-復核路徑規劃數學模型

揀貨員從復核臺領取揀貨單，出發去往各個揀貨點揀選商品，最后返回復核臺交驗貨物的過程，具有經過且只經過揀貨點一次并最終回到起點的特點，這符合旅行商問題(Travelling Salesman Problem，TSP)的基本特征，因此可將這類問題轉化為TSP問題進行建模。

將倉庫內需要經過的復核臺和揀貨點看作TSP頂點，對其進行編號即構成TSP 問題的頂點集。設某次揀貨單需要經過的復核臺和揀貨點共有S個，記為V={v0,v1,v2,...,vS} ，定義如下0-1變量：

則可建立如下0-1規劃模型：

上述模型中，xij∈{0,1}；式（7）為目標函數，表示所經過的路徑長度；式（8）和式（9）使得每一個頂點只能有一條邊進和一條邊出；式（10）和式（11）表示所經過的路徑不構成任何子回路，其中集合U 是頂點集V 的子集，| |U表示該集合所包含頂點個數，它不少于2個頂點，但不超過S+1個頂點。

2 小生境遺傳算法的設計

倉庫揀貨路徑問題屬于NP-hard 問題，現代智能啟發式算法［18-19］是求解這類問題的主要方法。遺傳算法在這類問題上已取得不錯的成果，但容易出現“早熟”現象和后期收斂速度較慢等缺點。在自然界中，每個物種都有自己特定的生存環境。在生物學范疇內，把特定環境中的角色或功能稱為小生境［20-21］。小生境在形成初期，小生境中的物種基因常常不同，缺乏一定的交流，使得物種間的基因差異得以保留。同時，又由于各個小生境中的進化方向不同，小生境間的個體差異就會不斷擴大，使得小生境間的物種基因差異進一步擴大［22］。因此，本文引入了具有進化優勢的小生境技術進行遺傳算法的設計。

2.1 編碼方案與種群初始化

根據1.4節的0-1規劃模型，倉庫內的全部揀貨點（含復核臺）都是路徑節點，其中復核臺的編號為0，其余揀貨點編號為1到K，為此采用從0開始的不重復自然數編碼方案，與這些路徑節點一一對應。若某揀貨單需要到S(S≤K)個揀貨點去揀貨，則每一個遺傳個體可表示為：

其中，pi∈{1,2,…,S};i= 1,2,…,S。

個體的第一個基因編碼固定取值為0，表示總是復核臺出發且最終再回到復核臺；其余基因編碼取值為[1,K]中的不重復自然數，表示需要經過的那些揀貨點的位置編號。

根據種群規模大小，利用不重復自然數的隨機生成函數，可生成一組符合要求的遺傳個體，構成一個種群。

2.2 適應度函數

適應度函數用于評估和區分種群個體的優劣，是進行遺傳選擇的依據。根據式（11）的基因編碼方案，遺傳個體的適應度不能直接采用式（6）作為適應度函數，而重新構造為以下函數：

上式中，d0S即為從最后一個揀貨點返回復核臺的距離。

2.3 選擇策略

遺傳算法選擇策略的任務是按一定規則挑選出相同種群規模的適應度較優的個體遺傳給子代。本文采用錦標賽選擇策略。

該策略模擬了體育比賽中的分組聯賽機制，基本思想是每次從種群中隨機選擇一定數目的個體構成一個小組，然后從該組中選擇最優的一個個體進入子代種群。其具體步驟如下：

（1）設定錦標賽策略的分組大小r（也稱為r元錦標賽）；

（2）從種群中隨機抽取r個個體組成一個小組，在組內選擇最優的一個個體進入子代種群；

（3）重復步驟（2），直到子代種群達到預定的種群規模。

2.4 交叉策略

交叉策略是把兩個父代個體的部分基因作交換而生成新的子代個體。通過交叉，種群會產生新的基因組合，個體的多樣性增加，可以獲得比父輩更優秀的個體以達到進化的目的。

算法采用基因片段交叉與修復策略，其處理步驟為：

（1）隨機產生2 個不同的正整數a和b(1 ＜a＜b)，確定出兩個父個體中介于[a,b]內的基因片段，在兩個基因片段中依序查找出相同的基因并作上標記。這里要求a＞1，即確保個體的第一個基因點（對應于復核臺）不參與交叉。

（2）將兩個父個體的基因片段按交叉概率進行交換。

（3）對交換后的每一個新個體，在基因片段外依次查找片段內未標記的基因（此為重復基因），從交換前的基因片段中按序取一個未標記基因予以替換，全部查找和替換完成后，即得到無重復基因的新子代個體。

2.5 基于小生境的變異策略

變異策略的目的是使個體基因突變，變異為新的個體，從而擴大尋優范圍，避免陷入局部最優。采用普通的變異方法往往會破壞一些優秀個體，而且兩個相似父代個體不利于產生較優的新個體，最終會出現“近親繁殖”的現象。為避免該現象的產生，在此引入一種新的變異策略，即融入小生境生存競爭機制的變異策略。其具體步驟如下：

（1）從種群中隨機選取兩個個體P1、P2；

（2）隨機產生兩個基因點a、b(1 ＜a＜b)，將個體P1、P2 中介于[a,b]內的基因片段作逆轉變異操作，得到兩個變異個體P3、P4；這里仍然要求a＞1，即第一個基因點（復核臺）始終不參與變異；

（3）設定一個閾值，求兩個父代個體P1、P2 的適應度之和f1=fp1+fp2，以及兩個子代個體P3、P4的適應度之和f1=fp3+fp4，若f1-f2的差大于給定閾值，則將兩個變異個體P3、P4 遺傳到下一代，否則將兩個父代個體P1、P2遺傳到下一代。

（4）重復步驟（2）和步驟（3），直到子代個體數達到種群規模。

2.6 小生境遺傳算法流程圖

綜合上述算法設計，本文小生境遺傳算法流程圖如圖3所示。

圖3 小生境遺傳算法流程圖

3 仿真實驗與分析

3.1 實驗環境與初始數據

本文實驗的硬件環境為Intel Corei7CPU/16GB/Win10 系統，編程環境為Matlab R2017a。倉庫內總共有K=216 個貨格，按矩形排列成的行數和列數為M=18，N=12，每一列貨架的貨格數為T=6，排列后形成3個行貨區、6個列貨區。貨格邊長a=0.8 m，揀貨通道寬度w=2 m，復核臺位置坐標為（0，11.2）。所有貨格從左下角以自然數1開始編號，按從左到右、從下到上進行編號為1,2,…,216。為驗證本文算法的有效性和實用性，揀貨單數據選取如表1所示的4組不同規模數據。

表1 4組揀貨單數據

為更好地體現算法性能，采用標準遺傳算法(Standard Genetic Algorithm,SGA)和小生境遺傳算法(Niche Genetic Algorithm,NGA)分別求解上述4 組揀貨單數據，將相關結果進行比較和分析。求解時，遺傳算法的參數設置為種群規模為100,200,300,300；交叉概率為0.9；變異概率為0.01。對揀貨單為1,2,3,4；迭代次數分別設置為100,300,400,500。

3.2 實驗結果

按圖3 算法流程編寫本文算法(NGA)程序以及參照標準遺傳算法(SGA)流程分別求解表1中的4組數據。由于求解結果較多，后面將適當給出一個揀貨單的求解結果。以下主要對求解結果進行統計和比較，見表2。

表2 兩種算法求解4組揀貨單數據的結果

從表2可以看出，隨著倉庫揀貨點規模增大，小生境遺傳算法求解結果所節約的路徑也更多，節約路徑長度的百分比也越來越大，相應地完成揀貨任務的效率也更早。因此，小生境遺傳算法在保留了優秀基因的同時，增加了種群的多樣性，提高了局部搜索能力，具有較好的尋優能力。

為便于觀察求解結果，這里以揀貨單1為例，用本文算法求解結果：復核臺→25→51→77→66→116→93→22→36→108→156→115→173→209→122→205→復核臺，揀貨路徑總長度為161.28 m，倉庫揀貨-復核的最優路徑如圖4所示。

圖4 揀貨單1的路徑示意圖

3.3 算法性能分析

為了進一步測試本文算法的性能，下面分別從求解過程中，隨機選取其中一次的適應度的進化曲線，對算法的求解精度與穩定性進行比較和分析。

采用標準遺傳算法（SGA）和小生境遺傳算法（NGA）求解表1 中4 組揀貨單時，其適應度進化曲線如圖5所示。

就收斂結果來看，在圖5（a）中，小生境遺傳算法相比于標準遺傳算法的優越性較不明顯。但在圖5（d）中，當揀貨點數量較多的情形下，適應度值和收斂性能都明顯優于標準遺傳算法。

其次，從圖5（c）中可見，標準遺傳算法在130代的時候適應值開始陷入局部最優解，沒有達到理想的搜索結果。而小生境遺傳算法在第80 代的時候開始趨于收斂。對比之下，圖5 中小生境遺傳算法的收斂速度都較標準遺傳算法快，且搜索精度更高，能較好地跳出局部最優。

圖5 兩種算法求解的適應度進化曲線

為進一步評估和衡量本文小生境遺傳算法的性能，將標準遺傳算法（SGA）和小生境遺傳算法（NGA）各自獨立運行50次，分別統計兩種算法的最好值、平均值和標準差，結果見表3。

表3 兩種算法尋優精度對比

表3 中，“最好值”是指50 次獨立運行算法程序所求得的最好近似最優值，“平均值”、“標準差”是指這50次求得的近似最優值的平均值和標準差。

從表3 可以看出，在4 組揀貨單中，小生境遺傳算法（NGA）獨立運行50 次所求得的最好值均比標準遺傳算法（SGA）更小，說明本文算法尋優結果質量更高。尤其是當揀貨點越多時，揀貨-復核路徑規劃的優化效果就越明顯。此外，小生境遺傳算法（NGA）獨立運行50 次的最好值的標準差也均明顯低于標準遺傳算法（SGA），這表明本文算法的穩定性更強。

由此可見，小生境遺傳算法不但增強算法的尋優能力，而且算法的穩定性也得到很大的提升。

4 結束語

基于矩形倉庫布局路徑規劃研究的基礎上，根據實際的揀貨運作場景，借鑒TSP 問題的建模和求解思路，建立了關于矩形倉庫問題的數學模型。采用遺傳算法和小生境技術相結合的方式，設計一種小生境遺傳算法。通過實驗數據的驗證，小生境遺傳算法在一定程度上克服了遺傳算法的早熟收斂現象，且收斂速度更快，提高算法搜索效率，能較好地跳出局部最優解。同時，求解結果能有效提升揀貨效率，對提高倉儲工作效率和倉儲作業智能化具有重要意義。

本文的數學模型及小生境遺傳算法仍然適用于數據規模更大的倉庫揀貨問題，還可以推廣應用于其他物流企業的路徑規劃問題。但是由于實際生活中物流配送中心倉庫揀貨問題的復雜性，本文的方法仍有許多不足之處，如未能考慮多人揀貨、多復核臺運作、時間窗口和載重量等因素，有待今后繼續進行研究和完善。