劉 松， 郭 敏， 樂美龍， 彭 勇

(1.南京航空航天大學(xué)民航學(xué)院， 南京 211106； 2.重慶交通大學(xué)交通運(yùn)輸學(xué)院， 重慶 400074； 3.山地城市交通系統(tǒng)與安全重慶市重點(diǎn)實(shí)驗(yàn)室， 重慶 400074)

近幾十年來，地震、洪水、臺(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)化問題受到了學(xué)者的廣泛關(guān)注，這些研究主要集中在增加運(yùn)輸模型約束條件或算法設(shè)計(jì)方面。祝新等[1]考慮到路況對(duì)于傳統(tǒng)醫(yī)療冷鏈物流配送模型的影響，建立了以綜合成本為目標(biāo)的配送模型。陳疇鏞等[2]研究了在時(shí)間窗及配送公平性影響下的運(yùn)輸路徑規(guī)劃問題。何婷等[3]研究了疫情背景下生鮮電商企業(yè)的車輛路徑優(yōu)化問題。Jiang等[4]建立了將多項(xiàng)目包裝與車輛路徑和分批配送相結(jié)合的優(yōu)化模型。劉松等[5]研究了碳排放限制下冷藏集裝箱的路徑優(yōu)化問題。陳汨梨等[6]研究了不確定條件下多式聯(lián)運(yùn)路徑優(yōu)化問題。

在應(yīng)急物資運(yùn)輸方面，許多學(xué)者在研究確定環(huán)境下的多目標(biāo)優(yōu)化及物資調(diào)度與選址問題。宋英華等[7]建立了雙目標(biāo)應(yīng)急物資配送車輛路徑問題整數(shù)規(guī)劃模型，并驗(yàn)證了模型的有效性。薛星群等[8]研究了通行約束和運(yùn)力限制條件下的應(yīng)急物資聯(lián)合調(diào)度問題。劉倩宇[9]將選址問題與路徑優(yōu)化問題進(jìn)行了結(jié)合，考慮到備選配送中心的優(yōu)先級(jí)，對(duì)應(yīng)急物流的選址——路徑優(yōu)化進(jìn)行了研究。呂偉等[10]研究了應(yīng)急物資需求緊迫程度差異下的物資配送路徑優(yōu)化問題。劉晉等[11]運(yùn)用自適應(yīng)遺傳算法，對(duì)應(yīng)急物資儲(chǔ)備庫選址及調(diào)度問題進(jìn)行了研究。

隨著研究的深入，有學(xué)者注意到確定環(huán)境下給出的應(yīng)急物資運(yùn)輸方案難以滿足實(shí)際中的應(yīng)急物資運(yùn)輸要求，對(duì)不確定環(huán)境下的應(yīng)急物資運(yùn)輸開展了研究。張夢玲等[12]研究了不確定需求下考慮供應(yīng)商參與機(jī)制的應(yīng)急物資配置問題。Wang等[13]提出了一種海運(yùn)不確定性條件下的多式聯(lián)運(yùn)綜合調(diào)度模型。王妍妍等[14]研究了模糊信息下多種類應(yīng)急物資多周期分配優(yōu)化問題。葛顯龍等[15]針對(duì)動(dòng)態(tài)事件對(duì)配送過程的干擾問題，研究了多品類共同配送車輛路徑優(yōu)化問題。但是已有的研究大多假設(shè)已知部分參數(shù)的概率分布，而在實(shí)際運(yùn)輸作業(yè)過程中，尤其是發(fā)生突發(fā)事件后的應(yīng)急物資運(yùn)輸，這些參數(shù)卻因缺少歷史數(shù)據(jù)而無法知道其概率分布情況，而更應(yīng)該尋求魯棒運(yùn)輸路徑。然而，單一運(yùn)輸方式下的魯棒路徑優(yōu)化問題已經(jīng)被證明是NP-Hard(nondeterministic polynomial-hard)問題[16]，對(duì)該類問題的研究一直以來都是學(xué)者研究的熱點(diǎn)。孫秀巧等[17]運(yùn)用改進(jìn)遺傳退火算法，對(duì)高速公路巡邏車輛路徑優(yōu)化調(diào)度問題進(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)化問題需要同時(shí)考慮不同運(yùn)輸方式之間的轉(zhuǎn)運(yùn)以及鐵路、水路等的發(fā)班時(shí)刻限制等，對(duì)其求解相較于單一運(yùn)輸方式下的路徑優(yōu)化問題更為困難，需要針對(duì)模型的獨(dú)特性設(shè)計(jì)專門的算法。

綜上所述，當(dāng)前中外學(xué)者對(duì)確定環(huán)境下的路徑優(yōu)化問題研究較多，而不確定環(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 問題描述及建模

1.1 問題描述

在如圖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 模型假設(shè)與變量

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)過一次，即運(yùn)輸途中不出現(xiàn)封閉回路。

(5)運(yùn)輸途中除了由于班期限制導(dǎo)致等待外，其他地方無需等待。

1.2.2 模型參數(shù)及變量

本文模型參數(shù)及變量如表1所示。

表1 模型參數(shù)

1.3 目標(biāo)函數(shù)及運(yùn)輸條件

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)

2 問題求解

由于傳統(tǒng)的最短路算法不能求解應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化模型，現(xiàn)設(shè)計(jì)遺傳算法進(jìn)行求解。

2.1 編碼及初始種群的生成

2.1.1 編碼

由于多式聯(lián)運(yùn)運(yùn)輸方式，運(yùn)輸路線都未知，故采用可變長的路徑編碼方法。具體編碼過程如下。

(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)值，即路徑長度。

(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)。

2.2 適應(yīng)度評(píng)價(jià)與約束條件判斷

因本文中以時(shí)間成本最小為目標(biāo)，而遺傳算法的適應(yīng)值越大越好，故采用目標(biāo)函數(shù)的倒數(shù)為適應(yīng)值函數(shù)，即

f=1/Z

(10)

2.3 遺傳操作

2.3.1 選擇

采用輪盤賭選擇方法。

2.3.2 交叉

對(duì)第一段染色體采用兩點(diǎn)交叉的遺傳方式，并對(duì)于交叉后可能產(chǎn)生的非法染色體通過Floyd法進(jìn)行修復(fù)，具體過程如下。

(1)若第一個(gè)交叉節(jié)點(diǎn)直接與起點(diǎn)相連，且與起點(diǎn)之間沒有通路，則可通過Floyd法找到兩點(diǎn)間的一條連通路。同樣的方法也可處理第二個(gè)交叉節(jié)點(diǎn)與終點(diǎn)相連時(shí)的阻斷情況。

(2)若兩個(gè)交叉點(diǎn)皆在路徑中間位置，則任意交叉點(diǎn)和相鄰節(jié)點(diǎn)無法連通時(shí)，都可以通過找到與之相鄰的上一節(jié)點(diǎn)之間的連通路徑進(jìn)行方案改進(jìn)。若無連通路徑，則繼續(xù)探查再上一節(jié)點(diǎn)。如圖3所示:染色體U1與染色體U2交叉后得到的染色體U3為非法染色體。因節(jié)點(diǎn)2和節(jié)點(diǎn)4之間存在連通路，則無需繼續(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ù)編碼過程同上。如圖4所示，若有染色體1-2-6-8-2-3-1，現(xiàn)將第二個(gè)基因位上的基因2去掉，因?yàn)楣?jié)點(diǎn)1和節(jié)點(diǎn)6之間無連通路，所以可利用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

2.4 算法說明

在上述理論基礎(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)行遺傳操作，具體過程如圖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)行過程中，會(huì)針對(duì)每個(gè)染色體的適應(yīng)值匹配專屬的交叉概率與變異概率。對(duì)于適應(yīng)值較高的個(gè)體，采用較低的交叉-變異概率組合，使其被保留進(jìn)入下一代的概率加大；對(duì)于適應(yīng)值較低的個(gè)體，則采用較高的交叉-變異概率組合，使其被淘汰的概率增加，具體過程如圖6所示。

Pc為交叉概率；Pm為變異概率；F為要交叉的兩個(gè)個(gè)體中交大的適應(yīng)度值；k1、k2、k3、k4為常數(shù)圖6 自適應(yīng)遺傳算法流程圖Fig.6 Flow chart of adaptive genetic algorithm

3 算例分析

3.1 算例設(shè)計(jì)

為驗(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)輸速度及班期

3.2 結(jié)果分析

采用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，說明兩種算法求解得到的應(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è)初始解所求得的平均初始解均未超過760，而最優(yōu)解為550，說明兩種算法所產(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í)間總是相同的，說明大變異遺傳算法求解更快更高效。且當(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所示，大變異遺傳算法存在“階梯狀”的迭代過程，表明其在運(yùn)行過程中跳出了局部最優(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

4 結(jié)論

自然災(zāi)害發(fā)生后，對(duì)于應(yīng)急物資的輸送問題引起了運(yùn)輸領(lǐng)域?qū)＜遗c學(xué)者的廣泛關(guān)注。因?yàn)樵诰仍镔Y運(yùn)輸途中，存在各種不確定因素的影響，鑒于此，研究不確定環(huán)境下的應(yīng)急物資多式聯(lián)運(yùn)魯棒路徑優(yōu)化問題，得到如下結(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)通過對(duì)已有實(shí)例進(jìn)行修改，將大變異遺傳算法以及自適應(yīng)遺傳算法的求解結(jié)果進(jìn)行了對(duì)比分析，最終確定采用大變異遺傳算法在Pc=0.5、Pm=0.02的概率組合下進(jìn)行算例求解，求解結(jié)果可以為應(yīng)急物資運(yùn)輸決策者提供一定的參考。