器材揀選決策的改進節(jié)約算法

葛 陽，王曉峰， 郝 冰，寧劍平 GE Yang,WANG Xiao-feng,HAO Bing,NING Jian-ping

（1.軍械工程學(xué)院，河北 石家莊 050003；2.63869部隊，吉林 白城 137001；3.76127部隊，湖南 郴州 424202）

0 引 言

1 揀選作業(yè)的數(shù)學(xué)模型

假設(shè)： （1）貨位間距為常數(shù)，h為貨位高度，b為貨位寬度，長度忽略不計。 （2）器材外形規(guī)則，周轉(zhuǎn)貨箱裝箱能力僅與待裝器材體積有關(guān)。 （3）器材擺放位置可視為貨格的中心點上，貨位坐標為（x,y ），表示位于第x層第y列。 （4）貨箱容積大于任一貨位內(nèi)器材的體積。

符號： （xlk,ylk）——第l次取貨，第k步巷道車停留在貨架的第xlk層第ylk列；A（ i,j,m）——貨架第i層第j列第m種器材庫存數(shù)量 （已知）；B（ xik,yik,m）——第l次取貨，第k步揀選第m種器材的數(shù)量；dm——調(diào)撥單中需要調(diào)撥的第m種器材的數(shù)量 （已知）；vm——第m種器材的體積 （已知）；V0——貨箱的容積 （已知）。

假設(shè)巷道車在橫向和縱向的速度是恒定的，影響揀選作業(yè)效率的主要因素就是巷道車行走距離的多少，所以優(yōu)化的目標就是尋求一條最短的揀選路徑。當揀選器材較多時，受揀貨箱容積和承重的限制 （對于小件器材一般只考慮貨箱容積的限制），可能無法一次完成揀選作業(yè)，需要分多次進行，因此，巷道車在整個揀選作業(yè)過程中所行走的距離就是進行每一次揀選路徑的距離之和。

目標函數(shù)：

式 （1）中，S代表巷道車行走的最短距離，Sl表示第l次取貨時，巷道車所走的距離，xlk-xl（k-1）b表示巷道車第l次第k步取貨， 由貨位 （xl（k-1）,yl（k-1））移動到貨位 （xlk,ylk）時橫向行走的距離， 同理ylk-yl（k-1）h表示縱向的行走距離。由于巷道車一般有兩個電機驅(qū)動，一個負責(zé)橫向移動，另外一個負責(zé)縱向移動，所以這里認為巷道車行走的距離就是巷道車在橫向和縱向行走的距離之和。

約束條件：

每次揀選的器材體積之和小于等于貨箱的容積，即：

揀選第m種器材的數(shù)量之和等于調(diào)撥單中第m種器材的數(shù)量，即：

對第i層第j列揀選的第m種器材的數(shù)量小于等于該貨位上存放的第m種的數(shù)量，即：

貨架存放的第m種器材的數(shù)量大于等于調(diào)撥單中該種器材的數(shù)量，即：

2 節(jié)約算法求解

揀選路徑最優(yōu)問題，已被證明是NP-難問題[2]，精確算法的計算量太大，一般采用近似算法或啟發(fā)式算法，節(jié)約算法是一種常見的啟發(fā)式算法，由于它簡單實用在配送領(lǐng)域的路線規(guī)劃上被廣泛應(yīng)用，本文將其引入到器材揀選作業(yè)中，以求得路徑優(yōu)化的滿意解 （不一定是最優(yōu)解）。

2.1 節(jié)約量公式

設(shè)巷道口為P0，N個貨位分別是P1,P2,…,PN，已知其中任意兩個貨位 Pi和Pj之間的距離為 dij別為Pi和 Pj的坐標 ）。從巷道口開始揀選貨位Pi和Pj，有兩種方案，一是一次性完成兩個貨位的揀選后回到巷道口，二是往返兩次分別揀選這兩個貨位，前者比后者行走距離的節(jié)約量為：

式 （6）就是著名的節(jié)約量公式。由推導(dǎo)結(jié)果可知，Dij≥0。

2.2 節(jié)約算法的思路

由于同一種器材可能存放于多個貨位，入庫年份也可能不同，如果隨機揀選，入庫較早的器材可能一直不被揀選到，隨時間推移，器材過了保質(zhì)期就難免報廢，造成浪費。所以，首先要根據(jù) “先進先出” （或 “用舊存新”）原則及式 （3）確定好待揀貨位及數(shù)量，其次是將所有待揀貨位兩兩組對，并計算其行走距離節(jié)約量，將節(jié)約量按由大到小順序排列，選擇節(jié)約量最大的兩個貨位，判斷這兩個貨位待揀器材體積之和是否超過貨箱的容積，如果不超過貨箱的容積，則將這兩個貨位合并為一次揀選，如果超過貨箱的容積，則不合并這兩個貨位，轉(zhuǎn)而判斷節(jié)約量稍小的另兩個貨位能否合并為一次揀選。直到所有可能合并為一次揀選的貨位全部合并，最終得到巷道車行走距離優(yōu)化的滿意解。節(jié)約算法流程如圖1所示。

根據(jù)節(jié)約算法，3算例分析中的算例可得最終的揀選路線 （見表4）為：r1=（0→16→17→7→5→0 ）；r2=（0→8→15→6→0 ）； r3=（0→4→14→11→0 ）； r4=（0→2→3→0 ）； r5=（0→12→13→9→10→0）；r6=（0→1→0 ）?？梢钥闯鲆还卜?次揀選，巷道車行走總距離為534米。

2.3 節(jié)約算法的不足及改進

由3算例分析中的計算過程可以看出節(jié)約算法應(yīng)用在器材揀選中還存在一些缺陷，需要改進。一是每個貨位內(nèi)的待揀器材數(shù)量不允許分割必須一次性揀完，這可能導(dǎo)致貨箱不能裝滿，影響貨箱容積的利用率，從而使揀選次數(shù)增加；二是每次揀選路線，貨位都是按節(jié)約量的大小和貨位序號進行排列的，貨位的前后左右的位置可能較亂，造成巷道車在一次揀選過程中往復(fù)行走，使得行走距離增加，如算例中第1次揀選路線：r1=（0→16→17→7→5→0 ）， 巷道車行走的距離為178米， 如果按照 （0→7→17→16→5→0 ）順序揀選， 則巷道車行走的距離為166米。所以需要對以上兩點不足進行改進。

針對貨位存放的待揀器材數(shù)量不能分割問題，本文提出以下改進思路：將待揀貨位兩兩組合，并計算其節(jié)約量，選擇節(jié)約量最大的兩個貨位：①如果它們存放的待揀器材體積之和小于貨箱容積，則合并它們一次揀選，并進一步尋找與這兩個貨位之一合并帶來最大節(jié)約量的貨位，把這個貨位也合并到當前次揀選路線上，直到該線路上待揀器材的體積之和等于或大于貨箱容積，合并最后一個貨位使得貨箱剛好滿載或不能再裝其他器材。②如果這兩個貨位器材體積之和等于貨箱的容積，則合并它們在一條線路上揀選。③如果這兩個貨位器材體積之和大于貨箱容積，則合并它們在一條線路上揀選，并使貨箱滿載或不能再裝其他器材，將剩余的器材和其他待揀貨位組成一個新的揀選決策問題，重復(fù)上述方法，直到所有貨位全部被合并。

針對巷道車在一次揀選過程可能多次往復(fù)問題，本文提出以下改進方法：對于M層N列的固定貨架，令r為不大于M/2的最大整數(shù)；將1～r層貨位按列號從小到大排序；將r+1～M層貨位按列號從大到小排序；在每一次揀選過程中先揀選1～r層貨位再揀選r+1～M層貨位，則可避免巷道車往復(fù)問題。

改進的節(jié)約算法相比傳統(tǒng)的節(jié)約算法：一是允許貨位存放的待揀器材分多次揀選，提高貨箱利用率；二是將每一次要揀選的貨位進行排序，避免巷道車多次往復(fù)，減少其行走的距離。改進的節(jié)約算法具體流程如圖2所示。

按改進的節(jié)約算法，再計算3算例分析中的實例，如表5所示，可得以下揀選路線：

r1= （0→8→7→17→16→0 ）； r2= （0→15→8→5→4→0 ）； r3= （0→6→4→14→11→12→13→0）；r4=（0→3→2→13→0 ）； r5=（0→1→13→9→10→0 ）， 共分5次揀選， 巷道車行走的總距離為492米。

3 算例分析

自動化立體器材倉庫某一巷道貨架共10行 （層）72列，貨位高和寬均為1m，貨箱容積為20dm3，根據(jù)器材調(diào)撥單要揀選5種器材，隨機產(chǎn)生調(diào)撥單和器材貨位對照表如表1所示 （為簡化計算這里認為器材體積可直接相加）。要求制定揀選計劃，使得揀選距離最短。

3.1 確定待揀貨位

根據(jù) “先進先出”原則和調(diào)撥單數(shù)量要求，可確定以下待揀貨位及數(shù)量如表2所示。

3.2 計算節(jié)約量

表1 器材調(diào)撥單及庫存貨位對照表

表2 待揀貨位表

將待揀貨位兩兩組對，計算距離節(jié)約量如表3所示。

3.3 節(jié)約算法求解

按照圖1所示的節(jié)約算法流程及已確定的待揀貨位和數(shù)量，可得表4所示決策結(jié)果 （具體步驟略）。

表3 貨位組合距離節(jié)約值表

3.4 改進節(jié)約算法求解

利用改進節(jié)約算法進行求解，具體步驟如下。

表4 節(jié)約算法決策結(jié)果

（1）選擇節(jié)約量最大的16、17貨位，器材體積為1×4+1×4=8，揀貨箱未裝滿，在與貨位16和貨位17有關(guān)的組合中查找最大節(jié)約量為16、7貨位 （或16、8，17、7，17、8），將貨位7加入當前揀選序列，此時器材體積為8+2×3=14，揀貨箱仍未裝滿，在貨位16、17、7有關(guān)的組合中查找最大節(jié)約量為16、8貨位，將貨位8加入當前揀選序列，此時揀貨箱只能再揀選貨位8內(nèi)2個器材就裝滿，巷道車返回巷道口，此時貨位8還剩余1個器材等待揀選。這樣可以確定第一次揀選的貨位 （數(shù)量）為7（2 ）、8（2 ）、16（1 ）、17（1 ）。

（2）將已經(jīng)揀選完成的貨位7、16、17從待揀選貨位中刪除，重復(fù)步驟 （1），此時應(yīng)注意貨位8內(nèi)器材數(shù)量為1，應(yīng)保留與剩余的待揀貨位組成新的揀選決策問題，按照 （1）中的步驟進行，直至所有待揀貨位全部合并，可以確定第二次揀選的貨位 （數(shù)量） 為4（5）、5（4）、8（1）、15（2）；第三次為4（1）、6（3）、11（2）、12（1）、13（1）、14（6）；第四次為2（5）、3（4）、13（2）；第五次為1（3）、9（2）、10（1）、13（3）。

經(jīng)過以上三步分析計算，可得揀選決策結(jié)果，如表5所示。

表5 改進節(jié)約算法決策結(jié)果

3.5 結(jié)果分析

由計算結(jié)果可以看出，在揀選作業(yè)決策上，利用改進節(jié)約式算法比傳統(tǒng)的節(jié)約算法更能減少揀選次數(shù)和巷道車的行走距離，說明在揀選作業(yè)中利用改進的節(jié)約式算法方法是可行和正確的。

4 結(jié) 論

本文首先建立了的器材揀選作業(yè)的路徑優(yōu)化模型，利用傳統(tǒng)節(jié)約算法計進行貨位揀選的安排決策，分析了傳統(tǒng)節(jié)約算法用于器材揀選作業(yè)中存在的不足，并針對兩點不足進行了改進，使得揀選次數(shù)更少，揀選行走距離更短，為自動化立體器材倉庫的揀選優(yōu)化問題提供了一種新的思路。

[1] 李詩珍.配送中心揀貨作業(yè)優(yōu)化設(shè)計與控制研究[D].成都：西南交通大學(xué) （博士學(xué)位論文），2008:2－4.

[2] 常發(fā)亮，劉増曉，辛征,等.自動化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐，2007(2):139－143.

[3] 于潔，蘇志忠，孫燕飛.蟻群算法在揀貨路徑優(yōu)化中的應(yīng)用研究[J].電腦知識與技術(shù)，2008(4):466－467.

[4] 陳一永，許力.C－K節(jié)約算法在配載車輛調(diào)度問題上的應(yīng)用研究[J].商場現(xiàn)代化，2009(562):149.