考慮多類型時間窗的集裝箱多式聯運路徑雙目標優化研究

孫 巖，虞 楠，王丹竹，陳偉建

（1.山東財經大學 管理科學與工程學院，山東 濟南 250014；2.交通運輸部水運科學研究院 物流工程技術研究中心，北京 100088；3.中國鐵道科學研究院集團有限公司 運輸及經濟研究所，北京 100081；4.中車建設工程有限公司 城軌運營事業部，北京 100078)

0 引言

在經濟全球化的驅動下，商品流通日益繁榮，運輸需求日益旺盛，運輸渠道顯著延長，運輸網絡迅速擴張，運輸環境更加復雜，從經濟性、時效性等方面對運輸業提出了挑戰。在此背景下，依靠單一運輸方式的運輸組織形式已經無法滿足客戶的運輸需求[1-2]。作為一種先進的運輸組織形式，集裝箱多式聯運以標準化集裝箱為載運單元，綜合利用鐵路、公路、水路等不同運輸方式的優勢，為客戶提供靈活、高效、多樣的運輸服務，并在全球范圍內得到了迅速的推廣和應用[3]。隨著集裝箱多式聯運網絡的不斷發展完善，作為提高集裝箱多式聯運系統運營效率關鍵的路徑優化問題得到了學界和業界的廣泛關注[4]。

目前，關于集裝箱多式聯運路徑優化的文獻較為豐富。張建勇等[5]在構建多式聯運網絡的基礎上，構建了以總成本最小為優化目標的多式聯運路徑規劃模型。在文獻[5]的基礎上，王濤等[6]研究了多式聯運的運輸方式組合優化問題，構建了優化模型，設計了基于Dijkstra 算法的啟發式算法。張運河等[7]以總成本最小為優化目標研究了多式聯運的最短路問題，通過在多式聯運網絡中增加虛擬發站與到站，使得問題求解可以借助Dijkstra 算法。魏航等[8]研究了時變網絡下的多式聯運最短路問題，在對多式聯運網絡進行變形處理的基礎上構建了優化模型，并設計了基于Dijkstra 算法和動態規劃的求解方法。Sun 等[9]以最小化運輸成本以及降低碳排放為目標，研究了考慮時間隨機性的多式聯運路徑雙目標優化問題。蔣琦瑋等[10]研究了運輸時間不確定下的多式聯運路徑優化問題，構建了問題優化的機會約束模型，設計了問題求解的啟發式算法。

近年來，隨著準時生產等先進生產策略的應用，客戶對運輸時效性的重視程度越來越高。尤其是多式聯運應用于長距離運輸中，往往因運輸組織方案規劃不合理導致運輸距離增加，造成多式聯運經濟性和時效性優勢發揮不夠顯著的問題。既有研究也采取了多種方法以提高集裝箱多式聯運路徑優化的時效性。陳雷等[11]在研究考慮碳排放的多式聯運路徑優化時規劃了運輸時限約束，使得集裝箱到達終點的時間不超過給定的運輸時限。Verma等[12]在規劃危險品公鐵聯運路徑時，以及Sun 等[13]在研究考慮開行方案的多商品流多式聯運路徑優化時均構建了運輸時限約束。梅夢婷等[14]將運輸時間最小化作為優化目標，構建了多式聯運路徑優化的“成本-時間-碳排放”多目標優化模型，設計了問題求解的帶精英策略的非支配排序遺傳算法。與文獻[13]的時效性優化方法相同，Sun 和Xiong等[15-16]均構建了多式聯運路徑優化的“費用-時間”雙目標優化模型，設計了求解問題帕累托解的算法。除規劃運輸時限約束、構建多目標優化2 種方法外，既有文獻提出了采用時間窗刻畫約束時間對多式聯運時效性進行優化。Zhang 等[17]在規劃考慮碳排放的多式聯運路徑優化時規劃了時間窗約束，保證集裝箱在規定的時間窗內運到終點。與文獻[17]相反，Sun 等[18]認為集裝箱可以較規定的時間窗提前或者延遲到達終點，但是會導致懲罰費用的產生，據此研究了帶有時間窗的多式聯運路徑優化問題。

既有文獻在多式聯運路徑優化研究上取得了一定的成果，但仍然存在不足之處。①多式聯運網絡中的一些中轉節點存在固定作業時間窗限制了節點中轉作業的進行[19]，而上述文獻忽略了節點固定作業時間窗對中轉作業的限制，影響多式聯運路徑優化的可行性。②在優化多式聯運時效性時，規劃運輸時限約束往往會導致集裝箱提早運到終點，致使倉儲保管等額外費用的產生。同時，運輸的準時性并不總是意味著運輸時間越短越好。此外，采用時間窗刻畫運輸時限符合客戶對集裝箱運到終點的準時性需求，但是構建硬時間窗約束忽視了客戶在一定程度上接受集裝箱提前或延遲運到終點這一事實，而采用軟時間窗構建懲罰費用時，單位懲罰費用取值往往難以準確確定，并且集裝箱提前或延遲運到終點并不一定會在短期內產生經濟損失[20]。

為此，對集裝箱多式聯運路徑優化問題進行研究，并在優化建模時考慮2 類時間窗：①規劃中轉節點固定作業時間窗硬約束，保證集裝箱到達此類節點時的時刻在其固定作業時間窗內，從而保證后續中轉作業的進行；②規劃運輸時限軟時間窗，據此規劃集裝箱運到終點的提早或延遲時間，并以其最小化構建多式聯運時效性目標，提高多式聯運路徑規劃的準時性。據此，構建考慮多類型時間窗的多式聯運路徑優化雙目標混合整數線性規劃模型，采用標準化加權求和法結合數學規劃軟件對問題進行求解，進一步分析多式聯運路徑優化的經濟性目標和時效性目標的關系，為多式聯運經營人根據客戶需求規劃運輸方案提供定量支持。

1 集裝箱多式聯運路徑雙目標優化研究

1.1 問題描述

一批集裝箱需要在客戶規定的運輸開始時刻從起點通過多式聯運(綜合考慮鐵路運輸、公路運輸和水路運輸3 種運輸方式)運至終點。多式聯運路徑優化即選擇一條最優的運輸路徑實現集裝箱起點至終點之間的運輸。在進行優化時，研究將平衡多式聯運成本與效率之間的關系，考慮中轉節點的作業時間窗約束，保證多式聯運路徑優化方案在時間和空間上的可行性。假設如下。

（1）集裝箱在運輸過程和中轉過程中不可拆分，即集裝箱最多采用1 種運輸方式在節點間進行運輸，并在中轉節點上最多進行1 次不同運輸方式間的中轉。

（2）多式聯運網絡中運輸方式的運輸能力，以及中轉節點的中轉作業能力均滿足該批集裝箱的運量要求。

（3）集裝箱的運輸信息(包括起點、終點、運量及運輸時限等)，以及多式聯運網絡的參數信息(包括網絡結構、時間、費用等)均是已知的、確定的。

1.2 優化建模

1.2.1 符號及其表示

以G= (N，A，S)表示多式聯運網絡，其中，N表示多式聯運網絡中的節點集合，A表示多式聯運網絡中的有向弧集合，S表示多式聯運網絡中的運輸方式集合。一批集裝箱需要采用多式聯運從起點(標號為o)運至終點(標號為d)，其運輸量為q(單位為TEU)，運輸開始時刻為t0，運輸時限時間窗為[ηmin，ηmax]。

優化建模所需的其他符號如下。

（1）標號、集合、參數。h，i，j為多式聯運網絡中的節點標號，且有h，i，j∈N；(i，j)為多式聯運網絡中由節點i到節點j的有向弧，且有(i，j)∈A；r，k為多式聯運網絡中的運輸方式標號，且有r，k∈S；Ni-為節點i的前向節點集合，且有Ni-?N；Ni+為節點i的后向節點集合，且有Ni+?N；Si為連接節點i的運輸方式的集合，且有Si?S；Sij為有向弧(i，j)上的運輸方式的集合，且有Sij?S；dijk為有向弧(i，j)上運輸方式k的運輸距離，km；tijk為有向弧(i，j)上運輸方式k的運輸時間，h；tirk為集裝箱在節點i由運輸方式r中轉至運輸方式k的單位中轉時間，h/TEU；[φimin，φimax]為節點i的固定作業時間窗，若節點i不存在固定作業時間窗，則可將[φimin，φimax]設為[0，+∞]；cijk為有向弧(i，j)上運輸方式k的單位運輸費用，元/TEU；cirk為集裝箱在節點i由運輸方式r中轉至運輸方式k的單位中轉費用，元/TEU；M為極大正數；

（2）變量。xijk為0-1 變量，若集裝箱由運輸方式k由節點i運到節點j，則xijk= 1，否則xijk= 0；yirk為0-1 變量，若集裝箱在節點i由運輸方式r中轉至運輸方式k，則yirk= 1，否則yirk= 0；zi為非負變量，表示集裝箱到達節點i的時刻；wi為自然數變量，用于將zi轉化為屬于0 : 00 至24 : 00 之間的時刻；Δ1為非負變量，表示集裝箱較運輸時限時間窗下界提前到達運輸終點的時間，h；Δ2為非負變量，表示集裝箱較運輸時限時間窗上界延遲到達運輸終點的時間，h。

1.2.2 雙目標混合整數線性規劃模型

在參考以往優化建模[2]的基礎上，以提高多式聯運的經濟性及時效性為優化目標，以“點-弧”模型為參考，構建集裝箱多式聯運路徑優化模型。

（1）經濟性目標函數Obj1。

多式聯運包括有向弧上的運輸過程和節點上的中轉過程，相應地，完成集裝箱運輸的費用包括在途運輸費用和中轉作業費用。據此，構建如式(1)所示的經濟性目標函數，即完成集裝箱從起點到終點運輸的費用最小化。

（2）時效性目標函數Obj2。

同前所述，在組織多式聯運進行長距離運輸時，運輸時效性也是多式聯運經營人關注的重點。為了提高運輸的準時性，避免集裝箱過早或過晚到達終點，構建了如式(2)所示的時效性目標函數，即集裝箱運抵終點的提前時間或延遲時間最小化。

（3）約束條件。

約束條件(3)為多式聯運網絡中的流量平衡約束，保證規劃多式聯運路徑由起點經中轉節點到終點的連續性。約束條件(4)和(5)為集裝箱的完整性約束，前者保證一批集裝箱在運輸過程是不可分割的，后者則保證集裝箱在節點中轉過程中的不可分割。約束條件(6)和(7)為多式聯運路徑上中轉節點與運輸弧段接續的連續性約束，保證多式聯運運輸過程和中轉過程的合理銜接，保證“點-弧”建模的合理性。約束條件(8)假設集裝箱到達起點的時刻等于其運輸開始時刻，從而進一步計算集裝箱到達各個節點的時刻。約束條件(9)和(10)為變量的計算兼容性約束，計算集裝箱到達規劃路徑上各個節點的時刻。約束條件(11)和(12)為節點固定作業時間窗約束，要求集裝箱到達節點的時刻必須在規劃的時間窗內，從而保證后續中轉作業的順利進行。由于節點固定作業時間窗的上界和下界均為24 小時制，因此，集裝箱到達節點的時刻需首先按照約束條件(13)和(14)進行處理，使其轉化為屬于0 : 00 至24 : 00 之間的時刻。上述約束能夠有效提升多式聯運路徑優化方案的合理性，確保集裝箱到達某一中轉節點時，該節點能快速進行集裝箱的中轉，從而避免集裝箱在中轉節點的無效等待，提高多式聯運效率。約束條件(15)和(16)為變量的計算兼容性約束，分別計算了集裝箱運抵終點的提前時間和延遲時間。通過設定目標函數(2)與約束條件(15)和(16)，多式聯運路徑優化方案能有效提高集裝箱到達終點的準時性，既避免了集裝箱提早到達而導致額外倉儲保管等成本，又避免了集裝箱延遲到達而導致客戶無法按照計劃完成后續生產加工等活動。約束條件(17)至(23)為變量的取值約束。

據此，構建了考慮多類型時間窗的集裝箱多式聯運路徑優化的雙目標混合整數線性規劃模型。相較于既有文獻多構建非線性規劃模型并設計啟發式算法進行問題求解，所構建的優化模型更容易進行求解，可有效用數學規劃軟件求得問題的全局最優解。

1.3 求解方法

式中：?1和?2分別為經濟性目標和時效性目標的權重，其具體取值由決策者在進行求解前人為設定。

在計算過程中，通過不斷調整?1和?2的取值，并計算不同取值下的單目標優化模型的最優解，最終可求得問題的帕累托解。單目標優化模型的優化目標為式(24)，約束條件包括式(3)至式(23)。研究利用數學規劃軟件LINGO 運行分支定界算法求解單目標混合整數線性規劃模型的全局最優解。

2 算例分析

為驗證優化建模方法的可行性，設計了以下算例，同時對算例優化結果進行分析。集裝箱多式聯運路徑網絡如圖1 所示。集裝箱多式聯運網絡運輸時間、運輸距離參數如表1 所示。

表1 集裝箱多式聯運網絡運輸時間、運輸距離參數Tab.1 Time and distance for online transportation in container multimodal transportation

圖1 集裝箱多式聯運路徑網絡Fig.1 Routing network of container multimodal transportation

在多式聯運網絡中，中轉節點固定作業時間窗如表2 所示。

表2 中轉節點固定作業時間窗Tab.2 Fixed operation time windows of transshipping nodes

不同中轉方式的單位時間和費用如表3 所示。研究認為相同運輸方式之間不需要中轉，因此相關單位中轉時間和中轉費用均為0。

表3 不同中轉方式的單位時間和費用Tab.3 Unit time and cost of different transshipping modes

在多式聯運中，不同的運輸方式有不同的運費計算方式。根據文獻[10]中的數據計算不同運輸方式的單位運輸費用(單位為元/TEU)。

在算例中，假設一批集裝箱需要從節點1 (起點)運輸至節點11 (終點)，其運量為30 TEU，在節點1 的運輸開始時刻為第1 天6 : 00，在節點11的運輸時限時間窗為第2 天21 : 00 至第3 天2 : 00，也即運輸時限時間窗為[45，50]。根據上述設計，利用LINGO 軟件運行分支定界算法對集裝箱多式聯運雙目標優化問題進行求解，得到集裝箱多式聯運路徑優化問題的帕累托解如圖2 所示。

圖2 中的4 個帕累托解分別代表一種集裝箱多式聯運路徑優化方案，不同優化方案具有不同的經濟性目標和時效性目標。圖2 所示的最優集裝箱多式聯運路徑優化方案如表4 所示。較采用方案4，方案3 能夠將多式聯運的時效性提高約75%，而僅導致多式聯運的經濟性降低約4.7%。由圖2 和表4 可知，集裝箱多式聯運路徑優化的經濟性目標和時效性目標是互相矛盾的，無法同時達到最優，提高多式聯運的經濟性勢必以犧牲其時效性為代價，反之亦然。因此，多式聯運經營人需要對多式聯運的經濟性目標和時效性目標進行折中處理。

表4 最優集裝箱多式聯運路徑優化方案Tab.4 Optimal routing scheme for container multimodal transportation

圖2 集裝箱多式聯運路徑優化問題的帕累托解Fig.2 Pareto solutions to the routing problem of container multimodal transportation

當客戶十分重視多式聯運的時效性，期望集裝箱能夠準時運抵終點，且能夠接受較高的運輸費用時，路徑優化方案1 最為合適。如果客戶對多式聯運經濟性和時效性同等重視，則具有均衡解的路徑優化方案最為合適。對于所研究的算例，具有均衡解的路徑優化方案滿足式(29)所示條件。經過計算，路徑優化方案3 為均衡解方案，滿足客戶對多式聯運經濟性和時效性的同等重視。

綜上所述，圖2 所示的每個帕累托點均代表了不同客戶需求下的最優多式聯運路徑優化方案。在運輸實踐中，多式聯運經營人可以結合具體的客戶需求、貨物時間價值等多種因素選擇最為合適的集裝箱多式聯運路徑優化方案。算例研究表明，所構建的多式聯運路徑優化模型可以規劃多樣化的多式聯運路徑優化方案以滿足不同的客戶需求，具有一定的可行性。

3 結束語

對考慮多類型時間窗的集裝箱多式聯運路徑優化問題進行研究，規劃節點的固定作業時間窗硬約束以提高路徑優化的可行性，構建運輸時限的軟時間窗以提高規劃路徑的時效性。研究以降低多式聯運費用和提高多式聯運準時性為優化目標構建了雙目標混合整數線性規劃模型，采用標準化加權求和法轉化為單目標優化模型，并利用數學規劃軟件進行問題求解。算例研究表明，集裝箱路徑優化問題的經濟性目標和時效性目標是互相矛盾的，兩者無法同時達到最優，問題優化存在帕累托解。根據問題優化結果，多式聯運經營人可以根據客戶在經濟性和時效性上的偏好選擇合適的帕累托解設計多式聯運路徑方案。