吳秀麗，張雅琦

(北京科技大學(xué) 機(jī)械工程學(xué)院，北京 100083)

0 引言

近年來(lái)，為了滿(mǎn)足不斷提升的物流需求，配送中心的自動(dòng)化與智能化建設(shè)發(fā)展迅速。配送中心主要指為下游客戶(hù)提供配送、倉(cāng)儲(chǔ)、流通加工等服務(wù)的物流活動(dòng)場(chǎng)所。每天都有大量的配送車(chē)輛到達(dá)配送中心，并進(jìn)行裝卸貨作業(yè)，為提高車(chē)輛的裝卸貨效率，配送中心一般都建有月臺(tái)。配送中心的月臺(tái)也稱(chēng)站臺(tái)，一般指進(jìn)行裝卸貨物作業(yè)的高于地面的平臺(tái)，是配送中心的重要設(shè)施。月臺(tái)相較于車(chē)輛所在地面有一定高度，工作人員進(jìn)行裝卸貨物作業(yè)時(shí)減少了搬運(yùn)的高度差，使得裝卸貨物更加高效、省力，因此，月臺(tái)已成為配送中心的標(biāo)配。

月臺(tái)在配送中心系統(tǒng)中起著重要的作用，是倉(cāng)庫(kù)與運(yùn)輸車(chē)輛進(jìn)行裝卸貨物作業(yè)的資源交匯處，處于配送中心物流系統(tǒng)的咽喉位置，是連接配送中心中倉(cāng)庫(kù)與配送車(chē)輛的關(guān)鍵節(jié)點(diǎn)，是貨物進(jìn)出倉(cāng)庫(kù)必經(jīng)之路[1]。由此可見(jiàn)，月臺(tái)影響著物流運(yùn)作效率[1]和供應(yīng)鏈的整體運(yùn)作效率，所以配送中心需要特別重視對(duì)月臺(tái)的科學(xué)管理。月臺(tái)調(diào)度管理旨在根據(jù)配送車(chē)輛的月臺(tái)預(yù)約信息和可用的月臺(tái)資源合理地為車(chē)輛安排作業(yè)月臺(tái)與作業(yè)時(shí)間，使月臺(tái)與運(yùn)輸車(chē)輛之間的作業(yè)更加緊密、有序地進(jìn)行。如果沒(méi)有進(jìn)行合理的月臺(tái)調(diào)度管理，會(huì)給倉(cāng)庫(kù)與運(yùn)輸人員雙方造成困擾。對(duì)于倉(cāng)庫(kù)，如果沒(méi)有事先掌握月臺(tái)的占用情況、車(chē)輛的到達(dá)時(shí)間、貨物的裝卸作業(yè)進(jìn)程等信息，沒(méi)有進(jìn)行合理的月臺(tái)調(diào)度，從而合理安排倉(cāng)庫(kù)的出入庫(kù)作業(yè)、月臺(tái)資源分配，容易造成月臺(tái)裝卸貨作業(yè)忙閑不均，不能充分地利用人力、設(shè)備資源；對(duì)于運(yùn)輸人員，如果沒(méi)有事先進(jìn)行月臺(tái)調(diào)度，可能會(huì)需要長(zhǎng)時(shí)間滯留排隊(duì)等待作業(yè)，導(dǎo)致無(wú)效挪車(chē)、道路擁堵，甚至可能引發(fā)人員沖突。而在根據(jù)月臺(tái)、運(yùn)輸車(chē)輛作業(yè)的相關(guān)信息進(jìn)行合理的月臺(tái)調(diào)度后，對(duì)于倉(cāng)庫(kù)便可以實(shí)現(xiàn)月臺(tái)人力、設(shè)備資源的高效率利用，對(duì)于運(yùn)輸車(chē)輛可以實(shí)現(xiàn)高效裝卸貨作業(yè)。

然而，目前我國(guó)配送中心的月臺(tái)仍舊主要采取人工搬運(yùn)裝卸貨物，月臺(tái)調(diào)度決策也主要采用簡(jiǎn)單的調(diào)度規(guī)則進(jìn)行，如根據(jù)車(chē)輛到達(dá)園區(qū)時(shí)間、車(chē)輛預(yù)約時(shí)間[2]等順序按照先到先服務(wù)(First Come First Served, FCFS)規(guī)則進(jìn)行調(diào)度，這樣的方法可能導(dǎo)致很多有效信息被忽略，從而導(dǎo)致月臺(tái)資源利用率低，車(chē)輛等待時(shí)間長(zhǎng)，配送中心管理水平滯后。有少數(shù)企業(yè)開(kāi)始使用月臺(tái)管理系統(tǒng)對(duì)月臺(tái)資源進(jìn)行調(diào)度，根據(jù)《物流管理國(guó)際期刊》發(fā)布的《技術(shù)使用調(diào)研》報(bào)告可知，僅有8%的公司使用月臺(tái)管理系統(tǒng)對(duì)月臺(tái)進(jìn)行管理[3]。但隨著物聯(lián)網(wǎng)、大數(shù)據(jù)、人工智能以及移動(dòng)通信技術(shù)等技術(shù)的快速發(fā)展，近幾年來(lái)一些企業(yè)在智慧物流園區(qū)建設(shè)方面不斷發(fā)力，智能月臺(tái)調(diào)度系統(tǒng)已逐漸推廣使用[3]。上海富勒信息科技有限公司提供的FLUX WMS倉(cāng)庫(kù)管理系統(tǒng)提供了月臺(tái)管理的相關(guān)模塊，系統(tǒng)會(huì)根據(jù)月臺(tái)數(shù)量、月臺(tái)類(lèi)型、車(chē)輛類(lèi)型、車(chē)輛預(yù)約時(shí)間、車(chē)輛歷史作業(yè)信息等信息使用算法對(duì)月臺(tái)資源進(jìn)行管理[1]。普洛斯旗下的際鏈科技研發(fā)了獨(dú)立的智能月臺(tái)調(diào)度系統(tǒng)，系統(tǒng)實(shí)現(xiàn)了通過(guò)調(diào)度管理引導(dǎo)車(chē)輛準(zhǔn)確?？俊⒓皶r(shí)離開(kāi)月臺(tái)[1]。結(jié)果表明，智能化的管理方法提高了園區(qū)的管理水平，提高了月臺(tái)作業(yè)效率。但是，高效的月臺(tái)調(diào)度算法還比較缺乏。

月臺(tái)調(diào)度問(wèn)題可以建模為不相關(guān)并行機(jī)調(diào)度問(wèn)題，眾多學(xué)者在文獻(xiàn)中廣泛地研究了不同目標(biāo)下的不相關(guān)并行機(jī)調(diào)度問(wèn)題，目標(biāo)主要包括最小化最大完工時(shí)間、最小化總延遲時(shí)間、最小化總提前/延遲時(shí)間等。下面將從不同目標(biāo)分別總結(jié)不相關(guān)并行機(jī)調(diào)度問(wèn)題研究現(xiàn)狀。

對(duì)以最小化最大完工時(shí)間為目標(biāo)的不相關(guān)并行機(jī)調(diào)度問(wèn)題，國(guó)內(nèi)外學(xué)者針對(duì)不同約束條件下的問(wèn)題展開(kāi)了研究。FANJUL-PEYRO等[4]針對(duì)具有稀缺作業(yè)資源約束下的問(wèn)題，建立了兩個(gè)整數(shù)線(xiàn)性規(guī)劃模型，分別提出了3種數(shù)學(xué)策略。對(duì)于具有設(shè)置時(shí)間的問(wèn)題，F(xiàn)ANJUL-PEYRO等[5]提出一種新的混合整數(shù)線(xiàn)性規(guī)劃和基于數(shù)學(xué)規(guī)劃的算法，BAEZ等[6]提出一種結(jié)合貪心隨機(jī)自適應(yīng)搜索算法和變鄰域搜索的混合算法，EWEES等[7]提出基于螢火蟲(chóng)算法的改進(jìn)樽海鞘群算法。AVEDEENKO等[8]針對(duì)具有釋放時(shí)間的問(wèn)題提出一種動(dòng)態(tài)規(guī)劃方法，采用了一種自適應(yīng)的方法來(lái)減少搜索空間。

對(duì)以最小化總延遲為目標(biāo)的不相關(guān)并行機(jī)調(diào)度問(wèn)題，以下學(xué)者針對(duì)不同約束條件下的問(wèn)題進(jìn)行了研究。ATENCIO等[9]根據(jù)一個(gè)泊位分配實(shí)例，比較了3種著名的元啟發(fā)式方法的性能。DIANA等[10]研究了帶有序列、機(jī)器相關(guān)的設(shè)置時(shí)間的問(wèn)題，提出6種變鄰域搜索的鄰域結(jié)構(gòu)，并分析證明了用變鄰域下降算法替代局部搜索算子可以提高元啟發(fā)式算法的性能。ZHANG等[11]研究了具有設(shè)定時(shí)間依賴(lài)和機(jī)器—作業(yè)資格考慮的動(dòng)態(tài)不相關(guān)并行機(jī)問(wèn)題，使用Q學(xué)習(xí)算法，并采用5種啟發(fā)式方法作為動(dòng)作，實(shí)驗(yàn)結(jié)果表明該方法優(yōu)于單獨(dú)使用這5種啟發(fā)式方法。

對(duì)于以最小化總提前/延遲時(shí)間為目標(biāo)的不相關(guān)并行機(jī)調(diào)度問(wèn)題，以下學(xué)者針對(duì)不同約束條件下的問(wèn)題進(jìn)行了研究。對(duì)于具有交貨時(shí)間窗約束的問(wèn)題，ZEIDI等[12]設(shè)計(jì)了一種集成遺傳算法與模擬退火算法的智能算法，CHENG等[13]使用改進(jìn)的遺傳算法和分布式釋放時(shí)間控制機(jī)制來(lái)獲得近似最優(yōu)解。王宏等[14]針對(duì)帶有到達(dá)時(shí)間窗、序列相關(guān)設(shè)置時(shí)間的多跑道飛機(jī)調(diào)度問(wèn)題設(shè)計(jì)了一種遺傳算法進(jìn)行優(yōu)化求解。EKICI等[15]以一個(gè)電視生產(chǎn)商為研究對(duì)象，研究了存在時(shí)序相關(guān)的設(shè)置、不相等的釋放時(shí)間、機(jī)器—作業(yè)兼容性限制和工作負(fù)載平衡要求為約束的問(wèn)題，提出了4種啟發(fā)式方法，分別為：順序啟發(fā)式算法、禁忌搜索算法、隨機(jī)集合劃分算法和基于禁忌搜索的元啟發(fā)式算法。

總結(jié)現(xiàn)有文獻(xiàn)，可以發(fā)現(xiàn)：

(1)不相關(guān)并行機(jī)調(diào)度問(wèn)題廣泛存在于各種作業(yè)活動(dòng)中，如泊位調(diào)度[9]、飛機(jī)調(diào)度[14]、車(chē)間調(diào)度[16]等。目前，眾多學(xué)者們針對(duì)不同背景環(huán)境下的不相關(guān)并行機(jī)問(wèn)題展開(kāi)了研究，根據(jù)研究背景確定作業(yè)的目標(biāo)以及約束條件，再采用不同的算法設(shè)計(jì)出智能優(yōu)化方案對(duì)該問(wèn)題進(jìn)行優(yōu)化求解。然而，很少有學(xué)者針對(duì)以月臺(tái)調(diào)度為背景的不相關(guān)并行機(jī)問(wèn)題展開(kāi)研究。

(2)不同的作業(yè)活動(dòng)往往存在不同的約束條件，包括序列相關(guān)的釋放時(shí)間[15]、設(shè)置時(shí)間[5,10,14]、交貨時(shí)間窗[12]、到達(dá)時(shí)間窗[14]、機(jī)器-作業(yè)兼容性限制[15]等，其中對(duì)具有設(shè)置時(shí)間的問(wèn)題研究較多，而對(duì)機(jī)器—作業(yè)兼容性限制等約束條件研究較少。

(3)大多數(shù)學(xué)者研究的調(diào)度問(wèn)題為靜態(tài)問(wèn)題[4-7,9,10,12-15]，少數(shù)學(xué)者研究了動(dòng)態(tài)問(wèn)題[8,11]。

(4)學(xué)者們大多使用算法對(duì)不相關(guān)并行機(jī)調(diào)度問(wèn)題進(jìn)行求解，包括模擬退火算法[12]、樽海鞘群算法[7]、遺傳算法[12-13]、螢火蟲(chóng)算法[17]、禁忌搜索算法[15]、Q學(xué)習(xí)算法[11]等，只有少數(shù)學(xué)者采用精確求解或啟發(fā)式規(guī)則的方式[4-5]求解不相關(guān)并行機(jī)調(diào)度問(wèn)題。因此，本文將針對(duì)靜態(tài)的月臺(tái)調(diào)度問(wèn)題提出智能優(yōu)化方案。

信息化、自動(dòng)化和智能化是當(dāng)今物流行業(yè)的必然發(fā)展趨勢(shì)，月臺(tái)作為配送中心中連接倉(cāng)庫(kù)倉(cāng)儲(chǔ)作業(yè)與車(chē)輛運(yùn)輸作業(yè)的關(guān)鍵環(huán)節(jié)，也正向著智能化方向提升發(fā)展。本文將在充分了解國(guó)內(nèi)外配送中心月臺(tái)調(diào)度方法研究現(xiàn)狀的基礎(chǔ)上，針對(duì)配送中心月臺(tái)管理系統(tǒng)中的智能調(diào)度模塊，利用智能優(yōu)化算法，提出智能、高效的月臺(tái)調(diào)度方法。本文主要貢獻(xiàn)包括：①根據(jù)實(shí)際的月臺(tái)調(diào)度問(wèn)題進(jìn)行分析與建模；②提出學(xué)習(xí)型混合差分進(jìn)化算法，根據(jù)問(wèn)題特征設(shè)計(jì)了編/解碼算法，結(jié)合超啟發(fā)式算法(Hyper Heuristic, HH)，設(shè)計(jì)了學(xué)習(xí)型算子選擇機(jī)制，使算法可以學(xué)習(xí)選擇算子的經(jīng)驗(yàn)，并選擇對(duì)當(dāng)前有利的算子，結(jié)合變鄰域搜索算法(Variable Neighborhood Descent, VND)，提高算法的搜索能力。

1 月臺(tái)調(diào)度模型

1.1 問(wèn)題描述

本文研究的月臺(tái)調(diào)度問(wèn)題可以描述為：車(chē)輛需要提前一天預(yù)約裝卸貨作業(yè)的時(shí)間。有N輛預(yù)約成功的車(chē)輛，有M個(gè)可以進(jìn)行裝卸貨作業(yè)月臺(tái)。由于車(chē)型、月臺(tái)作業(yè)設(shè)備、供應(yīng)商、配送地點(diǎn)等因素影響，車(chē)輛與月臺(tái)有不同的作業(yè)類(lèi)別，車(chē)輛與月臺(tái)之間存在兼容性約束，一個(gè)類(lèi)型的車(chē)輛只能在可以處理該類(lèi)型車(chē)輛作業(yè)的月臺(tái)上進(jìn)行裝卸貨作業(yè)。車(chē)輛在信息系統(tǒng)上預(yù)約進(jìn)行作業(yè)的時(shí)間窗口，使用調(diào)度算法進(jìn)行調(diào)度，調(diào)度結(jié)果中車(chē)輛到達(dá)時(shí)間與離開(kāi)時(shí)間可以超出預(yù)約的時(shí)間窗口范圍，但需接受不同的提前、拖后懲罰，調(diào)度算法優(yōu)化的目標(biāo)為最小化總加權(quán)作業(yè)的提前、延遲懲罰。并且，為了給重要客戶(hù)提供更好的服務(wù)，為重要客戶(hù)設(shè)置更高的提前、拖后懲罰權(quán)重。

調(diào)度月臺(tái)資源時(shí)，需要根據(jù)車(chē)輛的類(lèi)型、預(yù)約作業(yè)時(shí)間窗口、提前懲罰、拖后懲罰與月臺(tái)的類(lèi)型、作業(yè)情況等信息為車(chē)輛合理分配月臺(tái)，減少所有作業(yè)車(chē)輛的總加權(quán)作業(yè)的提前、延遲懲罰。調(diào)度完成后，如果預(yù)約車(chē)輛到達(dá)配送中心的時(shí)間早于調(diào)度結(jié)果時(shí)間，則安排車(chē)輛在停車(chē)場(chǎng)等待；如果預(yù)約車(chē)輛到達(dá)配送中心的時(shí)間晚于調(diào)度結(jié)果時(shí)間，即車(chē)輛遲到，則需對(duì)該車(chē)輛作業(yè)進(jìn)行現(xiàn)場(chǎng)調(diào)度，為該車(chē)輛分配合適的月臺(tái)進(jìn)行裝卸貨作業(yè)。

為了簡(jiǎn)化月臺(tái)調(diào)度問(wèn)題，作出如下假設(shè)：

(1)在零時(shí)刻所有月臺(tái)可以使用；

(2)在零時(shí)刻所有車(chē)輛可以開(kāi)始作業(yè)；

(3)車(chē)輛預(yù)約作業(yè)時(shí)間窗口的長(zhǎng)度大于等于該車(chē)輛需要的作業(yè)時(shí)間；

(4)每個(gè)車(chē)輛僅可以在一個(gè)月臺(tái)進(jìn)行裝卸貨作業(yè)；

(5)裝卸貨作業(yè)一旦開(kāi)始便不允許中斷；

(6)每個(gè)月臺(tái)一次只能接受一個(gè)車(chē)輛的裝卸貨作業(yè)；

(7)不考慮為車(chē)輛進(jìn)行實(shí)時(shí)調(diào)度；

(8)不考慮在作業(yè)時(shí)間內(nèi)月臺(tái)設(shè)備出現(xiàn)故障。

1.2 符號(hào)定義

本文數(shù)學(xué)模型中使用的參數(shù)、變量和決策變量的符號(hào)以及定義如下：

(1)參數(shù)

M為總月臺(tái)數(shù)量；

Mj為第j個(gè)月臺(tái)，j=1, 2,…,M；

lmj為月臺(tái)Mj可以處理的車(chē)輛類(lèi)型集合，j=1, 2,…,M；

N為總預(yù)約車(chē)輛的數(shù)量；

Ji為第為i個(gè)車(chē)輛，i=1, 2,…,N；

lni為車(chē)輛Ji作業(yè)的類(lèi)型，i=1, 2,…,N；

dsi為車(chē)輛預(yù)約作業(yè)窗口開(kāi)始時(shí)間，表示車(chē)輛可以在dsi時(shí)間點(diǎn)后開(kāi)始作業(yè)，i=1, 2,…,N；

dei為車(chē)輛預(yù)約作業(yè)窗口結(jié)束時(shí)間，表示車(chē)輛需要在dei時(shí)間點(diǎn)前結(jié)束作業(yè)，i=1, 2,…,N；

pi為車(chē)輛Ji進(jìn)行裝卸貨作業(yè)所需要的時(shí)間，i=1, 2,…,N；

ai為車(chē)輛Ji單位時(shí)間的提前懲罰，i=1, 2,…,N；

bi為車(chē)輛Ji單位時(shí)間的拖期懲罰，i=1, 2,…,N。

(2)變量

Rj為月臺(tái)Mj上的作業(yè)車(chē)輛序列，j=1, 2,…,M；

si為車(chē)輛Ji開(kāi)始作業(yè)的時(shí)間，i=1, 2,…,N；

ei為車(chē)輛Ji結(jié)束作業(yè)的時(shí)間，i=1, 2,…,N。

(3)決策變量

Xij為0-1變量，若車(chē)輛Ji在月臺(tái)Mj上進(jìn)行作業(yè)，則Xij=1，否則Xij=0，i=1, 2,…,N，j=1, 2,…,M；

Yiy為0-1變量，若車(chē)輛Ji在車(chē)輛Jy前進(jìn)行作業(yè)則Yiy=1，否則Yiy=0，i,y∈Rj，i≠y，j=1, 2,…,M。

1.3 優(yōu)化模型

本文研究的問(wèn)題的數(shù)學(xué)模型表示為：

bi×max{0,ei-dei})。

(1)

s.t.

(2)

Xij×lni∈Xij×lmj,?i∈[1,N],?j∈[1,M];

(3)

dsi≥0,?i∈[1,N];

(4)

dei-dsi≥pi,?i∈[1,N];

(5)

si≥0,?i∈[1,N];

(6)

ei=si+pi,?i∈[1,N];

(7)

Yiy×ei≤Yiy×sy，?j∈[1,M]；

(8)

pi>0，?i∈[1,N]；

(9)

Xij∈{0,1}，?i∈[1,N]，?j∈[1,M]；

(10)

Yiy∈{0,1}；?i,y∈Rj，i≠y，?j∈[1,M]。

(11)

式(1)為本文研究月臺(tái)調(diào)度問(wèn)題的目標(biāo)函數(shù)，表示最小化總加權(quán)提前、延遲的懲罰。式(2)保證每個(gè)車(chē)輛的裝卸貨作業(yè)只分配給一個(gè)月臺(tái)，并保證了每個(gè)預(yù)約車(chē)輛都進(jìn)行了作業(yè)。式(3)表示一個(gè)類(lèi)型的車(chē)輛只能在可以處理該類(lèi)型車(chē)輛作業(yè)的月臺(tái)上進(jìn)行裝卸貨作業(yè)，即滿(mǎn)足車(chē)輛—月臺(tái)兼容性限制。式(4)表示每個(gè)車(chē)輛預(yù)約作業(yè)時(shí)間窗口的開(kāi)始時(shí)間大于等于零。式(5)表示每個(gè)車(chē)輛預(yù)約作業(yè)時(shí)間長(zhǎng)度大于車(chē)輛所需的作業(yè)時(shí)間。式(6)表示車(chē)輛開(kāi)始作業(yè)的時(shí)間大于等于零。式(7)表示一個(gè)車(chē)輛結(jié)束作業(yè)的時(shí)間等于開(kāi)始作業(yè)的時(shí)間加上該車(chē)輛的作業(yè)時(shí)間。式(8)表示在一個(gè)月臺(tái)上，一個(gè)車(chē)輛開(kāi)始裝卸貨作業(yè)的開(kāi)始時(shí)間不小于前一個(gè)車(chē)輛作業(yè)的結(jié)束時(shí)間，保證了一個(gè)月臺(tái)一次只能接受一個(gè)車(chē)輛進(jìn)行裝卸貨作業(yè)。式(9)表示車(chē)輛的作業(yè)時(shí)間不能小于零。式(10)～式(11)表示決策變量的取值。

2 學(xué)習(xí)型混合差分進(jìn)化算法

2.1 算法流程設(shè)計(jì)

單機(jī)器的總加權(quán)延遲最小化的調(diào)度問(wèn)題是NP-hard問(wèn)題[17]，因此本文研究的多個(gè)機(jī)器的總加權(quán)提前、延遲問(wèn)題也是NP-hard問(wèn)題。NP-hard問(wèn)題求解難度很高，且隨著問(wèn)題規(guī)模的增加，求解過(guò)程的時(shí)間以及存儲(chǔ)空間會(huì)隨著問(wèn)題規(guī)模的增加而呈現(xiàn)爆炸式增長(zhǎng)的趨勢(shì)，無(wú)法采用精確求解方法進(jìn)行求解。因此，本文嘗試使用智能算法進(jìn)行求解。近年來(lái)差分進(jìn)化算法(Differential Evolution，DE)[18]在車(chē)間調(diào)度[19]、信號(hào)處理[20]、電子設(shè)計(jì)[21]、經(jīng)濟(jì)學(xué)[22]等領(lǐng)域得到了廣泛應(yīng)用，具有結(jié)構(gòu)簡(jiǎn)單、自適應(yīng)能力強(qiáng)、收斂速度快、魯棒性強(qiáng)等特點(diǎn)，但是DE算法也存在一些問(wèn)題：①算法對(duì)變異算子、交叉算子有著很強(qiáng)的依賴(lài)，使用不同的算子對(duì)結(jié)果會(huì)產(chǎn)生很大的影響，以往學(xué)者的普遍做法是分別采用不同的算子進(jìn)行仿真實(shí)驗(yàn)從而找到一個(gè)最優(yōu)算子作為算法的算子，這樣的做法消耗了大量的時(shí)間；②種群容易提前收斂，陷入局部最優(yōu)解。因此，本文針對(duì)這些問(wèn)題對(duì)標(biāo)準(zhǔn)的DE算法進(jìn)行改進(jìn)：①設(shè)計(jì)多個(gè)變異算子與交叉算子，結(jié)合HH算法設(shè)計(jì)了一種學(xué)習(xí)型算子選擇機(jī)制，可以在線(xiàn)學(xué)習(xí)算子的表現(xiàn)情況,為算法選擇優(yōu)秀的算子;②添加局部搜索策略，對(duì)種群中的個(gè)體進(jìn)行局部搜索，使算法可以跳出局部最優(yōu)解，增加算法的尋優(yōu)能力。

本文提出的學(xué)習(xí)型混合差分進(jìn)化算法流程如圖1所示，具體流程如下：

步驟1初始化參數(shù)，設(shè)置終止條件、記錄獎(jiǎng)勵(lì)值的滑動(dòng)時(shí)間窗表格，進(jìn)入步驟2。

步驟2產(chǎn)生初始化種群，進(jìn)入步驟3。

步驟3計(jì)算種群適應(yīng)度，進(jìn)入步驟4。

步驟4判斷是否滿(mǎn)足終止條件，若是則結(jié)束并輸出最優(yōu)結(jié)果；否則，進(jìn)入步驟5。

步驟5使用學(xué)習(xí)型算子選擇機(jī)制選擇一個(gè)算子組合，并對(duì)當(dāng)前種群執(zhí)行算子組合的操作得到交叉種群，進(jìn)入步驟6。

步驟6計(jì)算交叉種群中個(gè)體的適應(yīng)度，進(jìn)入步驟7。

步驟7根據(jù)父代種群與交叉種群適應(yīng)度值執(zhí)行選擇操作得到選擇種群，進(jìn)入步驟8。

步驟8計(jì)算算子組合的獎(jiǎng)勵(lì)值，更新記錄獎(jiǎng)勵(lì)值的滑動(dòng)時(shí)間窗表格，進(jìn)入步驟9。

步驟9判斷是否滿(mǎn)足執(zhí)行局部搜索的條件，若是則進(jìn)入步驟10，否則，進(jìn)入步驟3。

步驟10對(duì)選擇種群執(zhí)行局部搜索操作，進(jìn)入步驟3。

2.2 詳細(xì)設(shè)計(jì)

2.2.1 編碼

在進(jìn)行優(yōu)化前，需要將問(wèn)題空間映射為解空間，因此首先將問(wèn)題的解編碼為染色體，每一條編碼對(duì)應(yīng)一個(gè)解。假設(shè)每個(gè)車(chē)輛ri的作業(yè)月臺(tái)為ki，則定義染色體的基因向量為[r1,r2, …,rN,k1,k2, …,kN]，其中加工任務(wù)的總數(shù)為N，染色體的總長(zhǎng)度為2×N，染色體分為兩個(gè)部分:第一部分為車(chē)輛序列，第二部分為對(duì)應(yīng)車(chē)輛作業(yè)的月臺(tái)，如圖2所示，染色體的第一部分與第二部分的第一位基因表示車(chē)輛3在月臺(tái)1作業(yè)。

2.2.2 初始化種群

種群初始化要兼顧考慮種群中個(gè)體的質(zhì)量與種群多樣性，因此本文采用調(diào)度規(guī)則產(chǎn)生部分染色體提高種群個(gè)體質(zhì)量，并隨機(jī)產(chǎn)生剩余部分染色體保證種群多樣性，初始化種群規(guī)模為Np。

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

首先，對(duì)染色體進(jìn)行解碼：根據(jù)染色體得到每個(gè)月臺(tái)停靠的車(chē)輛及其?？康拇涡颍蠓謩e計(jì)算每個(gè)月臺(tái)?？寇?chē)輛的開(kāi)始作業(yè)時(shí)間和結(jié)束作業(yè)時(shí)間。然后，根據(jù)式(1)計(jì)算目標(biāo)函數(shù)值得到該條染色體的適應(yīng)度值。

對(duì)解碼過(guò)程進(jìn)行詳細(xì)說(shuō)明。記Rj={rj1,rj2, …,rjw, …,rjW}為月臺(tái)Mj車(chē)輛?？孔鳂I(yè)的次序向量，月臺(tái)Mj共有W項(xiàng)作業(yè)。若車(chē)輛u與車(chē)輛v滿(mǎn)足su=ev，即車(chē)輛u與車(chē)輛v是連續(xù)作業(yè)的，則稱(chēng)車(chē)輛u與車(chē)輛v的作業(yè)組成一個(gè)塊Block。對(duì)月臺(tái)Mj上的車(chē)輛進(jìn)行解碼，假設(shè)現(xiàn)在已經(jīng)完成了前λ個(gè)車(chē)輛的解碼工作，得到了前λ個(gè)車(chē)輛的si與ei，并得到了Z個(gè)Block，分別為Block1，Block2，…，Blockz，…，BlockZ，得到了每個(gè)塊的開(kāi)始作業(yè)時(shí)間osz與結(jié)束作業(yè)時(shí)間oez，按照如下方法對(duì)月臺(tái)Mj上第λ+1個(gè)車(chē)輛rj(λ+1)進(jìn)行解碼。判斷oeZ與dsrj(λ+1)的大小關(guān)系，分為如下幾種關(guān)系進(jìn)行討論：

(1)如果滿(mǎn)足oeZ=dsrj(λ+1)，如圖3所示，其中橫軸為時(shí)間軸，實(shí)線(xiàn)框?yàn)橐呀?jīng)解碼完成的塊以及rj(λ+1)解碼后的作業(yè)時(shí)間，虛線(xiàn)框?yàn)檐?chē)輛rj(λ+1)的預(yù)約作業(yè)時(shí)間窗。車(chē)輛rj(λ+1)的作業(yè)開(kāi)始時(shí)間可以安排為預(yù)約時(shí)間窗的開(kāi)始時(shí)間，車(chē)輛rj(λ+1)與BlockZ中的作業(yè)是連續(xù)進(jìn)行的，將rj(λ+1)加入到BlockZ中。那么，車(chē)輛rj(λ+1)的開(kāi)始作業(yè)時(shí)間等于oeZ，車(chē)輛rj(λ+1)的結(jié)束作業(yè)時(shí)間等于車(chē)輛rj(λ+1)的開(kāi)始作業(yè)時(shí)間加上所需的作業(yè)時(shí)間，srj(λ+1)=oez，erj(λ+1)=srj(λ+1)+prj(λ+1)。之后，更新BlockZ的結(jié)束時(shí)間等于車(chē)輛rj(λ+1)的結(jié)束作業(yè)時(shí)間，oeZ=erj(λ+1)。在這種情況下車(chē)輛rj(λ+1)的作業(yè)調(diào)度沒(méi)有受到懲罰，該染色體的適應(yīng)度值沒(méi)有變化。

(2)若滿(mǎn)足oeZ

(3)如果滿(mǎn)足oeZ>dsrj(λ+1)，如圖5所示。車(chē)輛rj(λ+1)的作業(yè)開(kāi)始時(shí)間可以暫時(shí)安排為BlockZ中最后一個(gè)車(chē)輛的作業(yè)結(jié)束時(shí)間，然后再做調(diào)整。車(chē)輛rj(λ+1)與BlockZ中的作業(yè)是連續(xù)進(jìn)行的，將rj(λ+1)加入到BlockZ中。那么，車(chē)輛rj(λ+1)的開(kāi)始作業(yè)時(shí)間等于oeZ，車(chē)輛rj(λ+1)的結(jié)束作業(yè)時(shí)間等于車(chē)輛rj(λ+1)的開(kāi)始作業(yè)時(shí)間加上所需的作業(yè)時(shí)間，srj(λ+1)=oeZ，erj(λ+1)=srj(λ+1)+prj(λ+1)。之后更新BlockZ的結(jié)束時(shí)間等于車(chē)輛rj(λ+1)的結(jié)束作業(yè)時(shí)間，oeZ=erj(λ+1)。

在這種情況下，若車(chē)輛rj(λ+1)的作業(yè)調(diào)度受到了懲罰，導(dǎo)致該染色體的適應(yīng)度值增加，則需要考慮塊BlockZ的前移能否減小該月臺(tái)上已完成解碼作業(yè)的總懲罰值，即適應(yīng)度值，設(shè)BlockZ的前移距離為x，則BlockZ中的車(chē)輛整體向前移動(dòng)x時(shí)間單位后的適應(yīng)度值函數(shù)如式(12)所示。

bi×max{0,ei-x-dei})。

(12)

求解式(12)的最小值點(diǎn)對(duì)應(yīng)的x值，計(jì)算過(guò)程參考LEE等[23]提出的計(jì)算懲罰函數(shù)斜率的方法，并令x=max{x, 0}。BlockZ向前移動(dòng)直到遇到下面3種情況之一后停止：

(1)移動(dòng)距離達(dá)到使目標(biāo)函數(shù)達(dá)到最小值點(diǎn)的距離x；

(2)當(dāng)BlockZ為該月臺(tái)上的第一個(gè)塊時(shí)，移動(dòng)距離達(dá)到了osZ，即BlockZ不能夠再向前移動(dòng)；

(3)當(dāng)BlockZ不是該月臺(tái)上的第一個(gè)塊時(shí)，移動(dòng)距離達(dá)到了osZ-oeZ-1，即BlockZ向前移動(dòng)直到與BlockZ-1相連接。

當(dāng)遇到第3種情況停止后，BlockZ與BlockZ-1合并，需要重復(fù)塊向前移動(dòng)的過(guò)程，求出新的塊向前移動(dòng)的距離。

2.2.4 變異操作

(1)反轉(zhuǎn)變異

wr∈[1,Np]。

(13)

反轉(zhuǎn)變異操作的流程如下：隨機(jī)產(chǎn)生不同的兩個(gè)1～N之間的數(shù)字作為發(fā)生變異的位置，然后，分別對(duì)位于個(gè)體染色體第一部分與第二部分兩個(gè)變異位置之間的基因序列顛倒順序，如圖6所示。

(2)基于優(yōu)先工序交叉的差分變異

(14)

式中POX()表示采用基于優(yōu)先工序交叉。

基于優(yōu)先工序交叉的流程為：進(jìn)行操作的兩個(gè)個(gè)體分別記為父代1與父代2。對(duì)于染色體的第一部分與第二部分執(zhí)行相同的操作，隨機(jī)選擇復(fù)制父代1中的基因到變異個(gè)體，編號(hào)的位置與父代1相同，并刪除父代2中目前子代中包括的車(chē)輛作業(yè)編號(hào)，同時(shí)將父代2中剩余的基因按照順序填入變異個(gè)體的空位中，如圖7所示。

(15)

(3)隨機(jī)插入變異

變異個(gè)體產(chǎn)生的方式如式(16)所示。

wr∈[1,Np]。

(16)

隨機(jī)插入操作的流程為：從個(gè)體染色體的第一與第二部分中刪除隨機(jī)個(gè)數(shù)的相同位置基因，按照刪除的順序，對(duì)于染色體第一部分刪除的每一個(gè)基因，可以得到該車(chē)輛可以進(jìn)行作業(yè)的月臺(tái)集合，并隨機(jī)選擇一個(gè)該車(chē)輛可以進(jìn)行作業(yè)的月臺(tái)，將車(chē)輛與隨機(jī)選擇的月臺(tái)分別插入到染色體第一部分與第二部分的一個(gè)隨機(jī)位置。

2.2.5 交叉操作

(1)基于優(yōu)先工序交叉

交叉?zhèn)€體產(chǎn)生的方式如式(17)所示：

(17)

式中POX()表示采用基于優(yōu)先工序交叉操作。基于優(yōu)先工序交叉的流程見(jiàn)2.2.4節(jié)中基于優(yōu)先工序交叉的差分變異中所述的基于優(yōu)先工序交叉的流程。

(2)優(yōu)先級(jí)保存交叉

交叉?zhèn)€體產(chǎn)生的方式如式(18)所示：

(18)

式中PPX()表示采用優(yōu)先級(jí)保存交叉操作。

優(yōu)先級(jí)保存交叉的流程為：將進(jìn)行操作的兩個(gè)個(gè)體分別作為父代1與父代2。產(chǎn)生一個(gè)由數(shù)字1和2組成的隨機(jī)列表，表的長(zhǎng)度為父代基因長(zhǎng)度的一半。對(duì)染色體的第一部分與第二部分執(zhí)行相同的操作。從隨機(jī)列表最左側(cè)的第一個(gè)位置開(kāi)始，若隨機(jī)列表的數(shù)字為1，則取出父代1中的最左側(cè)沒(méi)有在子代中出現(xiàn)的基因；若為2，則取出父代2中的最左側(cè)沒(méi)有在子代中出現(xiàn)的基因，直到讀取到隨機(jī)列表的最后一位，如圖8所示。

2.2.6 學(xué)習(xí)型算子選擇機(jī)制

標(biāo)準(zhǔn)離散差分進(jìn)化算法在解決問(wèn)題時(shí)，通常會(huì)直接選定一個(gè)交叉算子和變異算子，然而針對(duì)不同的具體問(wèn)題以及使用算法對(duì)一個(gè)問(wèn)題進(jìn)行求解的不同階段，不同的交叉算子和變異算子組合可能會(huì)對(duì)問(wèn)題的尋優(yōu)過(guò)程有著不同的影響，通常學(xué)者們會(huì)通過(guò)仿真確定交叉算子與變異算子的組合，這樣的方法會(huì)耗費(fèi)大量的時(shí)間，且無(wú)法確?？梢哉业阶詈线m的算子組合。因此，本文設(shè)計(jì)了一種學(xué)習(xí)型算子選擇機(jī)制，根據(jù)不同算子的表現(xiàn)情況為算法選擇算子。

學(xué)習(xí)型算子選擇機(jī)制采用HH算法。HH算法的原理為通過(guò)高層次啟發(fā)式策略來(lái)管理和操縱一系列低層次啟發(fā)式方法以實(shí)現(xiàn)算法尋優(yōu)[25]，本文采用的高層次啟發(fā)式策略為學(xué)習(xí)型算子選擇機(jī)制，低層次啟發(fā)式策略為變異、交叉算子組合。學(xué)習(xí)型算子選擇機(jī)制采用文獻(xiàn)[26]提出的一種自適應(yīng)的多臂賭博機(jī)算法，并在獎(jiǎng)勵(lì)記錄時(shí)引入時(shí)間窗機(jī)制，其中參數(shù)wv為探索概率衰減的速率，本文算法采用文獻(xiàn)[26]推薦參數(shù)wv=0.95。算子組合采用2.2.4和2.2.5節(jié)中介紹的3個(gè)變異算子與2個(gè)交叉算子的組合，變異與交叉算子組合共有6種，如表 1所示。

表1 算子組合表

學(xué)習(xí)型算子選擇機(jī)制的流程如下：

輸入：滑動(dòng)時(shí)間窗長(zhǎng)度W，算子組合H個(gè)，當(dāng)前迭代次數(shù)t，探索概率衰減的速率wv，兩個(gè)W行H列的表格分別為算子選擇記錄表s、獎(jiǎng)勵(lì)值記錄表r；

輸出：s，r。

步驟1根據(jù)算子選擇記錄表s與獎(jiǎng)勵(lì)值記錄表r計(jì)算每個(gè)算子組合a∈[1,H]被選中的次數(shù)Nt(a)與每個(gè)算子的平均獎(jiǎng)勵(lì)值Qt(a)，進(jìn)入步驟2。

步驟2計(jì)算平均獎(jiǎng)勵(lì)值最小的算子被選擇的次數(shù)mt，計(jì)算探索概率p=wv/wv+mt2，在開(kāi)區(qū)間(0,1)取一個(gè)隨機(jī)數(shù)ran，進(jìn)入步驟3。

步驟3判斷ran是否大于p，若是，則進(jìn)入步驟4，否則進(jìn)入步驟5。

步驟4選擇動(dòng)作at=argamaxQt(a)，即平均獎(jiǎng)勵(lì)值最大的算子，進(jìn)入步驟6。

步驟5選擇動(dòng)作at=argaminNt(a)，即被選擇次數(shù)最少的算子，進(jìn)入步驟6。

步驟6執(zhí)行算子，計(jì)算執(zhí)行算子進(jìn)行運(yùn)算前后的平均適應(yīng)值之差f，并將f作為獎(jiǎng)勵(lì)值，進(jìn)入步驟7。

步驟7判斷t是否小于等于W，若是，進(jìn)入步驟8，否則進(jìn)入步驟9。

步驟8將選擇的算子與獎(jiǎng)勵(lì)值分別記錄到滑動(dòng)時(shí)間窗表格s、r中的第t行，結(jié)束并輸出。

步驟9遵循先進(jìn)先出的原則，將滑動(dòng)時(shí)間窗表格s、r中的第一行數(shù)據(jù)擠出表格，將其余行向上移動(dòng)一行，并將新數(shù)據(jù)記錄到表格中的最后一行，結(jié)束并輸出。

2.2.7 選擇操作

采用貪婪選擇的方法，一一對(duì)比Xt-1與Ut中的個(gè)體，選擇適應(yīng)度值較優(yōu)的個(gè)體組成Xt。

(19)

式中f()表示計(jì)算個(gè)體的目標(biāo)值。

2.2.8 局部搜索操作

本文采用VND算法作為局部搜索算法。在每一代種群中隨機(jī)選取floor(Np×ps×(t/100)2)個(gè)個(gè)體進(jìn)行局部搜索，其中:ps為變鄰域搜索參數(shù)，Np為種群個(gè)體數(shù)量，floor()表示向下取整，t為當(dāng)前迭代次數(shù)。圖9所示為當(dāng)ps=0.1時(shí)，隨著迭代次數(shù)的增加，執(zhí)行局部搜索個(gè)體數(shù)量的散點(diǎn)圖，可以觀(guān)察到，在算法的開(kāi)始階段進(jìn)行局部搜索個(gè)體的數(shù)目為0，之后隨著迭代次數(shù)的增加進(jìn)行局部搜索個(gè)體的數(shù)量也增加，并且增長(zhǎng)的速度越來(lái)越快。該方法可以使算法在開(kāi)始時(shí)不對(duì)個(gè)體進(jìn)行局部搜索，而在整個(gè)解空間中探索，并在算法的后期對(duì)大量的個(gè)體進(jìn)行局部搜索，增加了算法跳出局部最優(yōu)解的能力，增加了算法的尋優(yōu)能力。

本文采用的局部算法的流程如下：

輸入：K個(gè)鄰域結(jié)構(gòu)，種群規(guī)模Np，當(dāng)前迭代次數(shù)t，當(dāng)前種群P(t)，變鄰域下降參數(shù)ps；

輸出：當(dāng)前種群P(t)。

步驟1進(jìn)行局部搜索個(gè)體的數(shù)量num=0，進(jìn)入步驟2。

步驟2判斷num是否小于floor(Np×ps×(t/100)2)，若是，則進(jìn)入步驟3，否則，結(jié)束并輸出結(jié)果。

步驟3在種群中隨機(jī)選擇一個(gè)個(gè)體，進(jìn)入步驟4。

步驟4令探索的鄰域數(shù)量k=1，進(jìn)入步驟5。

步驟5判斷k是否小于等于K，若是，則進(jìn)入步驟7，否則，進(jìn)入步驟6。

步驟6用局部搜索后的個(gè)體替換種群中的原個(gè)體，num=num+1，進(jìn)入步驟2。

步驟7探索該個(gè)體的第k個(gè)鄰域結(jié)構(gòu)，進(jìn)入步驟8。

步驟8探索完畢后是否發(fā)現(xiàn)改進(jìn)，若是，則轉(zhuǎn)步驟4，否則，進(jìn)入步驟9。

步驟9令k=k+1，轉(zhuǎn)步驟5。

本文中采用的鄰域結(jié)構(gòu)有內(nèi)部插入、內(nèi)部交換、外部插入、外部交換，有兩種鄰域開(kāi)發(fā)順序：首次改進(jìn)方法(Best Improvement, BI)和最佳改進(jìn)方法(First Improvement, FI)，F(xiàn)I和BI的具體操作參考文獻(xiàn)[10]。本文采用的鄰域結(jié)構(gòu)設(shè)置參考文獻(xiàn)[10]，使用了采用BI的內(nèi)部插入鄰域結(jié)構(gòu)、采用FI的內(nèi)部交換鄰域結(jié)構(gòu)、采用BI的外部插入鄰域結(jié)構(gòu)、采用FI的外部交換鄰域結(jié)構(gòu)。

(1)內(nèi)部插入鄰域結(jié)構(gòu)

隨機(jī)選取一個(gè)有提前、拖后成本的月臺(tái)，刪除該月臺(tái)上的一個(gè)車(chē)輛并將其插入到該月臺(tái)的另一個(gè)位置。

(2)內(nèi)部交換鄰域結(jié)構(gòu)

隨機(jī)選取一個(gè)有提前、拖后成本的月臺(tái)，選取兩個(gè)位置的車(chē)輛并交換兩個(gè)車(chē)輛的作業(yè)位置。

(3)外部插入鄰域結(jié)構(gòu)

隨機(jī)選取一個(gè)有提前、拖后成本的月臺(tái)Mj，并隨機(jī)選取另一個(gè)月臺(tái)Mk。從Mj中選取一個(gè)車(chē)輛，將該車(chē)輛從Mj的作業(yè)序列中刪除，并插入到Mk作業(yè)序列中的一個(gè)位置。若有改進(jìn)或者已經(jīng)探索完所有可能，則返回解；否則選擇另一個(gè)未選擇過(guò)的機(jī)器，重復(fù)上述過(guò)程。

(4)外部交換鄰域結(jié)構(gòu)

與外部插入流程相似，不同點(diǎn)在于不是將一個(gè)作業(yè)插入另一個(gè)機(jī)器，而是交換兩個(gè)作業(yè)的位置。

3 數(shù)值實(shí)驗(yàn)

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

3.1.1 實(shí)驗(yàn)環(huán)境

本文提出的算法使用Python3.6進(jìn)行編寫(xiě)，在64位的配置Intel(R)Core(TM)i7-8550u CPU 180GHZ處理器、8GB內(nèi)存、Windows10操作系統(tǒng)的計(jì)算機(jī)上編譯通過(guò)。

3.1.2 實(shí)驗(yàn)數(shù)據(jù)

YANG等[27]針對(duì)以最小化總延遲時(shí)間為優(yōu)化目標(biāo)、有不同到期日和機(jī)器相關(guān)的設(shè)置時(shí)間的不相關(guān)并行機(jī)問(wèn)題提出了計(jì)算實(shí)例，WAN等[28]針對(duì)有到期時(shí)間窗約束的單機(jī)調(diào)度問(wèn)題提出了計(jì)算實(shí)例。本文研究的問(wèn)題為有作業(yè)時(shí)間窗約束與車(chē)輛—月臺(tái)兼容性約束的不相關(guān)并行機(jī)問(wèn)題，目標(biāo)為總加權(quán)提前、拖后懲罰最小。根據(jù)問(wèn)題的特點(diǎn)，參考以上兩個(gè)實(shí)例的生成方法，形成測(cè)試算例。

表2 測(cè)試數(shù)據(jù)參數(shù)表

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

學(xué)習(xí)型混合差分進(jìn)化算法結(jié)合了DE、HH與VND算法，因此，將學(xué)習(xí)型混合差分進(jìn)化算法記為DE-HH-VND，并將去掉局部搜索部分的學(xué)習(xí)型混合差分進(jìn)化算法記為DE-HH。

(1)參數(shù)設(shè)置試驗(yàn)

開(kāi)展正交試驗(yàn)，通過(guò)對(duì)比不同參數(shù)水平下算法性能確定參數(shù)的最優(yōu)水平。

(2)算法設(shè)計(jì)策略驗(yàn)證實(shí)驗(yàn)

對(duì)DE-HH-VND、DE-HH與采用不同算子組合的DE進(jìn)行對(duì)比，驗(yàn)證學(xué)習(xí)型算子選擇機(jī)制與局部搜索策略的有效性。

(3)性能對(duì)比實(shí)驗(yàn)

比較DE-HH-VND與DE，驗(yàn)證算法的有效性。對(duì)DE-HH-VND與目前企業(yè)廣泛采用的月臺(tái)調(diào)度規(guī)則(FCFS規(guī)則)進(jìn)行對(duì)比，驗(yàn)證本文提出的算法的實(shí)用性。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 參數(shù)正交試驗(yàn)

本文提出的算法有4個(gè)可控因素，每個(gè)因素設(shè)置4個(gè)水平，并設(shè)置一個(gè)空列用作誤差分析，采用正交表L16(45)。因素水平值取值先通過(guò)測(cè)試得到較好解的參數(shù)取值，然后在該參數(shù)附近的區(qū)間內(nèi)設(shè)置水平，避免算法計(jì)算結(jié)果差別過(guò)大，因素水平表如表3所示。

表3 因素水平表

使用T=0.3，RDD=1.4的問(wèn)題算例，共16個(gè)實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)進(jìn)行10次，種群規(guī)模設(shè)置為200，種群初始化策略為采用FCFS規(guī)則產(chǎn)生一條染色體并隨機(jī)產(chǎn)生其余染色體，算法的終止條件為最大迭代次數(shù)為100代或最優(yōu)方案適應(yīng)度值為0，進(jìn)行局部搜索的條件為進(jìn)化停滯10代，實(shí)驗(yàn)結(jié)果為10次實(shí)驗(yàn)的適應(yīng)度平均值，測(cè)試結(jié)果如表4所示，其中表中的數(shù)字分別指因素水平。

表4 參數(shù)設(shè)置試驗(yàn)結(jié)果表

(1)直觀(guān)分析

直觀(guān)分析數(shù)據(jù)，計(jì)算各因素不同水平的均值k，計(jì)算各因素不同水平均值的極差R，如表5所示。極差R越大因素越重要，可以得出4個(gè)因素以及空列的重要程度從大到小為pc>ps>W>pm>空列，空列的重要程度最低說(shuō)明參數(shù)設(shè)置實(shí)驗(yàn)并沒(méi)有漏掉其他重要因素，因素之間不存在不可忽略的交互作用。對(duì)于每一個(gè)因素而言，不同水平的均值k越小，該水平越好，由此可以得出每個(gè)因素的優(yōu)水平分別為水平3、水平4、水平3、水平4，如表5所示。

表5 直觀(guān)分析表

(2)方差分析

使用方差分析研究4個(gè)影響因素對(duì)結(jié)果的影響，需要計(jì)算因素的自由度df、離散平方和SS、均方值MS、計(jì)算統(tǒng)計(jì)量F，如表6所示。在顯著性水平α=0.05下，檢驗(yàn)問(wèn)題的臨界值為fα(k-1,n-k)≈9.3，由各因素的F值與臨界值進(jìn)行對(duì)比可以得出變異概率pm、交叉概率pc、滑動(dòng)時(shí)間窗長(zhǎng)度W、變鄰域下降參數(shù)ps對(duì)實(shí)驗(yàn)結(jié)果沒(méi)有顯著性影響。由于變異概率pm、交叉概率pc、滑動(dòng)時(shí)間窗長(zhǎng)度W、變鄰域下降參數(shù)ps，對(duì)算法的運(yùn)行時(shí)間的影響均可接受，對(duì)4個(gè)因素分別取4個(gè)水平中k值最大的水平。綜上所述，確定優(yōu)方案為pm=0.6，pc=0.8，W=45，ps=0.1。

表6 方差分析表

(3)驗(yàn)證優(yōu)方案

對(duì)優(yōu)方案進(jìn)行實(shí)驗(yàn)，結(jié)果如表 7所示，取10次實(shí)驗(yàn)的平均值為57.80，小于等于正交試驗(yàn)中的最優(yōu)結(jié)果57.80，可以確定該方案為此算法的優(yōu)方案。

表7 優(yōu)方案實(shí)驗(yàn)結(jié)果表

3.2.2 算法設(shè)計(jì)策略驗(yàn)證實(shí)驗(yàn)

使用T=0.1，RDD=1.4的實(shí)驗(yàn)算例進(jìn)行實(shí)驗(yàn)。分別對(duì)DE-HH-VND、DE-HH與DE進(jìn)行10次實(shí)驗(yàn)，其中，DE因?yàn)椴扇〔煌淖儺?、交叉操作?huì)產(chǎn)生不同的效果，所以DE算法的實(shí)驗(yàn)又分為6個(gè)實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)采取不同的算子組合，采取的算子組合見(jiàn)表1所示，算法的參數(shù)取3.2.1節(jié)中得出的取值，算法的終止條件為最大迭代次數(shù)為150代或最優(yōu)方案適應(yīng)度值為0，算法的其他設(shè)置均與3.2.1節(jié)中的設(shè)置相同，計(jì)算實(shí)驗(yàn)結(jié)果的平均值與最優(yōu)值，實(shí)驗(yàn)結(jié)果見(jiàn)表8所示，繪制每個(gè)算法的收斂曲線(xiàn)，如圖10所示。

表8 算法設(shè)計(jì)策略驗(yàn)證實(shí)驗(yàn)結(jié)果

由表8和圖10可以看出：

(1)DE-HH-VND的結(jié)果優(yōu)于DE-HH，可以得到局部搜索策略增加了算法的尋優(yōu)能力。

(2)DE-HH結(jié)果的平均值優(yōu)于所有采用不同算子組合的DE，DE-HH結(jié)果的最優(yōu)值優(yōu)于多數(shù)采用不同算子組合的DE，優(yōu)于“DE+算子組合1”、“DE+算子組合3”、“DE+算子組合4”以及“DE+算子組合6”，差于“DE+算子組合2”、“DE+算子組合5”，可以得到學(xué)習(xí)型算子選擇機(jī)制可以在線(xiàn)為算法選擇對(duì)尋優(yōu)有幫助的算子組合。

(3)“DE+算子組合2”的結(jié)果優(yōu)于“DE+算子組合1”、“DE+算子組合3”、“DE+算子組合4”、“DE+算子組合5”以及“DE+算子組合6”，可以得到DE算法采用算子組合2的結(jié)果優(yōu)于采用其他算子組合。

3.2.3 性能對(duì)比實(shí)驗(yàn)

由3.2.2節(jié)中的算法設(shè)計(jì)策略驗(yàn)證實(shí)驗(yàn)結(jié)果可以得到標(biāo)準(zhǔn)差分進(jìn)化算法的最佳的算子組合為算子組合2，因此性能對(duì)比實(shí)驗(yàn)中的標(biāo)準(zhǔn)差分進(jìn)化算法使用優(yōu)先操作交叉變異算子與優(yōu)先操作交叉算子。標(biāo)準(zhǔn)離散差分進(jìn)化算法的參數(shù)設(shè)置與本文提出的算法的差分進(jìn)化部分一樣，分別對(duì)T={0.1, 0.2, 0.3}，RDD={1.2, 1.4}的小規(guī)模與大規(guī)模實(shí)例進(jìn)行測(cè)試，共12組實(shí)驗(yàn)，算法的參數(shù)設(shè)置與3.2.2節(jié)中實(shí)驗(yàn)的設(shè)置相同，每個(gè)實(shí)驗(yàn)進(jìn)行10次，并計(jì)算10次實(shí)驗(yàn)適應(yīng)值的平均值與最優(yōu)值。對(duì)比算法與本文提出的算法的結(jié)果如表9所示。

表9 性能對(duì)比實(shí)驗(yàn)結(jié)果表

可以得出如下結(jié)論：

(1)對(duì)于本文中測(cè)試的12個(gè)算例，DE-HH-VND算法均比DE算法獲得了相等或更好的解，可以得出DE-HH-VND具有良好的求解性能。

(2)對(duì)于本文中測(cè)試的12個(gè)算例，DE-HH-VND算法均比目前企業(yè)廣泛采用的月臺(tái)調(diào)度規(guī)則(FCFS規(guī)則)獲得了更好的解，可以得出DE-HH-VND算法可以幫助企業(yè)更好地進(jìn)行月臺(tái)調(diào)度。

圖 11和圖 12分別為一個(gè)小規(guī)模、大規(guī)模算例的調(diào)度方案甘特圖。

4 結(jié)束語(yǔ)

本文針對(duì)配送中心的月臺(tái)調(diào)度問(wèn)題進(jìn)行研究，分析了問(wèn)題特征，考慮月臺(tái)—車(chē)輛兼容性約束以及車(chē)輛作業(yè)時(shí)間窗約束，建立了以總加權(quán)提前、拖后懲罰為目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)了該問(wèn)題的編解碼方法，并提出一種學(xué)習(xí)型混合差分進(jìn)化算法。該算法采用差分進(jìn)化算法作為框架，結(jié)合超啟發(fā)式算法，提出了學(xué)習(xí)型算子選擇機(jī)制，通過(guò)學(xué)習(xí)以前選擇算子的經(jīng)驗(yàn)為算法自動(dòng)選擇對(duì)當(dāng)前優(yōu)化過(guò)程最優(yōu)的變異算子與交叉算子，并結(jié)合變鄰域算法作為局部搜索策略，對(duì)種群中的部分個(gè)體進(jìn)行局部搜索，幫助算法跳出局部最優(yōu)解，增加了算法的全局搜索能力。然后，針對(duì)問(wèn)題特征設(shè)計(jì)了本文研究問(wèn)題的實(shí)驗(yàn)算例，通過(guò)正交試驗(yàn)的方法確定了算法的參數(shù)的最優(yōu)水平，通過(guò)對(duì)比試驗(yàn)證明了學(xué)習(xí)型算子選擇機(jī)制與局部搜索策略的有效性，證明了學(xué)習(xí)型算子選擇機(jī)制可以為算法自動(dòng)選擇出優(yōu)秀的算子組合，證明了變鄰域算法可以增加算法的全局搜索能力，并與標(biāo)準(zhǔn)差分進(jìn)化算法和目前企業(yè)廣泛采用的月臺(tái)調(diào)度規(guī)則(先到先服務(wù)規(guī)則)進(jìn)行了對(duì)比，證明了算法具有良好的優(yōu)化性能，學(xué)習(xí)型混合差分進(jìn)化算法可以幫助企業(yè)更好地進(jìn)行月臺(tái)調(diào)度，提高月臺(tái)利用率，減少預(yù)約車(chē)輛的提前作業(yè)時(shí)間和等待作業(yè)的時(shí)間，提高企業(yè)的服務(wù)水平。

接下來(lái)可以從以下方面進(jìn)行后續(xù)研究：

(1)對(duì)目前提出的算法進(jìn)行改進(jìn)，提升算法性能。

(2)考慮動(dòng)態(tài)因素對(duì)調(diào)度的影響，如車(chē)輛沒(méi)有按照約定時(shí)間到達(dá)園區(qū)、沒(méi)有進(jìn)行預(yù)約的車(chē)輛進(jìn)行現(xiàn)場(chǎng)預(yù)約等因素。