李 偉，鄭瀾波

（武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063）

1 引言

我國是世界上最大的煤炭生產(chǎn)與消費國，龐大的消費量以及產(chǎn)銷在地理上的差異，導(dǎo)致煤炭運輸周期長、供應(yīng)鏈結(jié)構(gòu)復(fù)雜。港口作為煤炭多式聯(lián)運中水陸模式的轉(zhuǎn)運節(jié)點，其協(xié)調(diào)上、下游供需的作用直接影響著整條供應(yīng)鏈的作業(yè)能力。據(jù)國家統(tǒng)計局?jǐn)?shù)據(jù)，2014-2018年我國主要港口煤炭及制品吞吐量增長了10.26%，年均增長達3 811.75萬t。在我國煤炭需求旺季，港口經(jīng)常出現(xiàn)煤炭場存供不應(yīng)求的現(xiàn)象，因此，對港口的堆場資源進行合理調(diào)度，最大程度地滿足船舶需求是煤炭港口面臨的重要問題[1]。目前，港口調(diào)度的研究集中在集裝箱碼頭，而散貨碼頭，更確切地說對于煤炭碼頭的研究較少[2]。輸出型煤炭港口的運作模式可以分為拉動式（Pull-based）和推動式（Push-based），拉動式以客戶需求為導(dǎo)向進行原煤運輸和混配[2]，采用開放式的堆場，港口需要為每個到港煤堆分配堆存空間；而推動式則采用固定垛位模式，通過預(yù)測、安全庫存等方式，事先在堆場堆存一定數(shù)量的原煤來滿足客戶的需求。

拉動式港口的研究可分為精確算法和啟發(fā)式算法兩個方向，由于港口調(diào)度問題的動態(tài)性和復(fù)雜性，精確算法想要達到較高的效率往往依賴于模型簡化。文獻[3]以巴西散貨碼頭為研究對象，針對港口的主要作業(yè)環(huán)節(jié)建立了整體的混合整數(shù)規(guī)劃（MIP，Mixed Integer Programming）模型，并提出一種結(jié)合列生成和分支定價算法的精確算法。考慮到煤堆矩形在堆場的時空布局與二維裝箱問題的相似性，有學(xué)者將煤炭堆場調(diào)度問題轉(zhuǎn)化成帶特殊約束的二維裝箱問題，并用約束規(guī)劃（CP，Constraint Programming）范式對其進行建模。文獻[4]分別建立了煤炭堆場空間調(diào)度問題的MIP模型和CP模型，并通過計算實驗證明CP的求解效果更好。文獻[5]結(jié)合兩種規(guī)劃范式的優(yōu)勢，將整體問題進行分解，分別用MIP和CP對港口調(diào)度主問題和堆場調(diào)度子問題進行建模，并提出一種基于benders分解的精確算法來提高模型求解效率。文獻[3]和[5]的決策時間步長均為1h，相比而言，啟發(fā)式算法能在更細的時間粒度下實現(xiàn)對堆場的精準(zhǔn)調(diào)度。以典型的拉動式煤炭供應(yīng)鏈HVCC（Hunter Valley Coal Chain）為例，文獻[6]提出一種基于貪婪思想的遺傳算法，該算法從全局和系統(tǒng)角度考慮了更全面的港口調(diào)度問題，并實現(xiàn)了煤炭出港作業(yè)在時空維度的連續(xù)調(diào)度。結(jié)合精確算法和啟發(fā)式算法的優(yōu)點，文獻[7]以堆場為核心節(jié)點分別建立了煤炭供應(yīng)的MIP和CP模型，通過滾動求解獲得初始解，并設(shè)計了大規(guī)模鄰域搜索算法對解進行改進，計算實驗表明，CP的自定義搜索策略機制讓其在求解中表現(xiàn)出更優(yōu)異的性能。

我國大部分的煤炭港口采用推動式進行管理，其調(diào)度問題的文獻研究主要基于規(guī)則和仿真方法，而基于數(shù)學(xué)模型和優(yōu)化技術(shù)的研究較少。文獻[8]將連續(xù)的堆場空間進行網(wǎng)格化處理，并提出了兩種物料堆存方案，使用WITNESS軟件對堆場離散時間進行仿真建模。文獻[9]結(jié)合貨物特性和堆場情況，提出三種堆存策略，并使用Plant-Simulation軟件構(gòu)建系統(tǒng)仿真模型對堆存方案進行實驗和評價。文獻[10]應(yīng)用WITNESS軟件對黃驊港的堆場進港作業(yè)系統(tǒng)進行仿真實驗，并建立多目標(biāo)MIP模型與之對比，發(fā)現(xiàn)MIP的求解效果更好。

在煤炭吞吐量逐年上漲的背景下，現(xiàn)有的基于規(guī)則和仿真的調(diào)度方法逐漸無法滿足我國港口的日常運作要求。本文借鑒CP在拉動式港口應(yīng)用的成功經(jīng)驗，以數(shù)學(xué)模型和優(yōu)化技術(shù)為基礎(chǔ)，為港口日常運作管理提供更合理、高效的調(diào)度算法。本文的研究對象為國內(nèi)某大型出口配煤港口，該港的堆場分為四個部分，其中一期工程的建立時間最早，堆場結(jié)構(gòu)也最復(fù)雜。因此，選取一期工程作為建模場景建立煤炭出港作業(yè)調(diào)度的CP模型，該模型充分考慮了固定垛位模式下的堆場作業(yè)特點，對于同類港口的調(diào)度問題具有普適性。為了解決問題動態(tài)性和組合性帶來的求解困難，采用分而治之的思想將問題進行分解，并設(shè)計基于變鄰域搜索的求解算法優(yōu)化求解結(jié)果，從而實現(xiàn)求解效率和精度的平衡。

2 出港作業(yè)調(diào)度的約束規(guī)劃模型

2.1 問題描述

一期工程共有6個條形堆場和8臺取料機，堆場的空間布局如圖1所示。每個條形堆場中坐落著多個垛位，垛位在堆場中占據(jù)一定的長度并存有一定數(shù)量的原煤。每個垛位的位置、煤種和存量信息已知，相鄰垛位為防止污染會留有一段距離。取料機位于條形堆場兩側(cè)的軌道上，取料時，取料機沿著軌道行走到指定垛位旁，通過傳送帶將原煤轉(zhuǎn)運至裝船機，最后由裝船機裝載到靠泊船的對應(yīng)艙位。

圖1 堆場的空間布局示意圖

客戶到港前，會先向港口發(fā)出提名（Nomination）以告知船的預(yù)計到達時間和需求，一艘船一般需要一至三種合同煤。合同煤是指發(fā)熱量、灰度等煤礦特性達到一定質(zhì)量要求的煤種，由于推動式煤炭港口只存有數(shù)量有限的原煤，因此需要在裝船過程中通過原煤混裝形成客戶需求的合同煤。每種合同煤一般由一至兩種原煤按比例混合而成，稱為配煤方案。此外，為了保持船體在水中的物理平衡，裝船前還需要預(yù)先設(shè)定不同艙位的作業(yè)順序。配煤方案選擇和裝船順序可通過將問題轉(zhuǎn)化為網(wǎng)絡(luò)流模型求得[1]，本文模型不涉及配煤方案的選擇且假定裝船順序已知。一艘船的裝船任務(wù)實際上就是按順序分輪、定量地裝載原煤，每個輪次指定了所需原煤的種類和數(shù)量，由于單個垛位的存量有限，一種原煤時常需要在多個垛位取料。

圖2是一個裝船作業(yè)的過程示例，船舶v的裝船作業(yè)分為3個輪次，輪次U1需要裝載10 000t原煤C1，存有 C1的垛位為N105、N408和N604，實際作業(yè)在8：00到9：40從N105取料10 000t；輪次 U2需要20 000t原煤C2，由于單個垛位存量有限，因此從多個垛位取料完成該輪次作業(yè)；最后，輪次U3從唯一存有C3的N201取料完成作業(yè)。每次作業(yè)都是一個決策單元，稱為裝船單元，裝船作業(yè)調(diào)度就是在船舶泊位和需求已知的情況下，為每個裝船單元分配合理的取料時間、取料量和取料設(shè)備。由于堆場中存放的原煤種類較多且港口設(shè)備之間存在復(fù)雜的可達性約束，多條船舶同時在港作業(yè)可能會搶奪堆場的場存和設(shè)備資源，造成裝船作業(yè)的延遲。裝船作業(yè)的目的就是科學(xué)合理地調(diào)度堆場資源，讓所有船能盡早完成作業(yè)離港。

圖2 船舶v取料裝船作業(yè)示意圖

2.2 模型假設(shè)

（1）所有到港船只的需求和?？坎次灰阎?，且所有決策不會超出預(yù)定的規(guī)劃期。

（2）堆場中垛位的位置、煤種和存量信息確定且已知，場存充足。

（3）單次取料過程由取料機、傳送帶和裝船機組成一條整體的作業(yè)線，其作業(yè)瓶頸為取料機，故以取料機能力為標(biāo)準(zhǔn)計算裝船單元的取料時長。

（4）由于CP模型只能處理整數(shù)，故對數(shù)據(jù)進行取整處理，煤炭數(shù)量都取整為t，時間取整為min，距離取整為m，數(shù)據(jù)步長均為1。

2.3 符號說明

（1）集合

V為船舶集合，按預(yù)計到達時間排序；

U為輪次集合，按所屬船舶的預(yù)計到達時間及裝船順序排序；

S為裝船單元集合，按所屬輪次排序。

（2）參數(shù)

etav為船舶v的預(yù)計到達時間，min；

Du為輪次u的取料量（時長），min；

vs為裝船單元s所屬的船舶；

us為裝船單元s所屬的輪次；

ns為裝船單元s的取料垛位；

pn∈{0,...,1 300}為垛位n在條形堆場的位置，測算起點為距離泊位最遠的堆場邊界，m；

Rn為垛位n可用的取料機集合；

Qn為垛位n的場存量，t；

speedR=30為取料機的行走速度，m/s；

rateR=100為取料機的作業(yè)效率，t/min，所有設(shè)備的行走速度和取料效率一致。

（3）決策變量

rs∈Rns為裝船單元s使用的取料機；

ts∈為裝船單元s的取料開始時間，其中T為規(guī)劃期的時間終點，min；

ds∈為裝船單元s的取料時長，由于設(shè)備的取料效率一致，為方便建模，用取料時長代表取料量，min。

（4）輔助變量

依托鄉(xiāng)土體育資源開展的陽光體育活動，改變了以往學(xué)生疲于應(yīng)付，被動活動的局面，變“要我運動”為“我要運動”，使學(xué)生在文明和諧的氛圍中陶冶情操，鍛煉身體，讓學(xué)生轉(zhuǎn)瞬即逝的青春留下照亮終生的火花，讓學(xué)生的人生充滿了陽光，使他們無論是處于順境還是逆境，都能樂觀而不消極。

departv為船舶v完成作業(yè)任務(wù)離港的時間，即該船最后一個裝船單元完成作業(yè)的時間，min。

2.4 約束規(guī)劃模型

裝船時間約束：裝船單元的取料開始時間不能早于所屬船的預(yù)計到港時間。

裝船順序約束：同一艘船分屬不同輪次的裝船單元需要按順序裝船。

船舶作業(yè)不重疊約束：同一艘船裝船單元的作業(yè)時間不能重疊。

垛位作業(yè)不重疊約束：在同一個垛位取料的裝船單元的作業(yè)時間不能重疊。

取料量約束：同屬一個輪次的裝船單元的取料量（時長）之和等于該輪次的總?cè)×狭浚〞r長）。

垛位場存約束：任一垛位的取料量不能超過其場存量。

取料機防撞約束：條形堆場之間一般只有一條軌道，且按假設(shè)每條軌道只有一臺取料機作業(yè)，而堆場1和堆場2之間有兩條軌道，R1位于靠近堆場2的軌道上，R2靠近堆場1，當(dāng)設(shè)備在各自靠近的堆場取料時，不會對彼此造成影響，否則將對另一臺設(shè)備的行走產(chǎn)生限制。如圖3所示，R2正在垛位N202取料，則位于其右側(cè)的R1無法越過R2到左側(cè)的N101和N201進行作業(yè)。

圖3 取料機R2在N202取料時對R1行走產(chǎn)生限制

先考慮R2限制R1行走的情況，假設(shè)裝船單元s使用設(shè)備R2在堆場2作業(yè)，則可能會對R1的作業(yè)產(chǎn)生影響，對任意一對先后由R1作業(yè)的裝船單元t1、t2需要至少滿足以下條件之一：t1、t2的設(shè)備移動發(fā)生在s作業(yè)之前或之后，即R1在時間上不會和R2產(chǎn)生沖突；t1、t2位于堆場的同一側(cè)，即R1在空間上不會和R2產(chǎn)生沖突；在裝船單元s作業(yè)開始之前或作業(yè)完成之后，R1有足夠的時間從t1的垛位移動到t2的垛位，同理可得R1限制R2行走的情況。

為了計算目標(biāo)函數(shù)值，給出派生變量departv的計算公式，裝船作業(yè)調(diào)度的目標(biāo)是讓所有船盡早完成作業(yè)離港，因此，目標(biāo)函數(shù)為最小化船舶離港時間departv的累和。

3 基于變鄰域搜索的求解算法

在上述CP模型中，決策變量ts和ds共同構(gòu)建了模型中大量的不重疊約束，導(dǎo)致一次性求解完整模型非常困難。因此，考慮將求解過程進行分解，先確定決策變量ds的取值，即裝船單元的取料方案，再求解完整模型，并設(shè)計一種改進的變鄰域搜索（VNS，Variable Neighborhood Search）算法優(yōu)化取料方案。VNS是一種基于多鄰域結(jié)構(gòu)的元啟發(fā)式算法，已被用于求解多個經(jīng)典的組合或全局優(yōu)化問題[12]，其主要思想是在搜索過程中系統(tǒng)地改變鄰域結(jié)構(gòu)，從而實現(xiàn)局部收斂和全局搜索的平衡。

3.1 算法主要組成部分

VNS只提供了求解問題的一般框架，本文根據(jù)問題結(jié)構(gòu)，將概率和延遲思想引入到當(dāng)前解更新的過程中，設(shè)計的VNS算法主要由五個部分組成：鄰域結(jié)構(gòu)的設(shè)計，這是基礎(chǔ)和關(guān)鍵；初始解與鄰域解的生成，實現(xiàn)解空間內(nèi)的隨機搜索；評價值計算與接受準(zhǔn)則，用來更新當(dāng)前解；延遲策略，實現(xiàn)解的局部收斂；終止條件。

3.1.1 鄰域結(jié)構(gòu)的設(shè)計。當(dāng)有多個裝船單元同時作業(yè)時，不同裝船單元可能會搶奪堆場資源，造成作業(yè)延遲，鄰域結(jié)構(gòu)的設(shè)計思路是改變部分裝船單元的取料量，通過調(diào)整不同輪次的取料方案消除作業(yè)沖突。應(yīng)用VNS時，為了避免消耗過多計算時間，鄰域結(jié)構(gòu)的數(shù)量不宜過多，建議為2[13]。本文設(shè)計了N0和N1兩種鄰域結(jié)構(gòu)，N1的結(jié)構(gòu)由N0的搜索結(jié)果決定。

（1）鄰域結(jié)構(gòu)N0。假設(shè)裝船單元的集合為S，裝船單元i對應(yīng)的取料量為di，則當(dāng)前解可定義為，從 X1中 隨 機 選 擇 K1（如個變量進行擾動（改變變量的取值），固定其他變量取值，隨機生成鄰域解

（2）鄰域結(jié)構(gòu)N1。給定集合U′?U，假設(shè)當(dāng)前解中 隨 機 選 擇 K2（如個變量進行擾動，要求被選變量所屬的輪次u∈U′，固定其他變量的取值，隨機生成鄰域解

（3）N0和N1的關(guān)系。算法首先在鄰域結(jié)構(gòu)N0內(nèi)搜索，如果當(dāng)前解有所改進，說明改變部分裝船單元的取料方案可以改進解的質(zhì)量，將這部分裝船單元所屬的輪次U′記錄下來，進入鄰域結(jié)構(gòu)N1，將其他輪次的取料方案固定，僅在更小的輪次U′范圍內(nèi)搜索鄰域解。

3.1.2 初始解與鄰域解的生成。初始解與鄰域解的生成有兩個要求，一是快速求解，二是保證解生成的隨機性?？紤]將CP模型中含有大量邏輯運算的約束（2）、（3）、（4）、（7）、（8）移除，并將最小化目標(biāo)改為求可行解，形成簡化的CP模型來求解取料方案。由于移除的約束不涉及決策變量ds，所以可以保證解的可行性。如前所述，鄰域解的生成依賴于擾動變量的選擇，假設(shè)當(dāng)前解為X1，如果擾動變量選擇不當(dāng)，則鄰域解X2可直接由約束（5）推出，此時X1=X2。為了保證鄰域解的隨機性，要求每次生成的鄰域解滿足，否則重新生成，直至滿足條件。

簡化的CP模型使用chuffed求解器的自由搜索（FS，F(xiàn)ree Search）策略求解模型，F(xiàn)S的自適應(yīng)搜索算法能進一步加快求解速度，并保證求解結(jié)果的隨機性[11]。

3.1.3 評價值計算與接受準(zhǔn)則。本文使用式（10）表示的目標(biāo)函數(shù)值評價解的質(zhì)量。用解表示的取料方案實例化CP模型中的取料時長變量ds，求出目標(biāo)函數(shù)值作為解的評價值。在VNS的基本框架中，算法只接受改進的解來更新當(dāng)前解。為了提高算法的全局搜索能力，本文借鑒模擬退火（SA，Simulated Annealing）的Metropolis準(zhǔn)則，以一定概率接受較差的解。給定比例系數(shù)α，假設(shè)評價函數(shù)為 f()x，當(dāng)前解為i，則接受鄰域解 j的概率為：

3.1.4 延遲策略。由于鄰域解的產(chǎn)生具有隨機性，因此每次當(dāng)前解更新后，選擇相同的變量繼續(xù)擾動，尋找局部范圍內(nèi)的更優(yōu)解。循環(huán)迭代，直至解在最近m次局部搜索沒有得到改進，說明已經(jīng)達到局部收斂，跳出循環(huán)進入下一步。

3.1.5 終止條件。使用兩種條件判斷算法是否終止運行：一是達到最大的迭代次數(shù)I，二是解足夠接近全局最優(yōu)。引入文獻[2]中的理想離開時間作為問題的理論下界，理想離開時間（EPDT，Earliest Possible Departure Time）是指船v在港口資源無限的情況下最早完成作業(yè)離港的時間，即船的預(yù)計到達時間加上其裝船單元的取料時長：EPDTv=etav+

3.2 算法框架

給定VNS的最大迭代次數(shù)I，VNS算法步驟如下：

Step 1 將場存數(shù)據(jù)Q和需求數(shù)據(jù)D載入到主程序。

Step 2 設(shè)置在鄰域結(jié)構(gòu)N0和N1內(nèi)執(zhí)行鄰域搜索的迭代次數(shù)為n0和n1。設(shè)置k=0，i=0，n=0，其中k、i和n分別表示第k鄰域結(jié)構(gòu)、第i次迭代和第n次鄰域內(nèi)迭代。

step 3 生成初始解X0，設(shè)置當(dāng)前解X=X0，最優(yōu)解Xb=X0。

step 4 設(shè)置當(dāng)前鄰域結(jié)構(gòu)為Nk，X執(zhí)行迭代次數(shù)為nk的鄰域搜索，在每次迭代中，使用接受準(zhǔn)則判斷是否接受鄰域解，若接受，根據(jù)延遲策略對X執(zhí)行局部搜索，轉(zhuǎn)step5；否則，轉(zhuǎn)step7。

step 5 如果X優(yōu)于Xb，則更新Xb，轉(zhuǎn)step6；否則，轉(zhuǎn)step7。

step 6 設(shè)置n=-1、k=k+1，如果k＞1，則設(shè)置k=0。

step 7 更新參數(shù)i、n，判斷是否達到終止條件，若是，則輸出Xb，結(jié)束程序；否則，轉(zhuǎn)step4。

4 數(shù)值實驗

為了驗證模型和算法的性能，本文根據(jù)港口歷史數(shù)據(jù)生成了10組測試用例，每組用例的船舶數(shù)量為2～7，每艘船舶需求量為10 000～35 000t，輪次數(shù)量為6～25。圖4是一個4艘船舶、11個輪次的測試用例求解的甘特圖，每個矩形代表一個裝船單元，矩形長度表示取料時長，標(biāo)注分別表示取料垛位和設(shè)備。

本次實驗在64位Windows10操作系統(tǒng)，intel?雙核2.30GHz處理器，6G運行內(nèi)存的電腦上完成。VNS算法使用Python3.6語言編寫，VNS的參數(shù)設(shè)置為：最大迭代次數(shù)I=55，鄰域N0內(nèi)迭代次數(shù)n0=5，鄰域N1內(nèi)迭代次數(shù)n1=3，局部搜索參數(shù)m=3。CP模型使用專用的約束規(guī)劃語言Minizinc2.3.2建模[11]，使用chuffed求解器求解。為了提高模型的求解效率，模型變量采用分組求解的策略，先從最重要的變量取料開始時間ts開始分支求解，之后依次確定取料時長ds以及取料設(shè)備rs。其中取料開始時間優(yōu)先嘗試可行域內(nèi)的最小值進行搜索，取料設(shè)備選擇可行域最小的變量先求解。由表1可以看出，制定求解策略后的模型求解效率得到大幅提升，CP的定制求解策略機制有利于充分發(fā)揮建模者的先驗知識，幫助求解器更快找到好的解[7]。

圖4 測試用例的甘特圖示例

表1 制定求解策略對CP模型的影響

為了驗證求解算法的有效性，將純CP模型的求解結(jié)果和加入VNS的求解算法的求解結(jié)果進行對比，并使用前文所述的理論下界評價解的質(zhì)量，求解時間設(shè)定為600s。從表2可看出，CP在數(shù)據(jù)規(guī)模較小的用例中求解效果好，用例1、2、3、4均能求得最優(yōu)解，且僅有用例4的耗時比VNS長。在其他數(shù)據(jù)規(guī)模較大用例中，CP無法在限定的時間內(nèi)求出結(jié)果，VNS則可以求得滿意解，其在用例5、6的求解結(jié)果與理論下界的差距不到1%，其他用例的差距不到10%。

綜合實驗結(jié)果可知，對于小規(guī)模算例，純CP的求解效果更好，但當(dāng)數(shù)據(jù)規(guī)模較大時，CP已無法在有效時間內(nèi)求解，而VNS則能得到較優(yōu)的滿意解。以上分析表明，基于VNS的求解算法是一種求解裝船作業(yè)調(diào)度的有效算法。

表2 CP與VNS的對比結(jié)果

5 結(jié)語

本文針對固定垛位模式下的煤炭出港作業(yè)調(diào)度問題，設(shè)計了結(jié)合CP和VNS的求解算法，算法求解分為兩步，先確定裝船的取料方案，再求解完整模型。將VNS引入到取料方案的優(yōu)化中，其中當(dāng)前解的更新采用Metropolis準(zhǔn)則以一定概率接受劣解，并設(shè)計了一種延遲策略在每次解更新后加速算法的局部收斂。該方法綜合考慮了出港作業(yè)調(diào)度問題的組合性和動態(tài)性，為提高煤炭港口的運作管理效率和水平提供了一種新的思路。