混合時間窗約束下多式聯(lián)運最優(yōu)路徑選擇研究

呂學偉，楊 斌，黃振東

（上海海事大學 物流科學與工程研究院，上海 201306）

0 引言

在現(xiàn)實的運輸過程中，公路運輸自由靈活，而鐵路、水路和航空運輸都有固定的到達時間和離開時間，貨物需要在運輸工具離開之前到達相應的節(jié)點位置，并完成相應的裝載任務，否則只能等待下一班次。對于收貨人而言，也存在一個收貨時間段，而這個時間段一般比較寬松。因此，在實際的運輸過程中，存在著運輸方式硬時間窗和收貨人收貨的軟時間窗組合而成的混合時間窗。

對于收貨人的軟時間窗，國內外的研究均較多，而對于運輸方式硬時間窗的研究，則國外的研究相對較多。Ziliaskopoulos 等[1]以鐵路、航空、水運等運輸方式的固定出發(fā)時刻表為約束條件，建立單目標或多目標模型，尋找最優(yōu)運輸路徑和運輸方式的組合；Chang[2]研究各節(jié)點處各種運輸方式的硬時間窗，并采用標號法尋找多目標下的最優(yōu)路徑和運輸方式組合；Cetin 等[3]重點研究收貨人的硬時間窗要求，規(guī)定在特定時間段內將貨物送達到收貨人的手里，以此為約束條件進行多式聯(lián)運最優(yōu)路徑的優(yōu)化；Marjani 等[4]以運輸過程中的軟、硬時間窗為約束條件，進行整車多式聯(lián)運、空箱調運等路徑優(yōu)化；付曉鳳等[5]綜合考慮危險品多式聯(lián)運過程中的安全性和經濟性，建立基于危險性最小，以及成本、時間最少的聯(lián)運方案優(yōu)化模型；黑秀玲[6]對時間窗進行敏感性分析；賴志柱[7]考慮到各節(jié)點處的軟時間窗，創(chuàng)立和聲搜索算法優(yōu)化運輸路徑；鄒宗峰等[8]以各個運輸節(jié)點上的軟、硬時間窗為約束，組成混合時間窗，采用加權法處理多目標優(yōu)化問題；梁曉慷[9]在考慮模糊運輸時限時間窗的基礎上，以運輸費用最小、客戶滿意度最高為優(yōu)化目標，構建多式聯(lián)運路徑優(yōu)化問題的線性規(guī)劃模型；楊江波[10]從實際運輸情況出發(fā)，考慮到公路運輸自由靈活，而鐵路、航空、水運在各個運輸節(jié)點處都有固定的發(fā)車時刻表，以這些固定時刻表為約束條件，建立總運輸成本最低的優(yōu)化模型，采用蟻群算法，為多式聯(lián)運經營人選擇最優(yōu)運輸方案。在此，從現(xiàn)實角度出發(fā)，研究混合時間窗對多式聯(lián)運最優(yōu)運輸方案的影響，以總成本最低為目標，構建混合時間窗約束下多式聯(lián)運最優(yōu)路徑選擇模型，并通過案例進行驗證。

1 混合時間窗約束下多式聯(lián)運最優(yōu)路徑選擇模型構建

1.1 問題描述及假設

將一批貨物從起始城市O運到終點城市D，采用集裝箱運輸方式，中間有多個節(jié)點城市，構成集合N，每個節(jié)點城市又有多種運輸方式，所有運輸方式構成集合K，在每個節(jié)點城市都可以轉換運輸方式。每個節(jié)點城市發(fā)往下一個節(jié)點城市的鐵路、水路運輸都有固定的到達和離開時間，而收貨人在收貨時有比較寬松的時間段。以鐵路運輸、水路運輸的硬時間窗和收貨人的軟時間窗組成的混合時間窗為約束，并以總的運輸成本最小為目標，為承運人選擇最優(yōu)的運輸方案。

假設在運輸途中貨物沒有被分割運輸，貨物狀態(tài)不發(fā)生任何變化，運輸工具和中轉工具的載運能力充足，能滿足集裝箱的運輸需求。

1.2 模型構建

以總運輸成本最低為目標，以混合時間窗為約束條件，構建多式聯(lián)運最優(yōu)路徑選擇模型如下。

式中：Z為總的運輸成本；n為集裝箱的標箱數；r為 1 標箱集裝箱的日租賃成本；Tt為貨主收貨時間；q為集裝箱的重量；為從第i個節(jié)點到第j個節(jié)點，采取第k種運輸方式的單位運輸成本；為從第i個節(jié)點到第j個節(jié)點，采取第k種運輸方式的運輸時間；為決策變量，當第i個節(jié)點到第j個節(jié)點采用第k種運輸方式時，值為 1，否則為 0；為在第i個節(jié)點，第k種運輸方式轉變?yōu)榈趌種運輸方式時的單位中轉費用，當k=l時，值為 0；為決策變量，如果在第i個節(jié)點處發(fā)生轉運，則該值為 1，否則為 0；為在第i個節(jié)點處采用第k種運輸方式的單位等待成本；為在第i個節(jié)點處等待第k種運輸方式到達的時間，在這個時間段內會發(fā)生等待成本；Ct為貨物提前到達終點的單位倉儲成本；Et為收貨人最早收貨時間點；Pt為延遲到達終點的單位懲罰成本；Lt為最遲收貨時間點；為在第i個節(jié)點，第k種運輸方式轉變?yōu)榈趌種運輸方式時的中轉時間，當k=l時，值為 0；為在第i個節(jié)點處第k種運輸方式等待離開第i個節(jié)點的時間；為第i個節(jié)點發(fā)往第j個節(jié)點的路線上，第k種運輸方式到達第i個節(jié)點的時間；為第k種運輸方式離開第i個節(jié)點的時間；，分別為下一班次，第k種運輸方式到達、離開第i個節(jié)點的時間；ti為貨物到達第i個節(jié)點處的實際時間；為第k種運輸方式在第i個節(jié)點處的總等待時間。

公式 ⑴ 表示總成本最小的函數，總成本包括租賃成本、運輸成本、中轉成本、等待成本、因偏離收貨人收貨時間窗而產生的懲罰成本；公式 ⑵表示第i個節(jié)點與第j個節(jié)點之間只能選擇一種交通工具；公式 ⑶ 表示在第i個節(jié)點處只能發(fā)生一次轉運；公式 ⑷ 表示總的運輸時間，包括運輸時間、中轉時間、在節(jié)點處等待運輸工具到達的時間，以及在運輸工具上等待離開節(jié)點的時間；公式 ⑸ 表示在各節(jié)點處等待運輸工具到達的時間，在這個時間段內會發(fā)生等待成本；公式 ⑹ 表示在第i個節(jié)點處在第k種運輸方式上等待離開第i個節(jié)點的時間，在這個時間段內不發(fā)生等待成本；公式 ⑺ 表示第k種運輸方式在第i個節(jié)點處的總等待時間，在第i個節(jié)點處等待第k種運輸方式到達的時間與在第i個節(jié)點處在第k種運輸方式上等待離開的時間之和，即公式 ⑸ 與公式 ⑹ 之和。

1.3 算法設計

多式聯(lián)運最優(yōu)路徑選擇問題被證明是 NP-hard問題。蟻群算法作為一種模擬進化算法，具有分布式、啟發(fā)式計算的特點，適合求解多式聯(lián)運的最優(yōu)路徑選擇問題。

在多式聯(lián)運的起點和終點之間，有n個節(jié)點，螞蟻在轉移的節(jié)點間釋放信息素，并通過信息素的交流來完成最優(yōu)路徑的選擇。螞蟻選擇可行的節(jié)點完成整個路徑，之后由其他的螞蟻按照剩下的可行節(jié)點完成整個路徑。當每只螞蟻到達終點后，進行局部信息素的更新，當所有螞蟻都到達終點后，進行全局信息素的更新，在經過最大迭代次數后得到最優(yōu)解，具體求解步驟如下。

（1）初始參數設置。設置蟻群數為m，起始時間為 0，最大迭代次數為NCmax，節(jié)點集合為P，讀入所有節(jié)點處所有運輸方式的運輸時間、運輸成本、中轉成本、等待成本、時間窗等信息，設定啟發(fā)信息和初始信息素，設定螞蟻結構包括運輸信息、線路選擇信息、中轉信息和到達節(jié)點的時間。

（2）對循環(huán)次數NC進行迭代，當達到最大迭代次數NCmax時，循環(huán)結束。即NC=NC+ 1。

（3）將各節(jié)點拆分成進入節(jié)點和離開節(jié)點，將螞蟻分配在各節(jié)點上，設置禁忌表tabum，記錄所有的起始節(jié)點。

（4）所有的螞蟻搜尋滿足條件的節(jié)點，將第r只螞蟻每次允許選擇的節(jié)點加入到候選集合allowedr。

（5）讓螞蟻選擇節(jié)點的公式可以表示為

式中：(t) 為t時刻，螞蟻r由第i個節(jié)點到第j個節(jié)點的概率；(t) 為t時刻路徑 (i，j) 上的信息素濃度；ηij為啟發(fā)函數，表示螞蟻從第i個節(jié)點到第j個節(jié)點的期望值，通常取 2 個節(jié)點城市間距離的倒數；α為啟發(fā)式因子，指螞蟻在移動時積累的信息量的多少對螞蟻的指導作用相對重要程度；β為期望的啟發(fā)式因子，指啟發(fā)信息對螞蟻搜索的相對重要程度。

對信息素進行更新的公式可以表示為

式中：τij(t+n) 為在 (t，t+n) 時間內，循環(huán)一次后，螞蟻在所有路徑上更新信息素的規(guī)則；ρ為信息素的揮發(fā)程度系數；1－ρ為信息素的殘留程度系數；Δτij(t，t+n) 為整個蟻群在經過 (t，t+n) 的時間，完成一次循環(huán)遍歷后，邊 (i，j) 上剩余的信息素；Δ(t，t+n) 為螞蟻r在經過 (t，t+n) 的時間，完成一次循環(huán)遍歷后，邊 (i，j) 上剩余的信息素。

（6）當所有的螞蟻都完成一次循環(huán)后，以總成本最低選擇最優(yōu)螞蟻。

（7）以最優(yōu)螞蟻的信息為依據，對全局進行信息素更新。

（8）當達到最大迭代次數時，循環(huán)結束，以步驟（6）的螞蟻所表示的信息為最優(yōu)解，否則返回步驟（2）。

2 案例分析

2.1 基礎數據

假設現(xiàn)有 10 t 貨物采用 20 ft 集裝箱從城市O運到城市D，中間有 5 個節(jié)點城市，分別記為A，B，C，E，F(xiàn)。每 2 個節(jié)點城市之間最多有 3 種運輸方式可供選擇，分別是公路、鐵路、水路。公路運輸沒有時間窗約束，鐵路、水路運輸都有固定的時間窗，收貨人有收貨的軟時間窗。各節(jié)點間連接方式如圖 1 所示。

圖 1 各節(jié)點間連接方式Fig.1 Connection modes among different nodes

假設公路運輸單價是 0.2 元/(t · km)，鐵路運輸單價是 0.15 元/(t · km)，水路運輸單價是 0.02 元/(t · km)，3 種運輸方式的速度分別是 60 km/h、60 km/h、30 km/h。假設 3 種運輸工具都是勻速運輸，而模型是研究時間窗對運輸方案的影響，將基于單位運輸距離的單位運輸成本轉化為基于單位運輸時間的成本，轉化后的運輸單價分別為 12 元/(t · h)、9 元/(t · h)、0.3 元/(t · h)。每標箱的日租賃成本是100 元，在鐵路車站因提前到達而產生的單位等待成本是 30 元/(t · h)，在碼頭是 20 元/(t · h)。假設各節(jié)點開往下一節(jié)點的鐵路每天有 4 列，時間窗寬度是 3 h，即在各個節(jié)點處，鐵路的停留時間是 3 h；船舶每天是 3 班，時間窗寬度是 5 h，即在各個節(jié)點處，船舶的停留時間是 5 h。鐵路和船舶的進站時間在指定范圍內隨機生成，貨主收貨的時間窗是[25，30]，提前到達的單位儲存成本是 40 元/(t · h)，延遲到達的單位懲罰成本是 60 元/(t · h)。假設OA1，O－A3弧中的鐵路和水運假設都是從 0 ∶ 00 開始出站，即貨物從0 ∶ 00 點開始發(fā)出。記某節(jié)點處某運輸方式的服務時間窗表示為 [a，b]，a表示運輸工具到達節(jié)點的時間，b表示運輸工具離開節(jié)點的時間。各節(jié)點的運輸時間參數如表 1 所示，各運輸方式間單位轉運成本、轉運時間參數如表 2 所示，各節(jié)點處鐵路、水路運輸的時間窗參數如表 3 所示。

表 1 各節(jié)點的運輸時間參數 hTab.1 Transport time parameters of each node

2.2 用蟻群算法進行求解

設置相關參數值：初始信息素為 0.1，啟發(fā)因子α為 2，期望啟發(fā)因子β為 5，信息素揮發(fā)系數ρ為0.05，蟻群規(guī)模m為 30，最大迭代次數NCmax為 200。得到的最優(yōu)解為：OA3A4A5D，運輸方式分別為鐵路-水運-水運-水運?；旌蠒r間窗下最優(yōu)路徑的運行數據如表 4 所示，各運輸方式的運行數據如表 5 所示。

2.3 比較分析

節(jié)點處沒有時間窗約束，相當于貨物在中轉途中各運輸方式無縫對接，這是目前大多數學者的思考模式。當無時間窗約束時，由蟻群算法得到的最優(yōu)解也為：OA3A4A5D，運輸方式為鐵路-水路-水路-水路，運行總成本是 717 元，運行時間是 23 h，運輸費用為 501 元，轉運費用為 120 元，租賃費用為 96 元。

表 2 各運輸方式間單位轉運成本、轉運時間參數Tab.2 Unit transportatn cost and transport time between different transportation modes

表 3 各節(jié)點處鐵路、水路運輸的時間窗參數Tab.3 Time windows for railway and waterway transport at each node

表 4 混合時間窗約束下最優(yōu)路徑的運行數據Tab.4 Operation data of optimal path constrained by mixed time windows

表 5 各運輸方式的運行數據Tab.5 Operating data for each mode of transport

將有混合時間窗限制與無混合時間窗限制下最優(yōu)路徑的費用與時間進行對比，成本對比如表 6 所示，時間對比如表 7 所示。

通過對比，無論是總費用、總時間，還是單個費用、單個時間，有混合時間窗約束的數值都要比無時間窗約束的數值高，至少是相等?？梢?，在現(xiàn)實的運輸過程中，因混合時間窗而產生的運輸費用不僅真實存在，而且這種數值有時還很大，對多式聯(lián)運最優(yōu)運輸方案的選擇會產生較大的影響。對于多式聯(lián)運的承運人而言，這種費用和時間不能無視，也就是不能無視混合時間窗的真實存在性，不僅要考慮收貨人軟時間窗的影響，更要考慮鐵路、水路、飛機等運輸工具硬時間窗的影響[11-13]。

表 6 成本對比 元Tab.6 Cost contrast

表 7 時間對比 hTab.7 Time contrast

3 結束語

基于運輸方式硬時間窗和收貨人收貨的軟時間窗，構成混合時間窗。在此基礎上，以總成本最少為目標，將混合時間窗納入約束條件，建立多式聯(lián)運最優(yōu)路徑選擇優(yōu)化模型，采用蟻群算法，能更精確和實際地反映多式聯(lián)運路徑選擇問題。通過有混合時間窗約束下的最優(yōu)路徑與無混合時間窗約束下的最優(yōu)路徑進行數據對比，無論運輸成本，還是運輸時間，兩者都有很大差距，這表明混合時間窗約束對多式聯(lián)運最優(yōu)運輸路徑的選擇具有重要影響，是經營人和承運人不能忽視的重要因素。由于設計的硬時間窗具有固定性，可以考慮隨機的硬時間窗進行深入研究，包括時間窗的寬度和時間窗的位置，以反映更為真實的運輸特征。