劉 松, 郭 敏, 樂(lè)美龍, 彭 勇
(1.南京航空航天大學(xué)民航學(xué)院, 南京 211106; 2.重慶交通大學(xué)交通運(yùn)輸學(xué)院, 重慶 400074; 3.山地城市交通系統(tǒng)與安全重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400074)
近幾十年來(lái),地震、洪水、臺(tái)風(fēng)等各種類型的自然災(zāi)害頻發(fā),造成大量的經(jīng)濟(jì)損失與人員傷亡。災(zāi)害發(fā)生后,能否在道路塌陷、運(yùn)力不足、交通受阻等情況下找到一條時(shí)間成本較低、效率較高的運(yùn)輸路線將救援物資盡快調(diào)撥到災(zāi)區(qū)成為了搶險(xiǎn)救災(zāi)、降低人員傷亡與經(jīng)濟(jì)損失的關(guān)鍵。
路徑優(yōu)化問(wèn)題受到了學(xué)者的廣泛關(guān)注,這些研究主要集中在增加運(yùn)輸模型約束條件或算法設(shè)計(jì)方面。祝新等[1]考慮到路況對(duì)于傳統(tǒng)醫(yī)療冷鏈物流配送模型的影響,建立了以綜合成本為目標(biāo)的配送模型。陳疇鏞等[2]研究了在時(shí)間窗及配送公平性影響下的運(yùn)輸路徑規(guī)劃問(wèn)題。何婷等[3]研究了疫情背景下生鮮電商企業(yè)的車輛路徑優(yōu)化問(wèn)題。Jiang等[4]建立了將多項(xiàng)目包裝與車輛路徑和分批配送相結(jié)合的優(yōu)化模型。劉松等[5]研究了碳排放限制下冷藏集裝箱的路徑優(yōu)化問(wèn)題。陳汨梨等[6]研究了不確定條件下多式聯(lián)運(yùn)路徑優(yōu)化問(wèn)題。
在應(yīng)急物資運(yùn)輸方面,許多學(xué)者在研究確定環(huán)境下的多目標(biāo)優(yōu)化及物資調(diào)度與選址問(wèn)題。宋英華等[7]建立了雙目標(biāo)應(yīng)急物資配送車輛路徑問(wèn)題整數(shù)規(guī)劃模型,并驗(yàn)證了模型的有效性。薛星群等[8]研究了通行約束和運(yùn)力限制條件下的應(yīng)急物資聯(lián)合調(diào)度問(wèn)題。劉倩宇[9]將選址問(wèn)題與路徑優(yōu)化問(wèn)題進(jìn)行了結(jié)合,考慮到備選配送中心的優(yōu)先級(jí),對(duì)應(yīng)急物流的選址——路徑優(yōu)化進(jìn)行了研究。呂偉等[10]研究了應(yīng)急物資需求緊迫程度差異下的物資配送路徑優(yōu)化問(wèn)題。劉晉等[11]運(yùn)用自適應(yīng)遺傳算法,對(duì)應(yīng)急物資儲(chǔ)備庫(kù)選址及調(diào)度問(wèn)題進(jìn)行了研究。
隨著研究的深入,有學(xué)者注意到確定環(huán)境下給出的應(yīng)急物資運(yùn)輸方案難以滿足實(shí)際中的應(yīng)急物資運(yùn)輸要求,對(duì)不確定環(huán)境下的應(yīng)急物資運(yùn)輸開展了研究。張夢(mèng)玲等[12]研究了不確定需求下考慮供應(yīng)商參與機(jī)制的應(yīng)急物資配置問(wèn)題。Wang等[13]提出了一種海運(yùn)不確定性條件下的多式聯(lián)運(yùn)綜合調(diào)度模型。王妍妍等[14]研究了模糊信息下多種類應(yīng)急物資多周期分配優(yōu)化問(wèn)題。葛顯龍等[15]針對(duì)動(dòng)態(tài)事件對(duì)配送過(guò)程的干擾問(wèn)題,研究了多品類共同配送車輛路徑優(yōu)化問(wèn)題。但是已有的研究大多假設(shè)已知部分參數(shù)的概率分布,而在實(shí)際運(yùn)輸作業(yè)過(guò)程中,尤其是發(fā)生突發(fā)事件后的應(yīng)急物資運(yùn)輸,這些參數(shù)卻因缺少歷史數(shù)據(jù)而無(wú)法知道其概率分布情況,而更應(yīng)該尋求魯棒運(yùn)輸路徑。然而,單一運(yùn)輸方式下的魯棒路徑優(yōu)化問(wèn)題已經(jīng)被證明是NP-Hard(nondeterministic polynomial-hard)問(wèn)題[16],對(duì)該類問(wèn)題的研究一直以來(lái)都是學(xué)者研究的熱點(diǎn)。孫秀巧等[17]運(yùn)用改進(jìn)遺傳退火算法,對(duì)高速公路巡邏車輛路徑優(yōu)化調(diào)度問(wèn)題進(jìn)行了研究??当蟮萚18]建立了多目標(biāo)應(yīng)急救援物資配送路徑優(yōu)化模型,并利用改進(jìn)后的遺傳算法驗(yàn)證了模型的正確性。昝新宇等[19]提出一種基于改進(jìn)蟻群算法的救援路徑規(guī)劃方法。趙邦磊等[20]建立了多目標(biāo)優(yōu)化的冷鏈物流配送模型,并設(shè)計(jì)改進(jìn)ACO(ant clony optimization)算法對(duì)模型進(jìn)行了求解。而應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化問(wèn)題需要同時(shí)考慮不同運(yùn)輸方式之間的轉(zhuǎn)運(yùn)以及鐵路、水路等的發(fā)班時(shí)刻限制等,對(duì)其求解相較于單一運(yùn)輸方式下的路徑優(yōu)化問(wèn)題更為困難,需要針對(duì)模型的獨(dú)特性設(shè)計(jì)專門的算法。
綜上所述,當(dāng)前中外學(xué)者對(duì)確定環(huán)境下的路徑優(yōu)化問(wèn)題研究較多,而不確定環(huán)境下的成果較少,這類研究忽略了外部環(huán)境對(duì)于系統(tǒng)的影響,得到的運(yùn)輸優(yōu)化路徑在應(yīng)用于復(fù)雜多變的應(yīng)急物資運(yùn)輸網(wǎng)絡(luò)時(shí)魯棒性較差。且少有學(xué)者同時(shí)考慮到應(yīng)急物資運(yùn)輸途中的不確定性以及水路、鐵路等運(yùn)輸方式的發(fā)班時(shí)刻限制?;诖?,針對(duì)應(yīng)急物資運(yùn)輸?shù)牟淮_定性和鐵路、水路等的發(fā)班時(shí)刻限制,構(gòu)建應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化模型,并針對(duì)模型求解的NP難特點(diǎn),設(shè)計(jì)大變異遺傳算法與自適應(yīng)遺傳算法,并進(jìn)行了算例應(yīng)用,可為應(yīng)急物資決策者提供一定的參考。
在如圖1所示的多式聯(lián)運(yùn)網(wǎng)絡(luò)圖中,假設(shè)現(xiàn)需將應(yīng)急物資從起點(diǎn)1運(yùn)輸?shù)浇K點(diǎn)8,物資在不同的運(yùn)輸方式間存在著轉(zhuǎn)運(yùn)時(shí)間。同時(shí),由于運(yùn)輸環(huán)境的不確定性,各節(jié)點(diǎn)之間所需要的運(yùn)輸時(shí)間是不確定的。另外,水路及鐵路運(yùn)輸需要按照發(fā)班時(shí)刻表發(fā)班,求一條時(shí)間成本較低且魯棒性能較好的物資調(diào)撥路徑。
圖1 多式聯(lián)運(yùn)運(yùn)輸網(wǎng)絡(luò)Fig.1 Multimodal transport network
1.2.1 模型假設(shè)
(1)貨物在運(yùn)輸節(jié)點(diǎn)只可轉(zhuǎn)運(yùn)一次。
(2)運(yùn)輸途中并不發(fā)生貨物的裝卸,即運(yùn)輸全程貨運(yùn)量保持不變。
(3)相鄰兩節(jié)點(diǎn)之間,只能采用一種運(yùn)輸方式進(jìn)行運(yùn)輸。
(4)每個(gè)運(yùn)輸節(jié)點(diǎn)最多被經(jīng)過(guò)一次,即運(yùn)輸途中不出現(xiàn)封閉回路。
(5)運(yùn)輸途中除了由于班期限制導(dǎo)致等待外,其他地方無(wú)需等待。
1.2.2 模型參數(shù)及變量
本文模型參數(shù)及變量如表1所示。
表1 模型參數(shù)
1.3.1 目標(biāo)函數(shù)
應(yīng)急物資運(yùn)輸最主要的特點(diǎn)是時(shí)效性要求高,因此將運(yùn)輸時(shí)間最短作為決策目標(biāo),另外,魯棒優(yōu)化分為絕對(duì)魯棒、相對(duì)魯棒以及偏差魯棒3種,采用絕對(duì)魯棒優(yōu)化方法,構(gòu)建目標(biāo)函數(shù),即
(1)
式(1)中:第一項(xiàng)為運(yùn)送時(shí)間;第二項(xiàng)為轉(zhuǎn)運(yùn)時(shí)間;第三項(xiàng)為由于班期限制導(dǎo)致的等待時(shí)間。
(2)
(3)
1.3.2 約束條件
(1)需要滿足流量守恒約束。即起點(diǎn)凈流量為1,轉(zhuǎn)運(yùn)點(diǎn)凈流量為0,終點(diǎn)凈流量為-1。表達(dá)式為
(4)
(2)應(yīng)急物資在相鄰兩個(gè)節(jié)點(diǎn)之間只能選擇一種運(yùn)輸方式,表達(dá)式為
(5)
(3)運(yùn)輸連續(xù)性約束,即
(6)
(4)應(yīng)急物資在節(jié)點(diǎn)處只能轉(zhuǎn)運(yùn)一次,即
(7)
(5)決策變量只能取0或者1。
(8)
(9)
由于傳統(tǒng)的最短路算法不能求解應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化模型,現(xiàn)設(shè)計(jì)遺傳算法進(jìn)行求解。
2.1.1 編碼
由于多式聯(lián)運(yùn)運(yùn)輸方式,運(yùn)輸路線都未知,故采用可變長(zhǎng)的路徑編碼方法。具體編碼過(guò)程如下。
(1)染色體的編碼由兩段組成,第一段采用Floyd法生成一條從起點(diǎn)到終點(diǎn)的運(yùn)輸路徑。
(2)第二段是在第一段生成運(yùn)輸路徑的基礎(chǔ)上,隨機(jī)生成一種對(duì)應(yīng)節(jié)點(diǎn)間已存在的運(yùn)輸方式,用數(shù)字1表示公路運(yùn)輸;2表示鐵路運(yùn)輸;3表示水路運(yùn)輸,如圖2所示。
圖2 編碼示意圖Fig.2 Coding diagram
2.1.2 初始種群的生成
采用如下方法生成初始種群。
(1)根據(jù)多式聯(lián)運(yùn)網(wǎng)絡(luò)圖生成稀疏矩陣,稀疏矩陣中的非零元素對(duì)應(yīng)于邊的權(quán)值,即路徑長(zhǎng)度。
(2)利用Floyd法生成染色體第一段編碼,接著隨機(jī)選擇節(jié)點(diǎn)間的運(yùn)輸方式,生成第二段編碼,得到一條初始染色體。
(3)判斷染色體數(shù)量是否達(dá)到種群規(guī)模,若已達(dá)到,則終止;否則將染色體第一段編碼所對(duì)應(yīng)的各節(jié)點(diǎn)間的路權(quán)擴(kuò)大一個(gè)較小倍數(shù),返回(2)。
因本文中以時(shí)間成本最小為目標(biāo),而遺傳算法的適應(yīng)值越大越好,故采用目標(biāo)函數(shù)的倒數(shù)為適應(yīng)值函數(shù),即
f=1/Z
(10)
2.3.1 選擇
采用輪盤賭選擇方法。
2.3.2 交叉
對(duì)第一段染色體采用兩點(diǎn)交叉的遺傳方式,并對(duì)于交叉后可能產(chǎn)生的非法染色體通過(guò)Floyd法進(jìn)行修復(fù),具體過(guò)程如下。
(1)若第一個(gè)交叉節(jié)點(diǎn)直接與起點(diǎn)相連,且與起點(diǎn)之間沒(méi)有通路,則可通過(guò)Floyd法找到兩點(diǎn)間的一條連通路。同樣的方法也可處理第二個(gè)交叉節(jié)點(diǎn)與終點(diǎn)相連時(shí)的阻斷情況。
(2)若兩個(gè)交叉點(diǎn)皆在路徑中間位置,則任意交叉點(diǎn)和相鄰節(jié)點(diǎn)無(wú)法連通時(shí),都可以通過(guò)找到與之相鄰的上一節(jié)點(diǎn)之間的連通路徑進(jìn)行方案改進(jìn)。若無(wú)連通路徑,則繼續(xù)探查再上一節(jié)點(diǎn)。如圖3所示:染色體U1與染色體U2交叉后得到的染色體U3為非法染色體。因節(jié)點(diǎn)2和節(jié)點(diǎn)4之間存在連通路,則無(wú)需繼續(xù)探查節(jié)點(diǎn)2與上一節(jié)點(diǎn)7之間的連通情況,可直接用Floyd法找到節(jié)點(diǎn)2與節(jié)點(diǎn)4之間的一條連通路2-3-4使染色體U3為合法染色體。
圖3 Floyd法尋找連通路Fig.3 Floyd’s method to find the connecting pathway
2.3.3 變異
采用的變異方法如下:隨機(jī)選擇第k個(gè)基因位作為變異位,去除該基因位上的基因,接著判斷第k-1個(gè)基因與第k+1個(gè)基因所對(duì)應(yīng)的節(jié)點(diǎn)間是否存在連通路。若連通,則直接在染色體第二段編碼對(duì)應(yīng)位置隨機(jī)生成一種運(yùn)輸方式;反之,則利用Floyd法找到兩點(diǎn)之間的一條最短路,將其連通,后續(xù)編碼過(guò)程同上。如圖4所示,若有染色體1-2-6-8-2-3-1,現(xiàn)將第二個(gè)基因位上的基因2去掉,因?yàn)楣?jié)點(diǎn)1和節(jié)點(diǎn)6之間無(wú)連通路,所以可利用Floyd法生成一條1和6之間的最短連通路。假設(shè)生成的連通路為1-3-6,接著便隨機(jī)生成節(jié)點(diǎn)1和節(jié)點(diǎn)3、節(jié)點(diǎn)3和節(jié)點(diǎn)6之間的運(yùn)輸方式,假設(shè)生成的運(yùn)輸方式為公路運(yùn)輸與鐵路運(yùn)輸,則最終該染色體將變異為1-3-6-8-1-2-1。
圖4 變異操作示意圖Fig.4 mutation operation diagram
在上述理論基礎(chǔ)上,本文中設(shè)計(jì)大變異遺傳算法和自適應(yīng)遺傳算法對(duì)應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化模型進(jìn)行求解。
2.4.1 大變異遺傳算法
大變異遺傳算法的主要思想如下:為避免算法出現(xiàn)“早熟”現(xiàn)象,當(dāng)某代的所有個(gè)體集中在一起時(shí),便以一個(gè)遠(yuǎn)大于設(shè)置概率的大變異概率進(jìn)行變異操作,將集中了的參數(shù)進(jìn)行“打散”,進(jìn)而跳出局部最優(yōu),保持種群多樣性;反之,則繼續(xù)采用設(shè)置的變異概率進(jìn)行遺傳操作,具體過(guò)程如圖5所示。
Fmax為代代最大適應(yīng)度;Favg為當(dāng)代平均適應(yīng)度;α為密集因子圖5 大變異遺傳算法流程圖Fig.5 Flow chart of large mutation genetic algorithm
2.4.2 自適應(yīng)遺傳算法
自適應(yīng)遺傳算法的關(guān)鍵在于算法運(yùn)行過(guò)程中,會(huì)針對(duì)每個(gè)染色體的適應(yīng)值匹配專屬的交叉概率與變異概率。對(duì)于適應(yīng)值較高的個(gè)體,采用較低的交叉-變異概率組合,使其被保留進(jìn)入下一代的概率加大;對(duì)于適應(yīng)值較低的個(gè)體,則采用較高的交叉-變異概率組合,使其被淘汰的概率增加,具體過(guò)程如圖6所示。
Pc為交叉概率;Pm為變異概率;F為要交叉的兩個(gè)個(gè)體中交大的適應(yīng)度值;k1、k2、k3、k4為常數(shù)圖6 自適應(yīng)遺傳算法流程圖Fig.6 Flow chart of adaptive genetic algorithm
為驗(yàn)證模型和算法的有效性,采用如圖7所示的多式聯(lián)運(yùn)網(wǎng)絡(luò)進(jìn)行驗(yàn)證。節(jié)點(diǎn)1為運(yùn)輸起點(diǎn),節(jié)點(diǎn)25為運(yùn)輸終點(diǎn),各節(jié)點(diǎn)坐標(biāo)由Solomon benchmark C102列的前25個(gè)數(shù)據(jù)確定,將兩點(diǎn)間的歐幾里得距離擴(kuò)大10倍作為兩點(diǎn)間的運(yùn)輸距離。由于運(yùn)輸環(huán)境的不確定性,運(yùn)輸速度為不確定值,各運(yùn)輸方式的轉(zhuǎn)運(yùn)時(shí)間、運(yùn)輸速度和班期如表2和表3所示。假設(shè)現(xiàn)需要將一批應(yīng)急救援物資于起點(diǎn)1運(yùn)出,求從節(jié)點(diǎn)1~節(jié)點(diǎn)25總運(yùn)輸時(shí)間最少的魯棒運(yùn)輸方案。
圖7 多式聯(lián)運(yùn)網(wǎng)絡(luò)Fig.7 Multimodal transport network
表2 不同運(yùn)輸方式的轉(zhuǎn)運(yùn)時(shí)間
表3 各運(yùn)輸方式的運(yùn)輸速度及班期
采用MATLAB R2017a編程實(shí)現(xiàn)算法。設(shè)置種群規(guī)模為70,遺傳代數(shù)為50。使交叉概率為0.9、0.8、0.7、0.6、0.5,變異概率為0.05、0.04、0.03、0.02、0.01兩兩組合計(jì)算,兩種算法在不同的交叉-變異概率組合下連續(xù)運(yùn)行10次,計(jì)算得到均值、最優(yōu)值、運(yùn)行時(shí)間等結(jié)果如表4、表5所示。
表4 大變異遺傳算法實(shí)驗(yàn)結(jié)果
表5 自適應(yīng)遺傳算法實(shí)驗(yàn)結(jié)果
下面根據(jù)兩種遺傳算法所得到的結(jié)果確定本文中具體的求解算法以及合適的概率組合。
3.2.1 求解算法以及概率組合的確定
(1)最優(yōu)解方面。如圖8所示,兩種算法在不同的概率組合下連續(xù)運(yùn)行10次找到的最優(yōu)解均為550,說(shuō)明兩種算法求解得到的應(yīng)急物資調(diào)撥方案所消耗的總運(yùn)輸時(shí)間均為550 min,求解效果都相對(duì)較好。
圖8 不同交叉-變異概率下兩種算法的最優(yōu)解Fig.8 Optimal solutions of two algorithms under different crossover mutation probabilities
(2)初始解均值方面。如圖9所示,每種算法在25種不同的交叉-變異概率組合下,連續(xù)運(yùn)行10次,每次運(yùn)行的種群規(guī)模為70,一共會(huì)有17 500個(gè)初始解。分別運(yùn)行兩種算法,則一共會(huì)有35 000個(gè)初始解。但是,這35 000個(gè)初始解所求得的平均初始解均未超過(guò)760,而最優(yōu)解為550,說(shuō)明兩種算法所產(chǎn)生的初始解均為連通路。
圖9 兩種算法的平均初始解Fig.9 The average initial solution of two algorithms
(3)運(yùn)行時(shí)間方面。如圖10可知,不管變異概率與交叉概率如何組合,在相同的概率組合下,大變異遺傳算法的運(yùn)行時(shí)間總會(huì)低于自適應(yīng)遺傳算法。由前文可知,兩種算法生成的初始解均為連通路,而且求解得到的應(yīng)急物資運(yùn)輸時(shí)間總是相同的,說(shuō)明大變異遺傳算法求解更快更高效。且當(dāng)Pc=0.5、Pm=0.02時(shí),大變異遺傳算法運(yùn)行時(shí)間最短。
圖10 兩種算法在不同交叉-變異概率組合下的平均運(yùn)行時(shí)間Fig.10 The average running time of two algorithms under different combination of crossover mutation probability
3.2.2 運(yùn)輸方案的確定
運(yùn)用大變異遺傳算法,在Pc=0.5、Pm=0.02下對(duì)算例進(jìn)行求解,得到結(jié)果如圖11所示。
圖11 迭代圖Fig.11 Iterative graph
如圖11所示,大變異遺傳算法存在“階梯狀”的迭代過(guò)程,表明其在運(yùn)行過(guò)程中跳出了局部最優(yōu)解,進(jìn)行了更大范圍的搜索。所需的運(yùn)輸總時(shí)間為550 min,運(yùn)輸方案如表6、圖12所示。
表6 運(yùn)輸方案
圖12 運(yùn)輸方案示意圖Fig.12 Schematic diagram of transportation scheme
自然災(zāi)害發(fā)生后,對(duì)于應(yīng)急物資的輸送問(wèn)題引起了運(yùn)輸領(lǐng)域?qū)<遗c學(xué)者的廣泛關(guān)注。因?yàn)樵诰仍镔Y運(yùn)輸途中,存在各種不確定因素的影響,鑒于此,研究不確定環(huán)境下的應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化問(wèn)題,得到如下結(jié)論。
(1)將快速、有效地組合應(yīng)急物資多式聯(lián)運(yùn)作為出發(fā)點(diǎn),考慮到運(yùn)輸途中各種不確定情況對(duì)于運(yùn)輸結(jié)果的擾動(dòng)以及各運(yùn)輸方式的發(fā)班時(shí)刻限制,運(yùn)用魯棒優(yōu)化方法,建立了不確定環(huán)境下帶班期限制的應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化模型,并設(shè)計(jì)了大變異遺傳算法和自適應(yīng)遺傳算法對(duì)模型進(jìn)行了求解,求解結(jié)果較好。
(2)通過(guò)對(duì)已有實(shí)例進(jìn)行修改,將大變異遺傳算法以及自適應(yīng)遺傳算法的求解結(jié)果進(jìn)行了對(duì)比分析,最終確定采用大變異遺傳算法在Pc=0.5、Pm=0.02的概率組合下進(jìn)行算例求解,求解結(jié)果可以為應(yīng)急物資運(yùn)輸決策者提供一定的參考。