皮幺梅，夏振喜，王維杰

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

1 引言

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

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

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

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

2 配裝計(jì)劃的最大流模型

2.1 問題描述

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

表1 船舶v1需求的合同煤種對應(yīng)的配煤方案

對于一艘船舶的一種合同煤種，可以同時(shí)選擇多個(gè)配煤方案，即為此合同煤種的配煤方案組合，但每種配煤方案下的基礎(chǔ)原煤取料數(shù)量需滿足配比關(guān)系。并且，每種合同煤種對應(yīng)的配煤方案組合下的總裝船數(shù)量等于船舶對此合同煤種的需求數(shù)量。可以看出，不同船舶之間可能需求相同的基礎(chǔ)原煤，即存在需求競爭關(guān)系。堆場堆存的基礎(chǔ)原煤種類很多，由于地理空間和設(shè)備工藝的限制，垛位堆放的基礎(chǔ)原煤只能被運(yùn)輸?shù)娇傻竭_(dá)若干泊位上，依此，與相同堆場相通的泊位為同類泊位，劃分為同一區(qū)域。與此區(qū)域的泊位相連通的條形堆場分為這一區(qū)域。例如，區(qū)域1內(nèi)的泊位為泊位1、泊位2、泊位3，區(qū)域1內(nèi)的堆場序號為1，2，3，4，5。區(qū)域1的煤炭只可運(yùn)輸?shù)絽^(qū)域1內(nèi)的泊位上。

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

2.2 最大流模型

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

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

其中，式（1）表示目標(biāo)函數(shù)，最大化網(wǎng)絡(luò)總流量，即所有船舶的最大裝船量之和；式（2）表示網(wǎng)絡(luò)流入量等于網(wǎng)絡(luò)流出量，即港口的總?cè)×虾涂傃b船數(shù)量應(yīng)相等；式（3）表示節(jié)點(diǎn)為發(fā)點(diǎn)和收點(diǎn)外的節(jié)點(diǎn)時(shí)，流出量等于流入量，表示單艘船舶的取料數(shù)量與裝船數(shù)量應(yīng)相等；式（4）表示配煤方案中基礎(chǔ)原煤之間的配比約束；式（5）表示一艘船舶只能?？吭谝粋€(gè)區(qū)域的泊位上；式（6）為容量約束，取料數(shù)量不得超過堆垛的剩余場存數(shù)量，且當(dāng)弧是斷開的時(shí)候，弧上流量為零。與一般的網(wǎng)絡(luò)流問題[9]相比，上述的煤炭港口裝配計(jì)劃網(wǎng)絡(luò)流是個(gè)帶特殊約束的網(wǎng)絡(luò)流問題，網(wǎng)絡(luò)圖中邊流量帶比例約束和節(jié)點(diǎn)帶分流約束。

表2 對象及對象屬性

3 禁忌搜索算法

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

假設(shè)船舶優(yōu)先級順序集合為P，船舶V={v1,v2,...,v||P}。優(yōu)先級大小為 p的船舶vp在網(wǎng)絡(luò)圖G對應(yīng)的節(jié)點(diǎn)集合為Nvp。定義最大迭代次數(shù)為T，每次搜索鄰居的個(gè)數(shù)為Num，禁忌表JinjiArr，長度為Len。禁忌搜索算法的設(shè)置如下：

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

（3）解集評價(jià)函數(shù)。將當(dāng)前解集與當(dāng)前最優(yōu)解中船舶vp(vp∈V)的最大裝船量進(jìn)行一對一比較，當(dāng)優(yōu)先級高的船舶表示的點(diǎn)的出弧流量（船舶最大裝船量）更高，則解更優(yōu)。

（4）終止條件。本文采用“迭代步數(shù)準(zhǔn)則”。當(dāng)運(yùn)行到步數(shù)T終止搜索，輸出當(dāng)前最優(yōu)解集。

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

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

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

改進(jìn)的禁忌搜索算法思想如下：對于優(yōu)先級p=1的船舶v1，若Nv1的元素個(gè)數(shù)則計(jì)算網(wǎng)絡(luò)G中只含的節(jié)點(diǎn)，得出Nv1中流量最大的節(jié)點(diǎn)集合，則選出船舶vp+1對應(yīng)的節(jié)點(diǎn)集合中優(yōu)先級下的最大流節(jié)點(diǎn)N'，并令如此，通過對初始解的改進(jìn)，達(dá)到加快禁忌搜索算法的收斂速度，繼而改進(jìn)禁忌搜索算法。

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

本文選取三組不同規(guī)模的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，見表3。A，B，C三組數(shù)據(jù)的船舶個(gè)數(shù)分別為10，20和30。每組數(shù)據(jù)的堆場垛位與船舶等對象構(gòu)成的網(wǎng)絡(luò)規(guī)模隨著船舶個(gè)數(shù)相應(yīng)增加。船舶集合中船舶的編號順序即為船舶的優(yōu)先級順序。分別運(yùn)用禁忌搜索算法和改進(jìn)的禁忌搜索算法求解不同規(guī)模下的煤炭堆場配裝問題。

表3 實(shí)驗(yàn)數(shù)據(jù)規(guī)模

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

表4 數(shù)據(jù)A1下船舶v1的裝船取料計(jì)劃

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

表5 禁忌搜索算法與改進(jìn)的禁忌搜索算法的結(jié)果對比

5 結(jié)語

本文根據(jù)大型煤炭裝卸港口煤炭配裝過程的多個(gè)物流狀態(tài)，建立了煤炭港口配裝計(jì)劃的最大流模型，為煤炭港口的計(jì)劃調(diào)度優(yōu)化問題提供了新的思路?？紤]船舶的服務(wù)優(yōu)先級順序，煤炭配裝問題是個(gè)帶優(yōu)先級順序的組合優(yōu)化問題。本文設(shè)計(jì)了禁忌搜索算法求解這類帶優(yōu)先級順序的組合優(yōu)化問題，并通過對初始解的優(yōu)化來改進(jìn)禁忌搜索算法。最后，算例實(shí)驗(yàn)表明，改進(jìn)的禁忌搜索算法具有較好的收斂性，可以較好地解決煤炭港口配裝計(jì)劃問題，對提高港口服務(wù)效率具有重要意義。