【文章內(nèi)容簡介】 巨大。但是在許多小型的倉庫中，都是運用這種方法進行揀選的[11]。 先到先揀選分批方法的結(jié)果可以作為本文數(shù)據(jù)結(jié)果分析的一個參照對象，這種方法展示了在訂單還沒有被分批時，揀選完所有貨物需要行走的總距離。間接表示了現(xiàn)實中，最常用的揀選方法消耗的運作成本是多少。實驗過程中，此方法的實驗結(jié)果可以作為一個參考對象，其他的方法通過與其進行比較，可以分析出優(yōu)化程度的多少，以及優(yōu)化意義如何。 種子啟發(fā)式算法就是訂單分批過程中， 選出一些具有某些特征的訂單作為“種子”，首先將這些種子訂單放入到要組合的批次中去，隨后再根據(jù)某些原則將剩余的訂單添加到已包含有種子訂單的批次中，從而完成整個分批過程的思路[24]。由上理論可以看出，種子方法構(gòu)造訂單批量主要分兩步進行：① 種子訂單的選擇，即從所有待分批的訂單中選擇一些有特色的訂單分別插入到確定好的揀選批次中，作為初始訂單；② 剩余訂單的插入，是指即將剩余的訂單插入到已經(jīng)包含有種子訂單的批次中來。種子揀選的準則有很多，根據(jù)不同的原則來選擇訂單作為種子，必定會對分批后的揀選效率產(chǎn)生很大的影響。根據(jù)優(yōu)化目標的不同，可以適時的選擇某個原則來揀選種子訂單，常用的有訂單體積、包含貨物的位置、單個訂單的揀選路線等等。將沒有分配的訂單插入到已包含有種子訂單的批量中來稱為剩余訂單的插入。一般情況下， 將一個訂單選入一個批量是根據(jù)訂單到這個批量中種子訂單距離的測量方法來確定的。例如：(1)此訂單 的加入所需要增加的通道數(shù)；(2)所加入訂單中心點與中子訂單中心點的差距；(3)加入訂單和種子訂單中最近貨物的總距離[24]。 節(jié)約啟發(fā)式算法最早由Clarke和Wright[21]在1964年提出，主要用于解決車輛的配載與調(diào)度問題。其基思想是運行路徑的節(jié)約問題，是通過將一批小的路徑合并到大路徑中，形成一個組合,從而來獲得最佳路徑。在車輛載重容量允許的情況下，將分別向各個客戶送貨改為由一輛車同時向多個客戶送貨，使得每次節(jié)約的里程數(shù)最大。根據(jù)這一思想，如果有一個配送中心分別向N個客戶配送貨物，在車輛載重能力允許的情況下，每輛車的配送線路上經(jīng)過的用戶個數(shù)越多，則配送線路越合理，總配送距離越小。借鑒節(jié)約法的思想， 主要有四種訂單分批節(jié)約啟發(fā)式算法法：L．CW算法；2．EQUAL算法；3．SL（Small一 Large）算法；4．MAXSAV算法。 節(jié)約啟發(fā)式算法的基本原理本質(zhì)上仍然是種子啟發(fā)式算法， 只不過無論采取上述哪種具體算法，其處理訂單的標準都是距離或時間的最大節(jié)約值，在種子訂單的選擇和相似性度量方面的標準都比較單一。自動化立體倉庫和多巷道的低層倉庫都可以采用節(jié)約啟發(fā)式算法對訂單進行分批處理。De Koster et 、揀選員到物的配送中心系統(tǒng)中比較了種子方法和節(jié)約方法兩種理論。這2個算法的執(zhí)行效果是通過兩種不同的啟發(fā)式行程來評價的。這種分批算法考慮了運行時間、組成的分批數(shù)量以及現(xiàn)實的可行性。兩種方法總結(jié)到,（1）即使是簡單的分批與先到先揀選相比也有明顯的優(yōu)越性；（2）種子啟發(fā)式算法法與S形行走方法、最大的設備容量相結(jié)合時效果最佳，然而，節(jié)約啟發(fā)式算法與最大跨度行走路線、較小設備容量相結(jié)合時效果最佳。 節(jié)約啟發(fā)式算法的基本思想史車輛路徑問題中的節(jié)約算法在訂單分批中的應用。節(jié)約算法就是將一對訂單合并成在一條路線上進行揀取的新訂單，使合并后的行走距離比分別揀取這對訂單具有最大的節(jié)約量。在訂單分批問題中，訂單相當于車輛路徑問題中的城市，訂單合并后產(chǎn)生的行走距離節(jié)約量相當于城市合并配送后節(jié)約的里程數(shù)。兩者本質(zhì)的不同在于合并的訂單中，存在具有共同存儲位置的品項。對這些品項的揀取，秩序訪問依次就能同時滿足多張訂單的要求。另外，由于車輛容量的限制，并不是每張訂單都能與其他訂單合并成一批進行揀取[25]。1．輸入一個時間段內(nèi)所有需要揀取的訂單數(shù)據(jù)，包括揀貨車的容量；2．將所有的訂單兩兩組對，計算其品項數(shù)之和，如果品項數(shù)之和小于等于，則計算其行走距離節(jié)約量； 3．將節(jié)約量按由大到小非增序排列； 4．選擇節(jié)約量最大的組合合并成一批，組成一個新的訂單，形成初始批量。5．分別以兩個選定訂單為基準訂單，檢查與兩個基準訂單與其余訂單的所有節(jié)約量，將節(jié)約量按由大到小非增序排列。6．選擇節(jié)約量最大的組合。 7．將當前批量中的訂單從帶分批的訂單集合中移走轉(zhuǎn)至4。8．如果所有的組合都已經(jīng)檢查完成，但仍有訂單沒有分配到適當?shù)呐?，則將這些訂單單獨成批。第四章 訂單分批揀選啟發(fā)式算法的研究與應用倉庫配送中心揀貨作業(yè)中的訂單分揀是為了提高揀貨作業(yè)效率而把多張訂單集合成一批，進行批次揀取作業(yè)，其目的是縮短揀取時平均行走搬運的距離和時間。若再將每批次訂單中的統(tǒng)一商品品項匯總后揀取，然后再把貨品分配給每一個不同的顧客訂單，則形成批量揀取，這樣不僅縮短了揀取時平均行走搬運的距離，也減少了重復尋找儲存位置的時間，而使揀貨效率提高。批量揀取特別適合與品項數(shù)少而訂單數(shù)量龐大的系統(tǒng)，越是少量多次的配送，批量揀取就越有效。訂單分批問題用數(shù)學語言來表達就是指將訂單按照適當?shù)姆绞竭M行分批并確定批量揀取路徑以使目標函數(shù)達到最優(yōu)。批量揀取的基礎目標有兩種：（1）減少揀貨行走的總時間；（2）減少揀貨行走的距離進而提升產(chǎn)能和改善交貨期。本文以最小化揀貨行走距離為目標構(gòu)造了訂單分批問題的數(shù)學模型，提出了解決該問題的兩種啟發(fā)式算法：①節(jié)約啟發(fā)式算法；②基于聚類分析的啟發(fā)式算法。其中節(jié)約啟發(fā)式算法需要事先知道路徑策略，而聚類問題的分析求解提出了多種相似系數(shù)的計算方法，且相似系數(shù)的計算不需要事先知道路徑策略。在提出解決問題的兩種啟發(fā)式算法之后，還將給出一個用這兩種方法求解該類問題的實例。節(jié)約啟發(fā)式算法和基于聚類分析的啟發(fā)式算法均可以有效求得訂單分批問題的近優(yōu)解，能夠廣泛運用于大型配送中心和流通倉庫的揀貨系統(tǒng)，以提高揀貨的效率。 訂單分批問題的數(shù)學模型 模型假設（1） 倉庫結(jié)構(gòu)已知；（2）一個訂單至少包含一個品項；（3）保持訂單的完整性，不允許分割訂單；（4）訂單數(shù)據(jù)及品項存儲位置已知；（5）每張訂單的品項數(shù)不超揀貨車的容量；（6）每批訂單的揀取都能在1條揀貨路線上完成；（7） 任意揀貨路徑的起點和終點都在出入口，即揀貨員推著揀貨車從出入口出發(fā)，按設定的路徑策略從倉庫中揀出貨物，最后返回出入口；（8） 揀取時不存在缺貨現(xiàn)象和緊急插單情況；（9） 訂單數(shù)據(jù)輸入后，計算機能按事先規(guī)定的路徑策略對需要揀取的品項進行路徑排序，形成順序揀貨單。 數(shù)學模型的建立根據(jù)假設，可以將訂單分批揀貨問題描述為：假設有a個訂單On(n=1，2，，a)需要揀取，每個訂單中包含若干品項，第n個訂單中的品項數(shù)為qn?，F(xiàn)要求在不分割訂單的情況下，對a個訂單進行分批揀取，每批訂單的揀取在一條路線上一次完成，并使揀取所有訂單的總行走距離最小。訂單分批揀貨問題的數(shù)學模型可以表示為：目標函數(shù)： mint∈Sdtxt ()約束條件： n=1aqnant≤C () t∈Santxt=1 , n=1,，a () xt∈0,1,ant∈{0,1} () 式中: a—需要揀取的訂單總數(shù) C—揀貨車的容量 qn—第n個訂單中所有品項的數(shù)量 S—所有可行訂單批量集合t—每個可行的訂單批量，t∈Sajs=1 訂 單 n 屬 于 第t 批 0 訂單n不屬于第t批 n=1,2,，adt—揀取第t批訂單中的所有品項的總行走距離xt=1 第t批 被 選 中0 第t批沒被選中 模型的目標函數(shù)是訂單分批后，使各批訂單揀取路線總和最小。約束條件（）表示每批訂單包含的品項數(shù)不超過揀貨車的容量，約束條件（）和（）表示每個訂單只能被分配到一個批量中。 節(jié)約啟發(fā)式算法求解訂單分批問題過程當模型訂單數(shù)量大于3時，屬于NP完全問題，其求解較復雜。節(jié)約啟發(fā)式算法的基本思想是車輛路徑問題中的節(jié)約算法在訂單分批中的應用。節(jié)約算法就是將訂單m和訂單n合并成在一條路線上進行揀取的新訂單，使合并后的行走距離比分別揀取訂單m和n具有最大的節(jié)約量Smn=dm+dndmn。在訂單分批問題中，訂單相當于車輛路徑問題中的城市，訂單合并后產(chǎn)生的行走距離節(jié)約量相當于城市合并配送后節(jié)約的里程數(shù)。兩者本質(zhì)的不同在于合并的訂單中，存在具有共同存儲位置的品項。對這些品項的揀取，秩序訪問依次就能同時滿足多張訂單的要求。另外，由于車輛容量的限制，并不是每張訂單都能與其他訂單合并成一批進行揀取[25]。 初始批量的形成（1）輸入一個時間段內(nèi)所有需要揀取的訂單數(shù)據(jù)，包括揀貨車的容量；（2）將所有的訂單兩兩組對，計算其品項數(shù)之和qmn=qm+qn(m=1,a；n=1,,a；n≠m)，如果qmn≤C，則計算其行走距離節(jié)約量Smn=Snm；（3）將節(jié)約量按由大到小非增序排列；（4）選擇節(jié)約量最大的組合Skp=maxSmn合并成一批（如果有兩組數(shù)字相同，則任選一組）；有訂單Ok和Op組成一個新的訂單，即Ot={Ok,Op}形成初始批量。 批量的優(yōu)化（1） 分別以訂單k和訂單p為基準訂單，檢查Smk和Snp(m=1,，a；n=1,，am≠p,n≠k)，將節(jié)約量按由大到小非增序排列。（2）選擇節(jié)約量最大的組合，存在兩種情況：① max{Smk，Snp}=Sxk,則計算Ot和Ox品項數(shù)之和qtx=qt+qx,若qtx≤C,則將訂單Ox加入當前批Ot中形成新的當前批Ot=Ot+Ox={Ok，Op，Ox}。否則對余下的組合重復（2），直到找不到符合組成條件的訂單為止。當前批Ot即為找到的優(yōu)化批量。② max{Smk，Snp}=Syk,則計算Ot和Oy品項數(shù)之和qty=qt+qy,若qty≤C,則將訂單Oy加入當前批Ot中形成新的當前批Ot=Ot+Oy={Ok，Op，Oy}。否則對余下的組合重復（2），直到找不到符合組成條件的訂單為止。當前批Ot即為找到的優(yōu)化批量。（3）（4）。（4） 如果所有的組合都已經(jīng)檢查完成，但仍有訂單沒有分配到適當?shù)呐校瑒t將這些訂單單獨成批。 節(jié)約啟發(fā)式算法的算例分析倉庫結(jié)構(gòu)為長方形，出入口位于倉庫的一角第1個巷道的中心處，共有8個揀貨巷道，貨架為底層固定貨架，每排貨架上沿巷道方向有15列存儲位置，圖41為倉庫貨架二維平面圖。已知貨架長15個單位，巷道中心距離為4個單位，揀貨車容量為10品項?，F(xiàn)有5個需要揀取得訂單，包括8種不同的品項。