一種配送中心訂單分揀優(yōu)化問題的研究

馬 超，雷 斌，陳洪滿

(蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州 730070)

一種配送中心訂單分揀優(yōu)化問題的研究

馬 超，雷 斌，陳洪滿

(蘭州交通大學(xué) 機(jī)電技術(shù)研究所，甘肅 蘭州 730070)

研究一種配送中心訂單分揀優(yōu)化問題．目標(biāo)函數(shù)設(shè)置為總的揀選訂單行走的距離，使用遺傳算法優(yōu)化訂單的分批組合，并且在本文中訂單分批時，先挑選種子訂單，通過對種子訂單有策略的選取，最終達(dá)到優(yōu)化揀選的總距離的目的．所采用的模型、方法對訂單分揀有較好的優(yōu)化．

訂單揀選；訂單分批；遺傳算法；優(yōu)化

0 引言

在現(xiàn)在物流供應(yīng)鏈中，配送中心起了很大的作用，它可以很好的滿足客戶的特定要求，比如配送時間．目前其類型仍以密集型為主[1]，其中揀貨作業(yè)流程在其中占了很大比例，揀選作業(yè)的時間投入也占整個總體運作時間的40%左右[2]，所以正確的規(guī)劃和設(shè)計揀選作業(yè)對于提高整體的運作效率有很大的影響．

訂單分批揀選，是為了應(yīng)對不同客戶的要求，將貨物按訂單要求取出的過程．在揀選之前，要進(jìn)行訂單分批，即對訂單按不同的需求批次進(jìn)行揀選．這種分批模式的目的是為了減少人力物力的消耗和縮短揀選路程[3]．

之前的研究表明，訂單分批問題是典型的NP—hard問題[4]．很多學(xué)者對此問題采用啟發(fā)式算法來研究，而這些算法的核心內(nèi)容主要是種子算法和節(jié)約算法兩種思路．節(jié)約算法[5]，它是將多路徑或者短路徑的訂單合并轉(zhuǎn)換到長路徑的訂單中，從而實現(xiàn)優(yōu)化揀選路徑的方法．種子算法就是當(dāng)全部訂單未分批時先選出一個訂單作為特定訂單，將其分配到其他的批次中．剩余的訂單也按照某標(biāo)準(zhǔn)插入其中，整體形成一個揀選批次，來實現(xiàn)高效分批的目的[6]．

本文研究問題不同之處在于選擇S形路線進(jìn)行揀貨[7]，以體積較大和重量較重兩個限制條件來選擇種子訂單．考慮揀選設(shè)備的容量和承重并采用單區(qū)型倉庫模型為假設(shè)條件，以揀選的行走距離為優(yōu)化目標(biāo)來測試此模型的優(yōu)化效果，并且對該模型的求解方法用遺傳算法．

1 訂單分批揀選問題描述

為了本論文的研究需要，做以下假設(shè)：

圖1 倉庫的布局結(jié)構(gòu)

(1)配送中心的存儲空間由貨架并行排列行成，本文的模型是單區(qū)型倉庫,基本布局結(jié)構(gòu)如圖1所示．

(2)揀選人員或揀選設(shè)備數(shù)量至少為一個．

(3)忽略貨架高度所帶來的位移，該位移不計入揀選路徑的計算．

(4)每張訂單至少包含一個貨品，并且訂單不能被拆分為多個批次進(jìn)行揀選．

(5)每批次有N個揀選人員(揀選設(shè)備)同時進(jìn)行揀選，揀選完一個批次后繼續(xù)進(jìn)行下一個．

(6)每一個揀選設(shè)備的承重和容量限制是同等的，并且單個貨品不能超過一個揀選設(shè)備的質(zhì)量和容量限制．

(7)對于每個批次揀選訂單上的所有物品，不能超過該揀選批次中所有揀選設(shè)備的總?cè)萘亢涂傊亓肯拗疲?/p>

(8)沒有緊急插入訂單和缺貨的情況．

(9)揀選單上物品的存儲貨位是已知的．

(10)揀選過程中采用的是改進(jìn)S型策略．

2 揀選數(shù)學(xué)模型建立

訂單分批的問題模型可以被描述為：假設(shè)有N個訂單Qn(n=1,2,3,…,N)，用來揀選設(shè)備的數(shù)量為M，每個訂單含有多個貨品且必須揀選完畢．本文要求對N個訂單分批揀選，由m個揀選設(shè)備對每批訂單同時揀選，在此期間，被揀選的訂單不能分割到其它批次．但在同一個批次中，訂單可以劃分到其它揀選設(shè)備上完成本次揀選，最終實現(xiàn)總的揀選路徑最?。疚闹械挠唵畏峙鷶?shù)學(xué)模型如下所示：

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

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

N：需要揀選的總訂單數(shù)；

M：揀選人員(揀選設(shè)備)的數(shù)量；

On：訂單n；

vnk：批次k中，訂單n中貨品的容積，k=1，2，…，K；

qnk：批次k中，訂單n中貨品的重量，k=1,2,…，K；

no_batchk：第k個揀選批次，k=1,2,…，K；

K：訂單的分批批數(shù)；

capmv：揀選設(shè)備m的最大載貨容積；

capmq：揀選設(shè)備m的最大載貨質(zhì)量；

L：路徑總數(shù)；

Tik：揀選批次k包含的揀選路徑I，i=1,2,…，L；

Di：按路徑Ti進(jìn)行揀選行走的總距離；

Pnk決定訂單n是否在批次k中；

Xni決定訂單n是否在批次i中；

Z：貨品種類數(shù)．

(1)是目標(biāo)函數(shù)，即對全部訂單分批揀選得到的最小的總揀選路徑．(2)表示任意揀選批次中，被揀選的總重量要低于該批次揀選設(shè)備的最大承重．(3)表示任意揀選批次中，被揀選貨物的總體積要低于該批次揀選設(shè)備的最大容量．(4)表示任意訂單中，揀選設(shè)備的數(shù)量要多于揀貨路徑數(shù)量，即不會出現(xiàn)閑置的揀貨路徑．(5)表示訂單不可分割，由一個揀選批次完成揀選．(6)表示任意揀選批次中，所有貨物能由揀選設(shè)備一次性揀選完成．(7)表示訂單n在分批k中時取值為1，否則為0．(8)表示訂單n在路徑i中時取值為 1，否則為0．(9)表示訂單都會被分配．(10)表示每個訂單只會分配一次．

3 遺傳算法的改進(jìn)與實現(xiàn)

遺傳算法的操作主要有以下幾種步驟：(1)確定對應(yīng)的編碼方法；(2)交叉、變異[8]；(3)合理的選擇．現(xiàn)具體描述如下：

(1)染色體編碼方法

把訂單集合S{O1,O2,O3…,ON}中所有的訂單進(jìn)行參數(shù)編碼操作，本文中采用的模型是多個批次和多個揀選設(shè)備，所以選取r-t這種方式來表示，r代表訂單所在的批次，t代表訂單由哪個揀選設(shè)備．例如{2-31,2-12,…,r-tn}中數(shù)項2-3表此位置的訂單被分配到第2個批次的地3個揀選設(shè)備上．

(2)種子訂單設(shè)置

根據(jù)De Koster[9]的研究結(jié)論，種子訂單要根據(jù)體積和重量這兩個限制條件來綜合確定，其剩余的訂單插入是由計算機(jī)隨機(jī)完成的，但不會超過揀選設(shè)備的容量限制．

(3)適應(yīng)度函數(shù)設(shè)計

在求極大值maxx∈(a,b)f(x)問題的時候，適應(yīng)度函數(shù)可以直接用模型的目標(biāo)函數(shù)f(x)來表示[10]．

(4)選擇策略的設(shè)計

這是選擇概率算子，每個染色體都要按上式算出其選擇概率算子，然后應(yīng)用其選出用于交叉繁殖的染色體．

(5)交叉操作

本文選擇的交叉方法是單點交叉，而且交叉點是隨機(jī)選取的，交叉的同時沒有改變訂單所屬的批次．所有的交叉完畢后，形成新一代群體，比如：

父代：A=(A1,A2,A3,A4,|A5,A6,A7,A8)B=(B1,B2,B3,B4,|B5,B6,B7,B8)

子代：A=(A1,A2,A3,A4,|B5,A6,A7,A8)B=(B1,B2,B3,B4,|A5,B6,B7,B8)

(6)變異操作

遺傳算法中的變異操作是將染色體編碼中的某些基因位用該基因位的其它等位基因來替換，來形成一個新的個體．比如：

父代：A=(A1,A2,A3,A4,A5,A6,A7,A8)A=(A1,A2,A3,A4,|B5,A6,A7,A8)

變異后的子代：A=(A1,A2,A3,A4,B5,A6,A7,A8)B=(B1,B2,B3,B4,|A5,B6,B7,B8)

4 實驗計算結(jié)果

本文的研究問題所采用的數(shù)據(jù)是參考萬杰[11]的研究數(shù)據(jù)，但是在算法上進(jìn)行了不同的改進(jìn),添加了設(shè)計問題中對應(yīng)的限制條件．本文中采用的遺傳算法的編程是通過Visual C實現(xiàn)的．其基本數(shù)據(jù)如表1所示．

表1 算例基本初始數(shù)據(jù)

由于初始種群是隨機(jī)生成的，而且在遺傳算法中有以一組數(shù)據(jù)對其結(jié)果有重大影響，稱之為控制參數(shù)[12]．本文中的控制參數(shù)：種群規(guī)模chro=20，最大遺傳代數(shù)為500，迭代次數(shù)為50．為了加快尋優(yōu)速度，在此我們將交叉概率設(shè)為1，就是每次都要交叉．

在多次數(shù)字試驗中，結(jié)果都比原文中的尋到的值優(yōu)．表2列舉了相應(yīng)的數(shù)據(jù)，并且和其參考文獻(xiàn)采用的的基本遺傳算法GABM進(jìn)行對應(yīng)數(shù)據(jù)的比較，本文中含有種子訂單選擇的遺傳算法描述為GASM．

表2 實驗結(jié)果比較

表2中方差反映了不同批次策略的勞動強度的平衡狀況，數(shù)據(jù)大，說明一個批處理過程的差異程度越大．很容易看出，在有相同的遺傳代數(shù)的前提下選擇種子訂單揀選方法進(jìn)行試驗，揀選總距離相對較小，那按照一定的條件比隨機(jī)選擇種子的訂單更好．

5 結(jié)論

在本文中，用遺傳算法來求解構(gòu)建的訂單分批模型，以揀選距離最短為最終目標(biāo)，采用了不同于以往的分批優(yōu)化算法，在初始的訂單分批中加入了種子訂單揀選的策略．通過這種有效的策略，進(jìn)一步使揀選的總距離得到了顯著的優(yōu)化．

由于遺傳算法的靈活性，能夠很容易的運用到各種不同的假設(shè)情況和不同的倉庫布局模型，所以在以后的實驗中，相應(yīng)的限制條件可以適當(dāng)變更，更加符合現(xiàn)實．即在揀選路徑方式，種子訂單選擇方法、揀選機(jī)械限制條件等發(fā)生變化時，訂單分批揀選的優(yōu)化問題．

[1]R.D.Koster,T.Le-Duc,K.J.Roodbergen.Design and control of warehouse order picking:a literature review[J].European Journal of Operational Research，2007，182:481～501.

[2]張大海.物流配送中心訂單分批配送問題研究.中國科學(xué)技術(shù)協(xié)會、河南省人民政府.第十屆中國科協(xié)年會科技人力資源與區(qū)域經(jīng)濟(jì)發(fā)展論壇論文集[C].中國科學(xué)技術(shù)協(xié)會、河南省人民政府,2008.

[3]李 哲.物流中心揀選單處理及揀選路徑優(yōu)化研究[D].大連：大連海事大學(xué)，2011.

[4]王艷艷,吳耀華,孫國華,等.配送中心分揀訂單合批策略的研究[J].山東大學(xué)學(xué)報(工學(xué)版)，2010，(3):124～140.

[5]劉進(jìn)平.配送中心分揀系統(tǒng)設(shè)計方法研究[D].大連：大連海事大學(xué),2011.

[6]陳伊菲,劉 軍.倉儲揀選作業(yè)路徑VRP模型設(shè)計與應(yīng)用[J].計算機(jī)工程與應(yīng)用，2006，(3):97～104.

[7]李詩珍,王 轉(zhuǎn).訂單揀取路徑優(yōu)化研究——S形啟發(fā)式方法在配送中心揀貨中的應(yīng)用[J].物流技術(shù)與應(yīng)用,2002,(5):67～70.

[8]J.H.Holland.Progres in Theoretical Biolo-gy[J].Adaptation，1976，(4):264～293.

[9]R.D.Koster,E.S.Van der Poort,Wolters M.Efficient order batching methods in warehouses[J].International Journal of Production Research，1999，(7):1479～1504.

[10]王銀年.遺傳算法的研究與應(yīng)用[D].無錫：江南大學(xué),2009.

[11]萬 杰,張少卿,李 立.基于遺傳算法的配送中心訂單揀選優(yōu)化問題研究[J].河北工業(yè)大學(xué)學(xué)報,2009,(5):10～14.

[12]李延梅.一種改進(jìn)的遺傳算法及應(yīng)用[D].廣州：華南理工大學(xué),2012.

ResearchontheDistributionCenterOrderPickingBatch

MAChao，LEIBin，CHENHong-man

(Mechanical and Electrial Technology Institute,Lanzhou Jiaotong University,Lanzhou 730070,China)

In this paper,the distribution center order picking optimization problem was researched.The objective function was set to the total distance travelled by picking orders using a combination of genetic algorithm optimization batch orders.And in the order in batches,the first selection was the seed orders.By strategically selecting seed orders, the purpose of optimizing the total distance was ultimately achieved.The model and method used in the paper were the optimization for order piching.

order picking;order batching;genetic algorithms;optimization

郎集會)

2014-05-26

甘肅省自然科學(xué)基金項目(1310RJZA056)；蘭州交通大學(xué)青年基金項目(2013016)

馬 超(1988-)，男，河北省石家莊市人，現(xiàn)為蘭州交通大學(xué)機(jī)電技術(shù)研究所碩士研究生．研究方向：物流信息調(diào)度優(yōu)化．

TP312

A

1674-3873-(2014)03-0118-04