煤炭堆場空間調(diào)度的GRASP算法研究

趙習(xí)強(qiáng)，鄭瀾波,陳致遠(yuǎn)

(1.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063；2.神華黃驊港務(wù)有限責(zé)任公司，河北 滄州 061113)

煤炭是我國目前使用的主要能源之一，“北煤南運(yùn)”、“西煤東運(yùn)”的運(yùn)輸格局使得港口成為煤炭供應(yīng)鏈中重要的一環(huán)。堆場是煤炭在港口中轉(zhuǎn)運(yùn)輸?shù)木彌_區(qū)，堆場作業(yè)的流暢程度直接影響到港口整體作業(yè)效率的提升。但由于堆場資源的有限性，堆場調(diào)度往往成為港口作業(yè)的瓶頸環(huán)節(jié)。堆場調(diào)度包括堆場設(shè)備的調(diào)度和堆場空間的分配。如顏佳佳[1]從黃驊港煤炭碼頭的實(shí)際數(shù)據(jù)出發(fā)，基于翻堆作業(yè)系統(tǒng)建立模型，通過Witness仿真軟件對翻車機(jī)、堆料機(jī)、皮帶機(jī)進(jìn)行調(diào)度及優(yōu)化。樊小波[2]總結(jié)了散貨碼頭露天條形堆場空間分配和封閉筒倉堆場空間分配問題的研究現(xiàn)狀。

還有學(xué)者采用數(shù)學(xué)優(yōu)化的方法來研究開放垛位模式的堆場空間分配，如BOLAND等[3]以紐卡斯?fàn)柛鄣拿禾慷褕稣{(diào)度為研究內(nèi)容，考慮堆取料機(jī)的分配作業(yè)，建立數(shù)學(xué)模型，提出3種堆場規(guī)劃方法，通過實(shí)驗(yàn)分析發(fā)現(xiàn)基于整數(shù)規(guī)劃的結(jié)構(gòu)算法的性能最好。BELOV等[4]在文獻(xiàn)[3]的基礎(chǔ)上，采用大鄰域搜索的約束規(guī)劃方法在更短的時(shí)間內(nèi)搜索到最優(yōu)解。SAVELSBERGH等[5]以澳大利亞獵人谷煤炭供應(yīng)鏈問題為背景，以最小化船舶平均延遲為目標(biāo)建立動態(tài)模型，并設(shè)計(jì)了一種樹搜索算法來解決堆場調(diào)度在時(shí)間、空間兩個維度上的最優(yōu)化問題。文燦[6]以最小化煤堆占用堆場的時(shí)間為目標(biāo)，分別建立基于特殊順序約束二維裝箱問題的整數(shù)線性規(guī)劃(MIP)模型和約束規(guī)劃(CP)模型，并生成實(shí)驗(yàn)數(shù)據(jù)，利用分支定界算法和約束規(guī)劃算法進(jìn)行求解，通過實(shí)驗(yàn)證明了CP算法的求解效果更好。但CP算法隨著數(shù)據(jù)規(guī)模的增大求解耗時(shí)增加，且能求解的數(shù)據(jù)規(guī)模有限。

文獻(xiàn)[3]的研究結(jié)果表明，基于煤堆占據(jù)場地的空間和時(shí)間建立時(shí)空圖，堆場空間調(diào)度問題可以轉(zhuǎn)化為一個二維裝箱問題。二維裝箱是一個NP-hard問題，目前對二維裝箱問題的研究主要包括3類求解方法：①構(gòu)造近似算法。如BAKER等[7]提出的 BL(bottom left)算法，其策略是將選中的物體放在箱子的右上角，然后盡量向下向左做連續(xù)移動，直到不能移動為止。②精確算法。根據(jù)求解機(jī)制的不同，精確算法可分為數(shù)學(xué)規(guī)劃方法和約束規(guī)劃方法。如DELL′AMICO等[8]提出一種求解帶時(shí)間窗約束二維裝箱問題的分支定界算法，并通過大量計(jì)算實(shí)驗(yàn)進(jìn)行了驗(yàn)證。PISINGER等[9]則將約束規(guī)劃方法對一刀切等特殊約束的強(qiáng)大建模處理能力和分解算法對整數(shù)線性規(guī)劃模型的高效求解能力很好地結(jié)合在一起，可有效求解一般二維裝箱問題。③智能優(yōu)化算法。如WEI等[10]針對帶有卸載約束的二維條形裝箱問題，利用最佳適應(yīng)(best fit)算法來生成給定物品序列的裝箱方案，并通過隨機(jī)局部搜索改變物品序列的方式來改進(jìn)求解，最后實(shí)驗(yàn)驗(yàn)證了該方法的有效性和優(yōu)越性。

筆者針對堆場空間調(diào)度問題，結(jié)合GRASP算法[11]和求解二維裝箱問題的經(jīng)典算法即BL 算法，加入可以處理特殊位置約束的repair算子，實(shí)現(xiàn)可以求解更大規(guī)模樣本數(shù)據(jù)的GRASP算法，彌補(bǔ)現(xiàn)有研究利用精確算法求解的數(shù)據(jù)規(guī)模局限性，通過實(shí)驗(yàn)確定影響GRASP的關(guān)鍵參數(shù)，并對比分析基于CP的精確求解算法和基于GRASP的啟發(fā)式算法各自在不同規(guī)模樣本數(shù)據(jù)上的效果。

1 煤炭堆場空間調(diào)度模型

1.1 煤炭堆場空間調(diào)度問題描述

在煤炭堆場空間調(diào)度問題中，堆場場地多為長條矩形，實(shí)際作業(yè)時(shí)，通常每個煤堆在堆場的高度都一致且覆蓋了條形場地的整個寬度，故以煤堆占據(jù)條形場地長度的不同來表示煤堆占據(jù)堆場空間大小的不同。煤堆占據(jù)堆場空間的時(shí)間由堆料時(shí)間、堆積時(shí)間、取料時(shí)間3部分組成，其中堆料時(shí)間、取料時(shí)間分別對應(yīng)堆料機(jī)、取料機(jī)作業(yè)于該煤堆的時(shí)間，因堆料機(jī)、取料機(jī)工作速率恒定，故堆料時(shí)間、取料時(shí)間與煤堆大小成正比，而堆積時(shí)間是指從堆料結(jié)束至取料開始的時(shí)間，受堆料時(shí)間和取料時(shí)間共同影響。

建立堆場煤堆調(diào)度的時(shí)空圖，如圖1所示。其中，一個矩形代表一個煤堆的堆場調(diào)度，縱軸方向向上點(diǎn)H1為煤堆在堆場的起始堆放位置，橫軸方向點(diǎn)L1為煤堆的堆料開始時(shí)間，點(diǎn)L3為取料的開始時(shí)間。根據(jù)煤堆的需求量和場地單位空間容納能力可以計(jì)算出煤堆長度，確定煤堆在場地的末端位置，即點(diǎn)H2。同理，根據(jù)需求量和堆料機(jī)、取料機(jī)的速率可以計(jì)算出煤堆的堆料時(shí)間和取料時(shí)間，確定煤堆堆料完成時(shí)間(點(diǎn)L2)和取料完成時(shí)間(點(diǎn)L4)。煤堆堆料完成時(shí)間與取料開始時(shí)間的差值就是煤堆的堆積時(shí)間。

圖1 堆場煤堆調(diào)度時(shí)空圖

考慮實(shí)際作業(yè)情況，煤炭堆場空間調(diào)度問題還有以下特點(diǎn)：①時(shí)空圖中的煤堆矩形不能相互重疊。②同一艘船舶的煤堆的最早取料開始時(shí)間不得早于煤堆的最晚堆料完成時(shí)間。③同一艘船舶的煤堆必須按照一定的取料順序進(jìn)行取料。

因此，煤炭堆場空間調(diào)度問題可描述為：在一定數(shù)量的長度、寬度確定的條形堆場中，給定一定時(shí)期內(nèi)船舶所需的煤堆種類和每種煤堆的需求量，決策所有煤堆在條形堆場中占據(jù)堆場的長度位置和占據(jù)該位置的時(shí)間，使最后一艘船舶的離開時(shí)間最早，即最后一個煤堆的取料完成時(shí)間最早。

1.2 與二維條形裝箱問題的轉(zhuǎn)化

二維條形裝箱問題的定義為：設(shè)有一個長度為L、高度不限的長條形箱子和一組矩形物品集合J={j1,j2,…,jn}，矩形物品的高度和長度集合分別為H={h1,h2,…,hn}和L={l1,l2,…,ln}，尋求一種將所有矩形物品放入長條形箱子并保證物品占用箱子的總高度最小的方法。

二維條形裝箱問題和煤炭堆場空間調(diào)度的示意圖如圖2所示，可以看出二者有很大的相似性。若把二維條形裝箱問題中的每個矩形物品看作一個煤堆，則矩形物品的寬度代表煤堆占用場地的長度，矩形物品的長度代表煤堆占用場地的時(shí)間，最小化箱子總長度代表最小化最后一個煤堆的取料完成時(shí)間，這樣兩個問題就可以進(jìn)行很好的轉(zhuǎn)化。兩個問題的不同之處在于：①煤炭堆場空間調(diào)度的煤堆矩形由于煤堆堆積時(shí)間的不確定性而導(dǎo)致煤堆矩形的時(shí)間長度不確定；②煤炭堆場空間調(diào)度問題中，煤堆矩形之間有特殊的先后關(guān)系。

圖2 二維條形裝箱問題和煤炭堆場空間調(diào)度示意圖

綜上可知，煤炭堆場空間調(diào)度問題可以轉(zhuǎn)化為一個帶特殊位置約束的二維條形裝箱問題。文獻(xiàn)[6]對煤炭堆場空間調(diào)度問題轉(zhuǎn)化為帶特殊位置約束的二維條形裝箱問題后的數(shù)學(xué)模型給出了詳細(xì)的描述，在此不再贅述。

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

2.1 GRASP 算法原理

隨機(jī)貪婪自適應(yīng)搜索(GRASP)算法是一種迭代算法，其思路是先基于貪婪隨機(jī)原則構(gòu)建一個可行的初始解，再從該初始解出發(fā)不斷改進(jìn)，通過多次迭代，最終得到最優(yōu)解。每次迭代主要包含隨機(jī)貪婪構(gòu)造階段和局部搜索改進(jìn)階段兩個獨(dú)立的階段。即每次迭代中，首先通過隨機(jī)貪婪構(gòu)造階段構(gòu)造出一個初始可行解，然后在局部搜索子過程利用鄰域搜索算法來優(yōu)化隨機(jī)貪婪構(gòu)造階段產(chǎn)生的初始解，找到局部最優(yōu)解，當(dāng)局部最優(yōu)解比當(dāng)前最優(yōu)解更好時(shí)，則用局部最優(yōu)解替換當(dāng)前最優(yōu)解。迭代完成后，所得的當(dāng)前最優(yōu)解即為最終的全局最優(yōu)解。

具體而言，在隨機(jī)貪婪構(gòu)建階段，初始化可行解f為空，同時(shí)初始化候選集C并對候選集的每一個元素進(jìn)行評估，判斷是否可以加入限制候選列表(restricted candidate list，RCL)。隨后從RCL中隨機(jī)選擇一個元素與當(dāng)前解f進(jìn)行合并直到不滿足條件，更新候選集的元素并對候選集中每一個元素重新進(jìn)行評估。在局部搜索階段，對初始可行解的鄰域進(jìn)行局部搜索，若相鄰解f′比當(dāng)前最優(yōu)解f*更好，則更換f*=f′，直到找到局部最優(yōu)解。

2.2 算法實(shí)現(xiàn)

2.2.1 隨機(jī)貪婪構(gòu)建階段

(1)BL算法。在隨機(jī)貪婪構(gòu)建階段，從RCL中選出元素加入當(dāng)前解S時(shí)，采用二維裝箱問題經(jīng)典的啟發(fā)式構(gòu)造算法即BL算法來確定加入的元素在當(dāng)前解中放置的位置。

(2)貪婪函數(shù)。貪婪函數(shù)的作用是在隨機(jī)貪婪構(gòu)建階段評價(jià)候選集C中的元素，以判斷該元素是否能進(jìn)入RCL?？紤]煤堆矩形的長度和寬度兩個變量，選取煤堆矩形的長度ls、煤堆矩形的高度hs、煤堆矩形的長高和(hs+ls)、煤堆矩形的面積(hsls)作為貪婪函數(shù)。

(3)貪婪參數(shù)α。貪婪參數(shù)α的作用是控制貪婪程度。α=0對應(yīng)完全貪婪的過程，α=1則對應(yīng)完全隨機(jī)的過程。實(shí)際求解時(shí)，為了避免完全貪婪破壞隨機(jī)作用的擾動性，通常設(shè)置貪婪參數(shù)α的取值范圍為[0.5,1.0]，筆者設(shè)定貪婪參數(shù)α=0.5,0.6,0.7,0.8,0.9,1.0，再通過實(shí)驗(yàn)來選取合適的貪婪參數(shù)值。

(4)repair算子。由于同一艘船舶不同煤堆矩形之間存在特殊的位置順序約束，文獻(xiàn)[6]將這一約束轉(zhuǎn)化為同一艘船舶不同煤堆的堆料完成時(shí)間一致的最優(yōu)性定理約束，故在隨機(jī)貪婪構(gòu)建階段，當(dāng)同一艘船舶的煤堆矩形都加入當(dāng)前解S后，還需要對煤堆矩形的位置進(jìn)行修復(fù)，使得當(dāng)前解S成為可行解。

BL算法生成的當(dāng)前解如圖3所示。其中，虛線矩形S1、S2、S3是同一艘船舶需求的3個煤堆，a、c、e分別為3個煤堆的堆料開始時(shí)間，b、d、f分別為3個煤堆的堆料結(jié)束時(shí)間，可以看出同一艘船舶需求的煤堆S1、S2、S3的堆料完成時(shí)間并不一致，說明采用BL算法構(gòu)建的當(dāng)前解并不滿足最優(yōu)性定理的約束。

圖3 BL算法生成的解

圖4 repair算子修復(fù)后的可行解

2.2.2 生成相鄰解

ALVAREZ-VALDES等[12]提出一個GRASP中生成相鄰解的策略，并通過實(shí)驗(yàn)驗(yàn)證了該策略的有效性。該策略生成相鄰解步驟為：①去除當(dāng)前k解中最后k%的矩形(如20%)。②使用確定性構(gòu)造算法重新將這k%的矩形裝入條形中。

筆者選取該策略來生成相鄰解，選用BL算法作為重新裝填k%的矩形的算法。同時(shí)，權(quán)衡考慮參數(shù)對生成相鄰解的時(shí)間與質(zhì)量的影響，設(shè)置k=30。

2.2.3 選擇相鄰解

選擇相鄰解的策略有首次適應(yīng)和最優(yōu)適應(yīng)兩種。首次適應(yīng)策略是指當(dāng)?shù)谝淮嗡阉鞯奖瓤尚薪夂玫南噜徑鈺r(shí)，就用該相鄰解替換可行解，并以此作為新的起點(diǎn)進(jìn)行局部搜索。最優(yōu)適應(yīng)策略則要求所有的相鄰解都被搜索之后，使用最優(yōu)的相鄰解替換可行解。為了保證改進(jìn)解的質(zhì)量，筆者選取最優(yōu)適應(yīng)策略來選擇相鄰解。

3 計(jì)算實(shí)驗(yàn)

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

按文獻(xiàn)[6]生成測試數(shù)據(jù)的方法生成了6組測試實(shí)例，并與文獻(xiàn)[6]的CP求解算法進(jìn)行比較。本次算法實(shí)驗(yàn)的代碼通過Python 3.6語言編寫，求解文獻(xiàn)[6]的CP模型調(diào)用的求解器為IBM ILOG CPLEX 12.7中的CP Optimizer。本次實(shí)驗(yàn)的環(huán)境設(shè)置：CPU為2.5GHz Intel Core i7-4710MQ，RAM為12GB的戴爾一體機(jī)，操作系統(tǒng)為Ubuntn 18.04。

3.2 實(shí)驗(yàn)研究

3.2.1 貪婪函數(shù)對GRASP算法性能的影響

不同貪婪函數(shù)下GRASP算法求解的實(shí)驗(yàn)結(jié)果如表1所示。其中，最大迭代次數(shù)取500，實(shí)例編號X10_i表示第X組數(shù)據(jù)的第i個實(shí)例，10表示每個實(shí)例中船舶的數(shù)量，N表示每個實(shí)例需求的煤堆矩形的總數(shù)。從表1可以看出，貪婪函數(shù)為煤堆高度hs時(shí)的實(shí)驗(yàn)結(jié)果優(yōu)于其他3種貪婪函數(shù)的實(shí)驗(yàn)結(jié)果，在13個實(shí)例上都求得了當(dāng)前最優(yōu)解，僅在實(shí)例B10_3、C10_1上沒有求得當(dāng)前最優(yōu)解，但也求得了滿意解。

表1 不同貪婪函數(shù)下GRASP算法求解的實(shí)驗(yàn)結(jié)果

3.2.2 貪婪參數(shù)對GRASP算法性能的影響

不同貪婪參數(shù)值下GRASP算法求解的實(shí)驗(yàn)結(jié)果如表2所示(最大迭代次數(shù)取500)，可以看到當(dāng)貪婪參數(shù)α=1.0時(shí)，在 13 個實(shí)例上都求得了當(dāng)前最優(yōu)解，僅在實(shí)例 A10_3、 A10_4上求解的結(jié)果稍遜于當(dāng)前最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，貪婪參數(shù)α=1.0顯著優(yōu)于其他貪婪參數(shù)值。

表2 不同貪婪參數(shù)值下GRASP算法求解的實(shí)驗(yàn)結(jié)果

3.2.3 GRASP算法與CP算法對比分析

GRASP算法與CP算法的實(shí)驗(yàn)結(jié)果對比如表3所示。其中，由于GRASP算法具有隨機(jī)性，因此利用GRASP算法求解時(shí)分別運(yùn)行10次，并統(tǒng)計(jì)均值、最優(yōu)值；GRASP算法的最大迭代次數(shù)取1 000；貪婪函數(shù)為煤堆矩形高度hs；貪婪參數(shù)α=1.0。而CP算法是精確算法，求解時(shí)只運(yùn)行一次；CP算法的求解時(shí)間上限設(shè)為3 600 s。

(1)對比A、B、C 3組數(shù)據(jù)規(guī)模較小的實(shí)例求解結(jié)果可以看出，在實(shí)例A10_2的求解上，CP算法只求得了可行解且耗時(shí)達(dá)3 600.00 s；除此之外的其他實(shí)例，CP算法均能求得最優(yōu)解，且在求得最優(yōu)解的實(shí)例中，僅A10_5耗時(shí)較長，其余實(shí)例耗時(shí)均未超過1.00 s。GRASP算法僅在實(shí)例A10_2、A10_5上的求解耗時(shí)小于CP算法，所求解優(yōu)于或等于CP算法；在B組實(shí)例中，雖然GRASP算法在A10_3、A10_4實(shí)例上也求得了最優(yōu)解，但耗時(shí)較長；在實(shí)例C10_1、C10_2、C10_5、A10_1、A10_3、A10_4的求解上，GRASP算法同樣耗時(shí)較長，且GRASP算法所求解與CP算法所求解相差10%左右。

表3 GRASP算法與CP算法的實(shí)驗(yàn)結(jié)果對比

(2)對比D、E、F 3組數(shù)據(jù)規(guī)模較大的實(shí)例求解結(jié)果可以看出，CP算法僅在F組實(shí)例和實(shí)例D20_3、D20_4、D20_5上求得了可行解，且耗時(shí)較長；而GRASP算法在這些實(shí)例上的求解耗時(shí)遠(yuǎn)小于CP算法，且仍能求得與CP算法的偏差在10%左右的滿意解，其中GRASP算法在實(shí)例F20_3上的所求解甚至優(yōu)于CP算法；此外，在CP算法未求出可行解的其他實(shí)例上，GRASP算法仍能在一定時(shí)間內(nèi)求出可行解。

(3)在GRASP算法求解每個實(shí)例的結(jié)果中，目標(biāo)值標(biāo)準(zhǔn)差在0.00～1.83之間，求解結(jié)果的離散程度低，算法運(yùn)行的穩(wěn)定性較高，具有較好的魯棒性。綜合實(shí)驗(yàn)結(jié)果可知，對于小規(guī)模案例，CP算法的求解效果比GRASP算法更好；但對大規(guī)模數(shù)據(jù)樣本，GRASP算法能在更短時(shí)間內(nèi)求得滿意解，求解效果優(yōu)于CP算法。

4 結(jié)論

(1)針對煤炭堆場空間調(diào)度問題，采用GRASP算法求解煤炭堆場空間調(diào)度問題，設(shè)計(jì)并實(shí)現(xiàn)了GRASP算法，并通過實(shí)驗(yàn)研究確定了影響GRASP算法的關(guān)鍵參數(shù)。

(2)通過實(shí)驗(yàn)比較了GRASP算法與文獻(xiàn)[6]的CP算法在不同規(guī)模數(shù)據(jù)上的求解效果，實(shí)驗(yàn)結(jié)果表明：對于數(shù)據(jù)規(guī)模較小的案例，CP算法的求解效果優(yōu)于GRASP算法；對于數(shù)據(jù)規(guī)模較大的案例，GRASP算法的求解效果優(yōu)于CP算法，可以有效彌補(bǔ)CP算法在求解大規(guī)模數(shù)據(jù)時(shí)的不足。

(3)所提出的GRASP算法從理論上提供了求解經(jīng)典二維裝箱問題的算法處理特殊位置約束的思路，也彌補(bǔ)了精確算法求解堆場空間調(diào)度問題在數(shù)據(jù)規(guī)模上的局限性，使得求解實(shí)際規(guī)模數(shù)據(jù)的堆場空間調(diào)度問題成為可能。

(4)由于時(shí)間精力和理論技術(shù)水平的有限，筆者研究還存在以下需要進(jìn)一步改善的問題：①將堆場空間資源與堆場設(shè)備資源聯(lián)合、堆場資源與泊位等資源聯(lián)合進(jìn)行調(diào)度，以使得港口的整體作業(yè)效率更高。②融合約束規(guī)劃和啟發(fā)式方法的特點(diǎn)，在擴(kuò)大求解數(shù)據(jù)規(guī)模的同時(shí)，提升解的質(zhì)量，縮短求解時(shí)間。