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

張海軍，張 博，岳溥庥，郭 風

ZHANG Haijun,ZHANG Bo,YUEPuxiu,GUO Feng

北京物資學院 信息學院，北京 101149

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

1 引言

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

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

圖3 堆垛機在多巷道中揀選俯視圖

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

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

圖4 倉庫俯視示意圖

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

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

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

3 倉庫平面布置圖的數據存儲及需求點間路徑計算

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

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

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

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

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

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

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

4.1 編碼方案的確定

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

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

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

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

4.2 初始種群的確定

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

4.3 適應度計算

以個體“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，可以看到，由于揀選設備的容量Q=100，第一個揀選作業(yè)超過了揀選設備的容量，定義一個懲罰系數Pe=100來對違反揀選設備容量約束的情況進行懲罰，假設這三次揀選作業(yè)的總的行走距離為D，則該染色體的函數值為Fv=D+(101-100)×100，這個函數值越大，適應度值越小。為了避免較優(yōu)的個體迅速繁殖而使得遺傳算法過早收斂，這里采用基于函數值從小到大線性排序來計算適應度的方法。種群中最小函數值的個體適應度為2，最大距離的個體適應度為0，假設一個個體 j的排序為Pos，種群大小為N，則其適應度為：

4.4 選擇操作

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

4.5 交叉操作

新個體進行兩兩配對，按交叉概率Pc進行雙點交叉重組。

（1）隨機在兩個個體中選擇一個交配區(qū)域，如兩個個體及交配區(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”，其中兩個“|”之間的部分為交配區(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有重復，這時，找到交叉區(qū)域中基因1在A中的等位基因8，用它替換交叉區(qū)域前的重復基因1。得到：A′=“10，8，2，|1，4，8，6，3，|11，5，4，7”，然后，查找交叉區(qū)域后面部分與交叉區(qū)域相同的基因，可以發(fā)現基因4有重復，這時，找到交叉區(qū)域中基因4在A中的等位基因9，用這個基因替換交叉區(qū)域后的重復基因 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”，這幾個重復基因8、6、3在 A 中對應的等位基因為6、3、12，記D=“6，3，12”，然后去除C 與 D中的重復基因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”。對于B'用相同的方法替換重復基因，最后得到兩個新的個體為：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 變異操作

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

4.7 重插入操作

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

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

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

4.9 實驗參數的選擇

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

表1 參數選擇對比

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

5 實驗評測

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

5.1 實驗設計

隨機產生一個含有25個需求點的訂單（見圖4中標記的25個需求點），25個貨位編號分別為：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，各個貨位的需求量為 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，揀選設備容量限制為100，該訂單已知的最優(yōu)揀選路徑長度為184。

5.2 各算法實驗結果的比較

對于設定的某一群體規(guī)模和迭代次數隨機進行8次重復實驗，實驗結果見表2所示。

表2 各算法實驗結果

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

其中，v是粒子的速度，persent是粒子的當前位置，pbest是該粒子所經歷過的最好位置，gbest是整個種群當前獲得的最好位置，rand是介于0、1之間的隨機數。實驗中學習因子c1、c2設置為2，較大的慣性因子w適于對解空間進行大范圍探查，較小的w適于進行小范圍開挖。實驗中w設置為隨迭代次數的增加而逐漸變小：w=0.9-0.7×gn/gnmax，其中gn為當前代數，gnmax為設置的迭代次數。

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

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

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

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

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

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

6 結論

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

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

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

[2]常發(fā)亮，劉增曉.自動化立體倉庫揀選作業(yè)路徑優(yōu)化問題研究[J].系統(tǒng)工程理論與實踐，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]胡運權，郭耀煌.運籌學教程[M].3版.北京：清華大學出版社，2007.

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

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

[8]雷英杰.MATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，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].計算機工程與應用，2002，38（2）：1-3.

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

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

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