基于混合遺傳算法的多巷道間移動(dòng)揀選優(yōu)化

張海軍，張 博，岳溥庥，郭 風(fēng)

ZHANG Haijun,ZHANG Bo,YUEPuxiu,GUO Feng

北京物資學(xué)院 信息學(xué)院，北京 101149

School of Information,Beijing Wuzi University,Beijing 101149,China

1 引言

倉庫揀選作業(yè)是企業(yè)中最為頻繁的生產(chǎn)活動(dòng)之一，采購入庫的商品、配件需要倉庫作業(yè)人員分門別類地放置在貨架上，出庫的一單商品、配件需要作業(yè)人員從貨架中取出。許多大型倉庫、配送中心采用高層貨架式立體倉庫，相鄰兩排貨架之間有一條巷道，每條巷道有一臺(tái)堆垛機(jī)，堆垛機(jī)可以同時(shí)沿垂直方向和水平方向移動(dòng)，存取巷道兩側(cè)垂直貨架上的貨物，如圖1所示：0點(diǎn)為巷道出入口，a、b、c、d、e、f為垂直貨架上的幾個(gè)取貨點(diǎn)，堆垛機(jī)一次可以揀選若干個(gè)貨位上的貨物，然后返回到0點(diǎn)將貨箱放置到傳送系統(tǒng)上。以往的研究主要是針對(duì)堆垛機(jī)在單一巷道內(nèi)垂直貨架上的揀選作業(yè)進(jìn)行優(yōu)化，劉臣奇等[1]提出一種蟻群算法，對(duì)取貨點(diǎn)的存取順序進(jìn)行優(yōu)化，以使得作業(yè)時(shí)間最短。但是，該方法假定堆垛機(jī)一次作業(yè)可以揀選所有取貨點(diǎn)的貨物，沒有考慮堆垛機(jī)所攜帶的貨箱的容量限制，針對(duì)這一問題，常發(fā)亮等[2]提出一種遺傳算法，在堆垛機(jī)一次作業(yè)容量受限的情況下，針對(duì)垂直貨架上的多個(gè)取貨點(diǎn)，安排若干次揀選作業(yè)使得總的揀選代價(jià)最?。ㄈ鐖D2所示），圖2中表示兩次揀選作業(yè)，第一次的揀選順序?yàn)?-a-e-f-0，第二次揀選順序?yàn)?-b-c-d-0。對(duì)于堆垛機(jī)需要行進(jìn)到其他巷道中進(jìn)行揀選的問題，該方法不能夠解決，當(dāng)然，對(duì)于自動(dòng)化立體倉庫，一般每個(gè)巷道都有一臺(tái)堆垛機(jī)，負(fù)責(zé)揀選該巷道兩側(cè)貨架上的貨物，某一巷道的堆垛機(jī)不需要行進(jìn)到其他巷道進(jìn)行揀選。但是，在某些情況下，需要一臺(tái)堆垛機(jī)揀選多個(gè)巷道中的貨物，李梅娟等[3]對(duì)此問題進(jìn)行了研究，如圖3所示，堆垛機(jī)從0點(diǎn)出發(fā)，依次揀選巷道1、巷道2、…、巷道 j兩側(cè)貨架中的貨物，而后返回到0點(diǎn)，在揀選過程中，堆垛機(jī)所攜帶的貨箱容量有限，裝滿一箱貨物就返回到0點(diǎn)把貨物放置到傳送系統(tǒng)上，并且，前一巷道的揀選作業(yè)全部完成后才能進(jìn)入下一巷道進(jìn)行作業(yè)。以上這些方法主要優(yōu)化的是堆垛機(jī)在垂直高層貨架中取貨時(shí)在垂直作業(yè)面上的移動(dòng)距離。

圖2 巷道堆垛機(jī)在垂直貨架上的兩次存取作業(yè)示意圖

圖3 堆垛機(jī)在多巷道中揀選俯視圖

對(duì)于需要在多個(gè)巷道間移動(dòng)揀選，揀選作業(yè)需要優(yōu)化的主要是揀選作業(yè)人員水平移動(dòng)距離的情況下，以上的方法都不適用。例如超市、網(wǎng)店、書店、藥店以及需要堆垛設(shè)備在多巷道間移動(dòng)揀選的立體倉庫的補(bǔ)貨發(fā)貨作業(yè)。本文是對(duì)這種情況下的訂單揀選進(jìn)行優(yōu)化，以指導(dǎo)工作人員沿最短的揀選路線進(jìn)行作業(yè)以節(jié)省揀選時(shí)間和揀選費(fèi)用。圖4為這種情況下倉庫俯視示意圖，圖中標(biāo)記了某一訂單所涉及到的25個(gè)貨位，每個(gè)貨位取貨量不一，揀選設(shè)備的容量有限，如何安排揀選作業(yè)，使得這個(gè)訂單總的揀選路線最短。

本文的主要?jiǎng)?chuàng)新點(diǎn)有：第一，針對(duì)多巷道中移動(dòng)揀選問題，通過引入節(jié)點(diǎn)來減少直接計(jì)算各貨位間最短路徑的計(jì)算量。第二，使用混合遺傳算法結(jié)合Lin-Kernighan算法來實(shí)現(xiàn)訂單揀選的優(yōu)化，實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于粒子群優(yōu)化算法。

圖4 倉庫俯視示意圖

2 揀選路徑優(yōu)化的數(shù)學(xué)模型

假設(shè)某一訂單涉及到需要揀選的貨位數(shù)為n個(gè)，貨位編號(hào)從1到n，編號(hào)為0代表配貨點(diǎn)。第i個(gè)貨位點(diǎn)的需求量為qi，揀選設(shè)備的容量為Q，任一個(gè)貨位點(diǎn)的需求量都不大于揀選設(shè)備的容量Q。由此可知，該訂單所需揀選作業(yè)次數(shù)不超過n，假設(shè)需要n次揀選作業(yè)，每次揀選作業(yè)使用同樣的容量為Q的揀選設(shè)備。文獻(xiàn)[4]所給出的數(shù)學(xué)模型中揀選作業(yè)次數(shù)沒有明確指定，不利于對(duì)問題的理解，借鑒文獻(xiàn)[4]給出的模型，建立了以下數(shù)學(xué)模型見公式（1）~（9）。

其中cij為從貨位i到貨位 j的旅行距離。=1表示第v次揀選作業(yè)將先訪問貨位i而后緊接訪問貨位j，即i和 j之間構(gòu)成第v次揀選路線中的一邊，否則，=0。q為貨位i的需求量；Q為第v次揀選作業(yè)的iv可載容量。式（1）表明了優(yōu)化目標(biāo)是總的揀選路徑最短。約束（2）、（3）表示每個(gè)需求點(diǎn)必須且只能被揀選一次。約束（4）表示每次揀選作業(yè)經(jīng)過的路線必須是連續(xù)的，即某次揀選作業(yè)到達(dá)某個(gè)需求點(diǎn)時(shí)也必須離開這個(gè)需求點(diǎn)，并且最終構(gòu)成一個(gè)揀選回路。約束（5）表示每次揀選作業(yè)所服務(wù)的需求點(diǎn)的總需求量不超過該次揀選設(shè)備的容量。約束（6）表示每次揀選作業(yè)所使用的揀選設(shè)備容量相同，都為Q。約束（9）表示每次揀選作業(yè)消，也即總的實(shí)際的揀選次數(shù)小于n。從模型可以看出，此問題是一個(gè)NP-hard問題，需要尋求啟發(fā)式的方法來解決。

3 倉庫平面布置圖的數(shù)據(jù)存儲(chǔ)及需求點(diǎn)間路徑計(jì)算

倉庫的主要元素可以分為：巷道、貨位、節(jié)點(diǎn)、障礙物。巷道是存取商品的供揀選作業(yè)人員行走的通道，假定只有縱向和橫向兩種直線巷道。節(jié)點(diǎn)是縱向巷道和橫向巷道的交叉點(diǎn)。貨位是存儲(chǔ)貨物的單元，存取這個(gè)貨位中的貨物必需在特定的位置，有的貨位取貨位置在它靠近的左邊巷道，有的在位于其右側(cè)的巷道，有的在其他巷道。為了生成并存儲(chǔ)這些元素的信息，把倉庫平面分成若干行和列，行列交叉位置為一倉庫單元格，這個(gè)倉庫單元格可以是一個(gè)巷道單元也可以是貨位單元，因此，需要“倉庫單元格”這樣的一種數(shù)據(jù)結(jié)構(gòu)來記錄每個(gè)倉庫單元格的信息，它是一個(gè)矩陣，矩陣的第m行第n列的元素值為1，表示倉庫的第m行第n列的單元格為一貨位，并且取貨位置在上方巷道；值為2表示為貨位，取貨位置在下方巷道；值為3表示為貨位，取貨位置在左邊巷道；值為4表示為貨位，取貨位置在右邊巷道；值為5表示此單元格為一巷道單元；值為6表示為一障礙物單元?？梢砸詧D形化的界面讓用戶確定倉庫各單元的信息。

“倉庫單元格”矩陣記錄下了每個(gè)倉庫單元的信息，由此可以計(jì)算出所有的貨位、巷道和節(jié)點(diǎn)。一個(gè)巷道上的兩個(gè)相鄰的節(jié)點(diǎn)為鄰接節(jié)點(diǎn)，如圖5所示，E與C、C與 A、A與 B、B與 D、D 與 F、F與 E、C 與 D、C 與G、G與H互為鄰接節(jié)點(diǎn)。先計(jì)算出鄰接節(jié)點(diǎn)間的最短距離，構(gòu)成節(jié)點(diǎn)鄰接矩陣，鄰接節(jié)點(diǎn)間的最短距離是這兩個(gè)節(jié)點(diǎn)在同一巷道中相隔的倉庫單元的數(shù)量，如A和B這兩個(gè)鄰接節(jié)點(diǎn)的距離為6，鄰接矩陣中的第i行第 j列的值k如果不為無窮大，則表示第i個(gè)節(jié)點(diǎn)與第 j個(gè)節(jié)點(diǎn)鄰接，且它們之間揀選距離為k。由于節(jié)點(diǎn)的數(shù)量不大，可以在節(jié)點(diǎn)鄰接矩陣的基礎(chǔ)上用Floyd算法[5]計(jì)算出所有節(jié)點(diǎn)間的最短距離，并存儲(chǔ)這個(gè)所有節(jié)點(diǎn)間的最短距離矩陣以及相應(yīng)的路徑信息。

一個(gè)貨位的取貨點(diǎn)是巷道上的一個(gè)單元，如圖5所示，貨位13、14的取貨點(diǎn)為其緊鄰的右側(cè)巷道上的巷道單元，貨位25的取貨點(diǎn)是其緊鄰的左側(cè)巷道上的巷道單元。一個(gè)貨位最多有兩個(gè)與其鄰接的節(jié)點(diǎn)，如圖5所示，貨位13的鄰接節(jié)點(diǎn)是E和F，貨位14的鄰接節(jié)點(diǎn)是 A和 B，貨位25的鄰接節(jié)點(diǎn)是C和 D，貨位1、2、3的鄰接節(jié)點(diǎn)是G和H。在計(jì)算任意兩個(gè)貨位之間的最短揀選距離時(shí)，把這兩個(gè)貨位的鄰接節(jié)點(diǎn)間的最短距離再加上貨位到其鄰接節(jié)點(diǎn)的最短距離即可得到這兩個(gè)貨位之間的最短揀選距離（如果這兩個(gè)貨位的鄰接節(jié)點(diǎn)相同，則直接計(jì)算這兩個(gè)貨位間的歐氏距離即可）和揀選路徑。如圖5所示，要計(jì)算貨位1和14之間的最短揀選距離，可以借助貨位1的兩個(gè)鄰接節(jié)點(diǎn)G和H與貨位14的兩個(gè)鄰接節(jié)點(diǎn)A和B之間的交叉距離，具體計(jì)算見公式（10）：

其中Dist(i，j)表示i與 j之間的最短距離，任意兩個(gè)節(jié)點(diǎn)間的最短距離已經(jīng)事先計(jì)算了出來，貨位與其鄰接節(jié)點(diǎn)的最短距離也很容易求得，因此，公式（10）計(jì)算量不大。在計(jì)算一個(gè)訂單所涉及的貨位之間的最短距離時(shí)，可以臨時(shí)計(jì)算。

圖5 貨位鄰接節(jié)點(diǎn)示意圖

4 遺傳算法求解訂單揀選路徑

遺傳算法（Genetic Algorithm，GA）是Holland教授[6]最早提出的，是求解復(fù)雜組合優(yōu)化問題的有效方法，典型的遺傳算法主要包括選擇、交叉、變異三個(gè)基本的遺傳算子，其中交叉操作是遺傳算法的主要搜索手段，是影響算法收斂性及搜索效率的關(guān)鍵因素，常用的交叉操作有單點(diǎn)交叉和雙點(diǎn)交叉，雙點(diǎn)交叉能更有效地離散雜交子代群體，更有利于尋找到最優(yōu)解[7]，因此，采用雙點(diǎn)交叉的交叉運(yùn)算。在染色體適應(yīng)度值的計(jì)算以及重插入的操作中，使用了文獻(xiàn)[8]中所講述的英國設(shè)菲爾德（Sheffield）大學(xué)的MATLAB遺傳算法工具箱中的有關(guān)函數(shù)。

4.1 編碼方案的確定

定理1假設(shè)揀選設(shè)備容量為Q，一個(gè)訂單所涉及的需求點(diǎn)個(gè)數(shù)為n，每個(gè)需求點(diǎn)的需求量不大于Q，總的需求量為P，則使總揀選路徑最短的揀選作業(yè)次數(shù)K滿足公式（11）：

而總的需求量為P，總的揀選量W不可能大于P＋B。因此，肯定存在某一揀選作業(yè) j的載貨量不大于Q-B。那么可以把揀選作業(yè)i的最后一個(gè)需求點(diǎn)與作業(yè) j的第一個(gè)需求點(diǎn)連接，合并揀選，將得到更短的揀選路徑。

另一方面，需求點(diǎn)的個(gè)數(shù)為n個(gè)，每個(gè)需求點(diǎn)的需求量不大于Q，因此，最優(yōu)揀選次數(shù)K不超過n。而顯然的，得證。

假設(shè)揀選設(shè)備的容量為Q，某訂單所涉及的需求點(diǎn)為n個(gè)，這些需求點(diǎn)的總需求量為P。由定理1得，過引入K-1個(gè)虛擬需求點(diǎn)（即配貨點(diǎn)Depot，它的貨位編號(hào)設(shè)為0）來構(gòu)造一個(gè)染色體。假設(shè)Q=100，n＝8，該訂單所涉及到的需求點(diǎn)的貨位編號(hào)為“138，4，9，330，40，30，55，149”，這8個(gè)貨位各自取貨量分別為：64，34，14，29，16，27，12，3。可計(jì)算得 K=5，即需要4個(gè)虛擬需求點(diǎn)。用自然數(shù)列“1，2，3，4，5，6，7，8”代表這8個(gè)貨位，用9，10，11，12代表4個(gè)虛擬需求點(diǎn)。形如“10，1，2，8，9，6，3，12，11，5，4，7”的染色體表示進(jìn)行了三次揀選作業(yè)，這三次揀選作業(yè)的揀選路線分別為：“0-138-4-149-0”，“0-30-9-0”和“0-40-330-55-0”。在將一個(gè)染色體映射到一個(gè)訂單的多個(gè)揀選作業(yè)時(shí)，染色體的首尾視為各存在一個(gè)虛擬需求點(diǎn)，表示從配貨點(diǎn)出發(fā)以及返回到配貨點(diǎn)，另外，將兩個(gè)及兩個(gè)以上的連續(xù)的虛擬需求點(diǎn)視為一個(gè)虛擬需求點(diǎn)。按照此編碼方案，通過引入K-1個(gè)虛擬節(jié)點(diǎn)，可以涵蓋揀選次數(shù)從1到K的該訂單的可能的揀選情況。由定理1可知，染色體的長度確定為L=n+K-1，它所形成的L維空間涵蓋了最優(yōu)解空間。引入更多的虛擬點(diǎn)也即假設(shè)更多的揀選作業(yè)次數(shù)只會(huì)擴(kuò)大問題的維數(shù)，增大無用的搜索空間，不利于提高解的質(zhì)量和收斂速度。

4.2 初始種群的確定

以上面的訂單為例，該訂單涉及到貨位編號(hào)為“138，4，9，330，40，30，55，149”，把其映射到1~8的8個(gè)自然數(shù)，而后再加入 4個(gè)虛擬節(jié)點(diǎn)9，10，11，12，隨機(jī)產(chǎn)生1~12這12個(gè)整數(shù)的一個(gè)排列，這個(gè)排列即為一個(gè)個(gè)體。設(shè)種群規(guī)模為N，則隨機(jī)產(chǎn)生N個(gè)這樣的個(gè)體，即形成初始群體。

4.3 適應(yīng)度計(jì)算

以個(gè)體“10，1，2，8，9，6，3，12，11，5，4，7”為例，它表示的揀選路線分別為：“0-138-4-149-0”，“0-30-9-0”和“0-40-330-55-0”。這三次揀選作業(yè)各自的揀選量分別為：64+34+3=101，27+14=41和 16+29+12=57，可以看到，由于揀選設(shè)備的容量Q=100，第一個(gè)揀選作業(yè)超過了揀選設(shè)備的容量，定義一個(gè)懲罰系數(shù)Pe=100來對(duì)違反揀選設(shè)備容量約束的情況進(jìn)行懲罰，假設(shè)這三次揀選作業(yè)的總的行走距離為D，則該染色體的函數(shù)值為Fv=D+(101-100)×100，這個(gè)函數(shù)值越大，適應(yīng)度值越小。為了避免較優(yōu)的個(gè)體迅速繁殖而使得遺傳算法過早收斂，這里采用基于函數(shù)值從小到大線性排序來計(jì)算適應(yīng)度的方法。種群中最小函數(shù)值的個(gè)體適應(yīng)度為2，最大距離的個(gè)體適應(yīng)度為0，假設(shè)一個(gè)個(gè)體 j的排序?yàn)镻os，種群大小為N，則其適應(yīng)度為：

4.4 選擇操作

采用賭輪選擇法產(chǎn)生下一代90%的個(gè)體。首先計(jì)算上代群體中所有個(gè)體適應(yīng)度的總計(jì)算每此作為其被選擇的概率。然后，采用賭輪選擇法選擇相應(yīng)的個(gè)體進(jìn)入下一代。這里，設(shè)置代溝為0.9，即每一代中有10%的最優(yōu)個(gè)體直接復(fù)制到下一代中。

4.5 交叉操作

新個(gè)體進(jìn)行兩兩配對(duì)，按交叉概率Pc進(jìn)行雙點(diǎn)交叉重組。

（1）隨機(jī)在兩個(gè)個(gè)體中選擇一個(gè)交配區(qū)域，如兩個(gè)個(gè)體及交配區(qū)域選定為：A=“10，1，2，|8，9，6，3，12，|11，5，4，7”，B=“5，7，2，|1，4，8，6，3，|11，12，9，10”，其中兩個(gè)“|”之間的部分為交配區(qū)域。

（2）將A和B的交配區(qū)域交換，得：A′=“10，1，2，|1，4，8，6，3，|11，5，4，7”，B′=“5，7，2，|8，9，6，3，12，|11，12，9，10”。

（3）去重。以 A′為例，先查找交叉區(qū)域前面部分與交叉區(qū)域中基因相同的基因，可以看到基因1有重復(fù)，這時(shí)，找到交叉區(qū)域中基因1在A中的等位基因8，用它替換交叉區(qū)域前的重復(fù)基因1。得到：A′=“10，8，2，|1，4，8，6，3，|11，5，4，7”，然后，查找交叉區(qū)域后面部分與交叉區(qū)域相同的基因，可以發(fā)現(xiàn)基因4有重復(fù)，這時(shí)，找到交叉區(qū)域中基因4在A中的等位基因9，用這個(gè)基因替換交叉區(qū)域后的重復(fù)基因 4，得到：A′=“10，8，2，|1，4，8，6，3，|11，5，9，7”。接著，檢查 A′的交叉區(qū)域與 A 中交叉區(qū)域有相同的基因8、6、3，記 C=“8，6，3”，這幾個(gè)重復(fù)基因8、6、3在 A 中對(duì)應(yīng)的等位基因?yàn)?、3、12，記D=“6，3，12”，然后去除C 與 D中的重復(fù)基因6和3得到C=“8”，D=“12”。接著把 A′中交叉區(qū)域前后含有C的那些基因替換為C在D中的等位基因。該例中，可以看到A′交叉區(qū)域前面部分含有C中的基因“8”，把其改為 D中的基因“12”，而 A′交叉區(qū)域后面部分不含有C 中基因。因此，最后可以得到 A′=“10，12，2，|1，4，8，6，3，|11，5，9，7”。對(duì)于B'用相同的方法替換重復(fù)基因，最后得到兩個(gè)新的個(gè)體為：A′=“10，12，2，|1，4，8，6，3，|11，5，9，7”，B′=“5，7，2，|8，9，6，3，12，|11，1，4，10”。

4.6 變異操作

變異概率設(shè)置為 Pm ，以個(gè)體 A=“10，1，2，8，9，6，3，12，11，5，4，7”為例，當(dāng)該個(gè)體發(fā)生變異時(shí)，隨機(jī)選擇一個(gè)變異片段，假設(shè)為 A=“10，1，2，|8，9，6，3，12，|11，5，4，7”，其中兩個(gè)“|”之間部分為即將變異的片段。翻轉(zhuǎn)這個(gè)片段得到變異后的個(gè)體 A′=“10，1，2，|12，3，6，9，8，|11，5，4，7”。

4.7 重插入操作

為了保證遺傳算法能夠收斂，把父代中最優(yōu)的10%的個(gè)體直接插入到新產(chǎn)生的下一代中。

4.8 使用LK算法對(duì)各代最優(yōu)個(gè)體后優(yōu)化

使用以上所給的遺傳算法，對(duì)一個(gè)含有25個(gè)需求點(diǎn)的訂單進(jìn)行了多次實(shí)驗(yàn)，發(fā)現(xiàn)即使群體規(guī)模設(shè)為500，迭代100次以后，在一些最優(yōu)個(gè)體所表示的解中揀選路線仍存在不必要的折回往返情況，種群規(guī)模設(shè)為500，迭代200次后才基本可以收斂到已知最優(yōu)解。為了避免這種情況發(fā)生，進(jìn)一步優(yōu)化解的質(zhì)量，引入了LK（Lin_Kernighan）算法對(duì)各代的最優(yōu)個(gè)體進(jìn)行后優(yōu)化。LK算法是S.Lin和B.W.Kernighan于1973年在文獻(xiàn)[9]中最早提出的，它是在r-opt算法上發(fā)展來的，是求解TSP問題的非常有效的啟發(fā)式算法，原始的LK算法在求解50個(gè)城市的TSP問題時(shí)，只需一次計(jì)算幾乎就能100%地找到最優(yōu)解[10]，而改進(jìn)的LK算法[10-11]通過相應(yīng)的策略來構(gòu)造替換邊集以減少路徑判斷和交換次數(shù)，進(jìn)而可以以更高的效率求解頂點(diǎn)數(shù)過萬的大規(guī)模的TSP問題。由于一個(gè)揀選訂單所涉及的需求點(diǎn)一般不會(huì)很多，分解成多個(gè)揀選作業(yè)后，每一條哈密爾頓回路所涉及的需求點(diǎn)更少，因此，本文使用基本的LK算法對(duì)各代的最優(yōu)個(gè)體中的多個(gè)揀選作業(yè)（即多個(gè)哈密爾頓回路）進(jìn)行優(yōu)化，而后重新計(jì)算該個(gè)體的適應(yīng)度值，并把其復(fù)制到下一代中，以此來提高解的質(zhì)量，把本文的這種算法命名為GA-LK算法。之所以僅僅對(duì)各代的最優(yōu)個(gè)體進(jìn)行后優(yōu)化是考慮到算法的運(yùn)行時(shí)間問題，是在解的質(zhì)量和運(yùn)行效率之間的折衷。

4.9 實(shí)驗(yàn)參數(shù)的選擇

根據(jù)經(jīng)驗(yàn)值，一般交叉概率Pc的取值在0.4~0.99，變異概率Pm的取值在0.000 1~0.1[8]。選取交叉概率Pc和變異概率Pm的3個(gè)組合進(jìn)行測(cè)試，分別為Pc=0.6，Pm=0.05；Pc=0.8，Pm=0.1；Pc=0.9，Pm=0.1；之所以選擇較大的變異概率是因?yàn)榭紤]到路徑優(yōu)化的特殊性以及本文中染色體變異的特定操作是反轉(zhuǎn)特定的染色體片段，而根據(jù)以前的實(shí)驗(yàn)，發(fā)現(xiàn)有些路徑存在往復(fù)等情況，反轉(zhuǎn)染色體片段會(huì)在一定程度上解決此問題。每個(gè)組合對(duì)于特定的種群規(guī)模和迭代次數(shù)進(jìn)行了3次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表1所示。

表1 參數(shù)選擇對(duì)比

從以上實(shí)驗(yàn)結(jié)果可以看出，當(dāng)設(shè)置較大的初始種群和迭代次數(shù)時(shí)參數(shù)選擇Pc=0.6，Pm=0.05所獲得的平均揀選路徑較短，也即可以以較大的概率獲得更好的解。而當(dāng)設(shè)置較小的初始種群和迭代次數(shù)時(shí)，參數(shù)選擇Pc=0.8，Pm=0.1可以以較大的概率獲得更好的解。由于希望算法執(zhí)行的更快些，因此，本文最終選擇Pc=0.8，Pm=0.1。

5 實(shí)驗(yàn)評(píng)測(cè)

在這一部分，就第4部分提出的GA-LK算法與粒子群優(yōu)化算法[12]以及遺傳粒子群算法[13-15]進(jìn)行了對(duì)比。為了具有可比性，將粒子群算法及遺傳粒子群算法每代的最優(yōu)個(gè)體也進(jìn)行了后優(yōu)化，也即使用LK算法對(duì)其進(jìn)行了優(yōu)化。

5.1 實(shí)驗(yàn)設(shè)計(jì)

隨機(jī)產(chǎn)生一個(gè)含有25個(gè)需求點(diǎn)的訂單（見圖4中標(biāo)記的25個(gè)需求點(diǎn)），25個(gè)貨位編號(hào)分別為：186、98、116、48、217、52、54、26、141、143、47、222、36、225、37、31、138、220、65、234、126、30、45、169、5，各個(gè)貨位的需求量為 16、19、17、18、11、18、2、2、14 、3、13、20、6、11、6、7、13、17、4、8、4、9、10、15、3，揀選設(shè)備容量限制為100，該訂單已知的最優(yōu)揀選路徑長度為184。

5.2 各算法實(shí)驗(yàn)結(jié)果的比較

對(duì)于設(shè)定的某一群體規(guī)模和迭代次數(shù)隨機(jī)進(jìn)行8次重復(fù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表2所示。

表2 各算法實(shí)驗(yàn)結(jié)果

表2中，PSO-LK為粒子群LK算法，即在粒子群算法的每次迭代后，用LK算法優(yōu)化每代的最優(yōu)解；GA-PSO-LK為遺傳粒子群LK算法。PSO-LK算法中的粒子速度更新公式為（15），位置更新公式為（16）：

其中，v是粒子的速度，persent是粒子的當(dāng)前位置，pbest是該粒子所經(jīng)歷過的最好位置，gbest是整個(gè)種群當(dāng)前獲得的最好位置，rand是介于0、1之間的隨機(jī)數(shù)。實(shí)驗(yàn)中學(xué)習(xí)因子c1、c2設(shè)置為2，較大的慣性因子w適于對(duì)解空間進(jìn)行大范圍探查，較小的w適于進(jìn)行小范圍開挖。實(shí)驗(yàn)中w設(shè)置為隨迭代次數(shù)的增加而逐漸變?。簑=0.9-0.7×gn/gnmax，其中g(shù)n為當(dāng)前代數(shù)，gnmax為設(shè)置的迭代次數(shù)。

GA-PSO-LK算法是對(duì)GA-LK算法在交叉階段進(jìn)行了修改，在每一代的交叉階段以交叉概率1進(jìn)行交叉，不是兩兩隨機(jī)配對(duì)進(jìn)行交叉操作，而是將該個(gè)體與歷史上全局最優(yōu)個(gè)體進(jìn)行交叉，然后再與該個(gè)體所經(jīng)歷的最好個(gè)體進(jìn)行交叉以期望獲得更好的后代，而后根據(jù)變異概率Pm=0.1進(jìn)行變異，然后再用LK算法對(duì)每代的最優(yōu)解再次優(yōu)化。

從表2可以看出，對(duì)于GA-LK算法，當(dāng)實(shí)驗(yàn)群體規(guī)模設(shè)置為200，迭代次數(shù)為100時(shí)，實(shí)驗(yàn)8次得到的平均解與已知的最優(yōu)解相差不過7%，可基本收斂到已知的最優(yōu)解，圖6是這8次實(shí)驗(yàn)中最成功的1次實(shí)驗(yàn)所獲得的最優(yōu)解的進(jìn)化情況，從圖6可以看到，初始隨機(jī)產(chǎn)生200個(gè)個(gè)體中最好的揀選路線長度大概為360，經(jīng)過100次迭代后最優(yōu)揀選路徑長度為186，節(jié)省了近一半的揀選長度，說明算法應(yīng)用于實(shí)際訂單揀選時(shí)將是有效的。圖7是這次實(shí)驗(yàn)所獲得的最優(yōu)個(gè)體所表示的揀選路徑，從圖7可以看出該訂單需要分解為三次揀選作業(yè)，圖7中需求點(diǎn)旁邊所注的編號(hào)為這個(gè)需求點(diǎn)在這個(gè)揀選作業(yè)中的作業(yè)次序號(hào)，用以引導(dǎo)操作人員進(jìn)行揀選作業(yè)，對(duì)于一個(gè)大的訂單，分解成較多揀選作業(yè)的情況，可以依次將每個(gè)揀選作業(yè)的路徑繪制在移動(dòng)終端上，當(dāng)作業(yè)人員完成了本次揀選作業(yè)后再繪制下一個(gè)作業(yè)的揀選路徑，或者將該訂單的多個(gè)揀選作業(yè)路徑分別繪制在多個(gè)揀選作業(yè)人員的移動(dòng)終端上以引導(dǎo)多個(gè)作業(yè)人員同時(shí)對(duì)一個(gè)訂單進(jìn)行揀選。從圖7可以看出最優(yōu)揀選路徑中的各揀選作業(yè)不存在多余的折回往返情況。

圖6 最優(yōu)解進(jìn)化情況

圖7 訂單最優(yōu)揀選路徑

表2的實(shí)驗(yàn)結(jié)果表明，PSO-LK算法表現(xiàn)出過早收斂，隨著種群規(guī)模擴(kuò)大及迭代次數(shù)增加解的質(zhì)量改進(jìn)不大，解的質(zhì)量普遍差于GA-LK算法。而GA-PSO-LK算法獲得的解的質(zhì)量稍差于GA-LK算法。這兩種粒子群算法都不如GA-LK算法，可能是因?yàn)閱栴}的維數(shù)較大，粒子在高維空間中的移動(dòng)僅僅共享了全局最優(yōu)位置，而相互之間沒有交換更多的信息。PSO-LK算法是讓粒子向著種群當(dāng)前最優(yōu)解位置以及該粒子所經(jīng)歷的最好位置的夾角中某一方向移動(dòng)，而更好的位置并非一定位于這一夾角之中，而GA-PSO-LK算法中借鑒了GA算法的交叉操作使得新的位置可以跳出這一夾角，擴(kuò)大了搜索的范圍導(dǎo)致解的質(zhì)量較好。

揀選設(shè)備的容量限制主要有兩個(gè)維度，一個(gè)是容積，一個(gè)是載重量。而揀選作業(yè)既要滿足揀選設(shè)備容積限制又要滿足載重量限制，在計(jì)算訂單的最大揀選次數(shù)K時(shí)，分別從容積和載重量這兩個(gè)方面來計(jì)算，而后取較大的那個(gè)數(shù)再乘以一個(gè)大于1的經(jīng)驗(yàn)系數(shù)作為最大揀選次數(shù)。在計(jì)算一個(gè)染色體的函數(shù)值時(shí)是該染色體對(duì)應(yīng)的路徑長度加上這兩個(gè)維度上的懲罰值作為該染色體的函數(shù)值，依據(jù)此函數(shù)值計(jì)算該染色體的適應(yīng)度值。在大多數(shù)實(shí)際應(yīng)用中，根據(jù)實(shí)際問題的特點(diǎn)，只需關(guān)注某一維度的限制即可，例如對(duì)于載重量大的揀選設(shè)備只需關(guān)注它的容積限制，對(duì)于體積小而較重的物品只需關(guān)注揀選設(shè)備的載重量限制。

6 結(jié)論

訂單揀選是物流業(yè)中最為頻繁的作業(yè)之一，并非所有的行業(yè)都適合采用自動(dòng)化立體倉庫，對(duì)于需要在橫豎不一的各巷道間移動(dòng)揀選的情況，本文給出了一種解決方法，實(shí)驗(yàn)結(jié)果表明此方法是可行有效的，它可以對(duì)超市、書店等場(chǎng)合的配貨和補(bǔ)貨作業(yè)進(jìn)行路徑優(yōu)化。

容量限制的訂單揀選問題屬于CVRP（Capacitated Vehicle Routing Problem）問題，對(duì)于大規(guī)模的CVRP問題，遺傳算法的初始群體需要更好的設(shè)計(jì)，另外在迭代中盡量避免產(chǎn)生不符合約束的解，并且迭代中產(chǎn)生的符合約束條件的解盡量分散于解空間中以避免過早收斂，但這也會(huì)增加算法的時(shí)間復(fù)雜度和空間復(fù)雜度。對(duì)于更大規(guī)模的CVRP問題需要設(shè)計(jì)更高效的啟發(fā)式算法，在求解結(jié)果與所花費(fèi)時(shí)間代價(jià)之間進(jìn)行折衷，這也是下一步的努力方向。

[1]劉臣奇，李梅娟，陳雪波.基于蟻群算法的揀選作業(yè)優(yōu)化問題[J].系統(tǒng)工程理論與實(shí)踐，2009（3）：179-184.

[2]常發(fā)亮，劉增曉.自動(dòng)化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究[J].系統(tǒng)工程理論與實(shí)踐，2007（2）：139-143.

[3]李梅娟，陳雪波，王莉.多巷道固定貨架揀選作業(yè)優(yōu)化問題的研究[J].控制與決策，2008（12）：1338-1342.

[4]Filipec M，Skrlec D，Slavko K.An efficient implementation of genetic algorithms for constrained vehicle routing problem[C]//Proceedings of IEEE International Conference on System，Man and Cybernetics，1998.

[5]胡運(yùn)權(quán)，郭耀煌.運(yùn)籌學(xué)教程[M].3版.北京：清華大學(xué)出版社，2007.

[6]Holland J H.Adaptation and artificial systems[M].Ann Arbor：University of Michigan Press，1975.

[7]徐洪澤，陳桂林，張福恩.遺傳算法的單雙點(diǎn)雜交方法對(duì)比研究[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，1998（4）：64-71.

[8]雷英杰.MATLAB遺傳算法工具箱及應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2005.

[9]Lin S，Kernighan B W.An efficient heuristic algorithm for the traveling salesman problem[J].Operations Research，1973，21：498-516.

[10]Helsgaun K.An effective implementation of the Lin-Kernighan traveling salesman heuristic[J].European Journal of Operational Research，2000，126：106-130.

[11]Walshaw C.A multilevel lin-kernighan-helsgaun algorithm for the travelling salesman problem[R]//Mathematics Research Report，2001-09-27.

[12]李愛國，覃征.粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（2）：1-3.

[13]呂振肅，侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報(bào)，2004（3）：416-420.

[14]高尚，韓斌.求解旅行商問題的混合粒子群優(yōu)化算法[J].控制與決策，2004（11）：1286-1289.

[15]劉衍民，牛奔，趙慶禎.基于交叉和變異的多目標(biāo)粒子群算法[J].計(jì)算機(jī)應(yīng)用，2011（1）：82-84.