基于小生境遺傳算法的倉(cāng)庫(kù)揀貨-復(fù)核路徑規(guī)劃

蒲 晶，譚代倫,b，郭 瀟

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

引 言

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

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

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

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

1 倉(cāng)庫(kù)布局及其路徑規(guī)劃模型

1.1 倉(cāng)庫(kù)布局

選取貨柜按矩形排列、單復(fù)核臺(tái)、平面型的倉(cāng)庫(kù)布局形式，計(jì)算路徑長(zhǎng)度時(shí)要考慮貨格和通道的尺寸大小，整個(gè)倉(cāng)庫(kù)平面布局如圖1所示。

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

圖1 倉(cāng)庫(kù)布局圖

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

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

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

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

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

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

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

1.3 任意兩點(diǎn)間的距離

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

圖2 任意兩點(diǎn)之間的路徑

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 編碼方案與種群初始化

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

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

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

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

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

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

上式中，d0S即為從最后一個(gè)揀貨點(diǎn)返回復(fù)核臺(tái)的距離。

2.3 選擇策略

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

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

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

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

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

2.4 交叉策略

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

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

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

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

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

2.5 基于小生境的變異策略

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

（1）從種群中隨機(jī)選取兩個(gè)個(gè)體P1、P2；

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

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

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

2.6 小生境遺傳算法流程圖

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

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

3 仿真實(shí)驗(yàn)與分析

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

本文實(shí)驗(yàn)的硬件環(huán)境為Intel Corei7CPU/16GB/Win10 系統(tǒng)，編程環(huán)境為Matlab R2017a。倉(cāng)庫(kù)內(nèi)總共有K=216 個(gè)貨格，按矩形排列成的行數(shù)和列數(shù)為M=18，N=12，每一列貨架的貨格數(shù)為T=6，排列后形成3個(gè)行貨區(qū)、6個(gè)列貨區(qū)。貨格邊長(zhǎng)a=0.8 m，揀貨通道寬度w=2 m，復(fù)核臺(tái)位置坐標(biāo)為（0，11.2）。所有貨格從左下角以自然數(shù)1開(kāi)始編號(hào)，按從左到右、從下到上進(jìn)行編號(hào)為1,2,…,216。為驗(yàn)證本文算法的有效性和實(shí)用性，揀貨單數(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ù)設(shè)置為種群規(guī)模為100,200,300,300；交叉概率為0.9；變異概率為0.01。對(duì)揀貨單為1,2,3,4；迭代次數(shù)分別設(shè)置為100,300,400,500。

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

3.3 算法性能分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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