考慮貨物時間價值的國際集裝箱多式聯運路徑優化

吳曉黎，寇 淇*，汪泳波

(1. 華南理工大學 工商管理學院，廣東 廣州 510640；2.華南理工大學 電子商務系，廣東 廣州 510006；3. 深圳市中海通物流股份有限公司，廣東 深圳 518000)

0 引言

隨著全球經濟和貿易的不斷融合，跨國運輸聯系日益頻繁，多式聯運作為一種現代化的運輸組織方式，能夠最大限度地發揮各種運輸方式的優勢，從而實現更高效的資源利用、更長的運輸全程距離以及更好的綜合效益。近年來，新冠疫情的爆發為當前國際集裝箱運輸帶來了更大的機遇和挑戰。一方面，訂單和運量暴增，國際集裝箱運輸價格上升到之前的數倍甚至十倍；另一方面，由于疫情管控與工人停工等造成國際集裝箱運輸的時效延長，普遍存在延時問題。國務院也提出要大力發展多式聯運，優化運輸結構，提升運輸效率，降低運輸成本[1]。因此，在運輸路徑選擇中，如何同時實現成本和時效兩個方面的最優化，是一個迫切需要解決的難題。

隨著研究的不斷深入，部分學者也探究了多目標規劃問題。Topaloglu等[15]針對運輸過程中的車隊管理問題，結合相關算法建立了綜合模型。Ayed等[16-17]綜合各方面因素構建了多式聯運路徑選擇模型，旨在有效解決城市道路擁堵問題。Ayar等[18]針對海鐵聯運方面存在的問題，構建了多目標最優路徑規劃模型，以便控制運輸成本和減少滯港時間。Cho等[19]構建了WCSPP模型，該模型通過雙目標動態規劃算法的應用可以實現成本和時間的雙重兼顧。Ben-Akiva等[20]以客流預測為研究內容，構建了Logit模型，同時在貨運量預測方面構建了ADA模型。上述模型在很多國家進行了應用并取得良好效果，其有效性得到證明。Barceló等[21]以時間作為目標函數，通過構建實時決策模型來提升城市貨流分配效率，旨在有效解決貨流分配方面存在的問題。張敏等[22]將運輸成本、碳排放成本和客戶滿意度作為目標函數，通過多目標規劃研究了低碳多式聯運問題。上述多目標規劃研究均未考慮貨物時間價值，集裝箱箱型等因素，而本研究構建的雙目標優化模型考慮了上述因素的影響。并且，為了更好地解決多式聯運問題，本研究也改進了傳統Dijkstra算法。

綜上，隨著多式聯運的快速發展，國內外學者都進行了一系列深入研究?，F階段的多式聯運路徑規劃模型，包括單目標模型和多目標模型。單目標規劃模型常見的目標函數包括路程最短化，成本最小化等等。多目標規劃模型則包括兩種常見模式：第1種是目標權重約束設計；第2種是目標權重求解。但是就現階段而言，對國際集裝箱多式聯運的多目標規劃模型的研究較少。隨著全球經濟化的發展，國際貨物運輸需求逐年遞增，市場主體對貨物運輸方案的要求以及運輸企業的服務水平也逐漸提高[23]。而本研究以國際物流運輸為研究對象，對國際集裝箱多式聯運最優路徑規劃進行研究。本研究的創新之處主要體現在以下兩個方面：(1)在國際集裝箱多式聯運模型設計中考慮最小運輸成本、最小運輸時效兩個目標規劃模型，并采用權重分配將其轉化為單目標規模型，更有現實價值。其中，最小運輸成本模型在傳統基礎上考慮了相對微觀的決策影響因素，如箱型、多式聯運中轉時間、多式聯運等待時間等；(2)在模型求解算法上，為了讓傳統Dijkstra算法更好地解決多式聯運問題，從3個方面對其進行改進：考慮有向帶權的連通圖，循環多頂點標號，增加交通工具類型元素。

1 模型描述

1.1 問題描述

探究國際集裝箱運輸最優路徑規劃問題，問題可用已知的源G=(V，E，W，T)來表示。其中，V為國際集裝箱多式聯運過程中的節點組合，包含運輸起點、運輸中點和運輸終點。E為節點之間的運行方向。W為兩兩節點組成的權值，傳統權值主要是線路長短，由于研究對象為多式聯運的最優路徑規劃問題，因此權值為多目標規模模型的求解結果。T則為運輸交通工具類型，即兩兩節點組成的線段所需的交通工具類型。

1.2 研究假設

具體假設如下所示：

(1)各個節點換裝最多只有一次。多式聯運下的貨物運輸節點可以選擇換裝或者不換裝兩種決策，但換裝之后會確定相應轉運方式。

(2)運量不可細分，具有整體性。多式聯運下的貨物是統一整體，不可將其劃分成不同批次進行獨立運輸。

(3)運輸路線不能改變，具有固定性。另外，運輸速度和單位成本也具有固定性。

(4)運輸過程集裝箱的適配性。多式聯運下的集裝箱均采用國際標準，不存在所謂適配問題。

(5)排除外部意外因素的影響。例如交通擁堵、天氣惡化等因素。

(6)節點之間運費的穩定性。多式聯運下節點的運輸費用，不考慮淡旺季浮動的影響。

1.3 符號說明

使用到的符號及其具體含義如下所示：

決策變量：

其他變量：

2 模型構建

2.1 運輸成本節約模型

從節點i1到節點i2的國際集裝箱多式聯運的運輸成本如式(1)所示：

(1)

式(1)為從節點i1到節點i2的運輸成本主要由集裝箱使用費、運輸費、中轉費這3部分組成。

其中，集裝箱使用費計算如式(2)所示：

(2)

集裝箱運輸費用計算如式(3)所示：

(3)

集裝箱中轉費用計算如式(4)所示：

(4)

因此，從起點O到終點D的國際集裝箱多式聯運運輸的總成本Z如式(5)所示：

(5)

需要滿足如下的約束條件：

(6)

N1q1+N2q2≥Q，

(7)

(8)

(9)

N=N1+N2，

(10)

k，l∈{1，2，3，4}，

(11)

(12)

2.2 最短運輸時間模型

從節點i1到節點i2的運輸時間如式(13)所示：

(13)

因此，從起點O到終點D的運輸總時間T如式(14)所示：

(14)

式(14)需要滿足如下的約束條件：

(15)

(16)

(17)

(18)

T≤Tmax。

(19)

其中，式(15)～(18)與模型2.1中的約束條件有著相同的含義，在此不再贅述。式(19)為運輸時間要小于客戶所能承受的最大范圍。

2.3 貨物時間價值模型

周偉[24]認為將成本模型與效率模型通過權重設計轉化為單目標函數，需將效率模型與成本模型的單位統一。因此，將引入貨物時間價值函數，實現集裝箱多式聯運運輸時間模型向貨物時間價值模型的轉換，進而得出最優解，確定最優路徑。

為降低研究難度，本研究選擇線性函數展開研究?？紤]到貨物運輸持續時間不會過長，且貨物生命周期有限，因此本研究以月貶值率為指標。那么貨物時間價值函數具體如式(20)所示：

(20)

式中，Pmax為貨物最開始運輸時(T=0)，單位集裝箱的運輸價值；η和k分別為貨物的入箱率和貨物月貶值率。

2.4 雙目標優化模型

由于運輸成本與運輸時間本身之間存在著矛盾。通常運輸時間越短，運輸成本則越高，如何平衡二者關系是本研究需要探究的主要問題。在此，通過線性加權法將雙目標轉化為單目標，以此確保規劃模型的可解性。即根據不同類型客戶需求偏好靈活設計子目標模型權重，繼而求解模型最優解。

P=αC+βP(T)，

(21)

式中，α為成本偏好系數；β為時間偏好系數。

具體的雙目標優化函數如式(22)～(23)所示：

(22)

P(T)=

(23)

雙目標優化模型下的約束條件與模型2.1和2.2中的約束條件相同，即式(6)～(12)以及式(15)～(19)，在此不再贅述。

3 算法設計

求解“最短路徑”的算法有很多，其中比較常見的算法包括Dijkstra算法，Bellman-Fold算法，SPFA算法，Johnson算法等等。本研究主要采用Dijkstra精確算法求解最優路徑。

3.1 傳統Dijkstra算法

最優路徑規劃模型涵蓋兩個基本要素：運輸成本與運輸效率。王濤等[25]借助時間價值函數與權重系數實現了多目標向單目標的轉換。本節算法設計立足國際集裝箱，多式聯運實際。在Dijkstra算法實際應用中，需要輸入的參數涵蓋了基本查詢條件，比如：始發站、終點站以及出發時間。因此，研究可選擇精確串行算法中的Dijkstra算法作為本研究模型求解算法。

Dijkstra在最短路徑確認方面提出了標號法，該方法也是現階段被學者廣泛認可的一種算法。該算法主要是針對權圖中最短路徑問題而采取的算法，可以確定某一頂點到其他各與頂點之間的最短路徑。標號法目前在很多領域都得到非常廣泛的應用，無論是在物流運輸，還是在科學測繪等方面都取得良好成果。例如在高速公路收費、智能運輸系統應用等方面利用標號法實現了有效突破，在確定最短路徑方面發揮了重要作用。因此，很多學者開始探究基于Dijkstra的標號法，通過對這一算法進行優化和改進來更高效的探究最優路徑。

相較于其他類型算法，Dijkstra算法的最大優勢是應用了標號法。設G=(V，E，W)，該式中V為所有頂點的集合，E為兩兩頂點之間形成的路徑，W為路徑對應的權重系數集合。Wij是大于等于0的數值，當i與j出現不相鄰的情況，那么可出現Wij=∞。而Dijkstra算法的主要使用范圍是對圖G中任意兩兩節點之間的最短距離進行求解。

3.2 Dijkstra改進算法

3.2.1 Dijkstra算法的局限性

(1)尚未建立完善的算法退出機制。在一些有向帶權聯通圖中，原有的Dijkstra算法并不具備可行性。

(2)無法滿足多式聯運過程中多個頂點可同時獲得p標號的需求。

(3)無法滿足多式聯運交通工具多樣性需求。本研究將多式聯運作為研究對象，有向帶權交通圖涵蓋了節點、方向、權以及交通工具類型k，所以該算法難以針對交通工具組合，選擇提供有效的解決之道。

3.2.2 Dijkstra改進算法的符號設置

(3)假定Pr={v|v為已獲得永久性p標號的頂點}，那么標志著第r步通過集，r是大于等于0的數值；

(4)假定Tr=V-Pr，Tr標志著第r步的未通過集。

(5)假定Nr為第r步獲取永久性p標號的點集合。

3.2.3 Dijkstra算法的改進原理

針對傳統Dijkstra算法無法滿足多式聯運路徑規劃的局限性，提出以下改進思路：

3.2.4 Dijkstra改進算法的求解步驟

本研究對傳統Dijkstra算法進行改進之后，其計算過程主要包括3個步驟：

4 算例分析

4.1 算例數據

本研究選取了某公司由湖南C運往德國H的集裝箱貨物需求為案例場景，探究某公司多式聯運通道的最優選擇問題。具體描述如下：目前，某客戶的貨物需求為電子類產品，共計20個40尺普高箱和30個20尺開頂箱，共50箱貨物，由C運往H，可供選擇的多式聯運通道為華南至西北大通道、華南至中部各省份城市，與國際大通道海運或中歐班列等的結合。具體的運輸路徑如表1所述。

表1 湖南C市運往德國H市的集裝箱運輸路徑Tab.1 Container transport paths from city C in Hunan to city H in Germany

除此之外，還需搜集不同交通工具的運輸速度、節點之間不同交通方式的運輸距離以及運輸費用等。相關數據見表2。

表2 各節點之間的相關運輸數據Tab.2 Relevant transportation data among nodes

4.2 模型求解及結果分析

基于搜集的模型指標數據，賦予成本模型與效率模型不同權重，求解單目標綜合模型的求解結果。從極端值與均值兩個角度，分別進行權重設計試驗，求解不同權重需求下，國際集裝箱運輸的最優路徑，具體求解結果可見表3。

表3 多式聯運最優路徑方案Tab.3 Optimal path program of multimodal transport

當成本偏好系數為α=0.2，時間偏好系數為β=0.8，該類型客戶為運輸時間偏好型客戶，即客戶希望運輸時間最短。最優路徑為“C—Z—H”，該路徑下的運輸長度P=909 152.2，運輸成本為C=1 303 437.2。

當成本偏好系數為α=0.5，時間偏好系數為β=0.5。該類型顧客會綜合考慮運輸時間和運輸成本，此時，最優路徑為“C—L—H”，該路徑的長度為P=1 025 310.7，運輸成本為C=11 957 690.6。

當成本偏好系數為：α=0.8，時間偏好系數為：β=0.2，該類型客戶為運輸成本偏好型客戶，即希望運輸成本最小。在此需求下，最優路徑為“C—Z—H”，該路徑的長度和成本分別為P=982 510.0和C=786 963.3。

綜上，本研究構建的國際集裝箱多式聯運最優路徑規劃模型與算法，可為不同運輸目標型客戶，提供不同的最優運輸方案，能夠滿足不同類型客戶差異化需求，提升運輸效率，建立與客戶的良好關系。

4.3 最優路徑對年度運輸總量的影響

對客戶而言，除了關注當次的運輸成本、運輸時間外，也關注路徑規劃對年度運輸總量的影響，接下來，主要討論這3種路徑規劃對年度運輸總量的影響。

由表4可以得出，“C—L—H”，“C—Z—H”這兩個路徑下，年度運輸總量相差不大，但“C—L—H”路徑的成本較低；而“C—Z—H”這個路徑雖然成本較低，但年度運輸總量下降明顯，因此，在綜合考慮成本、時間以及年度運輸總量的情況下，“C—L—H”是最優路徑。

表4 不同最優路徑下年度運輸總量Tab.4 Total annual transportation with different optimal paths

4.4 改進Dijkstra算法的檢驗

為了驗證本研究構建的Dijkstra改進算法模型在解決多式聯運問題中的有效性，本節將引入啟發式算法對上述案例進行求解。然后，將這3種不同需求下Dijkstra改進算法模型與混合算法模型的結果進行對比分析。

4.4.1 啟發式算法及求解

考慮前文構建的Dijkstra改進算法模型在時間、成本方面進行了權重分配對比，因此，在混合算法的迭代中，也加入了這一因素，分別進行了3次迭代：對成本重視程度較高、對時間重視程度較高、時間成本均衡，關鍵參數設置為：種群數量為100，選擇概率為0.01，變異概率為0.15，信息素初始值為10。表5給出了3種不同需求偏好下的求解結果，從仿真結果可以看出，3種不同需求偏好求解問題的最終結果差異較大，但時間成本均衡下具有更快的收斂能力。

表5 不同需求偏好結果比較Tab.5 Comparison of results from different demand preferences

4.4.2 算法對比

將Dijkstra改進算法模型與混合算法模型結果進行對比見表6?？梢园l現，相對于混合算法而言，改進Dijkstra算法求解效果要略微優秀，在這3種需求下，總時間均比較小。成本方面，只有對成本偏好較高 (α=0.8，β=0.2)時，混合算法成本略低于Dijkstra改進算法，其他兩種情況，混合算法都是高于Dijkstra算法的，特別是時間成本均衡的情況下，差值相對較大，而這種情況是客戶需求做多的情況，充分驗證了本研究構建的Dijkstra改進算法模型在解決多式聯運問題中的有效性。

表6 Dijkstra改進算法與混合算法結果比較Tab.6 Comparison of results between improved Dijkstra algorithm and hybrid algorithm

5 結論

本研究在考慮貨物時間價值，集裝箱箱型等因素的條件下，研究集裝箱多式聯運問題，依次建立運輸節約成本、最短運輸時間模型，以及整合運輸成本和時間加權的雙目標優化模型，并對傳統的Dijkstra算法進行改進。利用ZH公司的實際案例數據進行算例分析，驗證構建的雙目標優化模型和求解算法的可行性和有效性，并進一步地探究最優路徑對年度運輸總量的影響。研究結果表明：(1)不同運輸目標客戶的需求偏好會影響多式聯運最優路徑的選擇，進而影響運輸成本、運輸時效及年度運輸總量。(2)與混合算法相比，Dijkstra改進算法求解效果更優。只有對成本更加偏好時，混合算法在解決多式聯運問題時的成本略低于Dijkstra改進算法，而在其他情況下，Dijkstra改進算法求解出的運輸成本和時間則更加經濟高效，其最大時間節約率和成本節約率分別為30.86%，20.31%。

不足與展望：受限于各方面因素，本研究依然存在不足之處。例如，多式聯運過程中不同交通工具的發車時間、作業時間帶有一定的預估性，與實際存在一定偏差，實際上不同交通運輸方式會有專門的列車時刻表，因此，未來可將列車時刻表與模型算法共同導入智慧系統，實現對國際集裝箱多式聯運的智能選擇。