李敬峰，葉　艷，傅　惠

(廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006)

?

面向貨物裝卸需求的越庫倉門分配和貨車排序

李敬峰，葉艷，傅惠

(廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006)

摘要：在貨物種類多、批量少的越庫調(diào)度系統(tǒng)中，貨物的裝卸順序要求對于優(yōu)化倉門分配和貨車排序問題起著重要作用。針對這種情況，以最小化越庫操作完工時(shí)間為目標(biāo)，建立越庫調(diào)度模型。分別基于優(yōu)化倉門分配和貨車排序問題，設(shè)計(jì)慣性權(quán)重非線性改變和增加交叉操作的改進(jìn)粒子群算法進(jìn)行迭代尋優(yōu)。最后通過不同規(guī)模的數(shù)值實(shí)驗(yàn)，將改進(jìn)粒子群算法與標(biāo)準(zhǔn)粒子群算法和遺傳算法進(jìn)行對比分析，實(shí)驗(yàn)結(jié)果表明改進(jìn)粒子群算法在求解精度上比標(biāo)準(zhǔn)粒子群算法和遺傳算法有明顯優(yōu)勢，在求解時(shí)間上優(yōu)于遺傳算法，略遜色于標(biāo)準(zhǔn)粒子群算法。

關(guān)鍵詞：越庫； 裝卸要求； 貨車排序； 倉門分配； 粒子群算法

隨著物流技術(shù)的飛快發(fā)展，企業(yè)之間的競爭也越來越激烈，每個(gè)企業(yè)為了提升自己的競爭力，都在尋求一種適合自身發(fā)展的供應(yīng)鏈管理策略，如越庫(cross-docking)、供應(yīng)商管理庫存、物流配送網(wǎng)絡(luò)優(yōu)化等。越庫是一種高效快速的調(diào)度策略，貨物從入庫貨車被直接轉(zhuǎn)運(yùn)至出庫貨車，在越庫中心停留的時(shí)間不超過24 h，有時(shí)甚至?xí)s短到1 h內(nèi)。這不僅加快了顧客響應(yīng)時(shí)間，提高了服務(wù)質(zhì)量，而且也減少了貨物的儲(chǔ)存成本。很多大型企業(yè)(如沃爾瑪、UPS、豐田等[1-3])都已采用越庫策略優(yōu)化供應(yīng)鏈流程，越庫已成為倉庫管理的主流技術(shù)[4]。

越庫策略的成功實(shí)施關(guān)鍵取決于有效的車輛調(diào)度，即貨車的倉門分配和排序決策，它直接決定了入庫貨車和出庫貨車是否最佳協(xié)調(diào)、貨物是否能快速通過越庫中心。目前，國內(nèi)外相關(guān)文獻(xiàn)大多研究單倉門環(huán)境下的越庫車輛調(diào)度。文獻(xiàn)[5]研究兩臺(tái)機(jī)越庫流水車間調(diào)度問題，在證明該問題是NP難問題的基礎(chǔ)上，提出了基于Johnson規(guī)則的啟發(fā)式算法和分支定界算法。文獻(xiàn)[6]研究以帶權(quán)總完工時(shí)間為目標(biāo)的相同問題，提出逆向動(dòng)態(tài)規(guī)劃算法,并證明算法至少可以求解25個(gè)工件規(guī)模的問題。文獻(xiàn)[7]研究了運(yùn)輸時(shí)間非對稱不確定性條件下的越庫調(diào)度問題，以最小化完工時(shí)間為目標(biāo)建立了混合整數(shù)規(guī)劃模型，提出了期望值修正算法和基于修正期望值的啟發(fā)式算法。文獻(xiàn)[8]研究考慮緩存區(qū)的越庫車輛調(diào)度問題，提出9種優(yōu)化車輛停靠順序的排序策略，使停留在緩存區(qū)的貨物總數(shù)最小化，來達(dá)到最小化完工時(shí)間的目的，并設(shè)計(jì)了啟發(fā)式求解算法。文獻(xiàn)[9]采用文獻(xiàn)[8]的算法所得解為起點(diǎn)，提出解決上述問題的差分進(jìn)化算法、遺傳算法、粒子群算法、禁忌搜索算法和蟻群算法，數(shù)值實(shí)驗(yàn)證明所提的差分進(jìn)化算法性能最優(yōu)。文獻(xiàn)[10]則提出兩種組合差分進(jìn)化算法，并證明其優(yōu)于典型的差分進(jìn)化算法。文獻(xiàn)[11]研究以最小化越庫操作總時(shí)間和入庫貨車延遲時(shí)間為目標(biāo)的車輛排序優(yōu)化問題，設(shè)計(jì)了3個(gè)多目標(biāo)算法進(jìn)行求解。

多倉門環(huán)境下的越庫車輛調(diào)度問題研究相對較少。如文獻(xiàn)[12]研究以最小化貨物在越庫中心的傳送距離為目標(biāo)的貨車倉門分配問題，并設(shè)計(jì)分散搜索算法解決問題。文獻(xiàn)[13]研究出庫貨車的離開時(shí)間限于一定時(shí)間窗的入庫貨車調(diào)度問題，提出6種元啟發(fā)式算法，通過數(shù)值實(shí)驗(yàn)說明蟻群算法的性能較好。文獻(xiàn)[14]研究貨物裝卸帶有時(shí)間窗，并且越庫中心容量有限的入庫貨車調(diào)度問題，以最小化操作成本和懲罰成本為目標(biāo)，設(shè)計(jì)禁忌搜索算法和遺傳算法來優(yōu)化問題。文獻(xiàn)[15]對文獻(xiàn)[14]的研究問題進(jìn)行擴(kuò)展，考慮貨車到達(dá)和離開有時(shí)間窗限制，并設(shè)計(jì)自適應(yīng)禁忌搜索算法進(jìn)行求解。文獻(xiàn)[16]和[17]針對入庫和出庫貨車的倉門分配和順序優(yōu)化問題，分別設(shè)計(jì)了鄰域搜索算法和遺傳算法進(jìn)行求解。

越庫車輛調(diào)度的現(xiàn)有文獻(xiàn)都考慮自由裝卸方式，即貨車上的貨物按任意順序裝卸，這比較符合貨物批量大、種類少的情形。隨著顧客需求越來越多樣化，貨物的批量變少而種類變多，貨車單次接收的供應(yīng)商數(shù)量或配送的顧客數(shù)量變多。這時(shí)貨車的取貨、送貨順序通常是固定的，這就決定了入庫貨車和出庫貨車上的貨物存在卸載和裝載順序要求。這不僅增加了倉門分配和車輛調(diào)度的限制因素，使組合優(yōu)化難度增加，而且容易放大由于調(diào)度不當(dāng)引起的各種效率低下現(xiàn)象。例如，造成出庫貨車在裝運(yùn)倉門處等待時(shí)間加長，延長越庫總操作時(shí)間，或者貨物在運(yùn)轉(zhuǎn)中心儲(chǔ)存時(shí)間加長，增加貨物儲(chǔ)存成本等。

本文針對上述實(shí)際問題，首先建立考慮貨物裝卸順序要求的越庫車輛調(diào)度數(shù)學(xué)規(guī)劃模型，并提出改進(jìn)粒子群算法(ω-PSO)進(jìn)行求解。最后通過不同規(guī)模的數(shù)值實(shí)驗(yàn)，把改進(jìn)粒子群算法的求解結(jié)果與標(biāo)準(zhǔn)粒子群算法(PSO)和遺傳算法(GA)的求解結(jié)果進(jìn)行對比分析，驗(yàn)證所建模型的正確性和設(shè)計(jì)算法的有效性。

1問題描述及模型設(shè)計(jì)

1.1問題描述

越庫調(diào)度系統(tǒng)的結(jié)構(gòu)如圖1所示。越庫配送中心有多輛貨車和多個(gè)倉門，并且貨車數(shù)量大于倉門數(shù)量，貨物從入庫貨車上卸載下來，在配送中心進(jìn)行掃描、分揀等操作后，馬上裝運(yùn)到出庫貨車上。貨物的裝卸順序需按照貨物在貨車上的排列順序進(jìn)行，決策者需要決策每輛貨車分配到哪個(gè)倉門，以及貨車按什么次序停靠到指定倉門進(jìn)行卸貨或者裝貨。

圖1　越庫系統(tǒng)結(jié)構(gòu)圖

所研究問題有以下假設(shè)：1)所有倉門同時(shí)只能停靠1輛貨車；2)貨車一旦?？?，需等待貨車上的所有貨物卸載或者裝載完畢后才能離開；3)貨物只有在貨車?？總}門后才可以進(jìn)行裝卸；4)所有貨物的單位卸載或裝載時(shí)間相同；5)每輛貨車同時(shí)只能裝卸1個(gè)貨物；6)每種貨物只有1個(gè)。

1.2數(shù)學(xué)模型

為上述問題建立整數(shù)線性規(guī)劃模型，模型中用到的數(shù)學(xué)符號如下。

M為入庫貨車數(shù)量；

N為出庫貨車數(shù)量；

O為接收倉門數(shù)量；

P為裝運(yùn)倉門數(shù)量；

K為貨物種類數(shù)量；

Sop為貨物從接收倉門o轉(zhuǎn)運(yùn)到裝運(yùn)倉門p所需時(shí)間；

T為完工時(shí)間，從第一輛入庫貨車開始卸載貨物到最后一輛出庫貨車完成裝載貨物的時(shí)間；

d為貨車交換時(shí)間；

t為單位貨物的卸載/裝載時(shí)間；

CTm為入庫貨車m的停靠時(shí)間；

DTn為出庫貨車n的停靠時(shí)間；

FTm為入庫貨車m的離開時(shí)間；

LTn為出庫貨車n的離開時(shí)間；

GTk為貨物k開始卸載的時(shí)間；

HTk為貨物k開始裝運(yùn)的時(shí)間；

Z為一個(gè)大數(shù)；

rmk表示如果入庫貨車m上有貨物k則為1，反之為0；

snk表示如果出庫貨車n上有貨物k則為1，反之為0；

amkk′表示如果貨物k比貨物k′后從入庫貨車m上卸載下來則為1，反之為0；

bnkk′表示如果貨物k比貨物k′后裝上出庫貨車n則為1，反之為0。

決策變量：

ymo表示如果入庫貨車m分配到接收倉門o則為1，反之為0；

znp表示如果出庫貨車n分配到裝運(yùn)倉門p則為1，反之為0；

pmm′o表示如果分配到接收倉門o的入庫貨車m比入庫貨車m′后?？縿t為1，反之為0；

qnn′p表示如果分配到裝運(yùn)倉門p的出庫貨車n比出庫貨車n′后停靠則為1，反之為0。

數(shù)學(xué)模型：

min T。

s.t.

T≥LTn，n=1,2,…,N;

(1)

(2)

(3)

(4)

(5)

(6)

(7)

CTm≥FTm+d-Z1-pmm′o，m,m′=1,2,…,M, o=1,2,…,O;

(8)

DTn≥LTn+d-Z(1-pnn′p)，n,n′=1,2,…,N,

p=1,2,…,P;

(9)

GTk≥GTk+t-Z(1-amkk′)，k,k′=1,2,…,K,

m=1,2,…M;

(10)

HTk≥HTk+t-Z(1-bnkk′)，k,k′=1,2,…,K,

n=1,2,…N;

(11)

GTn≥CTm-Z(1-rmk)，k=1,2,…,K, m=1,2,…,M;

(12)

HTk≥DTN-Z(1-Snk)，k=1,2,…,K, n=1,2,…,N;

(13)

LTn≥HTk+t-Z(1-rmk)，k=1,2,…,K, n=1,2,…,N。

(14)

約束(1)表明完工時(shí)間的取值范圍；約束(2)和(3)保證每輛貨車只可以分配1個(gè)倉門；約束(4)和(5)規(guī)定每個(gè)倉門都必須參與調(diào)度；約束(6)和(7)保證入庫貨車和出庫貨車一旦?？勘仨毜却陨碡浳镅b卸完畢才能離開；約束(8)和(9)表明每個(gè)倉門同時(shí)只可以?？?輛貨車；約束(10)和(11)保證貨物按既定次序裝卸，即每件貨物只能在它之前的貨物卸載或裝載完畢后才開始卸載或裝載；約束(12)、(13)和(14)聯(lián)合定義了貨車之間發(fā)生轉(zhuǎn)運(yùn)關(guān)系的必要條件。

2算法設(shè)計(jì)

2.1標(biāo)準(zhǔn)粒子群算法介紹

粒子群優(yōu)化算法(particle swarm optimization，PSO)模擬鳥群集體覓食的行為，通過粒子之間的協(xié)作，使群體達(dá)到最優(yōu)目標(biāo)。它是一種基于群體迭代的、在解空間里追隨最優(yōu)粒子進(jìn)行搜索的算法。其基本原理是在D維空間中，有Q個(gè)粒子,xi=(xi1,xi2,…,xiD)表示第i個(gè)粒子的位置，把xi代入適應(yīng)函數(shù)f(xi)可求得適應(yīng)值，vi=(vi1,vi2,…,viD)表示第i個(gè)粒子的飛行速度,Pbesti=(Pbesti1,Pbesti2,…,PbestiD)表示第i個(gè)粒子經(jīng)歷過的最好位置,Gbestg=(Gbestg1,Gbestg2,…,GbestgD)表示種群所經(jīng)歷過的最好位置。每一次粒子飛行速度的迭代過程都按照式(15)進(jìn)行更新：

(15)

其中ω為慣性權(quán)重，用來調(diào)節(jié)對解空間的搜索范圍；c1和c2為學(xué)習(xí)因子，用于調(diào)整粒子的自身經(jīng)驗(yàn)與社會(huì)經(jīng)驗(yàn)在其運(yùn)動(dòng)過程中起到的作用；rand()為(0,1)之間均勻分布的隨機(jī)數(shù)，增強(qiáng)搜索的隨機(jī)性；u為當(dāng)代迭代次數(shù)。根據(jù)式(16)可以計(jì)算每個(gè)粒子更新后的位置：

(16)

通常情況下，粒子的飛行速度被限制在[-vmax,vmax]內(nèi)，位置被限制在[-xmax,xmax]內(nèi)，當(dāng)飛行速度或者位置超過這個(gè)值域時(shí)，則取臨界值，防止粒子在迭代過程中飛離搜索空間。

2.2ω-PSO設(shè)計(jì)

2.2.1慣性權(quán)重的改進(jìn)

在粒子群算法中，慣性權(quán)重起著權(quán)衡全局搜索和局部搜索的作用。當(dāng)慣性權(quán)重較大時(shí)，算法傾向于全局搜索，當(dāng)慣性權(quán)重較小時(shí)，算法傾向于局部搜索。為了使算法能夠更好地平衡全局搜索和局部搜索，本文采用動(dòng)態(tài)地改變慣性權(quán)重的方法，達(dá)到動(dòng)態(tài)調(diào)整算法搜索能力的作用。

目前，大多數(shù)文獻(xiàn)針對于慣性權(quán)重的改進(jìn)都是線性的改變，如文獻(xiàn)[18]。但粒子群算法搜索過程是非線性且復(fù)雜的，從全局搜索到局部搜索的線性變化并不能真實(shí)地反應(yīng)搜索全局最優(yōu)解所需的搜索過程[19]。因此，本文對慣性權(quán)重進(jìn)行非線性改進(jìn)，由于算法在前期需要較大的慣性權(quán)重值來擴(kuò)大算法搜索范圍，在后期需要較小的慣性權(quán)重來搜索最優(yōu)解，結(jié)合余弦函數(shù)曲線特性，本文提出慣性權(quán)重按照式(17)進(jìn)行非線性改變的策略來優(yōu)化問題。

(17)

其中ωmax為初始權(quán)重，ωmin為最終權(quán)重，u為當(dāng)代迭代次數(shù)，iteration為最大迭代次數(shù)，本文中ωmax的值為0.9，ωmin的值為0.4，iteration的值為500，ω的動(dòng)態(tài)變化曲線如圖2所示。與線性改變策略相比較，本文提出的改變策略讓慣性權(quán)重在算法初期和后期變化更加平緩，使算法在前期全局搜索能力更強(qiáng)，在后期局部搜索最優(yōu)解能力也更強(qiáng)。

圖2　慣性權(quán)重變化曲線

2.2.2算法編碼

本文按照入庫和出庫兩個(gè)部分對粒子進(jìn)行編碼。對于每個(gè)粒子，位置編碼為兩個(gè)A維向量：Xv和Xr，其中，A對應(yīng)于入庫部分的貨車數(shù)M或出庫部分的貨車數(shù)N，Xv的每一維分別表示每個(gè)貨車分配的倉門編號，Xr的每一維分別表示每個(gè)貨車的?？看涡?，同時(shí)，粒子的速度也編碼成兩個(gè)A維向量Vv和Vr。這種方式雖然使問題的維數(shù)增加，但這并不會(huì)增加改進(jìn)粒子群算法計(jì)算的復(fù)雜性，這一點(diǎn)通過在后文與遺傳算法進(jìn)行對比得以驗(yàn)證。

2.2.3初始解集的建立

位置向量Xv的每一維隨機(jī)取[1,B]之間的整數(shù)，其中，B對應(yīng)于入庫部分的接收倉門數(shù)O或出庫部分的裝運(yùn)倉門數(shù)P。為了滿足模型中每個(gè)倉門都必須參與調(diào)度的約束條件Xv，需包含[1,B]之間的所有整數(shù)，否則，重新初始化該位置向量。位置向量Xr從第1維開始依次在[1,A]之間產(chǎn)生不同的隨機(jī)實(shí)數(shù)，然后，按照這些實(shí)數(shù)從小到大的順序來確定貨車的停靠次序。速度向量Vv的每一維隨機(jī)取[-(B-1),(B-1)]之間的實(shí)數(shù)，Vr的每一維隨機(jī)取[-(A-1),(A-1)]之間的實(shí)數(shù)。這種方式保證初始粒子群的每個(gè)粒子都是可行解，為后續(xù)優(yōu)化減少了不必要的計(jì)算，提高了算法的運(yùn)行效率。

2.2.4整數(shù)規(guī)范原則

基本粒子群算法主要針對連續(xù)函數(shù)進(jìn)行搜索運(yùn)算。而越庫車輛的倉門分配和排序問題屬于離散組合優(yōu)化問題。為此，本文提出整數(shù)規(guī)范原則，對算法進(jìn)行離散化。

在更新粒子位置向量時(shí)，Xv向下取整，Xr按照值從小到大的順序依次重新取值1,2,…,A。例如，8輛貨車、4個(gè)倉門的問題，經(jīng)過迭代后位置向量如表1所示，進(jìn)行整數(shù)規(guī)范后的位置向量如表2所示。它對應(yīng)的解為：貨車1分配到倉門3,停靠次序?yàn)?；貨車2分配到倉門2,?？看涡?yàn)?；貨車3分配到倉門3,?？看涡?yàn)?；貨車4分配到倉門3,?？看涡?yàn)?；貨車5分配到倉門4,?？看涡?yàn)?；貨車6分配到倉門1,停靠次序?yàn)?；貨車7分配到倉門1,?？看涡?yàn)?；貨車8分配到倉門2,?？看涡?yàn)?。

2.2.5修復(fù)策略

在迭代過程中，由于父代粒子飛行的方向和距離具有一定的隨機(jī)性，因此子代中一些粒子的Xv向量可能沒有包含1～B的所有整數(shù)，即有的倉門沒有分配貨車，這種解稱之為非可行解。針對這種情況，本文采用替換策略對非可行解進(jìn)行修復(fù)：首先找出非可行解中未被分配貨車的倉門，然后找出該倉門在粒子局部最優(yōu)解中所分配的貨車及次序，用它們替換掉非可行解中相同位置的部分，最后對因此造成重復(fù)的貨車次序進(jìn)行調(diào)整。假設(shè)粒子i迭代后成為非可行解，如表3所示，倉門2未被分配貨車。該粒子的局部最優(yōu)解如表4所示，將其中的倉門2所分配的貨車及其次序替換掉表3中相同位置的部分，即原來分配到4號倉門的貨車2和貨車5調(diào)整到倉門2，且次序分別修改為3和5。這時(shí)，貨車6和7的次序需要由3和5調(diào)整成4和8。修復(fù)后粒子i的位置向量如表5所示。通過這種方法，在剔除非可行解的同時(shí)也使得粒子從局部最優(yōu)解遺傳到優(yōu)秀信息，提高算法的運(yùn)算效率。

表1　迭代后的位置向量

表2　整數(shù)規(guī)范后的位置向量

表3　粒子i的位置向量

表4 粒子i的局部最優(yōu)解位置向量

表5　修復(fù)后的粒子i的位置向量

2.2.6適應(yīng)值計(jì)算

本文研究的是最小值優(yōu)化問題，完工時(shí)間越短，粒子適應(yīng)值越高。單個(gè)粒子的適應(yīng)值

f(x)=Cmax-T(x)。

(18)

式中,Cmax是預(yù)先指定的一個(gè)較大的數(shù)，T(x)為該粒子完工時(shí)間，其計(jì)算方法詳述如下。

入庫貨車m的?？繒r(shí)間

(19)

在式(19)中，入庫貨車m的?？繒r(shí)間由兩部分組成：1)和入庫貨車m分配在同一個(gè)倉門，且比入庫貨車m先停靠的貨車上貨物的卸載時(shí)間之和；2)入庫貨車m?？恐?，其所在倉門處貨車的交換時(shí)間之和。當(dāng)入庫貨車m為第一個(gè)?？拷邮諅}門時(shí)，CTm的值為0。

在模型中，貨物是連接出庫貨車和入庫貨車的關(guān)鍵因素，在計(jì)算完工時(shí)間時(shí)，貨物的裝卸時(shí)間也起著至關(guān)重要的作用。貨物k開始卸載時(shí)間GTk和開始裝載時(shí)間HTk分別按照式(20)和式(21)計(jì)算。

(20)

HTk=max{φ1,φ2,φ3}。

(21)

其中，

φ1=DTn；

(22)

φ2=HTk′+t；

(23)

φ3=GTk+t+Sop。

(24)

式(20)中，貨物k的開始卸載時(shí)間分兩種情況：

1)若貨物k第1個(gè)從貨車m上卸載時(shí)，其開始卸載時(shí)間為貨車m的?？繒r(shí)間；

2)若貨物k不是第1個(gè)從貨車m上卸載時(shí)，其開始卸載時(shí)間為其前面1個(gè)貨物k′的開始卸載時(shí)間加上貨物k′卸載所需時(shí)間。

式(21)中，貨物k的開始裝載時(shí)間分3種情況：

1)若貨物k在裝運(yùn)倉門處等待被裝載，且它是出庫貨車n的第1件貨物，則它的開始裝載時(shí)間等于出庫貨車n的?？繒r(shí)間，即為φ1；

2)若貨物k在裝運(yùn)倉門處等待被裝載，但不是第1件待裝貨物，則其開始裝載時(shí)間等于其前面一個(gè)貨物的開始裝載時(shí)間加上貨物k′裝載所需時(shí)間，即為φ2；

3)若出庫貨車等待貨物k從接收倉門o轉(zhuǎn)運(yùn)到裝運(yùn)倉門p處再進(jìn)行裝載，則貨物k的開始裝載時(shí)間等于其開始卸載時(shí)間、卸載時(shí)間和倉門間運(yùn)輸時(shí)間之和，即為φ3。φ1、φ2和φ3分別按照式(22)、(23)和(24)計(jì)算。

出庫貨車n的離開時(shí)間按照式(25)計(jì)算。

(25)

式(25)中，出庫貨車n的離開時(shí)間為出庫貨車n上最后一個(gè)貨物k的開始裝載時(shí)間加上該貨物裝載所需時(shí)間。最后一輛出庫貨車的離開時(shí)間即為越庫操作的完工時(shí)間。

2.2.7交叉操作

在粒子群算法中，最優(yōu)個(gè)體控制了種群的搜索方向，所有粒子在飛行過程中都向最優(yōu)個(gè)體靠攏，使得種群容易陷入局部最優(yōu)，為了保持種群的多樣性，本文對粒子進(jìn)行交叉操作。在算法迭代過程中，若全局最優(yōu)粒子Gbestg連續(xù)e代未發(fā)生改變，則根據(jù)每個(gè)粒子適應(yīng)值的大小，把種群分成各占一半的精英種群和交叉種群，并對交叉種群中的粒子進(jìn)行交叉操作，精英種群保持不變，這樣使得算法在搜索過程中恢復(fù)了種群多樣性的同時(shí)也保留了質(zhì)量優(yōu)秀的粒子。交叉過程采用單點(diǎn)交叉方式，例如對粒子i和j進(jìn)行交叉時(shí)，在(1,A)之間隨機(jī)產(chǎn)生1個(gè)整數(shù)f，分別把粒子i的位置向量Xv、Xr和速度向量Vv、Vr中f維之后的部分與粒子j相應(yīng)部分進(jìn)行互換，得到新的粒子i′和j′。

2.2.8 算法步驟

1)初始化問題參數(shù)，生成初始解集；

2)計(jì)算粒子適應(yīng)值，并根據(jù)粒子適應(yīng)值更新局部最優(yōu)解和全局最優(yōu)解；

3)判斷是否滿足交叉操作條件，滿足則進(jìn)行交叉操作，不滿足則直接進(jìn)行下一步操作；

4)根據(jù)式(17)更新慣性權(quán)重ω；

5)根據(jù)式(15)、(16)更新粒子位置和飛行速度(實(shí)數(shù)向量)；

6)把所有粒子位置向量按照整數(shù)規(guī)范原則進(jìn)行修改(整數(shù)向量)；

7)對子代中不可行解進(jìn)行修復(fù)；

8)判斷是否滿足終止條件，滿足則結(jié)束，否則轉(zhuǎn)到步驟2)。

2.3遺傳算法設(shè)計(jì)要點(diǎn)

2.3.1染色體編碼

遺傳算法采用自然數(shù)編碼，根據(jù)所研究問題的特點(diǎn)，構(gòu)造雙層基因染色體，第1層表示貨車順序，第2層表示貨車分配的倉門。圖3為貨車數(shù)為6、倉門數(shù)為2的染色體構(gòu)造示意圖。

圖3染色體構(gòu)造示意圖

Fig.3The sketch map of chromosome

2.3.2交叉和變異

交叉過程采用單點(diǎn)交叉方式，隨機(jī)產(chǎn)生1個(gè)交叉點(diǎn)，將父代染色體劃分為兩部分。針對順序基因?qū)?，子?中的第1部分為父代的第1部分，第2部分由母代中與父代第1部分相異基因組合而成，子代2的產(chǎn)生過程與子代1類似，第1部分為母代第1部分，第2部分由父代中與母代第1部分相異基因而成，圖4(a)和(b)表示了兩個(gè)染色體順序基因?qū)咏徊娌僮鬟^程。針對倉門分配基因?qū)樱哟?由父代第1部分和母代第2部分組成，子代2則相反，如圖4(c)所示。

在變異過程中，順序基因?qū)硬捎没Q變異方式，隨機(jī)選擇兩個(gè)基因位，將它們的值進(jìn)行互換；倉門分配基因?qū)硬捎脝吸c(diǎn)變異方式，隨機(jī)選擇1個(gè)基因位，采用[1,B]之間隨機(jī)產(chǎn)生的異于該基因位原值的隨機(jī)整數(shù)進(jìn)行替換，父代染色體的變異過程如圖5所示。

圖4　交叉操作

圖5　變異操作

3實(shí)例分析

由于本文研究的越庫車輛調(diào)度問題在國際上尚無標(biāo)準(zhǔn)測試數(shù)據(jù)，本文根據(jù)實(shí)際情況隨機(jī)產(chǎn)生大量的實(shí)驗(yàn)數(shù)據(jù)來驗(yàn)證ω-PSO算法的有效性。所有實(shí)驗(yàn)均在Intel Core i3-3240 CPU@3.40GHz 4.0G內(nèi)存的計(jì)算機(jī)上進(jìn)行，算法均用VC++6.0語言編寫。

根據(jù)倉門總數(shù)、貨車總數(shù)、貨物種類數(shù)的不同將問題分為小、中、大3個(gè)規(guī)模，每個(gè)規(guī)模分別用GA、PSO、ω-PSO三種算法進(jìn)行10次獨(dú)立隨機(jī)實(shí)驗(yàn)。3種算法的參數(shù)如表6～8所示，為了保證算法比較的公平性，它們的迭代次數(shù)和種群規(guī)模相同，PSO和ω-PSO算法的學(xué)習(xí)因子、慣性權(quán)重按照文獻(xiàn)[20]的推薦值來選擇，該文獻(xiàn)詳細(xì)論述了選擇過程，本文不再重復(fù)。實(shí)驗(yàn)結(jié)果如表9～11所示，其中BB×AA×K表示該問題規(guī)模為BB個(gè)倉門、AA個(gè)貨車、K種貨物，其中O=P=BB/2，M=N=AA/2。

表6　GA參數(shù)

表7　PSO參數(shù)

表8　ω-PSO參數(shù)

表9　小規(guī)模問題的3種算法結(jié)果

表10　中等規(guī)模問題的3種算法結(jié)果

表11　大規(guī)模問題的3種算法結(jié)果

從表9～11可以看出，對于小規(guī)模算例，改進(jìn)粒子群算法在求解質(zhì)量上與標(biāo)準(zhǔn)粒子群算法和遺傳算法相差不大，都可以找到最優(yōu)解，在求解時(shí)間上改進(jìn)粒子群算法和標(biāo)準(zhǔn)粒子群算法基本一致，但優(yōu)于遺傳算法；對于中等規(guī)模算例，改進(jìn)粒子群算法在求解質(zhì)量上的表現(xiàn)最為突出，在求解時(shí)間上的表現(xiàn)要稍遜于標(biāo)準(zhǔn)粒子群算法，但仍然優(yōu)于遺傳算法；對于大規(guī)模問題，改進(jìn)粒子群算法的表現(xiàn)基本與中等規(guī)模一致。為了更加直觀地比較改進(jìn)粒子群算法相對于標(biāo)準(zhǔn)粒子群算法在求解質(zhì)量和時(shí)間上的改善，本文定義了兩者之間的求解質(zhì)量Gap1和求解時(shí)間Gap2，計(jì)算公式如下：

(26)

(27)

式中，PSO1和PSO2表示標(biāo)準(zhǔn)粒子群算法的平均完工時(shí)間和平均求解時(shí)間，ω-CPSO1和ω-CPSO2表示改進(jìn)粒子群算法的平均完工時(shí)間和平均求解時(shí)間。中等規(guī)模和大規(guī)模問題下相對Gap值如表12所示，可以看出，改進(jìn)粒子群算法與標(biāo)準(zhǔn)粒子群算法相比，求解質(zhì)量上的優(yōu)勢相對于求解時(shí)間上的劣勢要突出很多。

表12　標(biāo)準(zhǔn)粒子群算法與改進(jìn)粒子群算法相對Gap

為了更加清晰地表現(xiàn)3種算法的性能差異，本文選用大規(guī)模問題(倉門總數(shù)24，貨車總數(shù)140，貨物種類數(shù)700)繪制它們的進(jìn)化曲線圖，如圖6所示，縱坐標(biāo)表示完工時(shí)間，橫坐標(biāo)表示迭代次數(shù)。由圖6可知，標(biāo)準(zhǔn)粒子群算法和遺傳算法都較早陷入了局部最優(yōu)，而改進(jìn)粒子群算法的迭代曲線是不斷下降的，因此，改進(jìn)粒子群算法擁有較強(qiáng)的跳出局部最優(yōu)的能力，且在進(jìn)化初期更趨向于全局搜索，與預(yù)期目標(biāo)一致。

圖6　3種算法進(jìn)化曲線圖

4結(jié)束語

在越庫調(diào)度過程中，將貨物的實(shí)際裝卸順序要求考慮在內(nèi)，使得車輛調(diào)度研究更加貼近現(xiàn)實(shí)，對實(shí)際運(yùn)作具有十分重要的指導(dǎo)意義。本文研究了一種考慮貨物裝卸順序要求的越庫倉門分配和貨車排序優(yōu)化問題，建立以最小化完工時(shí)間為目標(biāo)的整數(shù)線性規(guī)劃模型，并提出改進(jìn)粒子群算法進(jìn)行求解。通過數(shù)值實(shí)驗(yàn)表明所提算法與標(biāo)準(zhǔn)粒子群算法和遺傳算法相比，在求解質(zhì)量上有明顯優(yōu)勢，尤其在倉門數(shù)、貨車數(shù)和貨物種類數(shù)較多的情況下，優(yōu)勢更加顯著。在以后的研究中，將進(jìn)一步考慮貨車以中斷和非中斷方式?？康脑綆靷}門分配和車輛排序優(yōu)化問題。

參考文獻(xiàn)：

[1]STALK G, EVANS P, SHULMAN L E. Competing on capabilities: the new role of corporate strategy[J]. Harvard Business Review, 1992, 70(2): 57-69.

[2]FORGER G. UPS starts world’s premiere cross-docking operation[J]. Modern Material Handling, 1995, 11(1):36-38.

[3]CE W. Cross docking: concepts demand choice[J]. Material Handling Engineering, 1998, 53(7): 44-49.

[4]鳳偉.越庫:未來倉庫管理的主流[J].科技資訊.2008, 31(1):167.

FENG W. Cross-docking system: the main technology of future warehouse management[J]. Science & Technology Information, 2008,31(1):167.

[5]CHEN F, LEE C Y. Minimizing the makespan in a two-machine cross-docking flow shop problem[J]. European Journal of Operational Research, 2009, 193(1): 59-72.

[6]馬東彥,陳峰.以總?cè)旯r(shí)間為目標(biāo)的兩臺(tái)機(jī)越庫排序的動(dòng)態(tài)規(guī)劃算法[J].上海交通大學(xué)學(xué)報(bào),2007,41(5):852-856.

MA D Y,Chen F.Dynamic programming algorithm on two machines cross docking scheduling with total weighted completion time[J]. Journal of Shanghai Jiaotong University, 2007, 41(5):852-856.

[7]陳杰，陳峰.非對稱不確定性越庫調(diào)度算法[J]．上海交通大學(xué)學(xué)報(bào),2010,44(9):1302-1306.

CHEN J,CHEN F.Algorithm on cross docking scheduling in asymmetrically uncertain environment[J]. Journal of Shanghai Jiaotong University, 2010, 44(9):1302-1306.

[8]YU W, EGBELU P J. Scheduling of inbound and outbound trucks in cross docking systems with temporary storage[J]. European Journal of Operational Research， 2008,184(1): 377-396.

[9]BOLOORI Arabani A R, FATEMI Ghomi S M T, ZANDIEH M. Meta-heuristics implementation for scheduling of trucks in a cross-docking system with temporary storage[J]. Expert Systems with Applications, 2011, 38(1):1964-1979.

[10]LIAO T W, EGBELUA P G, CHANG P C. Two hybrid differential evolution algorithms for optimal inbound and outbound truck sequencing in cross docking operations[J]. Applied Soft Computing, 2012, 12(1):3683- 3697.

[11]BOLOORI Arabani A R, ZANDIEH M, FATEMI Ghomi S M T. A cross-docking scheduling problem with sub-population multi-objective algorithms[J]. International Journal of Advanced Manufacturing Technology, 2012,58(1): 741-761.

[12]TARHINI A, MAKKI J, CHAMSEDDING M M J. Scatter search algorithm for the cross-dock door assignment problem[C/OL]. (2014-04-13). http://ieeexplore.ieee.org/stamp/stamp.jsp? tp=&arnumber=6820575.

[13]LIAO T W, EGBELUA P G, CHANG P C. Simultaneous dock assignment and sequencing of inbound trucks under a fixed outbound truck schedule in multi-door cross docking operations[J]. Int. J. Production Economics, 2013, 141(1): 212-229.

[14]MIAO Z W, LIM A, MA H. Truck dock assignment problem with operational time constraint within crossdocks[J]. European Journal of Operational Research，2009, 192(1):105-115.

[15]MIAO Z W, CAI S, XU D. Applying an adaptive tabu search algorithm to optimize truck-dock assignment in the crossdock management system[J]. Expert Systems with Applications, 2014, 41(1):16-22.

[16]KUO Y. Optimizing truck sequencing and truck dock assignment in a cross docking system[J]. Expert Systems with Applications, 2013,40(14): 5532-5547.

[17]LEE K, KIM B S, JOO C M. Genetic algorithms for door-assigning and sequencing of trucks at distribution centers for the improvement of operational performance[J]. Expert Systems with Applications, 2012, 39(1):12975-12973.

[18]余小兵. 基于改進(jìn)粒子群算法的多目標(biāo)應(yīng)急物資調(diào)度[J]. 工業(yè)工程,2014,17(3):18-21.

YU X B. Multi-objective emergency supplies scheduling based on improved particle swarm optimization[J]. Industrial Engineering Journal, 2014, 17(3):18-21.

[19]紀(jì)震,廖惠連,吳青華.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社,2009:21.

[20]EBERHART R, SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization[C/OL].(2000-07-16).http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=870279.

A Research on Dock Assignment and Truck Sequence in a Cross-docking System Considering the Unloading/Loading Sequences of Cargos

LI Jingfeng, YE Yan, FU Hui

(School of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China)

Abstract：In a cross-docking system with a wide variety and small batches of cargos, the practical requirement of cargos′ unloading/loading sequences plays an important role in the optimization of dock assignment and truck sequence. Under this situation, a new scheduling model to minimize the makespan of cross-docking operations is proposed, and an improved particle swarm algorithm for the proposed model is designed to optimize the dock assignment and the truck sequence. Many numerical experiments are conducted on instances with different scales by using genetic algorithm, standard particle swarm algorithm and improved particle swarm algorithm. Computational results of the three algorithms are compared and it is shown that the proposed algorithm performs better in solution accuracy than standard particle swarm algorithm and genetic algorithm. Its computing time is shorter than that of genetic algorithm and slightly longer than that of standard particle swarm algorithm.

Key words：cross-docking; unloading/loading requirement; truck sequence; dock assignment; particle swarm algorithm

收稿日期：2015- 11- 04

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(71302135，61104167)

作者簡介：李敬峰(1990-)，男，湖北省人，碩士研究生，主要研究方向?yàn)樵綆煺{(diào)度.

doi:10.3969/j.issn.1007- 7375.2016.02.017

中圖分類號：F253.4

文獻(xiàn)標(biāo)志碼：A

文章編號：1007-7375(2016)02- 0112- 09