鄭紅星 邵思楊 吳云強

(大連海事大學交通運輸工程學院 大連 116026)

0 引 言

多式聯(lián)運憑借其運輸靈活、可靠與環(huán)保的優(yōu)勢，成為了交通運輸行業(yè)新的發(fā)展趨勢。與此同時，大量外貿(mào)商品的出口流通形成了以港口為中心的集裝箱多式聯(lián)運運輸方式，以港口為終點的多式聯(lián)運集港運輸模式引起了廣泛關(guān)注。

近年來，國內(nèi)外學者對集裝箱多式聯(lián)運路徑優(yōu)化進行的研究主要集中在時間窗約束和中轉(zhuǎn)銜接兩方面。

帶時間窗的多式聯(lián)運路徑優(yōu)化可細分為單一時間窗、模糊時間窗、混合時間窗。單一時間窗方面，吳曉莉等人[1]以汽車銷售為背景，建立了以總運輸成本最小為目標的由單起點到多終點的優(yōu)化模型，并通過蟻群算法求解。模糊時間窗方面，熊桂武[2]和梁曉慷[3]考慮到客戶對運輸時效性的要求，建立了以客戶模糊滿意度最大且運輸成本最小為目標的多式聯(lián)運路徑優(yōu)化模型；于雪嶠等人[4]考慮運輸時間客戶滿意度的同時，加入中轉(zhuǎn)節(jié)點作業(yè)時間窗約束，建立了以總費用最小為目標的多式聯(lián)運路徑優(yōu)化模型?；旌蠒r間窗方面，呂學偉等人[5]考慮到運輸方式的硬時間窗和收貨時間的軟時間窗，構(gòu)建了以總運輸成本最小為目標的混合時間窗模型；張小龍等人[6]則將中轉(zhuǎn)節(jié)點設置為軟時間窗，將目的地節(jié)點設置為硬時間窗，建立了考慮運輸成本、時間成本以及環(huán)境成本的多目標多式聯(lián)運路徑優(yōu)化模型?？v觀考慮時間窗的多式聯(lián)運路徑優(yōu)化文獻，大多數(shù)以運輸總成本最小、客戶滿意度最大或者收益最大為優(yōu)化目標，以轉(zhuǎn)運次數(shù)、各節(jié)點貨物流量平衡等為核心約束，兼顧貨物抵達各節(jié)點的時間約束，構(gòu)建數(shù)學模型，并設計相應的算法求解，最終給出最優(yōu)的多式聯(lián)運路徑。

考慮中轉(zhuǎn)銜接的文獻可以細分為節(jié)點耗時和班期限制兩方面。涉及節(jié)點耗時的文獻中，王清斌等人[7]認為轉(zhuǎn)換時間和成本的變化會對運輸方案選擇產(chǎn)生影響，將轉(zhuǎn)換時間設置為服從正態(tài)分布規(guī)律的非確定值，令轉(zhuǎn)換成本隨轉(zhuǎn)換時間變化，以總成本最小為目標，建立了帶有時間約束的混合整數(shù)規(guī)劃模型。劉杰等人[8]考慮到運輸方式轉(zhuǎn)換的實際性給出了運輸方式中轉(zhuǎn)備選集，并根據(jù)不同出發(fā)時間會對運輸費用造成影響，建立了基于備選集的多式聯(lián)運動態(tài)路徑優(yōu)化模型。辛春林等人[9]考慮到危險品運輸過程中，運輸費用和人口風險具有較強的時變性，將中轉(zhuǎn)作業(yè)細分為中轉(zhuǎn)運輸、卸貨裝貨和等待出發(fā)3項子作業(yè)，構(gòu)建了以費用和風險的加權(quán)值最小為目標的多式聯(lián)運最短路徑選擇模型。劉松[10]將中轉(zhuǎn)節(jié)點耗時轉(zhuǎn)換為路段權(quán)重，將考慮中轉(zhuǎn)的多式聯(lián)運問題轉(zhuǎn)化為網(wǎng)絡最短路徑問題，并構(gòu)建了以總時間最短為目標的多式聯(lián)運路徑優(yōu)化模型。楊雄等人[11]提出了基于路徑多樣性的網(wǎng)絡節(jié)點影響力探測和評估方法，能夠更細粒度地對節(jié)點影響力進行有效的排序?？紤]到班期限制的文獻中，彭勇等人[12，13]提出了含班期限制的多式聯(lián)運路徑?jīng)Q策模型，驗證了班期限制對多式聯(lián)運路徑?jīng)Q策有較大影響。在此基礎上，又進一步建立了以總運輸費用、總運輸時間、總運輸風險為優(yōu)化目標的模型，求解得出考慮班期限制的多式聯(lián)運路徑優(yōu)化模型更加合理這一結(jié)論?？v覽考慮中轉(zhuǎn)銜接的文獻，大多數(shù)都將中轉(zhuǎn)節(jié)點或者中轉(zhuǎn)作業(yè)拆分開，以總成本最小、總運輸時間最短或總運輸風險最小為優(yōu)化目標，重點兼顧中轉(zhuǎn)等待成本，以場站換裝能力限制、班期限制、各節(jié)點時間限制為核心約束，構(gòu)建多式聯(lián)運路徑優(yōu)化模型并求解。

綜上所述，現(xiàn)有的文獻從不同的視角對集裝箱多式聯(lián)運路徑優(yōu)化問題進行了研究，然而這些研究大多數(shù)都只考慮到運輸過程中的總成本最小化或利益最大化，涉及終點節(jié)點處理貨物工作效率的文獻較少。港口是貨物及旅客的轉(zhuǎn)運樞紐，其作業(yè)復雜多樣，且與公路、鐵路、海關(guān)等諸多口岸單位密切相關(guān)[14]。在以港口為終點的多式聯(lián)運作業(yè)中，港口的工作效率往往會對運輸成本造成較大影響，若承運商沒有考慮港口忙閑度，僅僅保證在船期截止前抵達港口，可能會因未能及時裝卸貨物耽誤船期，也可能會因過早抵達港口增加承運商的等待成本，故本文將港口的忙閑度納入研究。

為此，本文在系統(tǒng)分析港口業(yè)務規(guī)律的基礎上，預測港口堆場業(yè)務的忙閑時段，以其來約束出口集裝箱抵港的時機，并考慮出口箱的船期和中轉(zhuǎn)節(jié)點的現(xiàn)實條件，使多式聯(lián)運承運商的總成本最少，最終給出出口集裝箱多式聯(lián)運的最優(yōu)方案。

區(qū)別已有文獻，本文重點考慮港口的忙閑時間窗，綜合考慮中轉(zhuǎn)節(jié)點的周期性時間窗以及中轉(zhuǎn)節(jié)點各運輸方式的班期。

1 問題描述與建模

1.1 問題描述

如圖1所示，在一個按照運輸樞紐層次劃分層級的集裝箱多式聯(lián)運網(wǎng)絡中，將一批貨物從起點城市O運到終點港口D。中間有若干個可以進行運輸方式轉(zhuǎn)換的節(jié)點，節(jié)點城市轉(zhuǎn)換運輸方式需要一定的轉(zhuǎn)換時間和轉(zhuǎn)換成本，以及與中轉(zhuǎn)時間成正比的中轉(zhuǎn)等待成本。各中轉(zhuǎn)節(jié)點都有帶周期性的空閑時間窗，在空閑時間窗之外到達該節(jié)點需等待下一個空閑時間窗才能進行中轉(zhuǎn)作業(yè)。每個節(jié)點發(fā)往下一個節(jié)點的水路和鐵路運輸都有固定的到達和離開時刻，公路運輸可隨時出發(fā)。

圖1 集裝箱多式聯(lián)運網(wǎng)絡圖

本文問題可描述為：某一多式聯(lián)運承運商承運一批出口集裝箱貨物，該貨物需經(jīng)一固定港口出口，重點考慮該港口的忙閑時間窗，兼顧出口集裝箱的船期和中轉(zhuǎn)節(jié)點的時間限制等現(xiàn)實約束，以運輸成本、中轉(zhuǎn)成本、中轉(zhuǎn)等待成本和港口等待成本最小為優(yōu)化目標，最終給出出口集裝箱多種運輸方式的最佳組合和最優(yōu)路徑。

1.2 假設條件

(1)貨物不能拆分；

(2)任意兩節(jié)點之間只能選擇一種運輸方式；

(3)運輸方式的轉(zhuǎn)換只能發(fā)生在節(jié)點處，且同一節(jié)點最多轉(zhuǎn)換一次；

(4)運輸工具與中轉(zhuǎn)設施能力充足；

(5)火車和輪船有固定的出發(fā)時刻，汽車可隨時出發(fā)；

(6)兩節(jié)點之間，不同運輸方式的運輸距離相同，運輸時間不同。

1.3 符號說明

基本符號與變量：

中間變量：

決策變量：

1.4 模型構(gòu)建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

?h,i∈A，?k,l∈V(8)

?i,j∈A，?k,l∈V(9)

(10)

(11)

(12)

(13)

?i∈A，j∈D，?k∈V(14)

2 求解算法

本文設計了基于禁忌搜索(tabusearch,TS)思想的改進遺傳算法(improved genetic algorithm,IGA)，即在傳統(tǒng)的遺傳算法的基礎上引入了禁忌搜索中禁忌表與鄰域搜索的思想；同時，對遺傳算法進行改進，設計了隨迭代次數(shù)變化的動態(tài)參數(shù)HR和PR，并在GA算法中融入了接受準則的思想，以一定的概率接受劣解，從而使算法可以跳出局部最優(yōu)解，算法流程如圖2所示。

圖2 算法流程圖

2.1 解的表示與初始種群生成策略

本文采用雙層染色體進行編碼，其中第1層表示所經(jīng)過的中轉(zhuǎn)節(jié)點，且長度為運輸樞紐層級數(shù)量，第2層表示各個運輸節(jié)點之間所采用的運輸方式，且長度為運輸經(jīng)過的所有節(jié)點數(shù)量減1。

鑒于所選中轉(zhuǎn)節(jié)點受到節(jié)點空閑時間段與等待成本的影響，且運輸方式主要受到運輸成本與轉(zhuǎn)換成本的影響以及所選中轉(zhuǎn)節(jié)點與所采用運輸方式相互影響，制定了如下初始種群生成策略。

步驟1初始化相關(guān)參數(shù)，m表示第1層中轉(zhuǎn)節(jié)點的數(shù)量，n表示第2層中轉(zhuǎn)節(jié)點的數(shù)量，j表示種群內(nèi)個體的序號，令j=1；

步驟2隨機從m與n中各自選擇一個隨機整數(shù)，從而生成個體j第1行；

步驟3針對個體第2行，比較出發(fā)節(jié)點與第1層所選中轉(zhuǎn)節(jié)點之間不同運輸方式的條件下到達中轉(zhuǎn)節(jié)點的時刻與節(jié)點可以最早空閑時刻之間的差值，選擇最小差值所代表的運輸方式，若時間差值一樣，則選擇此路段運輸成本最低的運輸方式，把它作為出發(fā)節(jié)點與第1層中轉(zhuǎn)節(jié)點之間的運輸方式；

步驟4按照上述同樣的方式，獲得第1層中轉(zhuǎn)節(jié)點與第2中轉(zhuǎn)節(jié)點間的運輸方式。比較不同運輸方式下到達港口的時刻，若時刻超過最晚時刻，則刪除此種運輸方式，且比較其他運輸方式到達港口時刻與離它最近的港口空閑時間窗的差值，選擇差值最小所對應的運輸方式，當作第2層中轉(zhuǎn)節(jié)點到達港口的運輸方式；

步驟5令j=j+1，若j大于種群規(guī)模p，則結(jié)束，否則令i=1，執(zhí)行步驟2。

2.2 新個體生成策略

本文采用3種新個體生成策略，分別為交叉、變異以及鄰域搜索策略，具體策略如下。

(1)交叉

選取最優(yōu)個體第1層或者第2層的部分染色體片段與任意其他染色體對應部分進行交叉，從而形成新染色體。

(2)變異

任選一個染色體，針對染色體第1層，把某個中轉(zhuǎn)節(jié)點換成此中轉(zhuǎn)節(jié)點層的其他中轉(zhuǎn)點；或者針對染色體第2層，把某2個運輸節(jié)點之間的運輸方式換成其他可以采用的運輸方式，從而形成新染色體。

(3)鄰域搜索策略

針對某個個體，在已知中轉(zhuǎn)節(jié)點的情況下，改變其各節(jié)點之間的運輸方式，選擇總成本最小時對應的個體當作新個體，其具體步驟如下：

步驟1針對個體的第1層基因，把起始點與第1層中轉(zhuǎn)節(jié)點之間的運輸方式換成其他可以采用的運輸方式，若到達第1層中轉(zhuǎn)節(jié)點的時刻超過第1層中轉(zhuǎn)節(jié)點與第2層中轉(zhuǎn)節(jié)點之間的運輸方式的出發(fā)時刻，則在滿足時間約束的條件下改變第1層中轉(zhuǎn)節(jié)點與第2層中轉(zhuǎn)節(jié)點之間的運輸方式，以此類推，調(diào)整其他節(jié)點之間的運輸方式，從而生成一個新個體；

步驟2按照上述方式，改變起始點與第1層中轉(zhuǎn)節(jié)點之間的運輸方式，若已不存在沒有采用過的運輸方式，則改變第1層中轉(zhuǎn)節(jié)點與第2層中轉(zhuǎn)節(jié)點之間的運輸方式，并在滿足時間約束的條件下改變其他節(jié)點之間的運輸方式，直到生成所有滿足條件的新個體；

步驟3計算各新個體的目標函數(shù)，將總成本最低的個體當作原個體對應形成的新個體。

2.3 解空間切割

在初始種群生成與新個體生成過程中，可能生成貨物在節(jié)點的離開時刻超過運輸方式的出發(fā)時刻或者貨物到達港口的時刻超過最晚時刻的個體。針對此種個體，需要在生成過程中進行刪除，從而提高算法的運行速度。

2.4 基因修復

在新個體生成過程中，可能存在以下2種情況：(1)節(jié)點之間不存在個體基因所對應的運輸方式；(2)到達節(jié)點的時刻早于節(jié)點最早開始空閑時刻。針對此2種情況，需要進行基因修復，使不可行解或者較劣解變成可行解或者較優(yōu)解，具體步驟如下：

步驟1針對任一個體，從染色體第2行開始，判斷此種運輸方式是否存在于此相鄰2個節(jié)點之間，若存在此種運輸方式，則轉(zhuǎn)到步驟2，否則，轉(zhuǎn)到步驟3；

步驟2計算到達第1個中轉(zhuǎn)節(jié)點的時刻，若小于節(jié)點最早開始空閑時刻，則改變運輸方式，選取其他成本更低的運輸方式；計算到達第2個中轉(zhuǎn)節(jié)點與港口的時刻，按照上述方法改變其運輸方式；

步驟3比較節(jié)點間存在的運輸方式到達下一節(jié)點的時刻，選取到達時刻與節(jié)點開始空閑時刻之間的差值最小所對應的運輸方式替換之前的運輸方式；

步驟4輸出新生成的個體。

2.5 禁忌表

每一個適應度值幾乎只與一個個體相對應，因此為了避免某個個體多次出現(xiàn)，把禁忌對象設為個體的適應度值。禁忌表分為短禁忌表和長禁忌表，短禁忌表為DC×1的矩陣，長禁忌表為CC×1的矩陣，其中DC為短禁忌表的長度，CC為長禁忌表的長度。在每一次迭代完成之后采取如下操作：

步驟1若迭代次數(shù)小于DC，在短禁忌表中，依次以前一行替換后一行。根據(jù)適應度值的大小對種群中的個體排序，并依據(jù)此排序選取不存在于短禁忌表中的適應度值放入短禁忌表的第1行，從而形成新短禁忌表，并把此適應度對應的個體當作下一次迭代的初始最優(yōu)個體；

步驟2若迭代次數(shù)大于DC，在種群中按照適應度從小到大的順序選取個體。若此個體對應的適應度值存在于短禁忌表中，則重新選取個體，直到個體的適應度值不存在于短禁忌表中。若此個體的適應度值存在于長禁忌表中，則此數(shù)值出現(xiàn)次數(shù)m=m+1；若m>M(最大允許出現(xiàn)的次數(shù))，重新選取個體，直到所選取的個體適應度值不存在于短禁忌表中且m不大于M。選取完滿足條件的個體后，轉(zhuǎn)到步驟3；

步驟3以短禁忌表的最后1行替換長禁忌表的第1行，且從第2行開始，依次以長禁忌表中前一行替換后一行，從而生成新長禁忌表。在短禁忌表中，依次以前一行替換后一行，并把此個體的適應度值放入短禁忌表的第1行，從而形成新短禁忌表，并把此個體當作下一次迭代的最優(yōu)初始個體。

3 算 例

3.1 案例描述

某多式聯(lián)運承運人將一批50集裝箱的貨物從城市A運輸?shù)浇K點港口D，經(jīng)由港口D出口外銷。運輸途中可由B1、B2、B3、C1、C2、C3、C4這7個集裝箱中轉(zhuǎn)站進行運輸方式的轉(zhuǎn)換，貨物需在船期截止前抵達港口并完成裝船作業(yè)。船期截止時刻為由出發(fā)時刻開始計時的第50個小時。多式聯(lián)運網(wǎng)絡圖及各節(jié)點之間的連接方式如圖3和圖4所示。

圖3 多式聯(lián)運網(wǎng)絡圖

圖4 各節(jié)點連接方式

3.2 參數(shù)取值

根據(jù)《國際集裝箱汽車運輸費收規(guī)則》以及中國鐵路總公司2018年發(fā)布的《關(guān)于調(diào)整鐵路集裝箱運價有關(guān)事項的通知》得到鐵路和公路的在途運輸費用計算公式為：運輸費用=(運輸基價1+運輸基價2×運輸距離)×貨運量。水路運輸采用包干計費950元/箱，且各運輸方式的單位運價及運輸速度見表1，各中轉(zhuǎn)節(jié)點的空閑時間窗及周期見表2，各運輸方式轉(zhuǎn)換的中轉(zhuǎn)成本和中轉(zhuǎn)時間見表3，各運輸節(jié)點間的距離見表4，各節(jié)點火車輪船時刻表見表5。

表1 各運輸方式的單位運價及運輸速度

注：“-”表示該節(jié)點不存在此種計價方式

表2 各中轉(zhuǎn)節(jié)點的空閑時間窗及周期

表3 各運輸方式轉(zhuǎn)換的中轉(zhuǎn)成本(元/箱)和中轉(zhuǎn)時間(h/箱)

表4 各運輸節(jié)點間的距離(km)

注：“-”表示節(jié)點間不直接連通

(續(xù)表5)

注：“-”表示該節(jié)點不存在此種運輸方式

4 結(jié)果分析

當港口不存在時間窗約束時，貨物抵達港口即可卸貨，不需承擔港口處的等待成本。由改進遺傳算法解得的最優(yōu)解為：運輸路徑AB2C3D，運輸方式分別為鐵路—水運—水運。運行總成本是348 540元，運行總時間為47.9 h，小于船期截止的時刻，方案成立。

考慮港口忙閑度時，解得的多式聯(lián)運最優(yōu)運輸方案會隨港口忙閑時間窗的變化而變化。不同港口忙閑時間窗的計算結(jié)果比較見表6。

(1) 當港口忙閑時間窗為[1 700， 1 900]和[2 100， 2 200]時由改進遺傳算法解得的最優(yōu)解：運輸路徑AB3C3D，運輸方式為水路—公路—鐵路，運輸總成本是361 670元，運行總時間為40.7 h。

(2) 當港口忙閑時間窗為[2 300， 2 500]和[2 800， 2 900]時由改進遺傳算法解得的最優(yōu)解：運輸路徑AB2C4D，運輸方式為水路—公路—鐵路，運輸總成本是392 020元，運輸總時間為44.2 h。

(3) 當港口忙閑時間窗為[2 650， 2 800]和[2 980， 3 180]時由改進遺傳算法解得的最優(yōu)解為：運輸路徑AB1C3D，運輸方式為水路—公路—公路，運輸總成本是454 060元，運輸總時間為45.5 h。

在此時間窗下，不考慮港口忙閑時間窗的運輸方案雖然能在船期截止前抵達港口，但抵達時刻卻在港口較為繁忙的時間段，不能及時進行集港作業(yè)，承運人不僅需額外承擔晚集港費和翻倒費，甚至會因延誤裝貨時間導致無法裝船。

表6 不同港口忙閑時間窗的計算結(jié)果比較

綜上所述，考慮港口忙閑度與不考慮港口忙閑度得到的最佳方案不相同，不同的港口忙閑時間窗對應的最佳方案也各不相同。不考慮港口忙閑度情況下得到的最優(yōu)方案往往會因為追求總成本最小使得總運輸時間偏長，抵達港口時刻接近截港時刻。但是實際工作中，港口普遍存在無法及時處理到港貨物的繁忙的時間段。若承運商不考慮港口忙閑度，那么對于抵港時刻接近截港時刻的最佳運輸方案需謹慎采用。

通過對比分析可知，港口忙閑度對運輸成本、運輸路徑及運輸方式的選擇有較大的影響。不考慮港口忙閑時間窗的情況下，得到的最佳運輸方案有較大概率需承擔因抵港時機不合適產(chǎn)生的高額晚集港費和預集港費，甚至會令貨物趕不上裝船。考慮港口忙閑時間窗的情況下，港口的忙閑時間窗距離截港時刻越近，對運輸方案造成的影響越大；由于港口忙閑時間窗對貨物抵港時機進行了約束，運輸時間長的方案總成本不一定最低；港口空閑時間段之間的時間間隔越大，對運輸方案帶來的影響越大，承運商不得不盡可能滿足此約束來避免港口等待成本過高。因此，承運商在制定多式聯(lián)運運輸方案時，必須將港口的忙閑度納入考慮范圍，使得貨物抵港時刻更合理，運輸方案更貼合實際。

5 結(jié) 論

本文對考慮港口忙閑度情況下的集裝箱多式聯(lián)運路徑優(yōu)化問題進行了研究，構(gòu)建了相對應的模型，并且運用改進遺傳算法對其求解，同時設計案例驗證其可行性。通過對結(jié)果的分析得出以下結(jié)論：(1)港口忙閑時間窗對承運人制定運輸方案有較大影響，越接近截港時刻影響越大；(2)港口空閑時間窗之間的間隔越大，對運輸方案的影響越大；(3)將港口空閑時段劃分為幾段，平均每段空閑時長越短但整體空閑頻率越高對承運商的影響越小；(4)在制定運輸方案時，承運人若沒有考慮到港口忙閑度，不僅會增加港口等待時間浪費大量運力資源，甚至會耽誤下一個運輸計劃；(5)若貨物抵港時刻接近截港時刻且處于港口繁忙時段，那么承運商不僅需要承擔額外集港費用，還需承擔因無法裝船導致的貨物與財產(chǎn)損失。綜上所述，承運商在制定運輸計劃時必須考慮港口忙閑度，令各類資源得到合理使用，運輸計劃更加貼合實際。