蒲 晶，譚代倫,b，郭 瀟

（西華師范大學(xué)a.數(shù)學(xué)與信息學(xué)院；b.計算方法及應(yīng)用軟件研究所，四川 南充 637000）

引 言

隨著近年來互聯(lián)網(wǎng)經(jīng)濟的高速發(fā)展，淘寶、京東等互聯(lián)網(wǎng)購物平臺使用率飛快增長，對于其背后倉儲物流系統(tǒng)的要求也越來越高。在倉儲作業(yè)中，揀貨作業(yè)則是配送中心的一個重要的環(huán)節(jié)，其作業(yè)效率研究成為近年來的重點研究課題。

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

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

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

1 倉庫布局及其路徑規(guī)劃模型

1.1 倉庫布局

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

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

圖1 倉庫布局圖

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

1.2 揀貨點及其坐標(biāo)

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

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

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

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

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

1.3 任意兩點間的距離

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

圖2 任意兩點之間的路徑

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

（1）當(dāng)這兩點在不同的行貨區(qū)時

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

經(jīng)過坐標(biāo)變換后，這兩點間的曼哈頓距離為：

（2）當(dāng)這兩點在相同的行貨區(qū)時

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

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

式（6）中，dij為相同行貨區(qū)內(nèi)兩點之間的距離。

1.4 揀貨-復(fù)核路徑規(guī)劃數(shù)學(xué)模型

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

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

則可建立如下0-1規(guī)劃模型：

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

2 小生境遺傳算法的設(shè)計

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

2.1 編碼方案與種群初始化

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

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

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

根據(jù)種群規(guī)模大小，利用不重復(fù)自然數(shù)的隨機生成函數(shù)，可生成一組符合要求的遺傳個體，構(gòu)成一個種群。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評估和區(qū)分種群個體的優(yōu)劣，是進(jìn)行遺傳選擇的依據(jù)。根據(jù)式（11）的基因編碼方案，遺傳個體的適應(yīng)度不能直接采用式（6）作為適應(yīng)度函數(shù)，而重新構(gòu)造為以下函數(shù)：

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

2.3 選擇策略

遺傳算法選擇策略的任務(wù)是按一定規(guī)則挑選出相同種群規(guī)模的適應(yīng)度較優(yōu)的個體遺傳給子代。本文采用錦標(biāo)賽選擇策略。

該策略模擬了體育比賽中的分組聯(lián)賽機制，基本思想是每次從種群中隨機選擇一定數(shù)目的個體構(gòu)成一個小組，然后從該組中選擇最優(yōu)的一個個體進(jìn)入子代種群。其具體步驟如下：

（1）設(shè)定錦標(biāo)賽策略的分組大小r（也稱為r元錦標(biāo)賽）；

（2）從種群中隨機抽取r個個體組成一個小組，在組內(nèi)選擇最優(yōu)的一個個體進(jìn)入子代種群；

（3）重復(fù)步驟（2），直到子代種群達(dá)到預(yù)定的種群規(guī)模。

2.4 交叉策略

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

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

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

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

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

2.5 基于小生境的變異策略

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

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

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

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

（4）重復(fù)步驟（2）和步驟（3），直到子代個體數(shù)達(dá)到種群規(guī)模。

2.6 小生境遺傳算法流程圖

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

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

3 仿真實驗與分析

3.1 實驗環(huán)境與初始數(shù)據(jù)

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

表1 4組揀貨單數(shù)據(jù)

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

3.2 實驗結(jié)果

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

表2 兩種算法求解4組揀貨單數(shù)據(jù)的結(jié)果

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

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

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

3.3 算法性能分析

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

采用標(biāo)準(zhǔn)遺傳算法（SGA）和小生境遺傳算法（NGA）求解表1 中4 組揀貨單時，其適應(yīng)度進(jìn)化曲線如圖5所示。

就收斂結(jié)果來看，在圖5（a）中，小生境遺傳算法相比于標(biāo)準(zhǔn)遺傳算法的優(yōu)越性較不明顯。但在圖5（d）中，當(dāng)揀貨點數(shù)量較多的情形下，適應(yīng)度值和收斂性能都明顯優(yōu)于標(biāo)準(zhǔn)遺傳算法。

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

圖5 兩種算法求解的適應(yīng)度進(jìn)化曲線

為進(jìn)一步評估和衡量本文小生境遺傳算法的性能，將標(biāo)準(zhǔn)遺傳算法（SGA）和小生境遺傳算法（NGA）各自獨立運行50次，分別統(tǒng)計兩種算法的最好值、平均值和標(biāo)準(zhǔn)差，結(jié)果見表3。

表3 兩種算法尋優(yōu)精度對比

表3 中，“最好值”是指50 次獨立運行算法程序所求得的最好近似最優(yōu)值，“平均值”、“標(biāo)準(zhǔn)差”是指這50次求得的近似最優(yōu)值的平均值和標(biāo)準(zhǔn)差。

從表3 可以看出，在4 組揀貨單中，小生境遺傳算法（NGA）獨立運行50 次所求得的最好值均比標(biāo)準(zhǔn)遺傳算法（SGA）更小，說明本文算法尋優(yōu)結(jié)果質(zhì)量更高。尤其是當(dāng)揀貨點越多時，揀貨-復(fù)核路徑規(guī)劃的優(yōu)化效果就越明顯。此外，小生境遺傳算法（NGA）獨立運行50 次的最好值的標(biāo)準(zhǔn)差也均明顯低于標(biāo)準(zhǔn)遺傳算法（SGA），這表明本文算法的穩(wěn)定性更強。

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

4 結(jié)束語

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

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