不確定環(huán)境下多式聯(lián)運(yùn)路徑多目標(biāo)優(yōu)化

彭 勇，肖云鵬，羅義娟

(重慶交通大學(xué) 交通運(yùn)輸學(xué)院，重慶 400074)

0 引 言

多式聯(lián)運(yùn)是目前最重要的運(yùn)輸組織模式之一，合理的多式聯(lián)運(yùn)路徑?jīng)Q策，將降低運(yùn)輸成本，提高運(yùn)輸效率。決策目標(biāo)是影響多式聯(lián)運(yùn)路徑優(yōu)化的關(guān)鍵因素，常見的優(yōu)化目標(biāo)有最小成本、最短時間、最小風(fēng)險、最低碳排放等。但過去單一決策目標(biāo)的研究對運(yùn)輸實(shí)踐的指導(dǎo)意義較小，因真實(shí)情況下決策目標(biāo)通常是不唯一且相悖的[1]。如貨主在運(yùn)輸某些具有強(qiáng)時效性、高附加值的貨物(輕工、紡織品及服裝、醫(yī)藥制品及鮮活易腐品等)時，通常要求盡快運(yùn)輸交付，但提高運(yùn)輸速度往往意味著運(yùn)輸企業(yè)要支出更多的成本[2]。因此選擇一條能滿足企業(yè)經(jīng)濟(jì)效益追求，同時能縮短運(yùn)輸時間的最優(yōu)路徑，對于提升企業(yè)效益與服務(wù)質(zhì)量，增強(qiáng)企業(yè)競爭力具有重要意義。現(xiàn)有研究針對多目標(biāo)多式聯(lián)運(yùn)問題的解決方法有權(quán)重法[3]，目標(biāo)轉(zhuǎn)換為約束[4]，Pareto解[5]等，真實(shí)情況下權(quán)重法中不同目標(biāo)權(quán)重的確定非常困難，目標(biāo)轉(zhuǎn)換為約束后增加了算法復(fù)雜度且求解質(zhì)量不高，而Pareto解能很好處理相悖目標(biāo)之間的表達(dá)，而被廣泛應(yīng)用于多目標(biāo)問題的研究中[6]。

此外多式聯(lián)運(yùn)實(shí)踐因受交通、天氣等影響，具有不確定性?，F(xiàn)有研究通過隨機(jī)理論[7]、模糊理論[8]或區(qū)間數(shù)[9]來處理多式聯(lián)運(yùn)路徑?jīng)Q策過程中的不確定性。然而忽略了對決策有重要影響的班期[10]，當(dāng)問題引入班期后，優(yōu)化目標(biāo)的分布函數(shù)或數(shù)值特征通過以上不確定處理方法求解非常困難[11]。而由電腦進(jìn)行統(tǒng)計抽樣實(shí)驗(yàn)的蒙特卡洛方法可為各種數(shù)學(xué)問題提供近似解，尤其針對這種太復(fù)雜以至很難分析求解的問題非常有效。

綜上，不確定環(huán)境下多式聯(lián)運(yùn)研究多以單目標(biāo)函數(shù)為主，忽略了現(xiàn)實(shí)情況下決策目標(biāo)的多樣性，且現(xiàn)有研究中涉及的不確定處理方法，都不能有效解決多式聯(lián)運(yùn)路徑?jīng)Q策中有重要影響的班期。故筆者在充分考慮決策人擁有多種互斥目標(biāo)需求的前提下，針對前人鮮有涉及的班期，構(gòu)建不確定環(huán)境下，考慮班期的以最小成本與最短時間為目標(biāo)的優(yōu)化模型。利用蒙特卡洛方法處理模型中時間的不確定性，設(shè)計一種將蒙特卡洛仿真與多目標(biāo)蟻群算法相結(jié)合的混合啟發(fā)式優(yōu)化求解算法，并改進(jìn)蟻群算法的轉(zhuǎn)移策略和信息素更新策略，提高算法求解質(zhì)量。

1 問題描述與建模

1.1 問題描述

圖1所示多式聯(lián)運(yùn)網(wǎng)絡(luò)中，節(jié)點(diǎn)間的貨物運(yùn)輸有多種運(yùn)輸方式供選擇，運(yùn)輸時間往往因天氣，事故等原因有一定不確定性。不同運(yùn)輸方式在節(jié)點(diǎn)處轉(zhuǎn)運(yùn)將產(chǎn)生轉(zhuǎn)運(yùn)時間及轉(zhuǎn)運(yùn)費(fèi)用。另外，在多式聯(lián)運(yùn)中，鐵路與水路運(yùn)輸往往按照一定的時刻表(班期)發(fā)班，貨物難以做到即到即走，而是要等待該運(yùn)輸方式該班發(fā)班時刻才能出發(fā)，本問題考慮節(jié)點(diǎn)處轉(zhuǎn)運(yùn)不同運(yùn)輸方式有其班期限制這一因素。筆者構(gòu)建不確定環(huán)境下運(yùn)輸總成本最小化及運(yùn)輸總時間最小化的雙目標(biāo)優(yōu)化模型，求起點(diǎn)到終點(diǎn)的最短路徑。

圖1 多式聯(lián)運(yùn)網(wǎng)絡(luò)Fig. 1 Multimodal transport network

1.2 模型假設(shè)

模型假設(shè)如下：①運(yùn)輸貨物單一且不可分割；②不同節(jié)點(diǎn)間單位運(yùn)輸成本已知；③不同節(jié)點(diǎn)間運(yùn)輸時間隨機(jī)分布已知；④不同運(yùn)輸方式之間的轉(zhuǎn)運(yùn)時間與成本已知；⑤貨物運(yùn)抵節(jié)點(diǎn)若需轉(zhuǎn)運(yùn)，則立即開始裝卸貨物；⑥貨物在完成轉(zhuǎn)運(yùn)后按所選運(yùn)輸方式最近班期開始后一行程運(yùn)輸。

1.3 數(shù)學(xué)模型

目標(biāo)函數(shù)為：

(1)

(2)

(3)

約束條件為：

(4)

(5)

(6)

?m,n∈M

(7)

(8)

(9)

(10)

(11)

(12)

(13)

式(1)為目標(biāo)函數(shù)；式(2)為運(yùn)輸總費(fèi)用；式(3)為運(yùn)輸總時間；式(4)保證路徑第一個節(jié)點(diǎn)為起點(diǎn)；式(5)保證節(jié)點(diǎn)間只選擇一種運(yùn)輸方式；式(6)保證單一節(jié)點(diǎn)最多發(fā)生一次轉(zhuǎn)運(yùn)服務(wù)；式(7)保證轉(zhuǎn)運(yùn)之后運(yùn)輸方式存在且連續(xù)；式(8)保證路徑最后一個節(jié)點(diǎn)為終點(diǎn)；式(9)保證路徑中每個節(jié)點(diǎn)的流入邊與流出邊是唯一且連續(xù)的；式(10)為到達(dá)節(jié)點(diǎn)j的時刻；式(11)為在節(jié)點(diǎn)j完成轉(zhuǎn)運(yùn)的時間；式(12)為在節(jié)點(diǎn)j等待運(yùn)輸方式m發(fā)車的時間；式(13)為離開節(jié)點(diǎn)j的時刻。

2 問題求解

多目標(biāo)多式聯(lián)運(yùn)路徑優(yōu)化問題屬于NP難問題，由M. DORIGO等[12]提出的蟻群算法在最短路徑問題最優(yōu)解質(zhì)量和搜索效率的平衡方面具有較大優(yōu)勢而被廣泛應(yīng)用于解決多目標(biāo)問題。

(14)

2.1 利用蒙特卡洛方法模擬不確定性

蒙特卡羅方法是利用隨機(jī)數(shù)和概率分布處理不確定和確定性問題的方法，通過給定一定數(shù)量的樣本，由優(yōu)化目標(biāo)的樣本平均值估計優(yōu)化目標(biāo)真實(shí)值，從而求解優(yōu)化問題。且由“強(qiáng)大數(shù)定律”，當(dāng)優(yōu)化目標(biāo)樣本數(shù)量足夠大時，樣本平均值為優(yōu)化目標(biāo)真實(shí)值的無偏估計量。

2.2 改進(jìn)蟻群算法

在多目標(biāo)規(guī)劃中，當(dāng)解xA的所有目標(biāo)優(yōu)于解xB的目標(biāo)時，稱xA支配xB，若無解支配xA，xA為非支配解(Pareto解)。

求解多目標(biāo)規(guī)劃的改進(jìn)蟻群算法信息素更新結(jié)合Pareto解，路徑信息素由其存留信息與Pareto解對應(yīng)螞蟻的信息素決定。路徑信息素更新后限制其濃度，避免過早收斂，同時引入方向啟發(fā)因子，加快迭代速度，改善基本蟻群算法在解決大規(guī)模問題時，迭代速度過慢，過早收斂等使算法求解質(zhì)量低的問題。

2.2.1 多式聯(lián)運(yùn)網(wǎng)絡(luò)編碼及參數(shù)初始化

將原多式聯(lián)運(yùn)網(wǎng)絡(luò)節(jié)點(diǎn)拆分為兩部分后組成新節(jié)點(diǎn)，新節(jié)點(diǎn)的整數(shù)位為原節(jié)點(diǎn)數(shù)，小數(shù)位為運(yùn)輸方式編碼。初始化蟻群算法相關(guān)參數(shù)。

2.2.2 螞蟻移動尋找路徑

大量的運(yùn)輸實(shí)踐經(jīng)驗(yàn)顯示：從起點(diǎn)到終點(diǎn)的最短路徑中任一路段與“起點(diǎn)-終點(diǎn)”連線間的夾角通常較小，即，最短路徑方向總是循著目的地方向，具體如圖2。即下一備選路徑與“起點(diǎn)-終點(diǎn)”連線間的夾角的大小與其成為最短路的概率呈負(fù)相關(guān)關(guān)系。

圖2 路段方向夾角示意Fig. 2 Schematic diagram of the angle of road section direction

(15)

(16)

式中：γ為節(jié)點(diǎn)i,j間的路段和“起點(diǎn)-終點(diǎn)”連線間的夾角，夾角越小，φij越大，其為最短路徑與選擇該路徑的概率就越大；τij,α分別為為節(jié)點(diǎn)i,j間的信息素濃度及其啟發(fā)因子；ηij,β分別為為節(jié)點(diǎn)i,j間的能見度及其啟發(fā)因子；allowedk是螞蟻下一步可選擇路徑的集合。

每只螞蟻從起點(diǎn)出發(fā)，首先確定下一節(jié)點(diǎn)的可行路徑并保存入allowedk中；若allowedk為空集，螞蟻返回起點(diǎn)，重新開始選擇路徑；否則根據(jù)式(16)確定的轉(zhuǎn)移概率與輪盤賭，選擇下一個節(jié)點(diǎn)，直至螞蟻到達(dá)終點(diǎn)，螞蟻完成一次路徑。

2.2.3 蒙特卡洛仿真

2.2.4 求Pareto解

運(yùn)用快速非支配排序算法[14]求截至本次迭代所有可行解的Pareto解。

2.2.5 信息素更新

對Pareto解路徑中節(jié)點(diǎn)i,j間路段更新信息素τij，更新策略為：

τij(u+1)=(1-ρ)×τij(u)+ρ×Δτij(u+1)

(17)

(18)

式中：τij(u)為第u次迭代，路段i,j上的信息素值；τij(u+1)為更新后的信息素值；Δτij(u+1)為信息素增量；L(u)為第u次迭代Pareto解中可行解的平均值；ρ為信息素?fù)]發(fā)系數(shù)。

為避免“過早收斂”，通過“最大-最小螞蟻系統(tǒng)”限制路段信息素。

τij(u+1)∈[τmin,τmax]

(19)

(20)

(21)

式中：Vn為節(jié)點(diǎn)總數(shù)；θbest為選取最優(yōu)的概率；h(u)為第u次迭代Pareto解中各組可行解平均值的最小值。

3 算例分析

選取文獻(xiàn)[15]的公鐵海聯(lián)運(yùn)實(shí)例，實(shí)例中包含25個節(jié)點(diǎn)，構(gòu)建以朔州為起點(diǎn)，上海為終點(diǎn)的多式聯(lián)運(yùn)網(wǎng)絡(luò)。假設(shè)不同節(jié)點(diǎn)同一運(yùn)輸方式班期相同，不同運(yùn)輸方式班期如表1，公路運(yùn)輸時間在±20%之間波動，鐵路與水運(yùn)運(yùn)輸時間在±10%之間波動。

表1 不同運(yùn)輸方式班期Table 1 Schedule of different transportation modes

3.1 算法對比

多目標(biāo)優(yōu)化解的質(zhì)量常用比較指標(biāo)有Pareto解的均勻性(SP)及其寬廣性(MS)。

SP定義為：

(22)

(23)

MS定義為：

MS=

(24)

蟻群算法參數(shù)設(shè)置為：螞蟻數(shù)量取20、迭代次數(shù)取20次，蒙特卡洛模擬次數(shù)K=1 000，α=0.8，β=0.2，ρ=0.3，貨物重1 t。將改進(jìn)蟻群算法、方向蟻群算法、信息素限制蟻群算法及基本蟻群算法，分別運(yùn)行50次，結(jié)果如表2。

結(jié)果顯示，方向蟻群算法的解集平均值優(yōu)于基本蟻群算法與信息素限制蟻群算法11%～25%，說明方向啟發(fā)因子能夠加快迭代速度；Pn低24%～57%表明其易過早收斂，無法為決策提供更多選擇。相反，信息素限制蟻群算法能找到更多的Pareto解，但是解的質(zhì)量不高。結(jié)合表2與圖3～圖6，同時考慮兩種策略的改進(jìn)蟻群算法能在考慮Pn同時兼顧解的質(zhì)量，相較其他算法有一定優(yōu)越性。

表2 算法運(yùn)行結(jié)果對比Table 2 Comparison of algorithm running results

圖3 SP對比箱圖基本蟻群算法Fig. 3 SP comparison box plot of basic ant colony algorithm

圖4 MS對比箱Fig. 4 MS comparison box plot

圖5 Pn對比箱Fig. 5 Pn comparison box plot

圖6 解集平均值對比箱Fig. 6 Solution set mean comparison box plot

3.2 算法參數(shù)分析

螞蟻個數(shù)設(shè)20，最大迭代次數(shù)30，α取0.7～0.9，β取0.3～0.1、ρ取0.2～0.4，其他參數(shù)不變，進(jìn)行50組對比實(shí)驗(yàn)。結(jié)果如圖7，僅α=0.9，β=0.1，ρ=0.4時，實(shí)驗(yàn)平均Pn波動超過1；實(shí)驗(yàn)平均解集平均值整體波動小于5%。

圖7 不同參數(shù)組合實(shí)驗(yàn)平均Pn與解集平均值Fig. 7 Experimental mean Pn and solution set mean of differentparameter combinations

設(shè)最大迭代次數(shù)30次，其他參數(shù)不變，螞蟻數(shù)分別為10、15、20和25進(jìn)行了50組對比實(shí)驗(yàn)。結(jié)果如圖8～圖9，不同螞蟻數(shù)算法都能在較低的迭代次數(shù)使實(shí)驗(yàn)平均Pn與解集平均值趨于定值；迭代結(jié)束實(shí)驗(yàn)平均Pn接近統(tǒng)一，實(shí)驗(yàn)平均解集平均值波動小于5%。以上結(jié)果表明改進(jìn)蟻群算法對參數(shù)設(shè)置要求較低，算法具有一定的魯棒性。

圖8 迭代次數(shù)與螞蟻數(shù)對實(shí)驗(yàn)平均Pn的影響Fig. 8 The influence of the number of iterations and ants on theexperimental mean Pn

圖9 迭代次數(shù)與螞蟻數(shù)對實(shí)驗(yàn)平均解集平均值的影響Fig. 9 The influence of the number of iterations and ants onthe average value of experimental mean solution set

3.3 Pareto解分析

取算例結(jié)果中部分Pareto解如表3，決策人可根據(jù)對成本與時間的敏感性挑選不同方案。

表3 部分非支配的運(yùn)輸方案Table 3 Partially non-dominant transportation scheme

將基于權(quán)重和基于Pareto理論的蟻群算法進(jìn)行比較，C和T兩個優(yōu)化目標(biāo)通過權(quán)重轉(zhuǎn)化為minZ=ω1C+ω2T單目標(biāo)，其中ω1和ω1為權(quán)重，通過調(diào)整權(quán)重比例得到如表4。

表4 不同權(quán)重下運(yùn)輸方案Table 4 Transportation schemes under different weights

通過圖10可知，Pareto解比基于權(quán)重的雙目標(biāo)蟻群算法的求解結(jié)果好，能提供更多可行方案，表明Pareto方法能更好地處理雙目標(biāo)問題。

圖10 Pareto解與權(quán)重解對比Fig. 10 Comparison of Pareto solution and weighted solution

4 結(jié) 語

以運(yùn)輸總成本與運(yùn)輸總時間為優(yōu)化目標(biāo)，構(gòu)建不確定環(huán)境下的多式聯(lián)運(yùn)最短路徑模型。使用蒙特卡洛方法處理網(wǎng)絡(luò)中的不確定性，改進(jìn)基本蟻群算法的轉(zhuǎn)移策略和信息素更新策略，結(jié)合非支配排序的改進(jìn)蟻群算法求解Pareto解。同一環(huán)境下進(jìn)行50次試驗(yàn)，驗(yàn)證改進(jìn)蟻群算法優(yōu)化效果；然后分別改變迭代次數(shù)、螞蟻數(shù)量、信息素啟發(fā)因子、能見度啟發(fā)系數(shù)和信息素?fù)]發(fā)系數(shù)，結(jié)果顯示：算法參數(shù)設(shè)置對算法影響不明顯；同時算法結(jié)果驗(yàn)證了Pareto理論解決多目標(biāo)問題的優(yōu)越性。

通過對一個仿真算例進(jìn)行實(shí)驗(yàn)分析。研究發(fā)現(xiàn)公路運(yùn)輸擁有較高靈活度，能提高貨物運(yùn)輸效率，但運(yùn)輸成本較高；鐵路運(yùn)輸各屬性平衡；海運(yùn)運(yùn)輸將大幅度提升運(yùn)輸總時間，但成本較低。故當(dāng)決策人對貨物無時效性要求，且對成本比較敏感，可選擇方案1或2，通過海運(yùn)運(yùn)輸，犧牲運(yùn)輸時間，降低運(yùn)輸成本；如決策人對貨物時效性(如原材料限制后續(xù)生產(chǎn))及成本皆有要求，可根據(jù)決策人實(shí)際要求選擇合適方案；如決策人對貨物時效性有要求，且愿意提高預(yù)算，可選擇方案5，在運(yùn)輸路徑中部分選擇公路運(yùn)輸，提高運(yùn)輸效率。