蘇 鑫

(中遠海運散貨運輸有限公司， 天津 300010)

0 引 言

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

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

1) 貨物屬性，包括種類、體積、重量、運費稅和傭金等；

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

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

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

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

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

1 船貨匹配模型和復雜場景概述

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

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

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

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

=+

(1)

式(1)中：為運輸成本；為燃油費；為港口使費。

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

=-(+)

(2)

式(2)中：為運費。

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

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

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

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

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

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

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

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

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

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

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

表5 Open TS的關鍵模塊和船貨雙邊匹配對應功能實現(xiàn)

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

3 算法設計和算例分析

3.1 基于TS的船貨雙邊匹配算法設計

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

1) 應用要求：

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

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

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

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

2) 實施步驟：

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

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

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

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

3.2 船貨雙邊匹配算例分析

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

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

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

表8 歷次更新最優(yōu)解時關鍵指標變化情況

3.3 船貨雙邊匹配方案的利潤計算

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

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

4 結(jié) 語

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

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

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