基于運(yùn)輸安全的自適應(yīng)多目標(biāo)路徑優(yōu)化算法

吳耕銳，郭三學(xué)，吳虎勝，薄 鳥

(1.武警工程大學(xué) 裝備管理與保障學(xué)院， 西安 710086； 2.武警警官學(xué)院 基礎(chǔ)部， 成都 610213；3.武警警官學(xué)院 信息通信系, 成都 610213)

軍事運(yùn)輸包含人員和物資(如武器裝備、后勤物資等其他物資)運(yùn)輸，運(yùn)輸是從物資倉(cāng)庫(kù)到部隊(duì)駐點(diǎn)的過(guò)程。處理大量重要物資的日常運(yùn)輸通常是由后勤保障部門完成。盡管運(yùn)輸任務(wù)是必要的，但運(yùn)輸安全也同樣重要，尤其在軍事運(yùn)輸中，由于運(yùn)輸?shù)奈镔Y特別重要，更容易成為攻擊目標(biāo)，因此對(duì)運(yùn)輸路徑安全性有特殊要求。

每次任務(wù)中，后勤部門收到部隊(duì)駐點(diǎn)的需求信息。需求信息主要包括運(yùn)輸物資(人員)數(shù)量、到達(dá)目的地規(guī)定時(shí)間和裝卸物資的OD位置信息，不同裝卸位置會(huì)出現(xiàn)不同組合。例如，從一個(gè)中心節(jié)點(diǎn)裝載軍用物資并運(yùn)送到另外一個(gè)軍事駐點(diǎn)。

該問(wèn)題屬于有容量限制和時(shí)間窗要求的車輛路徑問(wèn)題，問(wèn)題中包含了運(yùn)輸安全問(wèn)題。相關(guān)的路徑優(yōu)化問(wèn)題已在一些文獻(xiàn)中有研究。比如王坤等[1]在彈藥運(yùn)輸路徑選擇上進(jìn)行了多目標(biāo)優(yōu)化，提升了彈藥運(yùn)輸效率。黃軍等[2]分析了軍用油料運(yùn)輸安全風(fēng)險(xiǎn)影響因素，提出了安全風(fēng)險(xiǎn)的分析和識(shí)別方法。張夢(mèng)得等[3]用弗洛伊德與蟻群算法對(duì)裝備物資運(yùn)輸路徑進(jìn)行優(yōu)化，簡(jiǎn)化了計(jì)算，解決了道路被敵人破壞時(shí)路徑優(yōu)化問(wèn)題。張曉楠等[4]以運(yùn)輸成本和時(shí)間成本最小化目標(biāo)，建立了預(yù)優(yōu)化模型，并在實(shí)時(shí)調(diào)整階段提出了基于調(diào)整成本期望的實(shí)時(shí)調(diào)整策略，使模糊需求車輛問(wèn)題更貼近實(shí)際。陳希瓊等[5]建立了同時(shí)考慮車輛容量和距離約束的雙目標(biāo)模型，構(gòu)造了具有貪婪轉(zhuǎn)移準(zhǔn)則的多目標(biāo)蟻群算法，實(shí)現(xiàn)了運(yùn)輸成本和路徑間最大長(zhǎng)度差最小化的目的。張萌等[6]在危險(xiǎn)品運(yùn)輸路徑研究上，建立了事故后果最小及運(yùn)輸成本最小的雙目標(biāo)，設(shè)計(jì)了處理大規(guī)模問(wèn)題多項(xiàng)式，利于規(guī)避運(yùn)輸中重大事故問(wèn)題。Y.Kang等[7]對(duì)危險(xiǎn)品運(yùn)輸?shù)墓揭蛩靥岢隽寺窂揭?guī)劃模型。

提高安全性的一種辦法就是找到一條遠(yuǎn)離人群中心的路徑[8]，另一種辦法就是根據(jù)不同的非相似定義生成非相似安全路徑。

從犯罪學(xué)研究運(yùn)輸路徑安全性問(wèn)題可知，恐怖分子會(huì)搜集攻擊目標(biāo)的相關(guān)信息，還會(huì)詳細(xì)研究運(yùn)輸車隊(duì)的路線等，增加車輛路徑和行車計(jì)劃變化性可以降低車隊(duì)被攻擊概率。周邊社會(huì)經(jīng)濟(jì)人口密集地區(qū)易成為攻擊目標(biāo)[9]。例如，加拿大的一個(gè)研究發(fā)現(xiàn)，社會(huì)經(jīng)濟(jì)落后都與犯罪有很大關(guān)聯(lián)，特別是突襲和搶劫[10]。

以上研究雖然考慮了運(yùn)輸路徑的安全因素，但從本質(zhì)上去研究路徑問(wèn)題，即對(duì)路徑施加變化，降低路徑本身可預(yù)測(cè)性的研究還不多，而針對(duì)路徑易被攻擊問(wèn)題，以解決提升軍事運(yùn)輸路徑安全性的研究非常少。從以下因素考慮：按照相同的或者相似路徑運(yùn)輸，車隊(duì)容易被攻擊；運(yùn)輸路徑通過(guò)社會(huì)經(jīng)濟(jì)發(fā)達(dá)和人口密集地區(qū)，運(yùn)輸車隊(duì)容易遭遇攻擊。提出了一種綜合安全風(fēng)險(xiǎn)度量，將綜合安全風(fēng)險(xiǎn)度量作為自適應(yīng)多目標(biāo)隨機(jī)路徑選擇算法的一部分，用于求解運(yùn)輸路徑。算法是用k最短路徑和IPM算法在每對(duì)OD節(jié)點(diǎn)上形成一系列非相似路徑，根據(jù)車隊(duì)歷史運(yùn)輸路線，在之前路徑中隨機(jī)選擇出部分路徑，并把運(yùn)輸距離和運(yùn)輸安全值轉(zhuǎn)化成權(quán)重和，將成本矩陣作為輸入，在ALNS啟發(fā)式基礎(chǔ)上增加了自適應(yīng)隨機(jī)選擇算法和時(shí)間調(diào)整算法來(lái)求解運(yùn)輸路徑，進(jìn)一步提高運(yùn)輸路徑的安全性。其中，不同時(shí)間運(yùn)輸路徑的變化示意圖如圖1。

圖1 路徑變化示意圖

1 問(wèn)題描述

令G=(V,S)為一個(gè)有向圖，V為頂點(diǎn)，RS為弧?；?a,b)的長(zhǎng)度為lab，頂點(diǎn)集由一個(gè)中心節(jié)點(diǎn)和需求點(diǎn)構(gòu)成，即vo∈V和vn?V。算法就是在頂點(diǎn)集V的OD節(jié)點(diǎn)對(duì)之間生成一系列的非相似路徑，并交替使用這些路徑來(lái)解決運(yùn)輸路徑問(wèn)題。因此，令Dijk為路徑k中頂點(diǎn)i到頂點(diǎn)j的距離，Nid為第i個(gè)節(jié)點(diǎn)在第d天的需求，Z為車隊(duì)A中每輛車的載重量，目標(biāo)函數(shù)是使運(yùn)輸距離最短和運(yùn)輸安全性最高。

1.1 綜合安全風(fēng)險(xiǎn)模型

用地區(qū)的社會(huì)經(jīng)濟(jì)和人口密集條件值來(lái)計(jì)算頂點(diǎn)和弧的安全風(fēng)險(xiǎn)，同時(shí)將地區(qū)分為子地區(qū)或者周邊地區(qū)，其中每個(gè)路徑周邊人口用低、中、高三種基于地區(qū)收入、教育水平的策略來(lái)計(jì)算，每種策略的人口權(quán)重值與其相應(yīng)的安全風(fēng)險(xiǎn)相關(guān)。將頂點(diǎn)a和頂點(diǎn)b的弧的RS值定義如下：

(1)

將頂點(diǎn)i和頂點(diǎn)j間的路徑集Aijk中第k條路徑的RS值定義如下：

(2)

數(shù)值包含了路徑Aijk中每條弧的權(quán)重，弧越長(zhǎng)，車隊(duì)在弧上的行駛時(shí)間就越長(zhǎng)，該路徑就越不安全。這里假設(shè)路徑周邊地區(qū)的RS值固定不變，RU值會(huì)隨著弧的使用頻率變化而變化。

計(jì)算RU值時(shí)，每天都會(huì)計(jì)算相關(guān)路徑弧的使用頻率。RU值更新規(guī)則在一定程度上和指數(shù)平滑法相似。跟蹤Ued值，即第d天所有路徑中弧e所用的次數(shù)，是為了避免后續(xù)幾天連續(xù)使用已用過(guò)的弧來(lái)使路徑不可預(yù)測(cè)。因此，定義第d天弧e的預(yù)測(cè)計(jì)算公式如下：

Xed=α×Ued+(1-α)Xed

(3)

其中0<α<1為最近使用最頻繁的弧的平滑因子。這表明Xed的值越小，運(yùn)輸安全性就越高。在一些初始化后，Xed出現(xiàn)較大值時(shí)需要對(duì)其進(jìn)行調(diào)整。

(4)

其中，p是d天所有Xed值的平均值。

任意d天路徑Aijk的RU值計(jì)算公式如下：

(5)

1.2 目標(biāo)函數(shù)

將RU值和RS值合成一個(gè)綜合安全風(fēng)險(xiǎn)度量值。令0≤Ka≤1和0≤Kb≤1代表兩種安全風(fēng)險(xiǎn)的權(quán)重，將安全風(fēng)險(xiǎn)和每天運(yùn)輸距離成本優(yōu)化相關(guān)聯(lián)；令0≤Kc≤1。為第3部分的權(quán)重；令0≤Kd≤1為兩種安全風(fēng)險(xiǎn)度量與Kd相關(guān)的統(tǒng)一權(quán)重，其中Kc+Kd=1。第d天路徑Aijkd綜合安全風(fēng)險(xiǎn)值計(jì)算公式如下：

(6)

第d天路徑Aijkd成本計(jì)算公式如下：

Cijkd=Kc×Tc×dijk+Kd×Rijkd

(7)

其中，Rijkd表示綜合安全風(fēng)險(xiǎn)值，Ta、Tb和Tc是平衡3種成本函數(shù)的縮放系數(shù)，使用縮放系數(shù)的主要目的就是平衡3種成本函數(shù)的影響。當(dāng)Ta=1時(shí)，縮放系數(shù)就定義為綜合成本值的平均值，Ta等于被RU值分割的RS值的平均值。Tc表示被距離分割的綜合安全風(fēng)險(xiǎn)值的平均值。因?yàn)镽U值每天都發(fā)生變化，所以要重新計(jì)算縮放系數(shù)。

用式(7)計(jì)算安全性最高的路徑時(shí)，用自適應(yīng)隨機(jī)算法選出OD節(jié)點(diǎn)對(duì)(i，j)的特殊路徑，并將這個(gè)路徑的成本作為路徑算法成本矩陣的輸入。

2 求解算法

求解算法的描述如圖2所示，提出了一個(gè)帶成本矩陣的啟發(fā)式算法，可以在短時(shí)間內(nèi)求解出路徑近似最優(yōu)解。在預(yù)處理部分，每個(gè)節(jié)點(diǎn)對(duì)間會(huì)生成一個(gè)非相似數(shù)和最短路徑；在每天開始時(shí)，根據(jù)前一天路徑情況來(lái)更新RU值，在概率與它們距離和風(fēng)險(xiǎn)值成正比的路徑中選擇一條路徑。

圖2 算法流程框圖

2.1 生成非相似路徑

在每對(duì)節(jié)點(diǎn)(i，j)間生成替換Aij的非相似最短路徑。一般來(lái)說(shuō)，一系列短路徑就可能包含很多共同的弧，弧分離的路徑距離就可能很遠(yuǎn)。根據(jù)運(yùn)輸距離和非相似標(biāo)準(zhǔn)來(lái)選擇路徑，這個(gè)算法就成了用來(lái)求解雙重目標(biāo)路徑非相似性的有效近似邊界。步驟如下：

在每個(gè)節(jié)點(diǎn)對(duì)之間，用k最短路徑算法生成15條候選路徑，用IPM算法生成另外15條候選路徑，從中選出10條無(wú)條件路徑。算法首先隨機(jī)消除高于非相似閾值的路徑，然后迭代交換路徑來(lái)改進(jìn)路徑的平均距離和非相似性，當(dāng)達(dá)到最大迭代次數(shù)時(shí)停止。

通過(guò)所有路徑中的配對(duì)非相似性來(lái)計(jì)算一條路徑的平均非相似性。如果兩條路徑非相似，則該條路徑的所有節(jié)點(diǎn)都遠(yuǎn)離其他路徑的所有節(jié)點(diǎn)。為了測(cè)量路徑1和路徑2之間的非相似性，就要計(jì)算路徑1到路徑2的平均非相似性和路徑2到路徑1的平均非相似性，即路徑1包含每個(gè)節(jié)點(diǎn)到路徑2所有節(jié)點(diǎn)最短距離之和。路徑2到路徑1的非相似性計(jì)算也是如此。

求解算法的輸入包含距離、RS值和這些路徑的弧。通過(guò)該算法，可以求得平均距離短且非相似性高的路徑集合。當(dāng)路徑生成之后，計(jì)算路徑的RS成本。這些都是預(yù)處理部分的靜態(tài)數(shù)據(jù)。

2.2 路徑優(yōu)化

應(yīng)用路徑優(yōu)化算法，即算法1，確定每天的運(yùn)輸路徑。在預(yù)處理階段，應(yīng)用成本矩陣生成第一天最短路徑，對(duì)算法進(jìn)行初始化；將成本矩陣和節(jié)點(diǎn)需求數(shù)據(jù)作為ALNS啟發(fā)算法的輸入，用于求解某一天的路徑。在求得解后，算法會(huì)記錄路徑和所使用的弧，以更新路徑中弧的使用頻率，根據(jù)更新的頻率值對(duì)RU值重新進(jìn)行計(jì)算。為了便于規(guī)范更新所有路徑的綜合安全風(fēng)險(xiǎn)，算法將RU值規(guī)范在0～500，用于計(jì)算所有路徑的綜合安全風(fēng)險(xiǎn)值。

算法1路徑優(yōu)化算法步驟可總結(jié)如下：

第1步：初始化；

第2步：對(duì)于每個(gè)(i，j)節(jié)點(diǎn)：

1) 生成路徑集AijAij={Aij1,Aij2,…,Aijk}，Aijk的距離為Dijk；

3) 選擇節(jié)點(diǎn)(i，j)間最短路徑作為初始路徑。

第3步：當(dāng)t=1，Nd時(shí)，進(jìn)行循環(huán)：

1) 構(gòu)建選擇路徑的成本矩陣；

2) 用ALNS算法求解路徑問(wèn)題，得到每輛車的路徑總距離和安全風(fēng)險(xiǎn)值；

3) 如果t

① 記錄ALNS解中使用的路徑和??；

② 更新所有弧的使用頻率；

③ 計(jì)算所有路徑的RU值；

④ 更新所有路徑的綜合安全風(fēng)險(xiǎn)值；

⑤ 應(yīng)用自適應(yīng)隨機(jī)選擇算法來(lái)選擇OD節(jié)點(diǎn)對(duì)間的新路徑。

2.2.1自適應(yīng)隨機(jī)路徑選擇算法

算法用于選擇下一天所用路徑。對(duì)于每個(gè)(i，j)節(jié)點(diǎn)對(duì)，算法為Aij中路徑設(shè)置了一個(gè)選擇概率，該概率與路徑的成本成反比，路徑的距離和安全風(fēng)險(xiǎn)就歸并到?jīng)Q策者考慮的權(quán)重當(dāng)中，根據(jù)前一天的RU值來(lái)調(diào)整選擇概率。因此優(yōu)化過(guò)程可以避免連續(xù)訪問(wèn)順序節(jié)點(diǎn)。

該過(guò)程會(huì)隨機(jī)選擇路徑，生成多樣化路徑集。每天生成的路徑不一樣是因?yàn)椋涸L問(wèn)節(jié)點(diǎn)需求不同；不同的成本矩陣值，生成的訪問(wèn)節(jié)點(diǎn)順序不同；車輛隨機(jī)抵達(dá)時(shí)間有調(diào)整。具體算法步驟可總結(jié)如下：

第1步：初始化；

2.2.2路徑算法

這里使用ALNS算法，算法開始時(shí)有一個(gè)初始解，每一次迭代執(zhí)行破壞和修復(fù)機(jī)制后，生成一個(gè)新的更好的解，在迭代一定次數(shù)后得到一個(gè)可能的最優(yōu)解。

2.3 抵達(dá)時(shí)間調(diào)整算法

隨機(jī)性和安全風(fēng)險(xiǎn)效應(yīng)能提供一定的抵達(dá)時(shí)間多樣性，為了增加同樣需求節(jié)點(diǎn)抵達(dá)時(shí)間的變化性，使用調(diào)整算法來(lái)靈活分配與時(shí)間窗相關(guān)的節(jié)點(diǎn)訪問(wèn)時(shí)間。在時(shí)間窗上界和車輛抵達(dá)節(jié)點(diǎn)時(shí)間之間定義了一個(gè)松弛時(shí)間。調(diào)整算法是路徑算法后處理部分的輸出，每輛車運(yùn)行獨(dú)立調(diào)整算法。調(diào)整算法沒(méi)有改變路徑的順序，所以路徑的總距離和安全風(fēng)險(xiǎn)不變，只是在當(dāng)前抵達(dá)時(shí)間上增加了調(diào)整時(shí)間。調(diào)整時(shí)間是插入在兩個(gè)連續(xù)需求節(jié)點(diǎn)抵達(dá)時(shí)間之間的時(shí)間。在額外的時(shí)間間隔里，車輛可以停在兩個(gè)需求節(jié)點(diǎn)中任意一個(gè)節(jié)點(diǎn)上，也可以?？吭趦蓚€(gè)需求點(diǎn)間的一個(gè)安全位置。分配多個(gè)?？奎c(diǎn)的松弛時(shí)間可以降低車隊(duì)?？吭趩为?dú)一個(gè)位置的安全風(fēng)險(xiǎn)。將等待時(shí)間隨機(jī)分割成不同位置的較短的等待時(shí)間，可使路徑變得不可預(yù)測(cè)，從而提高路徑的安全性。算法每一次迭代中，找到最低松弛時(shí)間，隨機(jī)分成時(shí)間小塊，并插入抵達(dá)時(shí)間子集當(dāng)中。具體算法3步驟可總結(jié)如下：

第1步：初始化；

第2步：記錄當(dāng)前節(jié)點(diǎn)為節(jié)點(diǎn)O；

第3步：當(dāng)當(dāng)前節(jié)點(diǎn)不等于最后訪問(wèn)節(jié)點(diǎn)時(shí)，進(jìn)行循環(huán)：計(jì)算路徑A當(dāng)前節(jié)點(diǎn)到最后一個(gè)節(jié)點(diǎn)的松弛時(shí)間；令當(dāng)前節(jié)點(diǎn)最小松弛時(shí)間為tmin；在當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)間隨機(jī)分配最小松弛時(shí)間tmin；增加隨機(jī)數(shù)作為調(diào)整時(shí)間，修改抵達(dá)時(shí)間。

迭代時(shí)，首先是計(jì)算所有需求點(diǎn)的松弛時(shí)間。當(dāng)車輛在一個(gè)位置停留一個(gè)較長(zhǎng)的松弛時(shí)間，其安全性較低，如果將松弛時(shí)間隨機(jī)分成兩個(gè)部分，就變成了兩個(gè)不同地點(diǎn)的較短時(shí)間的停留，其路徑安全性顯然比較高，路徑不可預(yù)測(cè)性得到加強(qiáng)，不同地點(diǎn)中車輛的等待安全性也就更高了。因此要將松弛時(shí)間被隨機(jī)分成兩部分，用一個(gè)隨機(jī)數(shù)來(lái)確定被選需求點(diǎn)的松弛時(shí)間，這里稱之為剩余時(shí)間，隨機(jī)數(shù)代表路徑隨機(jī)性，以提高安全性。其中節(jié)點(diǎn)1的松弛時(shí)間最短是5.3。其次對(duì)于每個(gè)被訪問(wèn)節(jié)點(diǎn)來(lái)說(shuō)，生成的隨機(jī)數(shù)除去剩余時(shí)間后，將增加到抵達(dá)時(shí)間中作為時(shí)間調(diào)整。最后在每次迭代中添加和更新時(shí)間。第一次迭代后，下一個(gè)最小松弛時(shí)間為7.4，這個(gè)時(shí)間被分配到節(jié)點(diǎn)2和節(jié)點(diǎn)3。調(diào)整時(shí)間分配算法示意圖如圖3。

圖3 調(diào)整算法示意圖

用隨機(jī)數(shù)來(lái)確定被選需求點(diǎn)的松弛時(shí)間的一部分，是為了增加路徑的隨機(jī)性，即車輛在不同地點(diǎn)的等待時(shí)間變成隨機(jī)，讓其無(wú)法預(yù)測(cè)在某點(diǎn)的具體等待停留時(shí)間，當(dāng)然其隨機(jī)數(shù)也是有相應(yīng)時(shí)間取值范圍的，不可超過(guò)時(shí)間上界要求，因此這里隨機(jī)數(shù)來(lái)確定松弛時(shí)間是具有準(zhǔn)確性的。

調(diào)整算法在初始可行解基礎(chǔ)上進(jìn)行，只是增加了抵達(dá)時(shí)間，沒(méi)有違反時(shí)間窗可行性，因此不用考慮時(shí)間窗的下界。在這里雖然沒(méi)有考慮時(shí)間窗下界，但實(shí)際工程應(yīng)用中時(shí)間窗下界的影響是存在的，會(huì)出現(xiàn)個(gè)別情況時(shí)間下界數(shù)值較大時(shí)，會(huì)引起車輛服務(wù)質(zhì)量時(shí)效性下降，影響整體的運(yùn)輸旅行時(shí)間，也可能造成一定程度的燃料浪費(fèi)。

3 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證算法對(duì)路徑安全性、使用路徑和訪問(wèn)節(jié)點(diǎn)順序變化的影響，用兩個(gè)不同數(shù)據(jù)集測(cè)試，第一個(gè)數(shù)據(jù)集中，對(duì)單獨(dú)一天的需求求解，并對(duì)同樣需求10 d的數(shù)據(jù)進(jìn)行求解；第二個(gè)數(shù)據(jù)集中，對(duì)連續(xù)30 d求數(shù)據(jù)求解。數(shù)據(jù)集選擇連續(xù)10 d和30 d，一方面是使數(shù)據(jù)具有連續(xù)性而不是單一隨機(jī)的，另一方面取整，且取10的倍數(shù)，是為了便于計(jì)算。通過(guò)改變運(yùn)輸距離和安全風(fēng)險(xiǎn)目標(biāo)權(quán)重對(duì)5種條件下算法進(jìn)行測(cè)試：

條件1：安全性最高，不考慮距離(Kc=0,Kd=1)；

條件2：安全風(fēng)險(xiǎn)規(guī)避(Kc=0.25,Kd=0.75)；

條件3：安全中立態(tài)度 (Kc=0.5,Kd=0.5)；

條件4：愿意冒險(xiǎn)的態(tài)度(Kc=0.75,Kd=0.25)；

條件5：距離最短，不考慮安全性(Kc=1,Kd=0)。

實(shí)驗(yàn)可知，需求不變時(shí)路徑在不同天里的變化情況，算法有效。

運(yùn)輸安全值量化的思路如下：基于使用頻率的安全風(fēng)險(xiǎn)(RU)和考慮第k條路徑周邊的社會(huì)經(jīng)濟(jì)和人口情況RS值，用這兩個(gè)運(yùn)輸安全值來(lái)量化運(yùn)輸安全，一方面RU值增加時(shí)代表路徑使用重復(fù)的路徑頻率高，使用了的相同路徑概率高，其路徑不可預(yù)測(cè)性就會(huì)降低，即路徑安全性較低，相應(yīng)數(shù)值也就較大，相反當(dāng)其數(shù)值較小時(shí)，路徑重復(fù)使用頻率就降低，路徑變得不可預(yù)測(cè)，安全性就變高，因此用其值大小可衡量路徑安全性高低；另一方面，根據(jù)相關(guān)研究文獻(xiàn)結(jié)果可知，RS值大小也與路徑安全性高低相關(guān)，RS值大時(shí)，安全性降低，RS值小時(shí)，安全性就提高。

3.1 數(shù)據(jù)和實(shí)驗(yàn)環(huán)境

數(shù)據(jù)地點(diǎn)是中國(guó)北京。第一步應(yīng)用GIS軟件平臺(tái)ArcGIS 10.3生成道路網(wǎng)絡(luò)，初始化網(wǎng)絡(luò)圖如圖4所示，包含 9 627個(gè)節(jié)點(diǎn)和 18 645條弧。平臺(tái)中生成的相同節(jié)點(diǎn)和弧能夠被消除，以此降低求解時(shí)間。消除既沒(méi)有需求又不是中心節(jié)點(diǎn)的3種不同情況如圖5所示。

1) 節(jié)點(diǎn)有一條輸入和輸出弧，節(jié)點(diǎn)被消除，輸入和輸出弧合并成一條??；

2) 當(dāng)輸入弧的尾部和輸出弧的頭部相同時(shí)，節(jié)點(diǎn)被消除；

3) 節(jié)點(diǎn)有兩條輸入弧和兩條輸出弧，一條輸出弧同時(shí)是節(jié)點(diǎn)的出入弧時(shí)，節(jié)點(diǎn)被消除，與此相關(guān)的4條弧合并成兩條弧。

在消除節(jié)點(diǎn)后，節(jié)點(diǎn)數(shù)下降到1 865個(gè)，弧的數(shù)量下降到3 736條。盡管大部分節(jié)點(diǎn)是道路連接點(diǎn)，但生成和選擇的替換路徑的OD點(diǎn)數(shù)量會(huì)變得很大。算法預(yù)處理部分包含處理運(yùn)輸網(wǎng)絡(luò)和生成不同節(jié)點(diǎn)對(duì)之間的替換路徑，算法后半部分是在實(shí)驗(yàn)分析前進(jìn)行批量處理。

圖4 初始化道路網(wǎng)絡(luò)圖

圖5 節(jié)點(diǎn)減少的預(yù)處理過(guò)程

通過(guò)對(duì)100個(gè)不同需求節(jié)點(diǎn)進(jìn)行處理，可知不同節(jié)點(diǎn)位置越多，需求節(jié)點(diǎn)增加越多，計(jì)算量就越大。因此，額外的實(shí)驗(yàn)時(shí)間是可控的。

這里使用的是連續(xù)10 d和30 d北京駐軍某部的真實(shí)需求數(shù)據(jù)。一天內(nèi)需求節(jié)點(diǎn)的數(shù)量在50～150變化，需求值在0～6 000，包含15輛載重5 000 kg的軍用卡車，車速在40～60 km/h。實(shí)驗(yàn)環(huán)境是64位Intel(R) Core(TM)i7-4800MQ CPU 2.70 GHz和16 GB 內(nèi)存。

3.2 實(shí)驗(yàn)結(jié)果

首先，用算法求解連續(xù)10 d有相同需求數(shù)據(jù)的路徑解。5種不同距離和安全權(quán)重條件下的求解情況見表1。

表1 10 d路徑求解結(jié)果

從結(jié)果可知，優(yōu)化路徑時(shí)，只考慮距離最短，安全值就會(huì)很低，這個(gè)可以用RU值來(lái)衡量。因?yàn)槭惯\(yùn)輸距離最短也會(huì)降低RU值，所以RU值很大程度就成了安全風(fēng)險(xiǎn)值。

反過(guò)來(lái)，正如預(yù)期的一樣，短路徑會(huì)頻繁使用同一條弧。當(dāng)生成路徑時(shí)，只考慮使安全性最高，路徑距離就變得很長(zhǎng)。與條件5相比，條件1的路徑距離長(zhǎng)26%，安全性高47.7%?？芍繕?biāo)函數(shù)的安全風(fēng)險(xiǎn)權(quán)重增加時(shí)，路徑安全性就明顯提高。

在條件3下，當(dāng)決策者對(duì)運(yùn)輸距離和運(yùn)輸安全風(fēng)險(xiǎn)保持中立態(tài)度時(shí)，與條件5相比，其運(yùn)輸距離長(zhǎng)14.6%，安全性高38.7%。

分5種情況對(duì)目標(biāo)函數(shù)中距離成分權(quán)重對(duì)總運(yùn)輸距離的影響進(jìn)行量化，其具體描述如圖6所示。可知，從條件1到條件5，決策者所冒的風(fēng)險(xiǎn)更多，總安全風(fēng)險(xiǎn)值呈一個(gè)增加趨勢(shì)，而總距離是一個(gè)線性關(guān)系變化。

圖6 連續(xù)10 d的距離和安全風(fēng)險(xiǎn)值

弧作為影響路徑安全的一個(gè)指標(biāo)，主要衡量指數(shù)是弧在不同天的使用頻率。5種條件下一條弧在不同天里的使用頻率分布情況如圖7。分析得出，弧被使用的頻率越高，則路徑安全性就越低，當(dāng)目標(biāo)函數(shù)中安全風(fēng)險(xiǎn)的權(quán)重增大時(shí)，同一條弧重復(fù)使用頻率就降低。比如，在條件1下，10 d里23.8%的弧只用于其中1 d；相比而言，在條件5下，1 d只使用12.5%的弧，超過(guò)4.6%的弧每天都在使用。路徑的變化不僅僅是因?yàn)樗惴ǖ碾S機(jī)性，還因?yàn)樵?0 d里選擇替換路徑以及決策時(shí)安全風(fēng)險(xiǎn)的權(quán)重。當(dāng)安全風(fēng)險(xiǎn)權(quán)重Kd增加時(shí)，說(shuō)明決策者不喜歡冒風(fēng)險(xiǎn)，弧的使用頻率就會(huì)降低。這表明，算法可避免重復(fù)使用同一條路徑，特別是通過(guò)RU值來(lái)限制時(shí)，可實(shí)現(xiàn)這一目標(biāo)。

圖7 5種條件下一條弧在不同天里的使用頻率分布圖

算法運(yùn)行效率方面，對(duì)連續(xù)30 d軍事運(yùn)輸情況進(jìn)行測(cè)試，結(jié)果見表2。其結(jié)果與連續(xù)10 d數(shù)據(jù)求解結(jié)果相似，可知運(yùn)輸距離和安全風(fēng)險(xiǎn)的相關(guān)情況：當(dāng)安全風(fēng)險(xiǎn)的權(quán)重Kd從1減小到0時(shí)，安全風(fēng)險(xiǎn)值增加了47.6%，總距離減少了27.7%，5種條件下運(yùn)輸距離和安全風(fēng)險(xiǎn)值如圖8，可知路徑優(yōu)化中包含安全風(fēng)險(xiǎn)目標(biāo)的優(yōu)點(diǎn)。

表2 30 d路徑求解結(jié)果

圖8 連續(xù)30 d的距離和安全風(fēng)險(xiǎn)值

通過(guò)表1和表2求解情況可知，在安全性權(quán)重Kd從1～0變化過(guò)程中，運(yùn)輸安全風(fēng)險(xiǎn)值也隨之發(fā)生了相應(yīng)得從小到大的數(shù)值變化，表1給出的10 d求解路徑運(yùn)輸安全風(fēng)險(xiǎn)值從270.59逐漸增加到了399.76，表2給出的30 d求解路徑運(yùn)輸安全風(fēng)險(xiǎn)值從407.33逐漸增加到了601.32，說(shuō)明了安全風(fēng)險(xiǎn)權(quán)重大小與運(yùn)輸安全風(fēng)險(xiǎn)值的很好對(duì)應(yīng)關(guān)系，說(shuō)明其合理性。

通過(guò)驗(yàn)證調(diào)整算法對(duì)需求點(diǎn)抵達(dá)時(shí)間的影響，對(duì)比10 d里有同樣需求的每一天，是否運(yùn)用調(diào)整算法情況下的路徑求解中抵達(dá)時(shí)間的區(qū)別，并計(jì)算了連續(xù)10 d 5種條件下每個(gè)需求節(jié)點(diǎn)的抵達(dá)時(shí)間的變化范圍，如圖9所示，平均抵達(dá)時(shí)間存在92%的變化。同時(shí)，對(duì)變化值進(jìn)行配對(duì)T檢驗(yàn)，得到ρ值比10-5小，表明調(diào)整算法會(huì)增加變化值，但沒(méi)有超出需求節(jié)點(diǎn)抵達(dá)時(shí)間變化范圍，而每個(gè)需求節(jié)點(diǎn)的抵達(dá)時(shí)間是通過(guò)連續(xù)10d最大和最小的不同抵達(dá)時(shí)間來(lái)計(jì)算的， 5種條件下調(diào)整算法對(duì)抵達(dá)時(shí)間范圍值的影響如圖10，可知平均時(shí)間范圍有24.1%的變化。配對(duì)T檢驗(yàn)表明：調(diào)整算法會(huì)增加范圍值，但ρ值小于10-3。調(diào)整算法增加了抵達(dá)時(shí)間的變化性，提高了路徑的安全性。

圖9 調(diào)整算法使用前后抵達(dá)時(shí)間方差

圖10 調(diào)整算法執(zhí)行前后抵達(dá)時(shí)間范圍

4 結(jié)論

為了實(shí)現(xiàn)多目標(biāo)優(yōu)化，將成本矩陣作為求解路徑的輸入，運(yùn)用提出的自適應(yīng)選擇算法求解，降低路徑弧的使用頻率，根據(jù)弧的使用頻率來(lái)更新RU值，應(yīng)用隨機(jī)機(jī)制使路徑不可預(yù)測(cè)，并通過(guò)定義松弛時(shí)間，使用調(diào)整算法使抵達(dá)時(shí)間多樣化。

通過(guò)對(duì)北京地區(qū)駐軍某部實(shí)際需求節(jié)點(diǎn)的數(shù)據(jù)測(cè)試，結(jié)果表明：算法降低了相同路徑的使用頻率，量化了運(yùn)輸距離和安全目標(biāo)，調(diào)整算法實(shí)現(xiàn)了抵達(dá)時(shí)間多樣化，提高了路徑安全性，驗(yàn)證了算法有效性，能較好為軍事運(yùn)輸提供決策輔助。