基于鯨魚優(yōu)化算法的多目標多式聯(lián)運路徑選擇

吳志勇，戴 弌，鞠傳香，胡本佳，胡 嘯

(1. 青島藍智現(xiàn)代服務(wù)業(yè)數(shù)字工程技術(shù)研究中心，山東 青島 266100； 2. 山東理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，山東 淄博 255049)

0 引 言

近年來，我國物流產(chǎn)業(yè)迅速發(fā)展的同時也在大力實施運輸結(jié)構(gòu)調(diào)整策略，旨在推動我國綠色運輸，降低物流運輸成本，提高運輸效率。多式聯(lián)運是運輸結(jié)構(gòu)調(diào)整的重要方式之一，已成為當(dāng)前眾多企業(yè)國際、國內(nèi)運輸?shù)闹匾锪鞣绞街弧６嗍铰?lián)運指的是在一次運輸作業(yè)中，通過兩種及以上的運輸方式轉(zhuǎn)換將貨物運輸?shù)侥康牡氐倪^程。如何提升多式聯(lián)運效益，已成為眾多學(xué)者研究的課題[1-3]。

目前，國內(nèi)外針對多式聯(lián)運模型構(gòu)建的研究主要集中在約束環(huán)境下如何改進最優(yōu)路徑與運輸方式的組合。例如，L. MOCCZA等[4]在構(gòu)建模型時考慮了節(jié)點到達時間、出發(fā)時間和整體運輸時間等條件對運輸路徑的選擇，將多式聯(lián)運線路虛擬化為有向網(wǎng)絡(luò)后，采用列生成算法優(yōu)化路徑選擇；T. GRBENER等[5]構(gòu)建了城市中采用腳踏車、步行、公交車等多種方式快速到達目標地點的模型，設(shè)計了基于Dijkstra的改進Martins算法進行求解；J. ZHANG等[6]設(shè)計了考慮轉(zhuǎn)運時間和成本的總成本最小化的可靠雙目標優(yōu)化模型，并結(jié)合遺傳算法(genetic algorithm，GA)與模擬退火算法(simulated annealing, SA)對目標函數(shù)進行求解；姜金貴等[7]針對城市路徑優(yōu)化問題，采用隨機選取節(jié)點并引入信息素更新策略，以廣義代價作為目標函數(shù)，通過改進的蟻群優(yōu)化算法求得連續(xù)解；謝楚楚等[8]研究了引入環(huán)境成本，以客戶滿意度與時間窗為約束條件的多式聯(lián)運優(yōu)化模型，并利用符合節(jié)點時間及提升客戶滿意度的NGSA-Ⅱ算法進行求解；于雪嶠等[9]僅考慮了公路與鐵路兩種運輸方式，將用戶滿意度和時間窗約束條件引入，基于機會約束規(guī)劃方法對模型進行求解；萬杰等[10]將運輸費用和服務(wù)質(zhì)量引入多式聯(lián)運路徑優(yōu)化多目標模型，采用遺傳算法進行目標求解；萬杰等[11]將運輸成本、運輸時間和物流服務(wù)質(zhì)量引入多目標多式聯(lián)運路徑選擇模型，采用混合算法進行目標求解。

從上述研究來看，各文獻運輸成本考慮不一，目標函數(shù)的構(gòu)建需求、路徑優(yōu)化模型及仿真數(shù)據(jù)也不盡相同。但總體來看，模型的求解多采用啟發(fā)式算法，例如蟻群優(yōu)化算法[7]和遺傳算法[1,6,10]等。多式聯(lián)運成本因素不僅考慮了運輸費用和中轉(zhuǎn)費用，而且將運輸途中的碳排放綠色成本和到達目的城市的時間窗成本也考慮在內(nèi)，筆者提出了一種基于鯨魚優(yōu)化算法的多式聯(lián)運路徑選擇模型。仿真實驗結(jié)果表明：提出的路徑優(yōu)化模型在考慮多因素成本的同時能夠滿足運輸成本最小化，鯨魚優(yōu)化算法在求解最優(yōu)路徑方面也具有較好的全局尋優(yōu)能力和較快的收斂特性。

1 多式聯(lián)運路徑選擇問題的描述

1.1 模型假設(shè)

假設(shè)一批貨物從始發(fā)城市A運輸?shù)侥康某鞘蠦,途中可選擇m個節(jié)點城市作為中轉(zhuǎn)，并且兩個節(jié)點城市之間可以通過兩種及以上的運輸方式進行轉(zhuǎn)換。其中，運輸方式包括公路、水運、鐵路、空運等。運輸過程中，城市節(jié)點之間會產(chǎn)生運輸成本、碳排放成本、城市節(jié)點運輸方式轉(zhuǎn)換的轉(zhuǎn)運成本和到達目的城市非時間窗成本?？梢?，為完成運輸任務(wù)，選擇不同的運輸路線和方式組合會產(chǎn)生不同的運輸成本，目標是求解最佳運輸方式和路線組合。考慮到案例研究更加反映真實場景，筆者做出如下假設(shè)[11]：①一次運輸任務(wù)中，城市起點和終點明確，整體運量不變；②各運輸方式的運行速度為平均運輸速度，中轉(zhuǎn)時間在各城市節(jié)點明確；③運輸成本中的轉(zhuǎn)運費用在每個城市節(jié)點計算明確，碳排放成本僅考慮運輸過程中；④運輸中到達任何城市節(jié)點都可以選擇可變的運輸方式，并且只能改變1次；⑤運輸和中轉(zhuǎn)的載運能力充足；⑥貨物到達目的地的時間不在時間窗內(nèi)，將產(chǎn)生儲存費用和懲罰費用。

1.2 模型構(gòu)建

對于以上模型假設(shè)，建立如下3個目標函數(shù):

glmax(sD-TL,0)

(1)

式(1)表示運輸過程中的成本目標函數(shù)，其中包括所有運輸方式產(chǎn)生的運輸成本、城市節(jié)點之間進行運輸方式轉(zhuǎn)換時的轉(zhuǎn)運成本，以及到達終點非時間窗延期到達或提前到達時支付的時間懲罰成本。

(2)

式(2)表示貨物運輸過程中產(chǎn)生的碳排放成本最小目標函數(shù)。

(3)

式(3)表示貨物運輸任務(wù)到達目的城市B所耗費的最短時間目標函數(shù)。其中，利用式(4)計算，表示貨物到達各轉(zhuǎn)運城市節(jié)點的總等待時間，各轉(zhuǎn)運城市節(jié)點的等待時間等于該待轉(zhuǎn)運方式最近的出發(fā)時間減去到達此城市節(jié)點時間，然后加上在此城市節(jié)點進行運輸方式轉(zhuǎn)換所花費的時間。

(4)

式中：n為城市節(jié)點，n∈{0,1,…,C}；w為總等待時間；q為由城市節(jié)點i+1轉(zhuǎn)運方式m班次間隔時間；f為城市節(jié)點i到i+1轉(zhuǎn)運方式m最近的出發(fā)時間，避免在轉(zhuǎn)運節(jié)點錯過最近的班次造成時間浪費，定義式(5)作為約束條件。

(5)

為保證時間連續(xù)性，si+1用式(6)計算，表示到達下一個城市節(jié)點的運輸時間等于上一個節(jié)點運輸時間加上轉(zhuǎn)運時間和等待時間。

(?i,m,l)

(6)

用式(7)表示兩個運輸城市節(jié)點之間有且只有一種運輸方式。

(7)

式(8)表示在某個城市節(jié)點只允許一次運輸方式轉(zhuǎn)換。

(8)

式(9)表示當(dāng)前節(jié)點與后續(xù)節(jié)點運輸方式的連續(xù)性。

(9)

式(10)表示整個貨物運輸過程中時間的連續(xù)性。

(10)

為限制運輸方式要進行轉(zhuǎn)換時只能在相應(yīng)備選集中選取，定義式(11)作為約束條件。

(11)

上述式(1)～式(11)中的模型符號說明如表1。

表1 模型符號說明Table 1 Model symbol description

2 鯨魚優(yōu)化算法

2016年，澳大利亞學(xué)者S.MIRJALILI提出了一種鯨魚優(yōu)化算法(the whale optimization algorithm, WOA)[12-13]，WOA屬于一種通過模擬座頭鯨狩獵行為的新型群體智能算法,其搜索過程是對座頭鯨的泡泡網(wǎng)捕食策略進行數(shù)學(xué)建模[14]，主要包括了3個過程的數(shù)學(xué)結(jié)構(gòu)，即目標包圍、泡泡網(wǎng)攻擊和目標搜索。

2.1 目標包圍

在WOA模型中，將一個獵物坐標作為當(dāng)前的最佳解決法案，在這一次迭代搜索完成之后，搜索代理會根據(jù)更新的最佳搜索代理完成位置的更新，并進行下一次的迭代，整個過程為：

(12)

(13)

(14)

(15)

2.2 泡泡網(wǎng)攻擊

在WOA模型中，模擬座頭鯨泡泡網(wǎng)攻擊的步驟包括收縮包圍和螺旋更新位置兩部分：

2)螺旋更新位置的步驟是：先計算當(dāng)前鯨魚位置和最佳鯨魚位置的距離，然后在這個距離之間建立螺旋方程，如式(16)；然后，鯨魚延著螺旋路線到達最佳鯨魚位置，即獵物位置。

(16)

為模擬收縮包圍和螺旋更新位置的過程模型，筆者設(shè)置了鯨魚更新位置的概率閾值為0.5，如式(17)。其中，p表示概率，在[0，1]中隨機取值。

(17)

2.3 目標搜索

與基于更新當(dāng)前最佳鯨魚位置的包圍機制不同，模擬鯨魚搜索獵物的更新是通過隨機搜索代理實現(xiàn)的，數(shù)學(xué)模型可表示為式(18)和式(19)：

(18)

(19)

3 基于鯨魚優(yōu)化算法的多式聯(lián)運路徑選擇模型

鯨魚優(yōu)化算法是一種新提出的元啟發(fā)式優(yōu)化算法，已在車間調(diào)度、圖像分割等應(yīng)用領(lǐng)域有成功案例，與其它啟發(fā)式算法相比，鯨魚優(yōu)化算法具有結(jié)構(gòu)簡單、參數(shù)少、搜索能力強、易于實現(xiàn)等優(yōu)點。筆者將鯨魚優(yōu)化算法和Pareto求解多目標最優(yōu)理論方法相結(jié)合引入到多目標多式聯(lián)運路徑選擇問題中，仿真實驗顯示該算法在求解路徑選擇方面具有較好的全局尋優(yōu)能力和較快的收斂特性。

3.1 路徑選擇算法

在算法初始化階段，結(jié)合多式聯(lián)運仿真模型中城市節(jié)點數(shù)據(jù)要求，采用隨機生成節(jié)點的方式對各城市節(jié)點進行排序，同時對鯨魚優(yōu)化算法的初始化數(shù)據(jù)進行取整處理，基于節(jié)點隨機排列的初始解矩陣X為：

矩陣中共有k行記錄,對應(yīng)k條路徑選擇;其中,每行數(shù)據(jù)的前n個元素代表n個城市節(jié)點，后n-1個元素對應(yīng)了每兩個城市之間所選擇的運輸方式。

基于鯨魚優(yōu)化算法的多式聯(lián)運多目標路徑選擇模型計算步驟如下：

步驟1導(dǎo)入多式聯(lián)運網(wǎng)絡(luò)基礎(chǔ)數(shù)據(jù)，隨機初始化生成鯨魚路線Xi，其中i=1,2,…,k。

步驟2如果當(dāng)前迭代次數(shù)≤最大迭代次數(shù),則繼續(xù)步驟3～步驟5,否則輸出當(dāng)前最優(yōu)路線。

步驟5當(dāng)p≥0.5時,利用式(16)更新當(dāng)前路線Xi。

步驟6更新當(dāng)前路線,當(dāng)?shù)螖?shù)達到最大時，輸出結(jié)果最優(yōu)路線。

3.2 多目標優(yōu)化Pareto適應(yīng)度計算

Pareto是求解多目標最優(yōu)理論方法[15]，上述算法步驟3中需選擇Pareto適應(yīng)度最小的線路。在多式聯(lián)運過程中不同的運輸路線和方式組合會產(chǎn)生不同的運輸成本、碳排放成本和時間成本，每個運輸方式和路徑組合都對應(yīng)了Pareto適應(yīng)度值，求解最佳運輸方式和路徑組合的問題演變成求Pareto適應(yīng)度最小的過程。文中多式聯(lián)運路徑選擇的多目標優(yōu)化問題用式(20)表示為：

minY=[Y1(x)+Y2(x)+Y3(x)]

(20)

式中：Yk(x)為Y的第k個分目標，文中涉及3個目標函數(shù)，Y是x在模型中的目標值。若x使得任意一個目標函數(shù)不再減小，則x為Pareto最優(yōu)解。求Pareto適應(yīng)度具體包括4個步驟，可參考文獻[16]。

4 案例計算與分析

4.1 案例場景

假定某次貨物運輸任務(wù)需要將600臺家電從青島運輸?shù)綇V州，每臺家電重量約為50 kg，總運輸重量為30 t。設(shè)置貨物計劃到達目的地廣州的運輸時間控制在38～40 h區(qū)間，若運輸時間超過40 h，則按單位每噸每小時懲罰費用1 000元計算；若運輸時間小于38 h，則按單位每噸每小時儲存費用500元計算。表2是各種運輸方式的單位費用，表3給出了3種運輸方式碳排放的單位成本。

根據(jù)此次運輸任務(wù)路程的實際情況，在國內(nèi)選擇了青島、上海、武漢、南京、濟南、杭州、合肥、福州、南昌、鄭州、長沙、南寧、廣州等13個城市組成運輸網(wǎng)絡(luò)，城市之間公路、鐵路、水路運輸?shù)睦锍谭謩e如表4～表6。

表2 運輸方式費用Table 2 Transportation mode cost 元/km

表3 運輸方式碳排放Table 3 Carbon emissions of transportation mode 元/(t·km)

表4 各城市節(jié)點之間公路運輸距離Table 4 Highway transportation distance between nodes in each city km

表5 各城市節(jié)點之間鐵路運輸距離Table 5 Railway transportation distance between nodes in each city km

表6 各城市節(jié)點之間海路運輸距離Table 6 Sea transportation distance between nodes in each city km

4.2 運行結(jié)果與分析

算法模型利用MATLAB軟件仿真實現(xiàn)，運行環(huán)境為CPU Intel Core i7-6700 3.4 GHz，內(nèi)存16 G，Win10 64位操作系統(tǒng)。分別使用遺傳算法和文中鯨魚優(yōu)化算法進行比較驗證，遺傳算法初始設(shè)置種群規(guī)模和算法初始設(shè)置隨機矩陣k值均為20，最大迭代值50。圖1表示兩種算法的運輸費用迭代對比，圖2表示兩種算法的碳排放迭代對比，圖3表示了兩種算法的運輸時間迭代對比。從結(jié)果對比圖2～圖4中可以看出，遺傳算法(GA)模型迭代2次后運輸費用達到約2.1萬元左右穩(wěn)定值，迭代5次后碳排放達到490 kg穩(wěn)定值，迭代2次后運輸時間達到38 h穩(wěn)定值；而文中鯨魚優(yōu)化算法(WOA)模型迭代8次后運輸費用達到約1.8萬元左右穩(wěn)定值，迭代2次后碳排放達到490 kg穩(wěn)定值，迭代3次后運輸時間達到36 h穩(wěn)定值。與遺傳算法相比，筆者基于鯨魚優(yōu)化算法求解多目標多式聯(lián)運問題可以較快獲得更為合理的尋優(yōu)結(jié)果，具有更好的尋優(yōu)能力和收斂特性。

圖1 運輸費用迭代Fig. 1 Iterative diagram of transportation costs

圖2 碳排放迭代Fig. 2 Iteration of carbon emissions

圖3 運輸時間迭代Fig. 3 Iterative diagram of transportation time

圖4路線方案Pareto適應(yīng)度值，最大適應(yīng)度約1.187，最小適應(yīng)度約0.190 7。

表7顯示了模型運算求解得出的6條推薦路線方案，用戶可結(jié)合實際情況從推薦路線中選擇最佳運輸方案。例如，方案1的Pareto適應(yīng)度最低，表明該方案的運輸費用、碳排放和運輸時間綜合因素最佳；方案6總成本最少，但用時最多。兩種方案在成本和時間上各占優(yōu)勢，從適應(yīng)度來看比較符合運輸實際，充分體現(xiàn)文中鯨魚優(yōu)化算法迭代尋優(yōu)的優(yōu)勢，證明了其可行性和有效性。

表7 運算結(jié)果Table 7 Operation results

圖4 路線方案Pareto適應(yīng)度Fig. 4 Pareto adaptability of route plan

5 結(jié) 語

多式聯(lián)運是目前物流行業(yè)提高運輸效率，符合企業(yè)多目標運輸要求的最有效方法。綜合考慮運輸成本、環(huán)保和時限要求，引入鯨魚優(yōu)化算法和多目標適應(yīng)度算法，仿真驗證了多式聯(lián)運的路徑選擇問題的可行性和有效性。從目前研究文獻來看，多位學(xué)者對鯨魚算法的優(yōu)化策略進行了改進，研究團隊也針對該問題進行了相關(guān)研究，并取得了相關(guān)成果。下一步將利用提出的新鯨魚算法優(yōu)化策略對多式聯(lián)運場景進行深入應(yīng)用研究，達到提升更加有效的目的。另外，未來將考慮引入國際物流實驗數(shù)據(jù)，提升國際多式聯(lián)運效率。