吳秀麗，張雅琦

(北京科技大學 機械工程學院，北京 100083)

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 問題描述

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

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

為了簡化月臺調(diào)度問題，作出如下假設：

(1)在零時刻所有月臺可以使用；

(2)在零時刻所有車輛可以開始作業(yè)；

(3)車輛預約作業(yè)時間窗口的長度大于等于該車輛需要的作業(yè)時間；

(4)每個車輛僅可以在一個月臺進行裝卸貨作業(yè)；

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

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

(7)不考慮為車輛進行實時調(diào)度；

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

1.2 符號定義

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

(1)參數(shù)

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

Mj為第j個月臺，j=1, 2,…,M；

lmj為月臺Mj可以處理的車輛類型集合，j=1, 2,…,M；

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

Ji為第為i個車輛，i=1, 2,…,N；

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

dsi為車輛預約作業(yè)窗口開始時間，表示車輛可以在dsi時間點后開始作業(yè)，i=1, 2,…,N；

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

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

ai為車輛Ji單位時間的提前懲罰，i=1, 2,…,N；

bi為車輛Ji單位時間的拖期懲罰，i=1, 2,…,N。

(2)變量

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

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

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

(3)決策變量

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

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

1.3 優(yōu)化模型

本文研究的問題的數(shù)學模型表示為：

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

2 學習型混合差分進化算法

2.1 算法流程設計

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

本文提出的學習型混合差分進化算法流程如圖1所示，具體流程如下：

步驟1初始化參數(shù)，設置終止條件、記錄獎勵值的滑動時間窗表格，進入步驟2。

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

步驟3計算種群適應度，進入步驟4。

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

步驟5使用學習型算子選擇機制選擇一個算子組合，并對當前種群執(zhí)行算子組合的操作得到交叉種群，進入步驟6。

步驟6計算交叉種群中個體的適應度，進入步驟7。

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

步驟8計算算子組合的獎勵值，更新記錄獎勵值的滑動時間窗表格，進入步驟9。

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

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

2.2 詳細設計

2.2.1 編碼

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

2.2.2 初始化種群

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

2.2.3 適應值計算

首先，對染色體進行解碼：根據(jù)染色體得到每個月臺?？康能囕v及其停靠的次序，之后分別計算每個月臺?？寇囕v的開始作業(yè)時間和結(jié)束作業(yè)時間。然后，根據(jù)式(1)計算目標函數(shù)值得到該條染色體的適應度值。

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

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

(2)若滿足oeZ

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

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

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

(12)

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

(1)移動距離達到使目標函數(shù)達到最小值點的距離x；

(2)當BlockZ為該月臺上的第一個塊時，移動距離達到了osZ，即BlockZ不能夠再向前移動；

(3)當BlockZ不是該月臺上的第一個塊時，移動距離達到了osZ-oeZ-1，即BlockZ向前移動直到與BlockZ-1相連接。

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

2.2.4 變異操作

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

wr∈[1,Np]。

(13)

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

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

(14)

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

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

(15)

(3)隨機插入變異

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

wr∈[1,Np]。

(16)

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

2.2.5 交叉操作

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

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

(17)

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

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

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

(18)

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

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

2.2.6 學習型算子選擇機制

標準離散差分進化算法在解決問題時，通常會直接選定一個交叉算子和變異算子，然而針對不同的具體問題以及使用算法對一個問題進行求解的不同階段，不同的交叉算子和變異算子組合可能會對問題的尋優(yōu)過程有著不同的影響，通常學者們會通過仿真確定交叉算子與變異算子的組合，這樣的方法會耗費大量的時間，且無法確保可以找到最合適的算子組合。因此，本文設計了一種學習型算子選擇機制，根據(jù)不同算子的表現(xiàn)情況為算法選擇算子。

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

表1 算子組合表

學習型算子選擇機制的流程如下：

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

輸出：s，r。

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

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

步驟3判斷ran是否大于p，若是，則進入步驟4，否則進入步驟5。

步驟4選擇動作at=argamaxQt(a)，即平均獎勵值最大的算子，進入步驟6。

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

步驟6執(zhí)行算子，計算執(zhí)行算子進行運算前后的平均適應值之差f，并將f作為獎勵值，進入步驟7。

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

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

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

2.2.7 選擇操作

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

(19)

式中f()表示計算個體的目標值。

2.2.8 局部搜索操作

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

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

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

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

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

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

步驟3在種群中隨機選擇一個個體，進入步驟4。

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

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

步驟6用局部搜索后的個體替換種群中的原個體，num=num+1，進入步驟2。

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

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

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

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

隨機選取一個有提前、拖后成本的月臺，刪除該月臺上的一個車輛并將其插入到該月臺的另一個位置。

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

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

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

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

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

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

3 數(shù)值實驗

3.1 實驗設計

3.1.1 實驗環(huán)境

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

3.1.2 實驗數(shù)據(jù)

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

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

3.1.3 實驗設計

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

(1)參數(shù)設置試驗

開展正交試驗，通過對比不同參數(shù)水平下算法性能確定參數(shù)的最優(yōu)水平。

(2)算法設計策略驗證實驗

對DE-HH-VND、DE-HH與采用不同算子組合的DE進行對比，驗證學習型算子選擇機制與局部搜索策略的有效性。

(3)性能對比實驗

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

3.2 實驗結(jié)果與分析

3.2.1 參數(shù)正交試驗

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

表3 因素水平表

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

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

(1)直觀分析

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

表5 直觀分析表

(2)方差分析

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

表6 方差分析表

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

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

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

3.2.2 算法設計策略驗證實驗

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

表8 算法設計策略驗證實驗結(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”，可以得到學習型算子選擇機制可以在線為算法選擇對尋優(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 性能對比實驗

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

表9 性能對比實驗結(jié)果表

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

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

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

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

4 結(jié)束語

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

接下來可以從以下方面進行后續(xù)研究：

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

(2)考慮動態(tài)因素對調(diào)度的影響，如車輛沒有按照約定時間到達園區(qū)、沒有進行預約的車輛進行現(xiàn)場預約等因素。