蔣 洋， 張星臣， 周曉曄

(1. 沈陽工業(yè)大學(xué) a. 管理學(xué)院， b. 機(jī)械工程學(xué)院， 沈陽 110870； 2. 北京交通大學(xué) 交通運(yùn)輸學(xué)院， 北京 100044)

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

本文基于LRP的研究思路，在多式聯(lián)運(yùn)背景下探討網(wǎng)絡(luò)設(shè)計與支線配送路徑的綜合優(yōu)化方法，提出Ⅱ階段決策思路，對樞紐布局、網(wǎng)絡(luò)設(shè)計及支線運(yùn)輸服務(wù)設(shè)計等進(jìn)行綜合決策，并設(shè)計啟發(fā)式求解算法，為發(fā)展基于多式聯(lián)運(yùn)的“門到門”物流運(yùn)輸服務(wù)提供理論借鑒。

一、問題描述

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

定義多式聯(lián)運(yùn)網(wǎng)絡(luò)的節(jié)點(diǎn)集合為N，其中備選樞紐節(jié)點(diǎn)集合H?N，h∈H；非樞紐節(jié)點(diǎn)集合F?N；運(yùn)輸方式集合為M，m∈M。

本文研究假設(shè)如下：

(1) 干線運(yùn)輸網(wǎng)絡(luò)中各個樞紐節(jié)點(diǎn)間可設(shè)計多種不同運(yùn)輸方式，支線運(yùn)輸服務(wù)只能通過公路運(yùn)輸；

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

(3) 不經(jīng)過樞紐中轉(zhuǎn)的運(yùn)輸需求量不在本文研究范圍內(nèi)，如歸并于同一樞紐的非樞紐節(jié)點(diǎn)之間的運(yùn)輸需求。

二、模型構(gòu)建

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

階段Ⅰ：

(1)

s.t.

(2)

Xik≤Xkk?k∈H，i∈N

(3)

(4)

(5)

(6)

(7)

(8)

表1 參數(shù)符號

表2 決策變量

(9)

(10)

(11)

(12)

(13)

(14)

(15)

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

(16)

(17)

(18)

(19)

式(1)中f(xijv)為支線運(yùn)輸車輛進(jìn)行貨物取送服務(wù)成本，該車輛圍繞樞紐節(jié)點(diǎn)k∈H對其支線進(jìn)行服務(wù)，該成本由階段Ⅱ求解。階段Ⅱ參考帶時間窗的車輛路徑問題進(jìn)行建模，其中樞紐節(jié)點(diǎn)“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)

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

三、交叉熵為主體的啟發(fā)式方法

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

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

交叉熵為主體的啟發(fā)式算法思路如圖1所示，階段Ⅰ模型通過非樞紐節(jié)點(diǎn)歸并、干線運(yùn)輸網(wǎng)絡(luò)設(shè)計決策等影響階段Ⅱ的支線運(yùn)輸服務(wù)方案設(shè)計，反之亦然。通過Ⅰ、Ⅱ兩個階段之間的相互影響不斷反饋調(diào)節(jié)，最終形成綜合優(yōu)化方案。

圖1 算法迭代流程思路

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

四、算例分析

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

表4 網(wǎng)絡(luò)節(jié)點(diǎn)信息

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

表5 模型參數(shù)

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

圖2 交叉熵算法收斂性

表6 算例樣本配送路徑優(yōu)化結(jié)果

圖3 樞紐節(jié)點(diǎn)支線配送路徑

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

表7 階段Ⅱ模型與分別優(yōu)化的結(jié)果比較 元

兩階段分別優(yōu)化所得到的樞紐布局方案為1號點(diǎn)和2號點(diǎn)，且非樞紐節(jié)點(diǎn)需求全部歸并到2號節(jié)點(diǎn)，1號節(jié)點(diǎn)不提供任何支線服務(wù)。此時干線網(wǎng)絡(luò)中1號點(diǎn)與2號點(diǎn)之間的運(yùn)輸成本僅為665元，相對較小，但其第二個運(yùn)行優(yōu)化階段，即支線運(yùn)輸服務(wù)成本會顯著提升，相比本文模型提高了200 435元?；诒疚奶岢龅碾A段Ⅱ優(yōu)化決策方法所得到的優(yōu)化布局方案是1號點(diǎn)和3號點(diǎn)，總成本僅為60 203元，相較分別優(yōu)化的方法降低成本73%，非樞紐節(jié)點(diǎn)會根據(jù)具體需求、與樞紐點(diǎn)之間的位置關(guān)系等特點(diǎn)進(jìn)行歸并，因此系統(tǒng)性地降低了支線配送距離及成本。

之所以兩階段分別優(yōu)化的思路會產(chǎn)生需求歸并的不合理情況，是因?yàn)樵陔A段Ⅰ多式聯(lián)運(yùn)網(wǎng)絡(luò)設(shè)計中模型僅僅考慮了網(wǎng)絡(luò)設(shè)計、樞紐布局以及干線運(yùn)輸成本，而忽略了支線運(yùn)輸服務(wù)成本影響。根據(jù)模型約束條件式(12)可以看出，當(dāng)所有非樞紐節(jié)點(diǎn)歸并于一個樞紐時，干線上的總需求最小，總成本也最低，但會導(dǎo)致配送成本急劇增加。

五、結(jié) 論