馬 超，雷 斌，陳洪滿

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

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

馬 超，雷 斌，陳洪滿

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

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

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

0 引言

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

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

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

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

1 訂單分批揀選問(wèn)題描述

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

圖1 倉(cāng)庫(kù)的布局結(jié)構(gòu)

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

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

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

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

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

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

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

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

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

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

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

訂單分批的問(wèn)題模型可以被描述為：假設(shè)有N個(gè)訂單Qn(n=1,2,3,…,N)，用來(lái)揀選設(shè)備的數(shù)量為M，每個(gè)訂單含有多個(gè)貨品且必須揀選完畢．本文要求對(duì)N個(gè)訂單分批揀選，由m個(gè)揀選設(shè)備對(duì)每批訂單同時(shí)揀選，在此期間，被揀選的訂單不能分割到其它批次．但在同一個(gè)批次中，訂單可以劃分到其它揀選設(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個(gè)揀選批次，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：貨品種類(lèi)數(shù)．

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

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

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

(1)染色體編碼方法

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

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

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

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

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

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

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

(5)交叉操作

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

父代：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)變異操作

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

父代：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 實(shí)驗(yàn)計(jì)算結(jié)果

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

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

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

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

表2 實(shí)驗(yàn)結(jié)果比較

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

5 結(jié)論

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

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

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

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

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

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

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

[7]李詩(shī)珍,王 轉(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].無(wú)錫：江南大學(xué),2009.

[11]萬(wàn) 杰,張少卿,李 立.基于遺傳算法的配送中心訂單揀選優(yōu)化問(wèn)題研究[J].河北工業(yè)大學(xué)學(xué)報(bào),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

郎集會(huì))

2014-05-26

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

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

TP312

A

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