葛 陽，王曉峰， 郝 冰，寧劍平 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）器材擺放位置可視為貨格的中心點上，貨位坐標(biāo)為（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)化的目標(biāo)就是尋求一條最短的揀選路徑。當(dāng)揀選器材較多時，受揀貨箱容積和承重的限制 （對于小件器材一般只考慮貨箱容積的限制），可能無法一次完成揀選作業(yè)，需要分多次進(jìn)行，因此，巷道車在整個揀選作業(yè)過程中所行走的距離就是進(jìn)行每一次揀選路徑的距離之和。

目標(biāo)函數(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表示縱向的行走距離。由于巷道車一般有兩個電機(jī)驅(qū)動，一個負(fù)責(zé)橫向移動，另外一個負(fù)責(zé)縱向移動，所以這里認(rèn)為巷道車行走的距離就是巷道車在橫向和縱向行走的距離之和。

約束條件：

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

揀選第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的坐標(biāo) ）。從巷道口開始揀選貨位Pi和Pj，有兩種方案，一是一次性完成兩個貨位的揀選后回到巷道口，二是往返兩次分別揀選這兩個貨位，前者比后者行走距離的節(jié)約量為：

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

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

由于同一種器材可能存放于多個貨位，入庫年份也可能不同，如果隨機(jī)揀選，入庫較早的器材可能一直不被揀選到，隨時間推移，器材過了保質(zhì)期就難免報廢，造成浪費(fèi)。所以，首先要根據(jù) “先進(jìn)先出” （或 “用舊存新”）原則及式 （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é)約算法的不足及改進(jìn)

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

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

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

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

按改進(jìn)的節(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種器材，隨機(jī)產(chǎn)生調(diào)撥單和器材貨位對照表如表1所示 （為簡化計算這里認(rèn)為器材體積可直接相加）。要求制定揀選計劃，使得揀選距離最短。

3.1 確定待揀貨位

根據(jù) “先進(jìn)先出”原則和調(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 改進(jìn)節(jié)約算法求解

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

表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加入當(dāng)前揀選序列，此時器材體積為8+2×3=14，揀貨箱仍未裝滿，在貨位16、17、7有關(guān)的組合中查找最大節(jié)約量為16、8貨位，將貨位8加入當(dāng)前揀選序列，此時揀貨箱只能再揀選貨位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）中的步驟進(jìn)行，直至所有待揀貨位全部合并，可以確定第二次揀選的貨位 （數(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 改進(jìn)節(jié)約算法決策結(jié)果

3.5 結(jié)果分析

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

4 結(jié) 論

本文首先建立了的器材揀選作業(yè)的路徑優(yōu)化模型，利用傳統(tǒng)節(jié)約算法計進(jìn)行貨位揀選的安排決策，分析了傳統(tǒng)節(jié)約算法用于器材揀選作業(yè)中存在的不足，并針對兩點不足進(jìn)行了改進(jìn)，使得揀選次數(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.