隨機機會約束的多式聯運多目標優化

尹傳忠，方顥蓉，武中凱，鄭士源

(1.上海海事大學 交通運輸學院，上海201306；2.中國鐵路哈爾濱局集團有限公司 經營開發部，黑龍江 哈爾濱150006；3.大連交通大學 機械工程學院，遼寧 大連116028)

通常意義上的多式聯運優化研究是在不同情景下構建模型，通過某些算法得到最優運輸方案。運輸方案一般包括運輸路徑和運輸方式選擇，多假設問題所處的環境是確定的。ZILIASKOPOU‐LOS等[1]以運輸時間最短為目標建立了多式聯運最短路選擇模型。李玉民等[2]綜合考慮時間、費用和碳排放因素構建多目標優化模型，并根據客戶差異化需求加權求和，將模型轉化為單目標問題求解。HAO等[3]建立了限制交付時間的最小化廣義運輸成本的多式聯運動態規劃模型。MOCCIA等[4]認為聯運過程中預定運輸服務具有固定的時間窗口，研究帶時間窗的多式聯運組織優化。此類研究多為單目標模型，或將多目標問題轉化為單目標求解，在時間約束方面多考慮交付時間限制，或將各節點進行單一的時間窗設置。此外，一些文獻圍繞不確定規劃理論對多式聯運問題展開研究，HOFF等[5]設計了隨機需求下的多式聯運網絡。王清斌等[6]認為中間節點轉運作業時間具有隨機特征。DEMIR等[7]建立包含隨機運輸時間和需求的多式聯運服務網絡，運用樣本均值近似方法求解并用實例證明了考慮隨機性在提高運輸計劃可靠性上的優勢。目前，關于隨機規劃的求解方法主要包括2類：一是將其轉化為確定性形式求解，該方法適用于一些較為簡單的特殊情景。二是逼近法，即通過模擬仿真生成大量樣本數據集來逼近函數，并結合智能算法求解，該方法研究較少，但算法普適性較高，可使用范圍更廣泛，當模型進一步豐富完善時該算法仍然可行。本文建立考慮班期的隨機多式聯運多目標優化模型，該模型以總期望成本與總期望時間為優化目標，對鐵路與水路運輸設置班期限制，同時考慮在途時間和換裝時間的隨機性,引入貨物在時間窗內交付的準時率，以直觀反映運輸服務水平。設計一種結合隨機模擬技術和改進的自適應NSGA-II的混合啟發式算法(MO-ANSGA-II)求解。

1 問題描述

考慮到鐵路與水路具有固定的運輸時刻表，公路運輸較為靈活，中間節點的時間限制根據轉運情況不同有所區別。當轉運至公路運輸時，無時間約束；當轉運至鐵路/水路運輸時，該節點受班次限制，設置硬時間窗約束。如圖1，T1，T2，T3是某節點鐵路/水路的固定班次，貨物到達該節點后換裝至鐵路/水路，進行下一階段運輸時會出現3種情景：在t1時刻到該節點，班次T1恰好發出，需要先完成換裝，等待班次T2發往下一個節點；在t2時刻到達節點，完成換裝后等待T2班次；在t3時刻到達節點，在換裝過程中班次T2發出，需要等待班次T3發往下個節點。

圖1 鐵路/水路班次運行示意圖Fig.1 Railway/waterway transportation schedule

2 優化模型

2.1 模型假設

1)貨物在運輸過程中不進行拆分且僅在節點處進行轉運；

2)同種運輸方式的運輸速度和單位成本在不同路段均相同；

3)3種運輸方式的在途時間及換裝時間是隨機變量且均服從正態分布[6,8-10]。

2.2 符號說明

模型中的參數與變量說明見表1。

表1 模型參數與變量Table 1 Parameters and variables

2.3 模型構建

基于標準機會約束規劃[11]，構建基于隨機機會約束的多式聯運多目標優化模型。

目標函數：

其中：

式(1)表示總的期望成本最??；式(2)為總期望時間最??；式(3)指總期望成本包括在途運輸成本、換裝成本、中轉節點等待班次產生的等待費以及在目的地節點因過早/過遲交付貨物產生的等待費/懲罰費；式(4)指貨物從起點到終點所花費的總時間，包括在途時間、換裝時間、中轉節點等待班次的時間。

約束條件：

式(5)保證節點貨流平衡；式(6)使貨物在2節點間僅選擇一種運輸方式；式(7)表示貨物在節點換裝次數至多一次；式(8)與(9)保證運輸過程中貨流不可拆分；式(10)為貨物從起點O由運輸方式s到達節點i的總時間；式(11)為貨物從起點到達節點i且完成運輸方式s轉換為運輸方式p的總時間；式(12)為運輸方式s到達節點i經歷的天數；式(13)確定貨物從節點i到j是否選擇運輸方式s的第n班車；式(14)為貨物在節點i等待運輸方式s出發所產生的等待時間，當不發生轉運或轉為公路時值為0；式(15)為機會約束，在規定時間內交付貨物的概率不小于α，可將此概率稱為準時率，準時率越高，滿足在客戶要求的時間窗內交付的概率越大，直觀地反映方案運輸服務水平高低；式(16)～(18)為0-1變量；式(19)表示在起點與終點無轉運過程。

3 算法設計

模型中的目標函數與約束條件中均有隨機變量，可利用隨機模擬技術處理。此外，多式聯運多目標優化模型屬于NP-hard[12]問題，可使用智能算法求解,其中NSGA-II是權衡各子目標獲得Pareto解常用智能算法。因此設計一種改進的自適應NS‐GA-II與Monte Carlo模擬結合的混合算法(MOANSGA-II)。

3.1 Monte Carlo模擬

3.2 改進的自適應NSGA-II

3.2.1 染色體編碼與解碼

染色體采用混合編碼的方法，分為2個區域，前一部分代表網絡中的節點，長度為節點數，由0和1組成，1代表通過節點反之取0。頭尾部基因固定為1，代表起點與終點；后一部分代表2節點間的運輸方式，長度比前一部分小1。對染色體進行解碼時，后一區域的有效長度為L(L為前一區域1的數目)，無效區域不參與解碼。

3.2.2 種群初始化

多式聯運網絡往往是非完全連通的，隨機生成的初始解存在大量非可行解，影響算法尋優效率。使用深度優先搜索(DFS)得到所有連通的路徑集合，從該集合中隨機選擇滿足機會約束的個體作為初始種群，以避免非可行解的影響，提高算法效率。

3.2.3 改進的自適應擁擠距離選擇算子

傳統的擁擠距離Di是通過計算與其相鄰的2個體在各子目標上的距離差之和獲得。簡單淘汰擁擠距離小的個體，可能會導致某些個體間距離差距過大，此外2個相鄰個體在不同子目標上距離差異程度較大的個體無法獲得更多遺傳機會，這會影響種群分布多樣性。本文在個體選擇過程中進行自適應調整，避免了種群分布出現距離差距過大的情況。個體i的新擁擠距離D′i的計算公式[13]：

其中，表示個體i在各個子目標上與其相鄰個體的擁擠距離的方差，Vi=是非支配排序后個體i相鄰2個體的第k個子目標的函數值。新的擁擠度算子考慮到各個子目標擁擠度距離的差異程度，有利于保持種群分布的多樣性。

3.2.4 自適應交叉與變異

一般的NSGA-II交叉、變異概率是人為設置的固定值的，無明確的設置規則。本文考慮使用自適應策略調整概率，通過改變交叉變異的概率以期望跳出局部最優[14]，自適應調整按如下公式：

其中，P(i)是第i代進行交叉/變異的概率；ki為當前代數與最大進化代數之比；maxP，minP為預設的交叉/變異概率的上下限。

3.3 MO-ANSGA-II算法整體流程

算法的具體流程如圖2所示。

圖2 MO-NSGA-II算法流程Fig.2 Flow chart of MO-NSGA-II

4 算例分析

4.1 基礎數據

隨機生成一個有21個節點，37條運輸弧，3種運輸方式的多式聯運網絡。

假設有一批5 t的貨物從節點0運往節點20，準備開始運輸的時間為6點，托運人要求交付時間窗為(45 h，75 h)。設公路、鐵路、水路運輸的平均速度為70，60和30 km/h。

圖3 多式聯運運輸網絡圖Fig.3 Multimodal transport network

假設各城市節點間的在途運輸時間是隨機的，服從正態分布，方差為1；節點間轉運時間也是隨機的，服從正態分布，具體如表2。

表2 各運輸方式間的單位轉運時間/成本Table 2 Transfer time/cost of the different transport modes(h?元?1?t?1)

公路、鐵路、水路基于運輸距離的單位運輸成本分別為0.5，0.3和0.02元/(t?km)，單位換裝時間與成本如表2所示。貨物提前/延遲交付產生的單位等待/懲罰成本為1.5/2.5元/(t?h)；貨物在中間節點等待出發產生的單位等待成本為0.5元/(t?h)。

各城市節點間公路運輸靈活，鐵路運輸、水路運輸具有固定的運輸班次，隨機生成各城市節點間鐵路與水路的每日固定發車/船班次時刻表。

4.2 結果分析

本算例隨機模擬次數為500次，機會約束概率為α=0.6，初始種群為50，最大遺傳代數為300，交叉概率為MaxPc=0.95，MinPm=0.55，變異概率為MaxPm=0.05，MinPm=0.005。

采用python3.7求解，計算得到的Pareto最優解如圖4，每個點代表一種運輸方案。具體的Pare‐to最優解如表3(保留3位小數)。

圖4 Pareto最優解Fig.4 Pareto optimal solutions

表3 中，節點欄中數字代表經過節點的編號，運輸方式欄中1，2和3分別代表公路、鐵路、水路運輸。各方案在滿足準時率大于60%的同時對成本和時間2個目標進行權衡。方案的期望時間在規定的交付時間范圍內或附近，越靠近時間窗界限的方案，準時率越低，盡管靠近時間窗的方案能更好地完成某一目標，但當客戶對交付時間要求高時，這些方案存在劣勢。決策者可根據客戶偏好和當前條件選擇出更合適的方案。

表3 最終運輸方案集Table 3 Final transportation schemes

以方案中時間、成本、準時率某一項最優的方案1，8，15為例，對比是否隨機、有無班期情況下各指標區別，見表4。

表4 不同情景下運輸方案各指標對比Table 4 Indexes of transport schemes under different scenarios

1)隨機情景下方案的準時率能夠直觀地將運輸服務水平納入方案指標。確定性情景下雖有準時率指標，但僅能取值1或0，因為確定性情景中，只存在可以在時間窗內交付和不能交付2種情況。確定、無班期條件下，方案15準時率為0，是指不可能在時間窗內交付，此方案將被淘汰。在隨機、無班期情景下，方案15的準時率則是近似為0，表示“該方案在時間窗內交付”這一事件發生的概率極低，可近似視為不能在時間窗內交付。

2)采用單一運輸方式的方案8，隨機與確定性情景下成本、時間不同，但差異較小。

3)方案1和15在有班期、隨機情景下的成本比有班期、確定情景下分別提高6.188元與12.425元。其主要原因是隨機情況下可能出現時間窗外交付的情況，產生支付額外等待費/懲罰費，準時率越低發生概率越高。

4)有班期限制時，方案15在隨機情景下的運輸時間較確定情景下降低2.612 h。主要原因是該方案中貨物到達公鐵中轉節點的時間靠近某一班次發車時間，確定性情況下會錯過該班次而必須等待下一班次發出；而隨機情況下存在提前到達節點，可以趕上此班次發出的可能，導致方案總時間下降。反之，當隨機情況下出現錯過某一班次而不得不等待下一班次發車的情況時，等待班次的時間增加，方案總時間也增加。也就是說有班期時，隨機性可能會導致方案在中間節點出現提早發出或錯過計劃班次的情況，降低/增加等候班次時間，從而影響總時間。

5)相較于無班期，運輸方案由于等待班期的情況出現，成本與時間均有明顯提升。

總體上，是否考慮班期與隨機因素均會導致運輸方案的成本、時間、準時率發生變化，影響pareto最優解集選擇。忽略班期和隨機性不利于決策者制定符合實際的科學方案。

為了證明算法的有效性，對改進的自適應NS‐GA-II(ANSGA-II)與一般NSGA-II進行比較。兩算法分別運行50次后，改進前后算法的平均解集數量、各目標最優值如表5所示。圖5則顯示了2種算法不同目標函數均值(去除重復個體)的收斂情況，其中改進后的算法在100代左右收斂，一般的NSGA-II算法在175代左右收斂?？偟膩碚f，ANS‐GA-II搜索到的解集數量更多，尋優能力更強，收斂速度更快，算法性能得到了有效提升。

圖5 不同算法下各目標函數均值收斂Fig.5 Iterative graph of the average value of each objective function under different algorithms

表5 算法結果對比Table 5 Comparison of algorithm results

5 結論

1)相比于確定情景，考慮隨機情景的決策方案更能適應復雜的多式聯運環境。

2)在不同情景下運輸方案(是否隨機、是否有班期)的成本/時間不同，具體變化程度因各方案的轉運次數、班期、準時率等因素的不同而異。班期與隨機性影響運輸方案的成本、時間、準時率，從而改變得到的帕累托最優運輸方案組構成。

3)基于不確定性理論，將一般的多式聯運優化模型擴展為隨機機會約束的多式聯運多目標優化模型，反映在途與換裝時間隨機性，同時引入時間窗內交付貨物的準點率作為機會約束概率，保證了運輸服務水平。

4)MO-ANSGA-II用于求解隨機機會約束的多式聯運多目標優化模型，具有良好的運算性能。

面對復雜的多式聯運運輸過程，本文仍有進一步研究的空間，例如考慮多貨流、客戶需求等的不確定性，將綠色低碳納入優化目標等都具有研究價值，此外，本文采用的算法性能也仍具有提升空間。