基于禁忌搜索算法的煤炭港口配裝計劃

皮幺梅，夏振喜，王維杰

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

1 引言

煤炭作為我國的基礎性能源，是我國經濟飛速發展的重要支撐。不同煤種在發熱量、灰分、硫分、水分等特性上存在差異，其質量和對燃煤設備的損耗上也有所區別。為滿足客戶需求，需要將不同種類的基礎原煤按照一定的比例混合后形成客戶需求的合同煤種，這個混合過程就叫做配煤[1]。所需的原煤種類和比例稱為配煤方案，構成合同煤種的配煤方案有多種。隨著配煤迅速發展，配煤業務從煤炭生產企業和用煤企業延伸到了中轉港口。但由于堆場空間和設備限制，配煤方案的選擇和裝船取料時垛位選擇影響整個港口的場存情況，這種配裝的不合理也導致船舶因缺少配煤方案所需的煤種而長時間在港等待。因此，煤炭港口配裝計劃是否科學將直接影響到港口的吞吐能力、船舶在港?？康臅r間以及港口服務水平，進而影響到港口和貨主的經濟利益。而在我國煤炭需求旺季，港口經常出現煤炭場存供不應求的現象。因此，如何合理利用現有場存進行配裝，最大程度地滿足所有船舶需求是煤炭港口面臨的一個重要問題。

堆場是儲煤的場所，按照船舶需求，合理有序的配裝是碼頭作業中的一個重要問題。眾多學者分別從不同的角度分析煤炭港口的配裝問題，并運用不同的數學模型和算法來表述和求解這類問題。Boland等[2]充分考慮到船舶煤炭需求、堆場資源以及時間的不確定性，通過綜合優化泊位分配、堆料位置、裝配開始時間三個方面來提高港口服務效率，建立了堆場動態調度模型，并提出了基于貪婪構架、枚舉和整數規劃相結合的新技術。Savelsbergh[3]等研究澳大利亞獵人谷煤炭鏈中港口配煤的煤炭裝配問題，基于煤炭港口裝配問題在時空圖上顯示的幾何特性，提出了一種樹搜索算法來最大化堆場的吞吐量。Wen等[4]則從另一個角度和方法闡述煤炭配裝問題，將港口配煤裝配問題轉化成特殊順序約束的二維裝箱問題，建立了堆場動態調度CP模型。上述學者們的研究中，港口的條形堆場是連續型的，即配煤方案下煤種是連續堆放在一個條形堆場上。與之不同的是，我國部分大型的配煤港口條形堆場上的垛位是離散型的，每個垛位長度和堆放煤種是固定的，垛位堆放的是未經混合的基礎原煤，如秦皇島港。而針對這種情況下我國煤炭港口的煤炭配裝問題研究很少。

禁忌搜索算法（Tabu Search，TS）[5]是基于領域搜索的全局優化算法，它通過模擬人類思維過程，利用禁忌表記憶局部最優解，達到跳出局部搜索的目的。在解決眾多組合優化問題[6-7]上，TS算法較好地平衡了解的局部集中性和解的全局多樣性問題，是一種局部搜索能力很強的全局迭代尋優算法。但是，TS算法對初始可行解具有較強的依賴性，好的初始可行解能夠提高TS算法的搜索效率，而一個差的初始可行解則會影響TS算法的收斂速度[8]。

本文根據煤炭在煤炭港口的物流階段，以垛位、配煤方案、合同煤種和船舶等以對象建立網絡圖節點，以對象之間的關系建立相應的邊，用帶特殊約束的網絡流問題描述港口的配裝問題，并建立配裝計劃的最大流模型。考慮船舶的優先級順序，煤炭港口的配裝問題是個帶有優先級順序的組合優化問題，本文設計了禁忌搜索算法，并提出了基于初始解的改進禁忌搜索算法。

2 配裝計劃的最大流模型

2.1 問題描述

在一定長度的計劃期內，煤炭港口存在多艘待裝船舶。船舶需求的是合同煤種，一艘船需要的合同煤種一般為一到三種。合同煤種對應的配煤方案是港口已知的，見表1，船舶v1需求的合同煤種為d1，d2兩種。對于每種合同煤種，其配煤方案為多個。每種配煤方案由含比例關系的一到兩種基礎原煤組成。

表1 船舶v1需求的合同煤種對應的配煤方案

對于一艘船舶的一種合同煤種，可以同時選擇多個配煤方案，即為此合同煤種的配煤方案組合，但每種配煤方案下的基礎原煤取料數量需滿足配比關系。并且，每種合同煤種對應的配煤方案組合下的總裝船數量等于船舶對此合同煤種的需求數量?？梢钥闯?，不同船舶之間可能需求相同的基礎原煤，即存在需求競爭關系。堆場堆存的基礎原煤種類很多，由于地理空間和設備工藝的限制，垛位堆放的基礎原煤只能被運輸到可到達若干泊位上，依此，與相同堆場相通的泊位為同類泊位，劃分為同一區域。與此區域的泊位相連通的條形堆場分為這一區域。例如，區域1內的泊位為泊位1、泊位2、泊位3，區域1內的堆場序號為1，2，3，4，5。區域1的煤炭只可運輸到區域1內的泊位上。

假設堆場在該規劃期內不會補充庫存，已靠泊船舶不允許更換泊位，船舶之間存在服務優先級順序，港口的場存優先滿足高優先級船舶的需求?；诖耍禾扛劭诘呐溲b計劃是根據堆場堆存的煤炭種類和數量，泊位與堆場的可達性，計劃船舶合同煤種的配煤方案組合，在滿足配煤方案下煤種和配比要求的情況下，為船舶安排具體的取料垛位和相應的取料數量，以滿足優先級順序下的船舶需求。

2.2 最大流模型

設G=(N ,A)是有向網絡圖，N，A分別為網絡圖G中的節點集合和邊集合。在本問題中，研究對象包括垛位、配煤方案、合同煤種、船舶，其屬性見表2。按照對象屬性，分別建立垛位、配煤方案、合同煤種、船舶節點及發點與垛位層、垛位層與配煤方案層、配煤方案和合同煤種層、合同煤種層和船舶層、船舶層與到收點之間的邊。

網絡圖的符號定義如下：節點集合N={s,t}?Nm?Nl?Nd?Nv，其中，s和 t分別為發點和收點，Nm、Nl、Nd、Nv分別表示垛位層、配煤方案層、合同煤種層和船舶層的節點集合。Nv表示船舶v(v∈V)代表的節點集合，Nv∈Nv。配煤方案節點i的比例為ki，節點i的入弧左節點中（垛位節點），此配煤方案的第一種基礎原煤c的節點集合為Nc1，表1i示基礎原煤c的節點集合為Nc2。(i,j)∈A表示網絡2i圖中的有向邊，i,j表示網絡的兩個節點,δ-(i)和δ+(i)分別表示節點i的入弧和出弧集合。uij表示邊(i,j)上的容量，按照節點i,j表示的對象，分別為垛位堆存的煤炭數量、合同煤種需求、船舶總需求等。xij，yij為模型的兩個決策變量，xij表示邊(i,j)上的流量，0≤xij≤uij。yij表示邊(i,j)是否連通,連通時值為1，否則為0，即yij∈{0,1}。則煤炭港口的裝配網絡流模型如下：

其中，式（1）表示目標函數，最大化網絡總流量，即所有船舶的最大裝船量之和；式（2）表示網絡流入量等于網絡流出量，即港口的總取料和總裝船數量應相等；式（3）表示節點為發點和收點外的節點時，流出量等于流入量，表示單艘船舶的取料數量與裝船數量應相等；式（4）表示配煤方案中基礎原煤之間的配比約束；式（5）表示一艘船舶只能停靠在一個區域的泊位上；式（6）為容量約束，取料數量不得超過堆垛的剩余場存數量，且當弧是斷開的時候，弧上流量為零。與一般的網絡流問題[9]相比，上述的煤炭港口裝配計劃網絡流是個帶特殊約束的網絡流問題，網絡圖中邊流量帶比例約束和節點帶分流約束。

表2 對象及對象屬性

3 禁忌搜索算法

船舶的服務優先級順序是煤炭港口配裝計劃過程的重要考慮因素。在網絡圖G中，船舶的優先級順序體現在船舶層節點Nv的出弧帶優先級順序，優先級高的節點應被優先通過最大流量。對于邊含優先級順序的網絡流問題，可以被轉化成邊帶權重的網絡流問題，而隨著邊的個數增加，權重大小將呈指數型增長。為解決船舶含服務優先級順序的配裝計劃問題，本文將其考慮為邊含優先級順序的網絡流問題，并提出禁忌搜索算法及其改進。禁忌搜索的基本思想為：從一個初始可行解出發，選擇一系列的特定移動方向搜索局部最優值，通過對局部最優解的禁忌，達到跳出局部搜索的目的，其有效的鄰域變換實現全局優化。

假設船舶優先級順序集合為P，船舶V={v1,v2,...,v||P}。優先級大小為 p的船舶vp在網絡圖G對應的節點集合為Nvp。定義最大迭代次數為T，每次搜索鄰居的個數為Num，禁忌表JinjiArr，長度為Len。禁忌搜索算法的設置如下：

（2）鄰域選擇。鄰域移動采用“節點變換法”，即對解空間中兩個船舶的節點進行隨機變換。隨機選取兩艘船舶vi和vj，從船舶vi和vj對應的節點集合中各隨機選擇一個不同的節點ni和nj，形成新的解空間 F'，如F'={n1…ni…nj…n|P|}。

（3）解集評價函數。將當前解集與當前最優解中船舶vp(vp∈V)的最大裝船量進行一對一比較，當優先級高的船舶表示的點的出弧流量（船舶最大裝船量）更高，則解更優。

（4）終止條件。本文采用“迭代步數準則”。當運行到步數T終止搜索，輸出當前最優解集。

禁忌搜索算法過程如下，其中，Algorithm1為煤炭港口配裝計劃的禁忌搜索算法，Algorithm2為解集F的評價函數算法。

Algorithm1∶煤炭港口配裝計劃的禁忌搜索算法（考慮優先級順序）Input：網絡圖G ，Nv||P(?vp∈V)，初始解集 F0 Output：當前最優解集Fbest，解集下的節點最大流量集合MFbest Function：TS_Pr iority(G,F 0)初始化MFbest=φ，Fbest=φ MFbest=Maxflow(G,F 0)for t=0;t＜T;t++令當代最優解Flocal=φ，臨時解Ftemp=φ當代最優解和臨時解下的節點流量集合MFlocal=φ，MFtemp=φ for num=0;num＜Num;num++隨機選取F 0的鄰居Ftemp，若Ftemp在禁忌表，則重新選取Ftemp計算優先級順序的網絡最大流量，MFtemp=Maxflow(G,Ftemp)比較MFlocal與MFtemp若 MFtemp優于 MFlocal，則 MFlocal=MFtemp end for比較 MFlocal與MFbest若 MFlocal優于 MFbest，則 MFbest=MFlocal，Fbest=Flocal刪除JinjiArr第一個元素，將Flocal加入禁忌表JinjiArr end for Algorithm2∶解集F的評價函數算法Input：網絡圖G，解集 F={n1…n||P}Output：每艘船舶在滿足優先級順序的最大裝船數量集合MF Function：Maxflow(G,F)初始化：網絡圖G中的船舶層節點，得G'。令MF=φ for p=0;p＜ ||P;p++將np加入到G'，計算網絡最大流下的節點np的出弧流量 flownp固定網絡圖G'中節點np的出弧流量 flownp ，更新G'MF=MF?{flownp}end for

禁忌搜索算法采用了禁忌技術，彌補了局部搜索算法可能陷入局部最優的不足，用禁忌表對已達到的局部最優解進行“記憶”。但是禁忌搜索算法對初始解的依賴性較強，較好的初始解能幫助算法更快的收斂，尋到全局最優。因此，本文提出了基于初始解的改進禁忌搜索算法。

改進的禁忌搜索算法思想如下：對于優先級p=1的船舶v1，若Nv1的元素個數則計算網絡G中只含的節點，得出Nv1中流量最大的節點集合，則選出船舶vp+1對應的節點集合中優先級下的最大流節點N'，并令如此，通過對初始解的改進，達到加快禁忌搜索算法的收斂速度，繼而改進禁忌搜索算法。

4 數值實驗

本文選取三組不同規模的數據進行實驗，見表3。A，B，C三組數據的船舶個數分別為10，20和30。每組數據的堆場垛位與船舶等對象構成的網絡規模隨著船舶個數相應增加。船舶集合中船舶的編號順序即為船舶的優先級順序。分別運用禁忌搜索算法和改進的禁忌搜索算法求解不同規模下的煤炭堆場配裝問題。

表3 實驗數據規模

本實驗是在64位操作系統，英特爾雙核2.30GHz的處理器，6G運行內存的個人電腦上完成，運用java語言編程，結合CPLEX求解器，運用禁忌搜索算法求解煤炭碼頭的裝配計劃最優解。令最大迭代次數為T=100，每次搜索鄰居的個數為Num=20，禁忌表JinjiArr，長度為Len=20。以數據A1的求解結果為例，船舶v1的配裝計劃見表4。

表4 數據A1下船舶v1的裝船取料計劃

選取三類數據A，B，C，每類數據分三組進行試驗，結果見表5。通過對比可以得出，由于改進的禁忌搜索算法對初始解進行了改進，其改進的禁忌搜索算法略高于禁忌搜索算法。但是，9組不同規模的數據實驗結果中，改進的禁忌搜索算法的最優解出現的代數要平均早于禁忌搜索算法最優解出現的代數。這表明改進的禁忌搜索算法的收斂速度要優于未改進的禁忌搜索算法，算法的改進是有效的。由于改進的禁忌搜索算法在進行局部搜索之前，需要進行初始解的改進，所以，在求解時間上略高于未改進的禁忌搜索算法。

表5 禁忌搜索算法與改進的禁忌搜索算法的結果對比

5 結語

本文根據大型煤炭裝卸港口煤炭配裝過程的多個物流狀態，建立了煤炭港口配裝計劃的最大流模型，為煤炭港口的計劃調度優化問題提供了新的思路。考慮船舶的服務優先級順序，煤炭配裝問題是個帶優先級順序的組合優化問題。本文設計了禁忌搜索算法求解這類帶優先級順序的組合優化問題，并通過對初始解的優化來改進禁忌搜索算法。最后，算例實驗表明，改進的禁忌搜索算法具有較好的收斂性，可以較好地解決煤炭港口配裝計劃問題，對提高港口服務效率具有重要意義。