秦 馨，趙劍道，任 楠，李佳順，馬洪澤

（1.北京機(jī)械工業(yè)自動化研究所，北京 100120；2.北自所（北京）科技發(fā)展有限公司，北京 100120）

0 引言

隨著電商的飛速發(fā)展、物流效率的極大提升，市場需求開始呈現(xiàn)出多樣化的趨勢，銷售訂單也逐漸向零散化進(jìn)行轉(zhuǎn)變。為了適應(yīng)市場變化，更好的提升企業(yè)競爭力，很多企業(yè)開始通過建立自動化工廠來實(shí)現(xiàn)倉儲管理、備料配送等功能，物流配送向自動化、智能化發(fā)展，從而降低物流成本、提高倉儲效率。但是由于訂單的隨機(jī)性、差異性比較大，分揀作業(yè)依舊以人工作業(yè)為主，機(jī)械化程度比較低，嚴(yán)重影響著物流配送效率的提升，因此如何提高分揀作業(yè)的效率，成為了自動化物流管理的重要研究方向。經(jīng)過眾多學(xué)者的研究，選擇一種合理且有效的訂單分批策略，在優(yōu)化分揀作業(yè)流程、減少作業(yè)處理時間方面起著關(guān)鍵的作用。

1 訂單分批

分揀作業(yè)是指庫房在接收到一定量的訂單后，按照訂單內(nèi)容將每個訂單所需的物料分揀至訂單對應(yīng)的載具中。訂單分批則是將大量的訂單按照一定的策略劃分至不同的批次，每個批次中包含一定量的訂單，然后同一個批次中的訂單將所需物料合并來同時進(jìn)行分揀。因此每批次中不同訂單需要相同物料時可以一次性揀出，不必重復(fù)分揀，能夠減少揀選時的行走距離，有效的提高分揀效率。

1990年，Kenneth最早提出了訂單分批的概念。傳統(tǒng)的訂單分批策略主要是基于個人經(jīng)驗(yàn)來進(jìn)行選擇，一般是基于時間順序來進(jìn)行分批揀選，這種方式優(yōu)化效果較為有限。隨后，大量學(xué)者在這個方面進(jìn)行了深入的研究探討，先后提出了基于訂單相似性的各種啟發(fā)式算法，包括種子算法、節(jié)約算法、包絡(luò)算法和聚類算法等。但是隨著訂單數(shù)目的增加，算法受初始訂單影響較大，優(yōu)化效果不穩(wěn)定，而且這些研究大部分都是基于“人到貨”的模式，對于當(dāng)前更為流行的“貨到人”場景適配性不足，因此對“貨到人”應(yīng)用場景的訂單分批策略值得進(jìn)一步探索。

本文基于“貨到人”的實(shí)際應(yīng)用場景，采用基于遺傳算法的訂單分批策略，以最小化貨物搬運(yùn)次數(shù)為目標(biāo)構(gòu)建了訂單分批問題的數(shù)學(xué)模型，通過設(shè)定初始種群、選擇、交叉、變異等一系列遺傳操作設(shè)計(jì)得到了有效的分批結(jié)果。

2 模型與假設(shè)

在“貨到人”的模式下，人員不需要在貨架間行走，而是在固定的揀選工位進(jìn)行揀選，貨物則由輸送設(shè)備從庫房送到揀選臺，因?yàn)楝F(xiàn)實(shí)工作中每個揀貨員的揀選速度和每種物料的揀選時間都無法控制，因此所有訂單的揀選時間只與貨物的運(yùn)輸距離相關(guān)。由于貨物隨機(jī)存儲在貨架上，不同儲位到揀選工位的距離基本相等，則總的貨物的搬運(yùn)距離基本和貨物的搬運(yùn)次數(shù)線性相關(guān)。因此，本文訂單分批的總目標(biāo)為，訂單分批后進(jìn)行揀選作業(yè)時總的搬運(yùn)貨物次數(shù)最少。根據(jù)實(shí)際工程應(yīng)用場景，有以下約束條件：每個訂單中最少包含一種貨物；每個訂單不允許被分割，也不允許重復(fù)分配；每個揀選工位每批可揀選訂單數(shù)固定；每批訂單只能在一個工位進(jìn)行揀選；不存在缺貨情況。

假設(shè)庫房中共有M種物料，現(xiàn)有N個訂單Xi（i=1，2，…，n）需要進(jìn)行揀選，每批分揀訂單數(shù)為C，共可分為T批，總的搬運(yùn)次數(shù)為L，第j批的搬運(yùn)次數(shù)為Lj（即第j批中包含的訂單合并后所有物料的搬運(yùn)次數(shù)），xij表示訂單Xi的分批結(jié)果，若xij為1則該訂單分配到第j批中。綜上，該訂單分批問題建立的數(shù)學(xué)模型為：

目標(biāo)函數(shù)：

約束條件：

3 算法

遺傳算法（Genetic Algorithm）是一種隨機(jī)搜索算法，是通過對基于達(dá)爾文生物進(jìn)化理論與遺傳學(xué)機(jī)理的自然選擇和生物進(jìn)化過程進(jìn)行模擬搜索得到最優(yōu)解的方法。已經(jīng)大量應(yīng)用于函數(shù)優(yōu)化、圖像處理、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)和組合優(yōu)化等不同的領(lǐng)域中。不同于傳統(tǒng)的搜索算法，遺傳算法是一種基于概率進(jìn)行搜索的尋優(yōu)方式，它不需要提前確定搜索規(guī)則，可以自適應(yīng)的調(diào)整搜索方向，實(shí)現(xiàn)自動獲取搜索空間并進(jìn)行優(yōu)化指導(dǎo)。

本文采用的遺傳算法從待解決問題隨機(jī)生成的部分解集開始，這個解集包含一定數(shù)目的個體，這些個體一般采用一串?dāng)?shù)據(jù)或者數(shù)組來表示解的編碼，稱之為染色體。然后利用適應(yīng)度函數(shù)來衡量這些染色體的優(yōu)劣，并以此為依據(jù)借助遺傳算子選擇初始種群中的部分染色體，并進(jìn)行交叉和變異操作，從而形成新的種群。根據(jù)優(yōu)勝略汰的進(jìn)化原理不停的進(jìn)行迭代，這種進(jìn)化過程將在若干代以后使得種群中染色體的適應(yīng)度值逐漸增大，即算法將收斂于表現(xiàn)最出色的染色體，這就是我們所尋求的最優(yōu)解。因此，遺傳算法的主要內(nèi)容包括：初始編碼設(shè)計(jì)、確定適應(yīng)度函數(shù)、選擇、交叉、變異、設(shè)置終止條件。

采用遺傳算法解決訂單分批問題就是通過一定的遺傳進(jìn)化原理，將所有訂單分成不同的批次，然后對每一批的訂單進(jìn)行集中揀選，其目的是減少貨物的搬運(yùn)次數(shù)。

3.1 初始種群

3.1.1 編碼設(shè)計(jì)

一維染色體編碼是遺傳算法中目前最為常用的編碼技術(shù)，它是對問題的解的元素進(jìn)行編碼后，形成染色體，這些染色體中的元素成一維排列。由于本文中訂單數(shù)量比較大，基因特征較為復(fù)雜，采用實(shí)數(shù)編碼能夠更加精確的描述訂單分批的結(jié)果。

本文將每一個訂單都視為染色體的一個基因，該訂單在整個訂單分批之后的批次序號即為此基因的特征，所有訂單的批次集合組成了一條染色體。則n個訂單編碼后形成的染色體集合為：

其中：yi表示訂單Xi的分批結(jié)果，若該訂單被分配到第j批中，取值為 j。

根據(jù)約束條件(2)、(3)、(4)，染色體表達(dá)式(5)有約束條件(6)、(7)：

3.1.2 生成初始種群

每一種分批結(jié)果都視為一條染色體，則隨機(jī)生成的若干條染色體的集合形成初始種群，為了防止初次選擇時同一染色體的重復(fù)出現(xiàn)影響遺傳過程中算法的收斂效果，應(yīng)保證初始種群中任意兩個染色體之間都不相同。假設(shè)初始種群大小為H，則初始種群的表達(dá)式為：

初始種群的選擇不僅決定著最終解的好壞，也對算法計(jì)算效率有著很大影響。如果初始種群規(guī)模過小，則種群內(nèi)染色體的多樣性就會減小，算法很可能最終選取的是局部最優(yōu)解，而不是最優(yōu)結(jié)果或者附近；如果初始種群規(guī)模過大，那么進(jìn)化過程中每次迭代所需要的計(jì)算量及時間都很大，會影響算法效率。

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

適應(yīng)度是指某個生物對于外部環(huán)境的適應(yīng)程度，即用來衡量群體中個體性能的指標(biāo)。適應(yīng)度函數(shù)通常由目標(biāo)函數(shù)來確定，通過它來計(jì)算個體的適應(yīng)值，若適應(yīng)值越大，則代表該個體的性能越優(yōu)異，越能夠作為新一代遺傳的父本。

本文采用的目標(biāo)函數(shù)為最小化貨物的搬運(yùn)次數(shù)L，因此選取目標(biāo)函數(shù)的倒數(shù)來作為適應(yīng)度函數(shù)，當(dāng)目標(biāo)函數(shù)值越小時，適應(yīng)度函數(shù)值就越大。適應(yīng)度函數(shù)即為：

3.3 遺傳操作設(shè)計(jì)

3.3.1 選擇

選擇是指從種群中按照一定的概率選擇出若干個染色體，是一種基于適應(yīng)度值將種群收斂于優(yōu)異個體的過程。本文采用結(jié)合適應(yīng)度比例法和最佳個體保留法的策略來進(jìn)行選擇。

適應(yīng)度比例法的主要思想是從群體中選擇個體的概率與其適應(yīng)度評價有關(guān)，個體對應(yīng)的解求取的適應(yīng)度越高，得到的目標(biāo)函數(shù)值就越大，選擇的概率也越大。假設(shè)初始種群大小為H，即染色體編號為1，2，…，h，其中，個體 r 的適應(yīng)度值為fr，個體 r 被選中的概率設(shè)為pr，累計(jì)概率設(shè)為qr，則：

從[0，1]區(qū)間產(chǎn)生一個隨機(jī)數(shù) e，那么被選中的個體為：

從父本選擇出染色體進(jìn)行交叉變異后，形成子代種群，根據(jù)適應(yīng)度從父代和子代中分別篩選出50%的適應(yīng)度最高的個體組合成新的種群，既能使優(yōu)秀個體參與交叉變異操作，有利于突變產(chǎn)生更優(yōu)個體，又能保留父本中的優(yōu)秀個體，避免錯失更優(yōu)解，同時加快收斂速度。

3.3.2 交叉

交叉是指將父代中選取的兩個個體交換部分基因重新組合成新的子代，用于保證種群中個體的多樣性。本文采用兩點(diǎn)交叉的方式，從交配池中兩兩選擇父體，然后在每對中隨機(jī)指定兩個基因位置進(jìn)行交叉，從而產(chǎn)生新的一對個體，直到交叉全部結(jié)束，形成新的種群。例如，選中個體y、z進(jìn)行交叉，交叉前后的染色體編碼分別為：

3.3.3 變異

變異是選取部分染色體中的某些基因做出變化，增強(qiáng)了群體的多樣性，有效防止算法提早進(jìn)入收斂狀態(tài)。

由于揀選工位每批訂單數(shù)固定為C，而在經(jīng)過交叉操作后，很可能使得某個染色體中分配到同一批次的訂單數(shù)量大于C，因此本文通過變異操作，將染色體中的訂單分批結(jié)果進(jìn)行調(diào)整，使其滿足實(shí)際應(yīng)用的約束條件，具體步驟如下：

1）查找交叉操作后的染色體，統(tǒng)計(jì)其基因中所有同一編碼值的個數(shù)。

2）統(tǒng)計(jì)其中數(shù)量超過C的編碼j1、j2，與數(shù)量少于C 的編碼k1、k2。

3）將編碼值為j1或j2的其中一個基因變異為k1或k2，使得最后的每批訂單數(shù)均為C。

3.3.4 設(shè)置終止條件

經(jīng)過選擇、交叉、變異后，我們得到了新的種群，而在持續(xù)的選擇、交叉、變異下，如果不設(shè)置終止條件，遺傳算法會一直計(jì)算下去，因此需要設(shè)定可靠的終止條件。

本文設(shè)置的終止條件為：

1）當(dāng)算法運(yùn)行次數(shù)達(dá)到最大迭代代數(shù)后停止運(yùn)行。

2）當(dāng)算法成熟收斂，種群中染色體種類剩余一種時停止運(yùn)行。

3.4 算法流程

根據(jù)以上分析使用遺傳算法進(jìn)行訂單分批的具體算法流程如下：

1）隨機(jī)將訂單分批，生成初始種群，并根據(jù)編碼規(guī)則進(jìn)行編碼。

2）根據(jù)每個訂單所包含的貨物品項(xiàng)計(jì)算分批后訂單組的總品項(xiàng)，然后計(jì)算適應(yīng)度函數(shù)。

3）根據(jù)適應(yīng)度函數(shù)計(jì)算累計(jì)概率，并進(jìn)行選擇、交叉、變異，然后將子代中的優(yōu)秀個體與父本中的優(yōu)秀個體組成新的種群。

4）判斷是否滿足算法的終止條件，若不滿足，重復(fù)第2）、3）步不斷進(jìn)行迭代進(jìn)化，若滿足，則停止迭代，選取當(dāng)前種群中適應(yīng)度值最高的分批結(jié)果作為最終分批方案。

4 仿真

4.1 實(shí)驗(yàn)方案

假定共有50種貨物，然后隨機(jī)生成2000個包含這50種貨物的訂單作為實(shí)驗(yàn)數(shù)據(jù)，每個訂單包含2到20種貨物。根據(jù)現(xiàn)實(shí)使用場景，同一批次同時揀選訂單數(shù)量最多為5個。

本文采用基于遺傳算法的分批策略進(jìn)行研究，衡量該算法在訂單分批問題中的優(yōu)化效果。并且為了更好的驗(yàn)證本文提出的遺傳算法在訂單分批問題中的優(yōu)勢，將相同的數(shù)據(jù)分別采用不分批的策略和先到先分批的策略進(jìn)行計(jì)算，作為本文所提出算法的對照參考組。

將這2000個訂單隨機(jī)分為10組，每組包含200個訂單數(shù)據(jù)。每次實(shí)驗(yàn)都從10組數(shù)據(jù)中分別隨機(jī)抽取20、40、50、75、100、125、150、175、200個訂單來進(jìn)行分批計(jì)算，每組數(shù)據(jù)采用遺傳算法進(jìn)行分批時重復(fù)實(shí)驗(yàn)計(jì)算5次，取其平均值作為該組的貨物搬運(yùn)次數(shù)，然后再將這10組數(shù)據(jù)取其平均結(jié)果作為最終分批方案。

4.2 參數(shù)設(shè)置

選取一組訂單數(shù)據(jù)，采用遺傳算法，計(jì)算在設(shè)置不同的初始種群大小及不同的迭代次數(shù)時，最終的貨物搬運(yùn)次數(shù)。每種參數(shù)設(shè)置都重復(fù)5次取其平均值作為最終結(jié)果，當(dāng)訂單數(shù)為20時，結(jié)果如表1所示。

表1 貨物搬運(yùn)次數(shù)（訂單數(shù)為20）

由表1可得貨物搬運(yùn)次數(shù)與迭代次數(shù)和初始種群大小之間的關(guān)聯(lián)情況。不同迭代次數(shù)下貨物平均搬運(yùn)次數(shù)與初始種群大小的關(guān)系如圖1所示。由圖1可得當(dāng)初始種群H小于70時，貨物搬運(yùn)次數(shù)隨著初始種群數(shù)量的增加而顯著減少，當(dāng)H大于70時，搬運(yùn)次數(shù)趨于平穩(wěn)，基本不會隨著H的增加而繼續(xù)減少。因此設(shè)定當(dāng)訂單數(shù)為20時，本文實(shí)驗(yàn)設(shè)置初始種群大小H=70。

圖1 不同迭代數(shù)量的平均搬運(yùn)次數(shù)

初始種群數(shù)量不同時，貨物平均搬運(yùn)次數(shù)隨著迭代次數(shù)變化如圖2所示?？傻?，貨物搬運(yùn)次數(shù)隨著迭代次數(shù)的增加而減小，但是當(dāng)?shù)∮?5時，搬運(yùn)次數(shù)與迭代次數(shù)的負(fù)相關(guān)性較為明顯，當(dāng)?shù)螖?shù)大于25時，貨物搬運(yùn)次數(shù)受迭代次數(shù)影響較小?？紤]到算法的運(yùn)算效率將隨著迭代次數(shù)的增加而降低，因此訂單數(shù)為20時，本文采用遺傳算法的終止條件為迭代次數(shù)大于等于25次。

圖2 不同大小初始種群的平均搬運(yùn)次數(shù)

根據(jù)上述方式，分別計(jì)算出不同訂單數(shù)量下，選取的初始種群大小與迭代次數(shù)的參數(shù)如表2所示。

表2 參數(shù)設(shè)置

4.3 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)采用了基于遺傳算法的分批策略、先到先分批的策略和不分批策略三種方案進(jìn)行計(jì)算，對比驗(yàn)證不同方案的揀選效率。通過計(jì)算分批問題的目標(biāo)函數(shù)值，即所有訂單品項(xiàng)總的搬運(yùn)次數(shù)作為衡量分揀效率的指標(biāo)。對10組數(shù)據(jù)的實(shí)驗(yàn)結(jié)果計(jì)算其平均值如表3所示。由表3可得，在不同規(guī)模的數(shù)據(jù)集下，不采用訂單分批策略的方案最終的品項(xiàng)搬運(yùn)次數(shù)最高；采用先到先分批策略進(jìn)行訂單分批后，搬運(yùn)次數(shù)有所下降；而基于遺傳算法的分批策略，使得訂單總的搬運(yùn)次數(shù)最少。因此，基于遺傳算法的分批策略在訂單分揀作業(yè)中，對揀選效率有著很大提升。

表3 平均貨物搬運(yùn)次數(shù)（全部實(shí)驗(yàn)數(shù)據(jù)）

圖3為不同的分批策略下，最終的貨物搬運(yùn)次數(shù)與不分批策略搬運(yùn)次數(shù)的比值。由圖3可得，在不同規(guī)模的訂單數(shù)據(jù)集下，先到先分批策略對于揀選效率的優(yōu)化效果比較穩(wěn)定，比值在65%左右，基于遺傳算法的分批策略對揀選作業(yè)的優(yōu)化效果有著顯著提高，比值在55%到60%左右，而隨著訂單規(guī)模的增加，算法的優(yōu)化效果有所下降。

圖3 分批策略與不分批策略的搬運(yùn)次數(shù)比

5 結(jié)語

本文在基于“貨到人”的自動化物流中心的工作模式下，針對訂單分批問題，構(gòu)造了以最小化訂單品項(xiàng)總的搬運(yùn)次數(shù)為目標(biāo)函數(shù)的數(shù)學(xué)模型，并且搭建了基于適應(yīng)度度量的遺傳算法模型，與不分批的策略和傳統(tǒng)的采用先到先分批的策略進(jìn)行比較，本文提出的算法能夠有效的減少貨物搬運(yùn)次數(shù)，明顯提高了作業(yè)效率。

本文主要針對同種貨物單個儲位的自動揀選，無需考慮同一貨物儲存于多個儲位時對于揀選效果的影響，未來可對不同貨架承載貨物種類大小不一致、單一品項(xiàng)擁有不同儲位的揀選作業(yè)進(jìn)行進(jìn)一步的研究。