考慮支線運輸服務的多式聯運網絡優化*

蔣 洋， 張星臣， 周曉曄

(1. 沈陽工業大學 a. 管理學院， b. 機械工程學院， 沈陽 110870； 2. 北京交通大學 交通運輸學院， 北京 100044)

多式聯運是實現物流機動靈活、“門到門”服務的最好的運輸方式，其中的關鍵問題之一就是網絡優化設計問題[1]，主要圍繞網絡設計優化[2-3]、樞紐節點中轉服務過程[1]、選址布局優化[4-7]、配送車輛路徑優化[8-9]、能力及運力配置[1，10]等方面展開。考慮時間窗的車輛路徑問題(VRP with time windows，VRPTW)被廣泛應用于物流配送領域，如餐飲配送[11-12]、快遞配送等[13]。Br?ysy和Gendreau[14-15]對VRPTW問題的建模與求解算法進行了較全面的綜述，并按照求解算法將目前研究分為啟發式算法與人工智能算法兩類。其中，文獻[14]側重于啟發式算法在求解VRPTW問題方面的應用，而文獻[15]則對VRPTW問題的人工智能算法進行了總結。考慮到車輛路徑問題求解的復雜性，相關學者大多采用啟發式算法進行求解[16-17]。

本文基于LRP的研究思路，在多式聯運背景下探討網絡設計與支線配送路徑的綜合優化方法，提出Ⅱ階段決策思路，對樞紐布局、網絡設計及支線運輸服務設計等進行綜合決策，并設計啟發式求解算法，為發展基于多式聯運的“門到門”物流運輸服務提供理論借鑒。

一、問題描述

本文提出Ⅱ階段決策思路：階段Ⅰ中管理者對多式聯運的干線運輸網絡布局進行規劃，力求干線運輸中的固定成本與可變成本之和最小，同時對干線運輸網絡中的中轉集散樞紐布局進行設計；階段Ⅱ中管理者基于階段Ⅰ提供的樞紐及網絡布局規劃決策和非樞紐節點的需求歸并情況，針對任意一個樞紐節點進一步對支線運輸服務方案進行設計，決策內容包括各支線服務線路所服務的對象及順序情況。由于在此過程中考慮了服務時間窗因素，因此階段Ⅱ可以借鑒帶時間窗的車輛路徑問題的研究方法。

定義多式聯運網絡的節點集合為N，其中備選樞紐節點集合H?N，h∈H；非樞紐節點集合F?N；運輸方式集合為M，m∈M。

本文研究假設如下：

(1) 干線運輸網絡中各個樞紐節點間可設計多種不同運輸方式，支線運輸服務只能通過公路運輸；

(2) 同種運輸方式的運輸能力一致，忽略因等級等差異造成的影響；

(3) 不經過樞紐中轉的運輸需求量不在本文研究范圍內，如歸并于同一樞紐的非樞紐節點之間的運輸需求。

二、模型構建

階段Ⅰ和階段Ⅱ的決策優化模型可分別表述為式(1)和(20)，表1、2分別給出了模型參數及變量。

階段Ⅰ：

(1)

s.t.

(2)

Xik≤Xkk?k∈H，i∈N

(3)

(4)

(5)

(6)

(7)

(8)

表1 參數符號

表2 決策變量

(9)

(10)

(11)

(12)

(13)

(14)

(15)

Xik∈{0，1} ?i∈N，k∈H

(16)

(17)

(18)

(19)

式(1)中f(xijv)為支線運輸車輛進行貨物取送服務成本，該車輛圍繞樞紐節點k∈H對其支線進行服務，該成本由階段Ⅱ求解。階段Ⅱ參考帶時間窗的車輛路徑問題進行建模，其中樞紐節點“0”(k∈H)由階段Ⅰ給出。

階段Ⅱ：

(20)

s.t.

(21)

(22)

(23)

(24)

xijv(wiv+si+tij-wjv)≤0 ?v∈V，i，j∈N

(25)

(26)

a0≤wiv≤b0?v∈V，i∈{0}

(27)

(28)

(29)

xijv≥0 ?v∈V，i，j∈N

(30)

xijv∈{0，1} ?v∈V，i，j∈N

(31)

階段Ⅰ中目標函數實現了系統總成本最小化，包括樞紐及線路的建設成本以及干、支線運輸服務成本。約束條件式(2)、(3)表示一個非樞紐節點只能夠被一個樞紐節點服務；約束條件式(4)要求樞紐節點從集合H中產生；約束條件式(5)表示網絡中布局D個樞紐；式(6)～(9)表示樞紐間運輸方式應規劃約束；平衡流約束以及流量運行規劃約束如式(10)和(11)所示；式(12)計算結果表示由該樞紐點產生的或途徑中轉的總需求量；式(13)為干線運輸網絡中樞紐間的運輸成本；式(14)～(15)為線路及樞紐節點能力約束；式(16)～(19)為0-1變量定義。階段Ⅱ為帶時間窗的車輛路徑問題，該階段目標為實現各支線運輸總成本最小。約束條件式(21)確保了每個支線節點需求只被一條路徑服務；約束條件式(22)～(24)確保了任意一條路徑由一輛車進行服務；約束條件式(25)～(27)是時間窗約束；約束條件式(28)為車輛負載約束。式(29)表示樞紐所服務客戶的需求總量，是基于階段Ⅰ的貨流歸并后的結果，包括了兩部分需求的合并：一是歸并客戶與樞紐節點之間的貨運需求量；二是歸并節點與其他節點間需要經過樞紐節點中轉的需求量。式(30)、(31)定義了階段Ⅱ中的關鍵決策變量。

三、交叉熵為主體的啟發式方法

旅行商問題是VRP的一個特例。由于旅行商問題已被證明是NP難題，因此VRPTW也是NP難題。本文設計以交叉熵算法為主體的啟發式求解算法進行求解，算法流程借鑒文獻[24]的思路，主體算法流程偽代碼如表3所示，其中嵌入遺傳算法對模型階段Ⅱ進行求解。遺傳算法與交叉熵算法類似，都是一種優勝劣汰的隨機優化搜索算法，其主要優勢表現在優化過程中只需要適應度函數作為依據，不需要其他信息輔助，已在貨物配送路徑優化領域獲得廣泛應用[2]。

表3 基于交叉熵主體算法的流程

交叉熵為主體的啟發式算法思路如圖1所示，階段Ⅰ模型通過非樞紐節點歸并、干線運輸網絡設計決策等影響階段Ⅱ的支線運輸服務方案設計，反之亦然。通過Ⅰ、Ⅱ兩個階段之間的相互影響不斷反饋調節，最終形成綜合優化方案。

圖1 算法迭代流程思路

交叉熵算法的核心在于對選擇概率at不斷進行更新，使得越趨近于最優目標值的方案被選擇的概率越大，其他決策方案被選擇的概率越小，最終趨近于0，直至滿足收斂精度要求終止迭代。算法中，α表示交叉熵算法迭代權重系數；β表示算法迭代終止精度要求；ρ表示分位點；γt表示分位點位置的系統目標值；I表示0-1值。

四、算例分析

選取包含10個點的網絡算例對模型和算法的有效性進行測試，各點位置坐標如表4所示，其中擬規劃樞紐節點2個，非樞紐節點8個。網絡中包含公路和鐵路兩種運輸方式，具體參數如表5所示。假定網絡中任意兩個節點之間的運輸需求均為20噸，配送服務成本cij=1元/(噸·公里)，K=50輛，單車載重=400噸/輛。

表4 網絡節點信息

研究基于MATLAB開發算法。交叉熵算法的參數設置如下：Y=500，ρ=0.9，α=0.7，β=1e-5。設置遺傳算法中交叉概率為0.9、變異概率為0.1。

表5 模型參數

交叉熵算法收斂性如圖2所示。經過有限次迭代得到最優優化方案，可以看出交叉熵算法具有較好的穩定性，收斂速度較快。在前20次迭代過程中，系統目標值收斂速度明顯；在之后的迭代過程中系統目標值下降緩慢，30～40次迭代后達到誤差精度范圍。算例樣本配送路徑優化結果如表6所示。由表6可知，最優結果顯示選取1和3號點為樞紐節點，其余為非樞紐點。以1號點為中心的最優支線運輸服務路徑包括兩條：1→8→1，1→5→2→1(圖3a)；以3號點為中心的最優支線運輸服務路徑包括兩條：3→10→4→6→3，3→7→9→3(圖3b)。

圖2 交叉熵算法收斂性

表6 算例樣本配送路徑優化結果

圖3 樞紐節點支線配送路徑

在此算例樣本中，樞紐1～3之間選擇修建鐵路，且在節點1和3處分別建設鐵路車站。由于鐵路運輸區段的服務能力為1 000噸，可以滿足運輸需求，而且運輸成本低廉，單位噸·公里僅為0.2元，配送成本與網絡布局、干線運輸成本之和為60 203元。

表7 階段Ⅱ模型與分別優化的結果比較 元

兩階段分別優化所得到的樞紐布局方案為1號點和2號點，且非樞紐節點需求全部歸并到2號節點，1號節點不提供任何支線服務。此時干線網絡中1號點與2號點之間的運輸成本僅為665元，相對較小，但其第二個運行優化階段，即支線運輸服務成本會顯著提升，相比本文模型提高了200 435元。基于本文提出的階段Ⅱ優化決策方法所得到的優化布局方案是1號點和3號點，總成本僅為60 203元，相較分別優化的方法降低成本73%，非樞紐節點會根據具體需求、與樞紐點之間的位置關系等特點進行歸并，因此系統性地降低了支線配送距離及成本。

之所以兩階段分別優化的思路會產生需求歸并的不合理情況，是因為在階段Ⅰ多式聯運網絡設計中模型僅僅考慮了網絡設計、樞紐布局以及干線運輸成本，而忽略了支線運輸服務成本影響。根據模型約束條件式(12)可以看出，當所有非樞紐節點歸并于一個樞紐時，干線上的總需求最小，總成本也最低，但會導致配送成本急劇增加。

五、結 論