一種基于禁忌搜索算法的散貨船船貨雙邊匹配模型

蘇 鑫

(中遠(yuǎn)海運(yùn)散貨運(yùn)輸有限公司， 天津 300010)

0 引 言

不定期船運(yùn)輸方式在世界海運(yùn)貨物運(yùn)輸中占有重要地位。據(jù)統(tǒng)計(jì)，目前世界上不定期船運(yùn)輸航線的船舶空載率約為40%。由于船貨信息不對稱和缺少運(yùn)營決策工具的支持，主要貨源的地理位置分布不均勻，大宗散貨貿(mào)易運(yùn)輸?shù)拇翱蛰d率較高。很多航運(yùn)企業(yè)都在嘗試通過現(xiàn)代化的經(jīng)營管理手段進(jìn)一步提高船舶的利用率，縮短船舶空載航行時(shí)間和空載航程。

船貨匹配屬于典型的多屬性匹配問題。在實(shí)際的船貨匹配操作中，需考慮船舶運(yùn)力的基礎(chǔ)信息、貨物運(yùn)輸?shù)膶?shí)際要求和掛靠港口的注意事項(xiàng)等內(nèi)容。根據(jù)黃興文所述航次方案優(yōu)選分析因素，影響散貨運(yùn)輸?shù)膶傩灾饕校?/p>

1) 貨物屬性，包括種類、體積、重量、運(yùn)費(fèi)稅和傭金等；

2) 船舶屬性，包括吃水、夏季載重量、艙容、運(yùn)河載重量、航速油耗和預(yù)估每日費(fèi)用等；

3) 港口屬性，包括港口水深、泊位分類、裝/卸貨作業(yè)效率、港口里程和港口使費(fèi)等；

4) 路徑因素，包括船舶預(yù)空位置、加油港選擇和航線設(shè)計(jì)等，具體的貨物運(yùn)輸路徑由承運(yùn)人控制。

禁忌搜索(Tabu Search，TS)算法是一種智能優(yōu)化算法，在組合優(yōu)化和生產(chǎn)調(diào)度等方面得到了廣泛應(yīng)用。TS算法是通過擴(kuò)展局部鄰域搜索模擬人類智力過程，實(shí)現(xiàn)全局逐步尋優(yōu)的算法。該算法使用禁忌表避免出現(xiàn)迂回搜索的問題，借助藐視準(zhǔn)則解決優(yōu)良狀態(tài)被禁忌的問題，確保探索的多樣化和有效性，實(shí)現(xiàn)全局優(yōu)化的目標(biāo)。

盡管當(dāng)前有關(guān)匹配方法的研究已有很多，但滿足遠(yuǎn)洋貿(mào)易運(yùn)輸行業(yè)需求的船貨匹配方法還比較少。本文在已有研究的基礎(chǔ)上,研究復(fù)雜場景下散貨運(yùn)輸?shù)淖顑?yōu)決策問題，選取船貨雙邊匹配案例進(jìn)行建模，以最小化整體航次時(shí)間成本為最終目標(biāo)，解決多票貨物與多艘船舶的匹配問題。

1 船貨匹配模型和復(fù)雜場景概述

船貨匹配屬于多屬性匹配。散貨船運(yùn)輸是一種不定船期的航次貨物運(yùn)輸，根據(jù)航次任務(wù)的需求制訂航次計(jì)劃，綜合考慮執(zhí)行航次任務(wù)的船舶情況、貨物基本信息、貨物特殊運(yùn)輸要求、裝/卸貨港口的實(shí)際運(yùn)營能力、航線是否途經(jīng)運(yùn)河、空載/滿載航行里程和燃油消耗等內(nèi)容。根據(jù)以往的研究成果，本文所述船貨匹配模型用到的關(guān)鍵數(shù)據(jù)集包括船盤、貨盤和港口里程，具體的數(shù)據(jù)集屬性見表1。

表1 船貨匹配模型關(guān)鍵數(shù)據(jù)集屬性

簡單場景下的船貨匹配模型主要包括以貨定船和以船定貨2種，其中：以貨定船是指為確定的貨物(已知信息包括貨量、貨種信息、裝/卸貨時(shí)間、裝/卸貨港口和運(yùn)費(fèi)等)選取合適的執(zhí)行航次任務(wù)的船舶；以船定貨是指挑選合適的貨物，由指定的船舶完成航次任務(wù)。試驗(yàn)分析中，選取2項(xiàng)關(guān)鍵成本費(fèi)用(燃油費(fèi)和港口使費(fèi))進(jìn)行研究。

1) 在以貨定船模型中，在運(yùn)費(fèi)收入固定的情況下追求的是航次成本最低，以貨定船的成本目標(biāo)函數(shù)為

=+

(1)

式(1)中：為運(yùn)輸成本；為燃油費(fèi)；為港口使費(fèi)。

2) 以船定貨模型相對以貨定船模型需考慮不同的收入變動(dòng)，為指定船舶匹配合適的貨物，追求凈利潤最大化，的計(jì)算公式為

=-(+)

(2)

式(2)中：為運(yùn)費(fèi)。

以上2個(gè)模型適用于簡單場景下的船貨匹配，無法滿足復(fù)雜場景下的多艘船舶與多票貨物的雙邊匹配要求。

在實(shí)際應(yīng)用這2個(gè)模型過程中會(huì)出現(xiàn)船貨匹配沖突的情況，下面通過一個(gè)案例進(jìn)行說明(船舶和貨物信息分別見表2和表3)。對表2中的船舶執(zhí)行以船定貨操作，通過模型計(jì)算發(fā)現(xiàn)為它們匹配的最優(yōu)貨物為同一票貨物M。由表2可知，存在競爭的可執(zhí)行航次任務(wù)的船舶的基本情況類似，主要區(qū)別在于船舶的預(yù)空港口和預(yù)空時(shí)間不同。簡單地通過以船定貨模型為船舶V1、V2、V3和V4求解最優(yōu)匹配貨物已無法滿足實(shí)際決策要求，需借助新的匹配模型解決此類問題。

船貨雙邊匹配是一種復(fù)雜場景下的匹配問題。以貨定船和以船定貨2種模型能解決針對1票特定貨物從眾多候選船舶中選取最優(yōu)船舶和為指定船舶挑選最大利潤貨物的問題。在實(shí)際業(yè)務(wù)操作中，存在一種復(fù)雜場景，即：業(yè)務(wù)人員將船舶信息和貨物信息錄入系統(tǒng)之后，不會(huì)立即執(zhí)行匹配操作，而是在新的匹配對象錄入之后再進(jìn)行區(qū)域性船貨匹配操作。系統(tǒng)中會(huì)存在一定數(shù)量的未配載船舶和待匹配貨物，需依靠船貨雙邊匹配模型，從充分運(yùn)用船舶運(yùn)力、減少船舶空載航行時(shí)間和降低貨物滯留成本的角度充分挖掘潛在的機(jī)會(huì)，更好地為業(yè)務(wù)人員提供決策支持。

表2 執(zhí)行“以船定貨”存在沖突的船舶列表

表3 執(zhí)行“以船定貨”存在沖突的船舶最優(yōu)匹配貨物信息

決策偏好決定雙邊匹配的優(yōu)化目標(biāo)。從船舶所有人的角度考慮，優(yōu)化目標(biāo)包括最小化船舶航行距離和最小化船舶最長完工時(shí)間；從貨主的角度考慮，優(yōu)化目標(biāo)為最小化貨物等待時(shí)間；從整體的角度考慮，優(yōu)化目標(biāo)包括最大化船貨匹配訂單數(shù)和最大化經(jīng)營收益等。此外，還有更加個(gè)性化的決策偏好，例如大客戶的貨物優(yōu)先匹配和考慮船位價(jià)值的船舶擺位等。在激烈的航運(yùn)市場競爭環(huán)境中，基于決策偏好進(jìn)行高效、準(zhǔn)確的船貨雙邊匹配是保證船舶所有人盈利的關(guān)鍵基礎(chǔ)，對進(jìn)一步提高貨主的滿意度和提升航運(yùn)服務(wù)水平具有重要意義。

2 基于TS算法的船貨雙邊匹配模型

本文借鑒經(jīng)典的帶時(shí)間窗車輛路徑問題(Vehicle Routing Problem with Time Windows，VRPTW)的思想解決船貨雙邊匹配問題，利用TS算法求解組合最優(yōu)化問題。

TS算法是一種智能化的組合最優(yōu)化算法。該算法借助禁忌技術(shù)，能有效避免因鄰域搜索而陷入局部最優(yōu)的窘境，通過禁忌表記錄已取得的局部最優(yōu)解和取得局部最優(yōu)解的過程，達(dá)到在下一次搜索時(shí)跳出局部最優(yōu)解的目標(biāo)。TS算法的設(shè)計(jì)核心包括禁忌對象、禁忌長度、鄰域結(jié)構(gòu)、評價(jià)函數(shù)、候選集、特赦規(guī)則和終止規(guī)則。表4為本文提出的基于TS算法的船貨雙邊匹配模型詳細(xì)信息。

表4 基于TS算法的船貨雙邊匹配模型詳細(xì)信息

本文基于開源框架Open TS(Open Tabu Search)對模型進(jìn)行二次開發(fā)，求解船貨雙邊匹配問題。在搭建船貨雙邊匹配模型過程中，重點(diǎn)將船貨匹配的特定問題轉(zhuǎn)換為通用VRPTW問題，從而利用Open TS求解最優(yōu)匹配組合。表5為Open TS的關(guān)鍵模塊和船貨雙邊匹配對應(yīng)功能實(shí)現(xiàn)。下面以具體問題為例闡述基于Open TS求解VRPTW問題的原理，相關(guān)說明見圖1，其中:r1和r2為2個(gè)隊(duì)列;方框表示起點(diǎn)和終點(diǎn)。每個(gè)隊(duì)列對應(yīng)1艘船舶，隊(duì)列中每個(gè)圓圈的先后順序代表船舶執(zhí)行不同載貨任務(wù)，1個(gè)圓圈代表1項(xiàng)裝/卸貨任務(wù)。r1的執(zhí)行順序?yàn)?→1→9→2→3；r2的執(zhí)行順序?yàn)?→8→5→11→12。當(dāng)前的船貨雙邊匹配關(guān)系認(rèn)為是Open TS中的一個(gè)解決方案(Solution)，經(jīng)過TS的迭代發(fā)現(xiàn)，r1中的4與r2中的7交換執(zhí)行任務(wù)有助于提高整體收益，此時(shí)產(chǎn)生了1個(gè)移動(dòng)動(dòng)作(ComplexMove)。經(jīng)過1個(gè)移動(dòng)動(dòng)作之后，r1的執(zhí)行順序?yàn)?→1→9→2→3，r2的執(zhí)行順序?yàn)?→8→5→11→12。不斷地進(jìn)行迭代搜索，直至尋找到整體最優(yōu)的匹配方案。

表5 Open TS的關(guān)鍵模塊和船貨雙邊匹配對應(yīng)功能實(shí)現(xiàn)

圖1 基于Open TS求解VRPTW問題的原理說明

3 算法設(shè)計(jì)和算例分析

3.1 基于TS的船貨雙邊匹配算法設(shè)計(jì)

本文提出的算法側(cè)重于解決多艘船與多票貨物在執(zhí)行以船定貨或以貨定船操作過程中存在的最優(yōu)匹配沖突問題，從最小化時(shí)間成本函數(shù)的角度求解船貨雙邊匹配問題。匹配算法的應(yīng)用要求和實(shí)施步驟如下。

1) 應(yīng)用要求：

(1) 同一票貨物只會(huì)配載到1艘船上。若有1票貨物裝多艘船的需要，提前進(jìn)行貨物拆分操作，將該情況視為多票貨物配載處理。

(2) 若執(zhí)行航次任務(wù)的船舶提前抵達(dá)裝貨港口,需進(jìn)行等待;若執(zhí)行航次任務(wù)的船舶提前抵達(dá)卸貨港口,無需等待，直接進(jìn)行卸貨作業(yè)即可。

(3) 暫時(shí)不考慮貨物在裝/卸貨港口的作業(yè)時(shí)間。

(4) 船舶必須按貨物的受載時(shí)間抵達(dá)裝/卸貨港口。

2) 實(shí)施步驟：

(1) 為船盤中的每艘船執(zhí)行以船定貨操作，生成按利潤最大化倒序排列的貨物信息列表，匯總待匹配貨物信息，生成待匹配的貨盤；

(2) 按船貨匹配利潤最大化的原則將貨盤中的貨物依次分配到各船上，生成初始可行解；

(3) 執(zhí)行TS算法，求解最優(yōu)的船貨雙邊匹配方案。

在迭代搜索中，移動(dòng)動(dòng)作設(shè)計(jì)為將1票貨物M從A船移動(dòng)到B船時(shí)，1個(gè)動(dòng)作會(huì)被分為2步執(zhí)行。第一步會(huì)將貨物M從A船已有的執(zhí)行計(jì)劃中刪除，刪除的位置有3種可能(隊(duì)列頭部、隊(duì)列尾部和隊(duì)列中間)；第二步會(huì)將貨物M插入B船現(xiàn)有的執(zhí)行任務(wù)中，插入的位置有4種可能(隊(duì)列為空、隊(duì)列頭部、隊(duì)列尾部和隊(duì)列中間)。計(jì)算執(zhí)行動(dòng)作之后引起成本目標(biāo)函數(shù)發(fā)生變化。采用TS算法，不斷更新最優(yōu)解的匹配方案。

3.2 船貨雙邊匹配算例分析

選取5艘船進(jìn)行以船定貨操作，按最大利潤貨物優(yōu)先配載的原則初始化船舶運(yùn)輸任務(wù)，初始化的船貨雙邊匹配方案見表6,其中“初始運(yùn)輸任務(wù)計(jì)劃”一列中的數(shù)字為貨物編號。以船舶V1為例，其運(yùn)輸任務(wù)計(jì)劃包含5票貨物(20、24、31、50和53)，5艘船的初始運(yùn)輸任務(wù)計(jì)劃共包含12票貨物。執(zhí)行TS算法，經(jīng)過1 000次迭代，最優(yōu)解被更新7次，表7為歷次更新最優(yōu)解時(shí)船貨雙邊匹配方案的變化情況，其中“船貨雙邊匹配方案”一列中的數(shù)字為貨物編號。對比第1次更新后的匹配方案與初始化的匹配方案可發(fā)現(xiàn)，V1原有的31號貨物被挪動(dòng)到了V3執(zhí)行。經(jīng)過數(shù)次更新，算法最終得到收斂，得到了最優(yōu)解，第6次更新與第7次更新的最優(yōu)匹配方案相同。表8為歷次更新最優(yōu)解時(shí)關(guān)鍵指標(biāo)變化情況，從目標(biāo)函數(shù)值、總收入和凈利潤的維度展示了數(shù)次更新中相關(guān)指標(biāo)的變化情況。 隨著搜索的不斷進(jìn)行，目標(biāo)函數(shù)值不斷減小，從38.91減小至32.89。本文提出的船貨雙邊匹配模型的目標(biāo)函數(shù)設(shè)計(jì)包含航行時(shí)間成本、停時(shí)成本和違反時(shí)間窗口成本，具體情況參考表4中有關(guān)評價(jià)函數(shù)的描述。

表6 初始化的船貨雙邊匹配方案

表7 歷次更新最優(yōu)解時(shí)船貨雙邊匹配方案的變化情況

表8 歷次更新最優(yōu)解時(shí)關(guān)鍵指標(biāo)變化情況

3.3 船貨雙邊匹配方案的利潤計(jì)算

一次解更新生成的雙邊匹配方案的利潤計(jì)算可拆分成多個(gè)單票貨物與指定船舶匹配之后的利潤計(jì)算。以表7中第7次更新生成的方案關(guān)于船舶V2的貨物運(yùn)輸任務(wù)為例，V2的配載計(jì)劃為74→77→79→80。已有研究支持單票貨物與指定船舶匹配之后的利潤計(jì)算。首先計(jì)算V2運(yùn)輸74號貨物的利潤，74號貨物最終的卸貨港口是執(zhí)行77號貨物運(yùn)輸任務(wù)的起始預(yù)空港口；以此類推，直至V2完成所有貨物運(yùn)輸任務(wù)，計(jì)算該船完成所有貨物運(yùn)輸任務(wù)之后產(chǎn)生的利潤。以此類推，對所有船舶(V1、V2、V3、V4和V5)執(zhí)行運(yùn)輸任務(wù)之后產(chǎn)生的利潤求和，將所得結(jié)果作為此次更新方案的最終利潤。

基于保護(hù)商業(yè)機(jī)密考慮，采用統(tǒng)一標(biāo)識表示總收入，采用標(biāo)準(zhǔn)量化處理凈利潤，以初始解的凈利潤為參照。每次更新最優(yōu)匹配方案時(shí)，貨物在不同船舶的運(yùn)輸計(jì)劃中挪動(dòng)，船舶不會(huì)拒絕某票貨物的配載服務(wù)，因此整體收入保持不變。觀察凈利潤指標(biāo)的變化情況，隨著最優(yōu)匹配解的更新，凈利潤先下降后升高。出現(xiàn)凈利潤下降現(xiàn)象的原因是目標(biāo)函數(shù)更側(cè)重于時(shí)間和違規(guī)懲罰(例如超載、違反時(shí)間窗口要求)，凈利潤的計(jì)算與目標(biāo)函數(shù)直接相關(guān)，但還需考慮不同船舶空載/滿載航行時(shí)的耗油量區(qū)別。經(jīng)過TS的不斷更新迭代，凈利潤最優(yōu)解在初始解的基礎(chǔ)上提升了5%，進(jìn)一步驗(yàn)證了本文提出的船貨雙邊匹配模型的有效性。

4 結(jié) 語

本文針對散貨運(yùn)輸?shù)膹?fù)雜業(yè)務(wù)場景構(gòu)建了船貨雙邊匹配模型，根據(jù)多屬性匹配的思想提出了考慮貨物受載期、空載/滿載航行距離、港口使費(fèi)和燃油成本等因素的損失懲罰計(jì)算方法和收益計(jì)算方法，快速求解潛在匹配方案，實(shí)現(xiàn)最優(yōu)船貨雙邊匹配。后續(xù)可進(jìn)一步對該模型進(jìn)行改進(jìn)，例如：

1) 目前船抵達(dá)裝/卸貨港口的時(shí)間窗口約束采用的是硬時(shí)間窗口約束，即若運(yùn)輸任務(wù)不能在規(guī)定的時(shí)間內(nèi)完成，則直接舍棄當(dāng)前方案。該約束條件過于嚴(yán)苛，調(diào)整決策偏好接受軟時(shí)間窗口，能發(fā)現(xiàn)更多潛在高利潤方案，需由業(yè)務(wù)人員根據(jù)經(jīng)營管理需要調(diào)整評價(jià)函數(shù)。

2) 對評價(jià)函數(shù)進(jìn)行優(yōu)化設(shè)計(jì)和豐富完善。本文提出的船貨雙邊匹配評價(jià)函數(shù)側(cè)重于航行時(shí)間和硬時(shí)間窗口約束，未來可結(jié)合業(yè)務(wù)決策關(guān)注的重點(diǎn)，進(jìn)一步完善評價(jià)函數(shù)的設(shè)計(jì)內(nèi)容。