一、物流配送中心揀貨作業簡介
1 物流配送中心揀貨作業
1.1 問題描述
雙區型倉庫一般是由一定數量的等長巷道組成，巷道兩側的貨架上存放着需要揀取的各種物品。橫向有三條過道，不同于單區型倉庫（single-block warehouse）的是：除巷道上下兩端分别有過道外，中間還有一條過道（如圖1中的過道b），而單區型倉庫缺少中間這條過道。據相關文獻分析，該條中間過道在提高大型倉庫揀選效率方面有很大幫助[8,11,12]。
整個倉庫平面圖如圖1所示，I/O為倉庫的出入口，每個小方格代表一個貨物儲位，填充部分表示按某訂單需揀取的貨物所在的儲位，上面的數組{x-y-z}代表對應的儲位标号，其中x表示該所在的揀貨巷道号，取值為1～10;y表示該儲位位于巷道x的左邊還是右邊（1表示位于左邊，2表示位于右邊）；z表示為該儲位所在的行号（從下往上數），取值為1～40。例如：{5-2-26}表示該儲位位于倉庫中第5号巷道右邊的第26行。
由于在本文設計的倉庫中揀貨巷道的寬度并不太寬，面對巷道時，揀貨人員可以進行雙側取貨，即對同一巷道中左右兩邊取貨時揀貨人員移動的距離可以忽略。
圖1 雙區型倉庫平面圖
為訂單揀貨的時間可分成行走（步行或駕駛車輛）時間、搜尋時間、分揀時間等。按照Tompkins[13]的研究，行走時間常常占揀貨時間的一半（見圖2），可見，縮短行走距離對減少總的揀貨時間作用很大。而所選的路徑對行走路線長度和行走時間有直接的影響，是以，應該把路徑選擇作為提高揀貨效率的一項重要的内容。
1.2 問題分類
由于揀貨人員使用的推車的容量（或載重量）有限，本文将處理後的揀貨訂單的揀貨方式分成一單一車和一單多車兩種類型。
一單一車指的是某個揀貨訂單中所需的全部貨物可以由一輛推車來回一次從倉庫中一次全部取回，而不會超出推車的最大容量（或載重量）的情況。
一單多車指的是某個揀貨訂單中的所需的全部貨物必須通過一輛推車來回多次才能全部從倉庫中取回，即該訂單上的所有貨物的總體積（或總品質）已經超過了一輛推車的最大容量（或載重量）的情況。
1.3 模型建立
一單多車揀貨路徑問題主要考慮怎樣将訂單中所需貨物配置設定到多個車次中揀取，使其總的揀貨路徑最優，該類問題類似于運籌學中的車輛路徑問題（Vehicle Routing Problem,VRP），也稱車輛排程問題（Vehicle Scheduling Problem,VSP）。
VRP的一般描述是：對一系列給定的客戶點，要求确定适當的車輛行駛路線，使其從車場（如配送中心等）出發，有序地對它們進行服務，并在滿足一定的限制條件下（如車輛載重量、客戶需求量、時間窗限制等），使總運輸成本達到最小（如使用車輛數最少，車輛行駛總距離最短等）[14,15]。
結合VRP的數學模型設計了一單多車揀貨路徑問題的數學模型。
(1）問題假設。現需y次車都從一個共同的源點（倉庫出入口IO）出發，需要到倉庫中不同的儲位中去提取貨物。假設儲位為v1,v2，…，vm。并且源點和儲位的位置是已知的，考慮到倉庫中推車成本較低并且可重複使用，是以本問題不将車次數最小作為優化目标。
(2）模型目标。每一車次構成一個回路，确定每條回路内的路徑安排和排程，使得所有回路的總行走距離S最小。
(3）變量說明。Qij：第i次車在其子回路上對應的第j個儲位的取貨量；li：第i條回路上的儲位數；ci：第i次車對應的路徑；cij：第i次車對應的子回路中順序為j的儲位點；i：每次車對應的編号；W：推車最大載重量；V：訂單上所需揀取的貨物總重量；m：訂單中貨物在倉庫中的儲位數；v0：源點；y：需要的車次數；S：總行走距離；di(j-1)j：第i次車對應的路線中順序排列的第j-1個儲位和第j個儲位之間的最短距離；di(li）(0）：第i次車對應的路線中第li個儲位與源點v0之間的最短距離。
(4）建立模型
模型中，式（1）為目标函數，即最短的總行走距離；式（2）為推車的能力限制，即每個子回路中從儲位揀取的貨物的總量，保證每次車從儲位中揀取的貨物的總量不超過推車的最大載重量；式（3）表示揀取完訂單所需的全部貨物；式（4）～式（7）表示從每個待揀儲位有且僅能取貨一次；式（8）表示第i次車是否有揀貨任務。
當訂單上全部貨物品質小于推車總的載重量W時，即就是式（2）中的W足夠大，該數學模型表示一單一車情況下揀貨路徑模型。
2 遺傳算法求解揀貨路徑問題
2.1 算法流程
基于遺傳算法的揀貨路徑問題優化算法流程如圖3所示。
圖3 求解揀貨路徑問題的遺傳算法流程圖
2.2 确定編碼方案
對于一單一車的境況，采用自然數編碼方式，先對訂單上的貨物對應在倉庫中的存儲位置（儲位）按順序依次進行自然數編号，然後用這些儲位點編号所組成的自然數序清單示揀貨路徑。其具體表示方法如下：
設訂單中的有4種貨物需要從倉庫中揀取，這4種貨物分布在倉庫中4個儲位位置上。則可以用0表示倉庫出入口，從1至4的4個自然數分别依次表示一個儲位。假設該訂單的揀貨路徑如下：
路徑：出入口0→儲位點1→儲位點4→儲位點2→儲位點3→出入口0
遺傳算法所表示的自然數系列為：{0 1 4 2 3 0}。
考慮到一單多車情況下揀貨路徑問題中訂單上的揀取任務可能要通過多次車次才能完成，為了在可行解中展現出多車次的特點，将對應的自然數序列插入相應的零來展現多車特點。具體方法如下：
設訂單中的有7種貨物需要從倉庫中揀取，這7種貨物分布在倉庫中7個儲位位置上。則可以用0表示倉庫出入口，從1至7的7個自然數分别依次表示一個儲位。假設該訂單的揀貨路徑如下：
路徑1：出入口0→儲位點1→儲位點5→儲位點7→儲位點4→出入口0
路徑2：出入口0→儲位點2→儲位點3→儲位點6→出入口0
遺傳算法所表示的自然數系列為：{0 1 5 7 4 0 2 3 6 0}。
其中0的作用有兩點：一是表示實際的路程起始點（即本題中的倉庫出入口IO），二是用來分隔GA編碼。具體分隔的方法是：首先得到一個不含0的可行自然數序列{1 5 7 4 2 3 6}，再從左邊開始，每次加入一點，直到加入下一個點就超出車輛裝載能力限制為止，按所加入的點的先後順序排列，得到一條子路徑，即就是得到第一次車次的揀貨任務，比如{1 5 7 4}。再從未加入的點繼續該過程，獲得下一條子路徑。重複此過程至所有點均被選入為止，比如{2 3 6}。再在可行自然數序列中插入相應的0将個子路徑分隔開來，于是得到了染色體編碼{01 5 7 4 0 2 3 6 0}。
當染色體要進行下面的交叉、變異和“進化逆轉”操作時，可先将染色體編碼中表示多車的0去掉，算子操作完成後再按上面分隔編碼方法插入相應的0得到相應的染色體。
2.3 确定适應度函數
問題的适應度函數取為哈密爾頓圈的長度的倒數（無懲罰函數），但是為了避免适應度過小，本文将該函數乘上一個起調節作用的系數，系數值為：
處理後的新适應度函數如下：
其中maxdd為訂單中待揀貨物所在的儲位點之間的最大距離，lchrom為編碼後的染色體的長度，即路徑中經過儲位點數（包括出入口結點），X為對應可行解的揀貨路徑長度。
2.4 選擇（或複制）算子和交叉算子的設計
在文中用随機生成方法産生初始解群。然後按适應度比例方法（輪盤賭選擇）從父代中每次挑選兩個個體，以相應的機率參加交叉變異操作。
具體的交叉操作如下：
(1）随機在串中選擇一個交配區域，如兩父串交配區標明為：
(2）将B的交配區域加到A的前面或後面，A的交配區域加到B的前面或後面得到：
(3）在A′中自交配區域後依次删除與交配區相同的儲位号碼，得到最終的兩個子串為：
與其它方法相比，這種方法在兩父串相同的情況下也能産生一定程度的變異效果，能維持群體的多樣化特征。
2.5 變異算子的設計
由于後面将引入了“進化逆轉”操作技術，為保持群體内個體的多樣化，本文采用連續多次對換的變異技術，使可行解有較大的順序排列上的變化，以抑制“進化逆轉”的同化作用。變異操作發生的機率取值比較小（本文設計變異操作發生機率Pm的取值為0.008），一旦變異操作發生，則用随機方法産生交換次數為K（本文設計K的取值為1～100的随機整數），對所需變異操作的染色體進行K次對換（對換的兩碼位也是随機産生的）。最後為保持群體内個體的多樣化，在文中還采用了一種對解的擾動政策——最好解連續50代不變時則随機産生新的個體20個來替換20個随機抽取的舊個體[16]。
2.6“進化逆轉”算子的設計
本文使用的“進化逆轉”是一種單方向的（朝着改進的方向）和連續多次的“逆轉”操作，即對于給定的染色體，若“逆轉”使染色體（可行解）的适應度提高，則執行逆轉操作，否則就放棄。如此反複，直到不存在這樣的逆轉操作為止。這一操作實際上使給定的染色體改良到它的局部極點，這種局部爬山能力與基本遺傳算法的全局搜尋能力相結合在實驗中顯示了較好的效果。
為了盡量避免算法出現“早熟”現象，在進化初期，控制“進化逆轉”算子使用機率，確定算法能在全局範圍内尋優；但是到了進化後期，為了加快算法局部爬山能力，加大該算子的使用機率。具體在程式設計中處理如下：
其中Pm*為“進化逆轉”算子的操作發生機率，gen表示遺傳進化代數。
二、部分源代碼
clear all;
close all;
clc;
W=[0 0;10 15;10 20;10 70;10 85;20 5;20 95;30 70;45 75;45 85;50 55;60 60;70 70;70 85;70 95;75 20;75 45;80 5;80 45;90 75;95 90];
weight=[92 77 77 59 100 40 61 96 80 37 80 52 82 63 51 52 95 92 54 60];
NP=300;
D=20;
M=4;
fit=zeros(NP,D+M);
%fit
gen=0;
G=100;
N=size(W,1);
Dis=zeros(N);
fitness=zeros(1,NP);
pc=0.05;
pm=0.03;
bestg=[];
aa=100;%懲罰系數
fbestfitness=[];
for i=1:N
for j=1:N
Dis(i,j)=((W(i,1)-W(j,1))2+(W(i,2)-W(j,2))2)^0.5;
end
end
for i=1:NP
fit(i,:)=randperm(D+M);
rr1=find(fit(i,:)(D+1));
rr2=find(fit(i,:)(D+2));
rr3=find(fit(i,:)(D+3));
rr4=find(fit(i,:)(D+4));
fit(i,rr1(1,1))=0;
fit(i,rr2(1,1))=0;
fit(i,rr3(1,1))=0;
fit(i,rr4(1,1))=0;
end
dfitness=[];
sumfitness=0;
while gen<G
for i=1:NP
fitness(i)=fun1(fit(i,:),Dis,N,D,weight,aa,M);
end
maxfitness=max(fitness);
tt=find(fitness==maxfitness);
fit(NP,:)=fit(tt(1,1)😅;
fit(NP-5,:)=fit(tt(1,1)😅;
fit(NP-10,:)=fit(tt(1,1)😅;
fit(NP-20,:)=fit(tt(1,1)😅;
fit(NP-30,:)=fit(tt(1,1)😅;
%fitness
maxfitness=max(fitness);
minfitness=min(fitness);
sumfitness=sum(fitness);
fitvalue=fitness./sumfitness;
fitvalue1=cumsum(fitvalue);
ms=sort(rand(1,NP));
fiti=1;
newi=1;
fi=[];
n=[];
while newi<=NP
if (ms(newi))<fitvalue1(fiti)
fi(newi,:)=fit(fiti,:);
newi=newi+1;
else
fiti=fiti+1;
end
end
%%%%%%基于機率的交叉操作%%%%%%
%fi
temp=[];temp1=[];
index=randperm(NP);
fi=fi(index,:);
%fi
u=1;
for i=1:2:(NP-1)
for j=1:(D+M)
if rand<pc
pp=find(fi(i+1,:)==fi(i,j));
pp1=find(fi(i,:)==fi(i+1,j));
temp=fi(i,j);
fi(i,j)=fi(i+1,j);
fi(i+1,j)=temp;
temp1=fi(i,pp1(1,1));
fi(i,pp1(1,1))=fi(i+1,pp(1,1));
fi(i+1,pp(1,1))=temp1;
u=u+1;
end
end
end
%u
%fi
%%%%%%基于機率的變異操作%%%%%%
z=0;
for i=1:NP
if rand<pm
for j=1:ceil((D+M)/10)
r1=ceil((D+M)*rand);
z=fi(i,r1);
fi(i,r1)=ceil((D+M)*rand);
rr=find(fi(i,:)==fi(i,r1));
fi(i,rr(1,1))=z;
end
end
end
三、運作結果
四、matlab版本及參考文獻
1 matlab版本
2014a