基于遺傳算法的訂單分批策略研究

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

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

0 引言

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

1 訂單分批

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

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

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

2 模型與假設(shè)

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

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

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

約束條件：

3 算法

遺傳算法（Genetic Algorithm）是一種隨機(jī)搜索算法，是通過(guò)對(duì)基于達(dá)爾文生物進(jìn)化理論與遺傳學(xué)機(jī)理的自然選擇和生物進(jìn)化過(guò)程進(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)自動(dòng)獲取搜索空間并進(jìn)行優(yōu)化指導(dǎo)。

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

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

3.1 初始種群

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

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

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

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

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

3.1.2 生成初始種群

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

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

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

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

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

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

3.3.1 選擇

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

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

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

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

3.3.2 交叉

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

3.3.3 變異

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

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

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

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

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

3.3.4 設(shè)置終止條件

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

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

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

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

3.4 算法流程

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

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

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

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

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

4 仿真

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

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

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

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

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

選取一組訂單數(shù)據(jù)，采用遺傳算法，計(jì)算在設(shè)置不同的初始種群大小及不同的迭代次數(shù)時(shí)，最終的貨物搬運(yùn)次數(shù)。每種參數(shù)設(shè)置都重復(fù)5次取其平均值作為最終結(jié)果，當(dāng)訂單數(shù)為20時(shí)，結(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時(shí)，貨物搬運(yùn)次數(shù)隨著初始種群數(shù)量的增加而顯著減少，當(dāng)H大于70時(shí)，搬運(yùn)次數(shù)趨于平穩(wěn)，基本不會(huì)隨著H的增加而繼續(xù)減少。因此設(shè)定當(dāng)訂單數(shù)為20時(shí)，本文實(shí)驗(yàn)設(shè)置初始種群大小H=70。

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

初始種群數(shù)量不同時(shí)，貨物平均搬運(yùn)次數(shù)隨著迭代次數(shù)變化如圖2所示?？傻?，貨物搬運(yùn)次數(shù)隨著迭代次數(shù)的增加而減小，但是當(dāng)?shù)∮?5時(shí)，搬運(yùn)次數(shù)與迭代次數(shù)的負(fù)相關(guān)性較為明顯，當(dāng)?shù)螖?shù)大于25時(shí)，貨物搬運(yùn)次數(shù)受迭代次數(shù)影響較小。考慮到算法的運(yùn)算效率將隨著迭代次數(shù)的增加而降低，因此訂單數(shù)為20時(shí)，本文采用遺傳算法的終止條件為迭代次數(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ì)算，對(duì)比驗(yàn)證不同方案的揀選效率。通過(guò)計(jì)算分批問(wèn)題的目標(biāo)函數(shù)值，即所有訂單品項(xiàng)總的搬運(yùn)次數(shù)作為衡量分揀效率的指標(biāo)。對(duì)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è)中，對(duì)揀選效率有著很大提升。

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

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

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

5 結(jié)語(yǔ)

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

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