一種改進(jìn)型蟻群算法在帶硬時(shí)間窗的戰(zhàn)場車輛路徑問題中的應(yīng)用研究

呂 游，楊 波 LV You, YANG Bo

（國防科學(xué)技術(shù)大學(xué) 指揮軍官基礎(chǔ)教育學(xué)院，湖南 長沙410072）

(College of Basic Education for Commanding Officers, National University of Defense Technology, Changsha 410072, China)

“兵馬未動，糧草先行”，后勤補(bǔ)給在戰(zhàn)爭中具有不可替代的作用，隨著戰(zhàn)爭形態(tài)、戰(zhàn)爭規(guī)模和作戰(zhàn)方式的不斷演變，“深挖洞、廣積糧”的預(yù)有準(zhǔn)備的大量囤積已經(jīng)不能滿足現(xiàn)代戰(zhàn)爭中作戰(zhàn)部隊(duì)對后勤補(bǔ)給物資的需求，實(shí)時(shí)、快速、準(zhǔn)確的“精確保障”也就應(yīng)運(yùn)而生。軍事物流是后勤補(bǔ)給的重要環(huán)節(jié)，車輛配送則是確保補(bǔ)給物資及時(shí)、準(zhǔn)確、高效運(yùn)送到作戰(zhàn)單元的關(guān)鍵一環(huán)。

1 帶時(shí)間窗的戰(zhàn)場車輛路徑問題簡述

帶時(shí)間窗的車輛路徑問題（Vehicle Routing Problem with Time Windows，VRPTW） 也被稱為車輛配送問題。設(shè)某一局部戰(zhàn)場只有一個(gè)物資配送中心，該配送中心對多個(gè)作戰(zhàn)單元進(jìn)行服務(wù)保障，有多臺型號相同的運(yùn)輸車輛可供調(diào)用，多輛運(yùn)輸車可以同時(shí)從配送中心出發(fā)，各自按照一定次序完成對不同作戰(zhàn)單元的服務(wù)保障。各配送車輛型號、容量（最大載重量）、平均行駛速度均相同，各作戰(zhàn)單元只在一定時(shí)間窗口內(nèi)接受服務(wù)，若配送車輛早于規(guī)定服務(wù)時(shí)間到達(dá)作戰(zhàn)單元?jiǎng)t選擇等待，直至規(guī)定時(shí)間方可開始進(jìn)行服務(wù)，若配送車輛晚于規(guī)定時(shí)間到達(dá)則作戰(zhàn)單元拒絕接受服務(wù)，一個(gè)作戰(zhàn)單元只能被一輛車服務(wù)。各作戰(zhàn)單元有相應(yīng)的服務(wù)時(shí)間和物資需求量，在完成對某一作戰(zhàn)單元的服務(wù)后，配送車輛可以選擇下一個(gè)作戰(zhàn)單元，也可以回到配送中心，配送中心及各作戰(zhàn)單元間的距離預(yù)先可知，目標(biāo)函數(shù)為配送車輛總路程。

2 VRPTW 的數(shù)學(xué)模型

Q：配送車輛的容量（最大載重），本文假設(shè)配送車輛為同種型號，各運(yùn)輸車量容量均相同；

qi：第i個(gè)作戰(zhàn)單元的物資需求量，其中i=1,2,…,n；

dij：從出發(fā)點(diǎn)i到目標(biāo)點(diǎn)j的車輛行駛距離，其中i,j=0,1,2,…,n；

tij：配送車輛由出發(fā)點(diǎn)i至目標(biāo)點(diǎn)j的行駛時(shí)間，其中i,j=0,1,2,…,n；

ti：配送車輛為作戰(zhàn)單元i提供服務(wù)所需要的時(shí)間（卸貨時(shí)間），其中i=1,2,…,n；

Li：車輛實(shí)際經(jīng)過的路線，其中i=1,2,…,2n，一般情況下車輛實(shí)際經(jīng)過路線的作戰(zhàn)單元數(shù)量小于2n；第i個(gè)作戰(zhàn)單元接受服務(wù)的最早時(shí)間；第i個(gè)作戰(zhàn)單元接受服務(wù)的最晚時(shí)間；

xkij：車輛k的行駛線路是否包含由點(diǎn)i出發(fā)直接到點(diǎn)j的路段，其中：i,j=0,1,2,…,n，k=1,2,…,m；

yki：車輛k是否為作戰(zhàn)單元i提供服務(wù)，其中i=1,2,…,n，k=1,2,…,m；

問題的基本模型為：

在上述模型中，式（1） 為目標(biāo)函數(shù)，表示配送總路線最短，即總費(fèi)用最?。皇剑?） 表示每輛車所擔(dān)負(fù)的服務(wù)任務(wù)的作戰(zhàn)單元的總需求量不大于車輛最大載重量；式（3） 表示任何一個(gè)作戰(zhàn)單元只能由一輛車對其進(jìn)行服務(wù)；式（4）、（5） 表示任何配送車輛都是從配送中心出發(fā)，并只能選擇一個(gè)作戰(zhàn)單元進(jìn)行配送；式（6） 表示每輛車最后回到配送中心；式（7） 表示若某一車輛到達(dá)作戰(zhàn)單元j則必須為該作戰(zhàn)單元服務(wù)；式（8） 表示任一配送車輛對任一作戰(zhàn)單元可能選擇服務(wù)或者不服務(wù)；式（9） 表示每個(gè)作戰(zhàn)單元接受服務(wù)的時(shí)間窗口；式（10） 表示車輛k為作戰(zhàn)單元i的服務(wù)的時(shí)間段；式（11）、（12） 表示配送車輛k為作戰(zhàn)單元Li完成服務(wù)后，若對下一個(gè)作戰(zhàn)單元Li+1進(jìn)行服務(wù)，則到達(dá)該作戰(zhàn)單元的時(shí)間必須在該作戰(zhàn)單元所要求的時(shí)間窗之內(nèi)；式（13）、（14） 表示配送車輛k為某作戰(zhàn)單元Li+1服務(wù)的時(shí)間段與該作戰(zhàn)單元所需的服務(wù)時(shí)間tLi+1的關(guān)系；式（15）、（16） 表示相應(yīng)變量的取值范圍。

3 VRPTW 的改進(jìn)型蟻群算法

常見的求解VRP 問題有禁忌搜索算法、模擬退火算法、遺傳算法及蟻群算法等。VRP 問題已經(jīng)被證明為NP-hard 問題，很難通過傳統(tǒng)算法得到其最優(yōu)解。本文根據(jù)VRPTW 的特點(diǎn)，設(shè)計(jì)了一種改進(jìn)蟻群算法對問題求解。蟻群算法在求解該問題中通過個(gè)體之間的信息傳遞，有利于在發(fā)現(xiàn)有效解，同時(shí)蟻群算法通過對信息素的反饋機(jī)制對有效解不斷增強(qiáng)，使得問題不斷趨近于全局最優(yōu)。當(dāng)然，蟻群算法也存在一定缺陷，如搜索時(shí)間較長，構(gòu)造有效解需要大量計(jì)算時(shí)間，容易出現(xiàn)局部停滯現(xiàn)象等。本文主要在兩個(gè)方面對傳統(tǒng)蟻群算法進(jìn)行了改進(jìn)：一是將已訪問點(diǎn)附近一定范圍內(nèi)符合訪問要求的點(diǎn)作為待訪問對象，這樣有利于減少搜索時(shí)間和計(jì)算量，帶來的問題在于可能會錯(cuò)過最優(yōu)解，避免錯(cuò)過最優(yōu)解的方法為合理設(shè)置并變化待訪問點(diǎn)數(shù)量；二是用局部線路車輛訪問過的作戰(zhàn)單元數(shù)量和該路線長度作為信息素更新的依據(jù)，以突出車輛利用率。

3.1 改進(jìn)的蟻群算法基本流程

Step1 初始化每個(gè)參數(shù)，假設(shè)有m 只螞蟻從配送中心出發(fā)，分別選擇一個(gè)作戰(zhàn)單元作為第一個(gè)訪問點(diǎn)。

Step2 對每個(gè)螞蟻列出全部未訪問點(diǎn)，設(shè)其個(gè)數(shù)為S1個(gè)。

Step3 判斷S1取值。若S1=0，該螞蟻已經(jīng)完成全部配送任務(wù)，選取下一訪問點(diǎn)為配送中心，本條線路配送結(jié)束。若S1＞0，從S1個(gè)未訪問點(diǎn)中篩選出符合訪問條件的未訪問點(diǎn)為個(gè)，若S2=0，則表示沒有可選點(diǎn)符合條件，車輛返回配送中心，若S2＞0，在以當(dāng)前訪問點(diǎn)一定距離范圍內(nèi)選取S=min（S,S2）個(gè)候選訪問點(diǎn)，并將配送中心加入到候選訪問點(diǎn)，按照一定概率選取一個(gè)點(diǎn)作為下一個(gè)服務(wù)點(diǎn)，返回Step2。

Step4 判斷是否所有螞蟻都已經(jīng)完成配送任務(wù)。若所有螞蟻都完成了配送任務(wù)，計(jì)算本次配送中各螞蟻所經(jīng)過的總路線長度，從中選出最短路線并記錄，則按照一定規(guī)則更新信息素。

3.2 待訪問點(diǎn)選擇和信息素更新

待訪問點(diǎn)的選擇問題是影響VRPTW 計(jì)算復(fù)雜性的一個(gè)重要因素，我們希望在能夠減少計(jì)算量的同時(shí)不遺漏最優(yōu)解或者可行解。本文采取的策略是首先判斷可選點(diǎn)的集合，在帶時(shí)間窗的車輛配送問題中，配送車輛到達(dá)某一服務(wù)單元后，受到各種約束條件的限制，車輛可供選擇的服務(wù)點(diǎn)的數(shù)量不斷減少，進(jìn)行可選服務(wù)點(diǎn)的篩查有助于減少不必要的計(jì)算。

信息素的更新是決定算法收斂速度和求解效率的關(guān)鍵環(huán)節(jié)，本文采取“指數(shù)分段更新”策略，較好地解決了信息素更新的問題。基本思想是將配送車輛（螞蟻） 所經(jīng)過的路徑按照是否回到配送中心進(jìn)行分段。該方法有利于快速區(qū)分不同路線的優(yōu)劣程度，很大程度上提高了算法效率，同時(shí)為避免陷入局部最優(yōu)，給定信息素最小值，確保更多路線能夠被嘗試。信息素具體更新方式如下：

用τij表示路線從i到j(luò)上的信息素，初始值設(shè)為單位矩陣；用ηij表示路線從i到j(luò)上的啟發(fā)式信息值，初始值設(shè)為1/d表示對第k輛車在作戰(zhàn)單元i可選擇的目標(biāo)點(diǎn)，pk（i,j）表示第k輛車在作戰(zhàn)單元i選擇作戰(zhàn)單元j為配送目標(biāo)的概率，Rk表示第k輛車所經(jīng)過的路線。

式（17） 為第k輛配送車輛從作戰(zhàn)單元i出發(fā)，分別以不同的作戰(zhàn)單元j為目標(biāo)點(diǎn)的概率，其中α 為殘留信息的相對重要程度，β 為預(yù)見值的相對重要程度，本文仿真算例中令α=1，β=1；式（18）、（19）、（20） 表示信息素的更新步驟，其中式（18） 中K表示第k輛車所完成配送任務(wù)回到配送中心過程中所到達(dá)的作戰(zhàn)單元的個(gè)數(shù)，λ 為指數(shù)因子，根據(jù)情況由人為給出，本文在仿真計(jì)算中令λ=3，取得了較好的計(jì)算效果，ρ 為信息素?fù)]發(fā)參數(shù)，本文仿真計(jì)算中令ρ=0.5。τ0為信息素修正因子，由人為給出，以增加不同路線的選擇概率，避免算法早熟，本文仿真實(shí)例中令τ0=0.1。

3.3 仿真計(jì)算示例

客戶數(shù)為8 的VRPTW 問題，描述如下：某戰(zhàn)場配送任務(wù)中，有1 個(gè)配送中心和8 個(gè)作戰(zhàn)單元，各作戰(zhàn)單元的需求量為gi（單位：噸），服務(wù)（或卸貨） 時(shí)間為Ti（單位：小時(shí)），各作戰(zhàn)單元的服務(wù)時(shí)間范圍最大允許車輛數(shù)為5，車輛平均行駛速度為50，載重量為8。并且認(rèn)為行駛時(shí)間與距離成正比，配送中心與配送點(diǎn)的距離由表2 給出。要求合理安排車輛的行駛路線，使得既滿足條件完成運(yùn)輸任務(wù)，又能使總的花費(fèi)最小。具體信息如表1。

[1]設(shè)置群體規(guī)模為60，進(jìn)化代數(shù)為100，在賽揚(yáng)雙核T1400（主頻1.73GHZ） 計(jì)算機(jī)上運(yùn)行1 000 次，其得到最優(yōu)解、得到最優(yōu)解的概率、得到最優(yōu)解的平均運(yùn)行時(shí)間和平均迭代次數(shù)如表3、表4。

采用本文算法，使用因特爾酷睿2 雙核E7500（主頻2.93GHZ），比參考文獻(xiàn)[1]中所用計(jì)算機(jī)處理器運(yùn)算速度的1.7 倍。螞蟻數(shù)量40、α=1.0、β=2.0、ρ=0.2，得到的最優(yōu)結(jié)果與參考文獻(xiàn)[1]中的結(jié)果相同，計(jì)算時(shí)間和迭代次數(shù)顯著小于該文獻(xiàn)中所用方法，基本情況如表5。

表1 客戶數(shù)位8 的車輛配送問題描述

表2 各個(gè)作戰(zhàn)單元（包括配送中心） 之間的位置關(guān)系

表3 參考文獻(xiàn)[1]中的計(jì)算結(jié)果

表4 參考文獻(xiàn)[1]中算法的計(jì)算效率

表5 本文算法的計(jì)算效率

4 結(jié) 論

本文在不使用局部搜索算法的情況下，通過改進(jìn)螞蟻選擇路徑過程中的關(guān)鍵問題——信息素的更新方式，提高了狀態(tài)轉(zhuǎn)移效率和信息素更新速度，有效避免了算法限于早熟。通過與同類文獻(xiàn)結(jié)果對比，驗(yàn)證了改進(jìn)的蟻群算法的有效性。

參考文獻(xiàn)：

[1] 周和平. 軍事物流配送路徑優(yōu)化問題研究[D]. 合肥：合肥工業(yè)大學(xué)（碩士學(xué)位論文），2009.

[2] 王宗喜. 軍事物流概論[M]. 北京：海潮出版社，1993.

[3] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社，2006.