基于節(jié)點換裝時間不確定的多任務(wù)集裝箱運輸方案優(yōu)化

王清斌，董 悅

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）

0 引言

為高效率、低成本地完成集裝箱多式聯(lián)運運輸任務(wù),集裝箱多式聯(lián)運在制訂多任務(wù)的運輸計劃時,需要考慮運達時間限制、運輸方式和運輸路徑的選擇等因素,以及在中轉(zhuǎn)站進行運輸方式換裝過程中的時間因素,這樣才能確保多任務(wù)集裝箱運輸方案的合理性。在實際中,由于中轉(zhuǎn)站進行換裝作業(yè)的場地和設(shè)備等資源有限,而需要進行換裝作業(yè)的集裝箱量每天也不確定,使得這些資源被占用的情況無法確定。因此,集裝箱多式聯(lián)運在進行運輸方式和運輸路徑的選擇時,難以事先確定到達中轉(zhuǎn)站后的換裝時間,給集裝箱多式聯(lián)運的運輸組織決策帶來了難度。

國內(nèi)外很多學者在集裝箱多式聯(lián)運方案優(yōu)化研究方面已經(jīng)進行了較為廣泛和深入的研究。Wang等[1]在研究集裝箱多式聯(lián)運運輸方式組合優(yōu)化問題時考慮了箱型的選擇和運輸需求量為模糊的情況。Burak等[2]在進行集裝箱多式聯(lián)運運輸任務(wù)最優(yōu)路徑的選擇時,考慮海運服務(wù)是按照時間表運行的特點。Jae等[3]提出一種應(yīng)用標簽設(shè)置算法和修剪規(guī)則的動態(tài)規(guī)劃算法,以解決進出口國際集裝箱運輸?shù)募訖?quán)約束最短路徑問題。Li等[4]為解決動態(tài)的運輸需求和動態(tài)交通狀況,提出了一種滾動時域控制方法來解決深海碼頭與內(nèi)陸貨運港內(nèi)陸碼頭之間的聯(lián)運集裝箱流量分配問題。胡星星等[5]重點考慮運輸能力對集裝箱運輸方式選擇的影響。呂學偉等[6]研究在實際運輸過程中,混合時間窗對多式聯(lián)運最優(yōu)運輸方案選擇的重要影響。劉維林[7]針對集裝箱國際多式聯(lián)運網(wǎng)絡(luò)路徑的復雜性,通過設(shè)計動態(tài)蟻群算法提高模型的尋優(yōu)能力,為多式聯(lián)運最短路問題提供可靠的優(yōu)化方法。蔣洋等[8]提出采用交叉熵算法來解決多式聯(lián)運運輸方案選擇問題,通過實例驗證了算法的有效性。李愈等[9]研究同時考慮固定運輸費用和變動運輸費用的具有時間窗和能力限制的最短路徑問題。黃澤漢等[10]提出一種基于多蟻群并行優(yōu)化的網(wǎng)絡(luò)路徑規(guī)劃算法,按照一定的策略對關(guān)鍵網(wǎng)絡(luò)資源進行調(diào)度分配,同時滿足多個任務(wù)的運輸需求。劉杰等[11]考慮實際中鐵路、航空以及水運固定出發(fā)時間對多式聯(lián)運運輸任務(wù)路徑選擇的影響,并將運輸費用細化為固定費用、路段運輸費用、中轉(zhuǎn)費用以及等待出發(fā)的費用。王偉偉[12]指出集裝箱多式聯(lián)運是鐵路貨運與現(xiàn)代物流融合發(fā)展的重要方向。

目前在集裝箱多式聯(lián)運方面的研究大多都假定在節(jié)點進行運輸方式換裝時間是某一固定值,而未考慮換裝時間的變化對運輸路線和運輸方式選擇的影響。在實際作業(yè)中,當集裝箱在不同運輸方式間進行換裝時,常常因為等待或受其他不確定因素的影響,其換裝時間帶有一定的不確定性。另外,很多研究忽略了班輪具有固定出發(fā)時刻同時可用的箱位數(shù)存在限制等現(xiàn)實情況的影響?；谝陨涎芯?還應(yīng)綜合研究在集裝箱多式聯(lián)運組織多個任務(wù)時,換裝時間的不確定性、班輪的特性和不同任務(wù)優(yōu)先級策略等因素對運輸方案選擇的影響。

1 基于節(jié)點換裝時間不確定的多任務(wù)集裝箱運輸方案優(yōu)化模型及算法

在集裝箱多式聯(lián)運網(wǎng)絡(luò)中,將每2個節(jié)點間產(chǎn)生的集裝箱運輸需求看作一個任務(wù),每個任務(wù)的產(chǎn)生時間、集裝箱運量和運達期限已知,水運運段為按照固定船期表運行的班輪運輸,并且每個班期可用箱位數(shù)已知,不同運輸方式在節(jié)點上的換裝作業(yè)時間不確定,需要以最低的成本在所有任務(wù)的規(guī)定期限內(nèi)完成運輸?？梢钥闯?該問題是一個帶有時間和容量約束的多源多匯最短路問題?；诙嗳蝿?wù)集裝箱運輸方案優(yōu)化問題的特點,建立整數(shù)規(guī)劃模型,采用蟻群并行算法求解。

1.1 模型構(gòu)建

假設(shè)運量不可分割且使用單一箱型；集裝箱只在節(jié)點處發(fā)生運輸方式的轉(zhuǎn)換,同時不考慮在節(jié)點的等待成本；公路和鐵路運輸不受運輸能力和出發(fā)時刻的限制,在水運運段按照船期表運行且每個班次的可用箱位數(shù)已知。基于以上假設(shè),多任務(wù)集裝箱運輸方案優(yōu)化模型構(gòu)建如下。

式中：V為節(jié)點集合；M為集合運輸任務(wù)；K為運輸方式集合,K= {1,2,3},其中1代表公路運輸,2代表鐵路運輸；3代表水路運輸；ta,m為任務(wù)m的產(chǎn)生時刻,m∈M；tf,m為任務(wù)m到終點的最晚允許到達時刻；qm為任務(wù)m的集裝箱數(shù)量為任務(wù)m在節(jié)點i由運輸方式k換裝到s的時間,為任務(wù)m在節(jié)點i由k換裝到s的等待時間為在節(jié)點i由k換裝到s的單箱平均作業(yè)時間為運輸方式k從節(jié)點i到j(luò)需要的時間；為運輸方式k從節(jié)點i到j(luò)的單位運輸成本；為在節(jié)點i由k換裝到s的單箱換裝成本；Ai,m為任務(wù)m到達中間節(jié)點i的時刻為從節(jié)點i到j(luò)的班次的數(shù)量為水路運輸從節(jié)點i到j(luò)的第l個班次的出發(fā)時刻為節(jié)點i到j(luò)的第l個班次的可用箱位數(shù)為節(jié)點i的后向節(jié)點為節(jié)點i的前向節(jié)點；om為任務(wù)m的起點；dm為任務(wù)m的終點為任務(wù)m選擇運輸路徑和方式的決策變量,當任務(wù)m從節(jié)點i到j(luò)選擇運輸方式k時,當任務(wù)m沒有從節(jié)點i到j(luò)選擇運輸方式k時為任務(wù)m在節(jié)點i發(fā)生運輸方式轉(zhuǎn)換的決策變量,當任務(wù)m在節(jié)點i由運輸方式k轉(zhuǎn)換到s時當任務(wù)m沒有在節(jié)點i由運輸方式k轉(zhuǎn)換到s時為任務(wù)m選擇水路運輸班次的決策變量,當任務(wù)m從節(jié)點i到j(luò)選擇水路運輸班次l時,當任務(wù)m沒有從節(jié)點i到j(luò)選擇水路運輸班次l時,

公式 ⑴ 表示所有任務(wù)運輸成本和換裝成本最低；公式 ⑵ 至公式 ⑷ 表示每個任務(wù)從起點到終點有一條完整的路徑；公式 ⑸ 表示節(jié)點最多發(fā)生一次中轉(zhuǎn)；公式 ⑹ 表示節(jié)點前后運輸方式的對應(yīng)約束,如果在節(jié)點由運輸方式由k變?yōu)閟,則i的前向節(jié)點到i采用的是運輸方式k,i到i的后向節(jié)點采用的是運輸方式s；公式 ⑺ 表示每個任務(wù)在節(jié)點的換裝時間；公式 ⑻ 表示任務(wù)m到節(jié)點i的時刻；公式 ⑼ 表示每個任務(wù)到達終點的時刻不超過最后期限；公式 ⑽ 表示采用水路運輸且發(fā)生運輸方式轉(zhuǎn)換時可選班次的時間要求；公式 ⑾ 表示采用水路運輸且沒發(fā)生運輸方式轉(zhuǎn)換時可選班次的時間要求；公式 ⑿ 表示某班次所運輸?shù)乃腥蝿?wù)不能超過其可用箱位數(shù)；公式 ⒀ 表示任務(wù)在某2個節(jié)點間選擇水路運輸時只能選擇1個班次。

1.2 蟻群并行算法設(shè)計

蟻群并行算法的基本思想是將所有螞蟻分為k個蟻群,每個蟻群包括m只螞蟻,在一次迭代中一共有k×m只螞蟻參與路徑搜索。如果2只以上螞蟻對同一個水路運段的同一個班次的班輪提出使用請求時,采用一定的策略決定該資源的分配方案。蟻群并行算法流程如圖1所示。

在圖1中按照一定規(guī)則選擇1只螞蟻,需要判斷螞蟻的當前節(jié)點i是否為目標節(jié)點dk,如果不是目的節(jié)點,找到該螞蟻所處當前節(jié)點的鄰接點,按照狀態(tài)轉(zhuǎn)移概率pk(i,j)選擇下一節(jié)點,可以表示為

圖1 蟻群并行算法流程圖Fig.1 Flow chart of ant colony parallel algorithm

式中：τk(i,j)為節(jié)點間的信息素濃度；ηk(i,j)為節(jié)點間的預見度；α為殘留信息的相對重要程度；β為預見值的相對重要程度。

當螞蟻選擇了水路運輸時,更新該班次可用的箱位數(shù)。當k×m只螞蟻都進行路徑尋優(yōu)之后,完成一次迭代,找到總成本最低的各個運輸任務(wù)的方案,進行全局信息素更新,信息素濃度可表示為

式中：Q為決定信息素濃度的參數(shù)；Lbest為螞蟻走行的最佳路線。

經(jīng)過n次迭代的最優(yōu)方案,可以作為模型的最優(yōu)解。通過蟻群算法可以得到問題的最優(yōu)解,由于節(jié)點換裝時間存在隨機性,問題的最優(yōu)解不是集中在惟一一條路徑上,因而要通過任務(wù)路徑集中度和平均可用箱位利用率對問題的最優(yōu)解進行統(tǒng)計分析。任務(wù)路徑集中度可以表示為

式中：γ為任務(wù)路徑集中度,是衡量在多次模擬計算的結(jié)果中,各任務(wù)走行相同路徑的程度；πm為任務(wù)m最優(yōu)路徑的條數(shù)；LC表示總?cè)蝿?wù)數(shù)。平均可用箱位利用率可以表示為

式中：θ為平均可用箱位利用率,衡量在多次模擬計算的結(jié)果中班輪可用箱位的利用率的平均值；bs為第s次模擬利用的箱位數(shù)；gs為第s次模擬可利用的箱位數(shù)。

2 算例分析

2.1 換裝時間的確定

在一個包含公路、鐵路和水路3種運輸方式的網(wǎng)絡(luò)中,有A,B,C,D,E,F,G7個節(jié)點,各個節(jié)點間產(chǎn)生的集裝箱運輸需求的時間、數(shù)量和運達期限已知,運輸任務(wù)在節(jié)點換裝作業(yè)時間不確定。 在集裝箱多式聯(lián)運網(wǎng)絡(luò)的水運運段為班輪運輸,每個班次的可用箱位數(shù)已知。水路運段最早班次出發(fā)時間為0點,每隔11 h發(fā)一班。集裝箱多式聯(lián)運網(wǎng)絡(luò)如圖2所示。

圖2 集裝箱多式聯(lián)運網(wǎng)絡(luò)Fig.2 Multimodal container transport network

在集裝箱多式聯(lián)運網(wǎng)絡(luò)中,換裝時間包括集裝箱換裝作業(yè)時間和作業(yè)期間發(fā)生的換裝等待時間。節(jié)點的集裝箱換裝作業(yè)時間取決于進行換裝作業(yè)的機械效率及操作的集裝箱量,單位換裝作業(yè)時間相對穩(wěn)定,集裝箱換裝作業(yè)時間=集裝箱量×單位平均換裝作業(yè)時間。研究取各節(jié)點的單位平均換裝作業(yè)時間均為2 min。節(jié)點的換裝等待時間具有不確定性,通過統(tǒng)計可知各集裝箱中轉(zhuǎn)站的換裝等待時間大致服從正態(tài)分布X～N (μ,σ2),分布如表1所示。

2.2 求解結(jié)果及其分析

為比較不同的運輸任務(wù)特征對求解運輸方案的影響,根據(jù)運輸任務(wù)數(shù)、運輸規(guī)模的不同,即根據(jù)運輸任務(wù)數(shù)量的多少和運輸批量的大小設(shè)計9種不同類型的算例。發(fā)生多運輸任務(wù)爭奪水路運輸有限可用箱位時,分別采用大批量先服務(wù)、小批量先服務(wù)和先到先服務(wù)3種服務(wù)策略進行資源分配。為模擬換裝時間的不確定性,每個算例在每種服務(wù)策略下計算100次,算法中的換裝等待時間在每次運行時按照表1隨機生成。按照公式⒁計算任務(wù)路徑集中度,按照公式⒂計算平均可用箱位利用率。各種算例在3種服務(wù)策略下運行100次的結(jié)果如表2所示。

表1 各集裝箱中轉(zhuǎn)站的換裝等待時間分布Tab.1 Distribution of waiting time for replacement of container depots

由表2的結(jié)果進一步分析3種服務(wù)策略對各種類型算例的影響,9個算例在3種服務(wù)策略下的特征如表3所示。

表2 各種算例在3種服務(wù)策略下運行100次的結(jié)果Tab.2 Results of various examples running 100 times under three service strategies

由表2和表3可知,在任務(wù)數(shù)較少時,小批量先服務(wù)的服務(wù)策略成本最高,大批量先服務(wù)和先到先服務(wù)無明顯差異。隨著任務(wù)數(shù)的增加,大批量先服務(wù)的策略使得班輪利用率逐漸提高,成本優(yōu)勢也越來越明顯。當任務(wù)數(shù)量較少時,任務(wù)路徑的集中度較高,這是因為任務(wù)數(shù)量少,相互間基本沒有影響；而隨著任務(wù)數(shù)的增加,任務(wù)間的影響開始明顯,導致任務(wù)路徑的集中度開始分散。由此可見,集裝箱多式聯(lián)運在多個運輸任務(wù)對班輪的箱位數(shù)產(chǎn)生資源爭奪時,采用大批量先服務(wù)的策略,可以有效減少運輸總成本。另外,影響總成本的主要因素是水路運輸?shù)馁Y源,如能爭取到更多的可用水路運輸資源,則可以為進一步降低運輸總成本帶來空間。

表3 9個算例在3種服務(wù)策略下的特征Tab.3 Features of 9 examples under 3 service strategies

3 結(jié)束語

單一的集裝箱運輸模式已經(jīng)不能滿足當今的貨物運輸需求,以顧客為中心的、快速、高效、安全、低成本的集裝箱多式聯(lián)運已成為發(fā)展趨勢。實現(xiàn)集裝箱多式聯(lián)運模式的高效發(fā)展已經(jīng)成為國家經(jīng)濟可持續(xù)發(fā)展的關(guān)鍵之一,加快推進我國多式聯(lián)運集裝箱運輸?shù)陌l(fā)展也成為國家交通運輸業(yè)的重要發(fā)展戰(zhàn)略。近年來國家大力促進多式聯(lián)運的發(fā)展,多式聯(lián)運越來越受到重視,鐵水聯(lián)運、公鐵聯(lián)運等運輸方式也因其結(jié)合了各種運輸方式的優(yōu)點而受到青睞,在交通運輸領(lǐng)域發(fā)揮著越來越大的作用?；诠?jié)點換裝時間不確定的多任務(wù)集裝箱運輸方案優(yōu)化研究,有助于提高多式聯(lián)運經(jīng)營人組織運輸?shù)男?促進多式聯(lián)運系統(tǒng)高效運轉(zhuǎn)和物流行業(yè)的蓬勃發(fā)展。