呂 游，楊 波 LV You, YANG Bo

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

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

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

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

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

2 VRPTW 的數(shù)學模型

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

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

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

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

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

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

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

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

問題的基本模型為：

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

3 VRPTW 的改進型蟻群算法

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

3.1 改進的蟻群算法基本流程

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

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

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

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

3.2 待訪問點選擇和信息素更新

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

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

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

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

3.3 仿真計算示例

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

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

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

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

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

表3 參考文獻[1]中的計算結(jié)果

表4 參考文獻[1]中算法的計算效率

表5 本文算法的計算效率

4 結(jié) 論

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

參考文獻：

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

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

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