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

皮幺梅，夏振喜，王維杰

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

1 引言

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

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

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

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

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

2.1 問(wèn)題描述

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

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

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

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

2.2 最大流模型

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

網(wǎng)絡(luò)圖的符號(hào)定義如下：節(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表示的對(duì)象，分別為垛位堆存的煤炭數(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ù)量不得超過(guò)堆垛的剩余場(chǎng)存數(shù)量，且當(dāng)弧是斷開(kāi)的時(shí)候，弧上流量為零。與一般的網(wǎng)絡(luò)流問(wèn)題[9]相比，上述的煤炭港口裝配計(jì)劃網(wǎng)絡(luò)流是個(gè)帶特殊約束的網(wǎng)絡(luò)流問(wèn)題，網(wǎng)絡(luò)圖中邊流量帶比例約束和節(jié)點(diǎn)帶分流約束。

表2 對(duì)象及對(duì)象屬性

3 禁忌搜索算法

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

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

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

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

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

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

Algorithm1∶煤炭港口配裝計(jì)劃的禁忌搜索算法（考慮優(yōu)先級(jí)順序）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)先級(jí)順序的網(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的評(píng)價(jià)函數(shù)算法Input：網(wǎng)絡(luò)圖G，解集 F={n1…n||P}Output：每艘船舶在滿(mǎn)足優(yōu)先級(jí)順序的最大裝船數(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)的不足，用禁忌表對(duì)已達(dá)到的局部最優(yōu)解進(jìn)行“記憶”。但是禁忌搜索算法對(duì)初始解的依賴(lài)性較強(qiáng)，較好的初始解能幫助算法更快的收斂，尋到全局最優(yōu)。因此，本文提出了基于初始解的改進(jìn)禁忌搜索算法。

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

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

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

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

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

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

選取三類(lèi)數(shù)據(jù)A，B，C，每類(lèi)數(shù)據(jù)分三組進(jìn)行試驗(yàn)，結(jié)果見(jiàn)表5。通過(guò)對(duì)比可以得出，由于改進(jìn)的禁忌搜索算法對(duì)初始解進(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é)果對(duì)比

5 結(jié)語(yǔ)

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