改進(jìn)的遺傳算法在戰(zhàn)時(shí)油料運(yùn)輸車(chē)輛路徑問(wèn)題中的應(yīng)用研究

蔣敬東　周慶忠　李　凌　楊　方

摘要：文章首先對(duì)戰(zhàn)時(shí)油料運(yùn)輸車(chē)輛路徑問(wèn)題（VRP）進(jìn)行了分析，闡述了戰(zhàn)時(shí)油料運(yùn)輸車(chē)輛路徑問(wèn)題的優(yōu)化目標(biāo)，并建立了多目標(biāo)的優(yōu)化模型；接著簡(jiǎn)介了遺傳算法的優(yōu)缺點(diǎn)，并設(shè)計(jì)了一種改進(jìn)的遺傳算法運(yùn)用到問(wèn)題的求解中；最后舉例進(jìn)行了計(jì)算和分析，驗(yàn)證了模型和算法的有效性。

關(guān)鍵詞：戰(zhàn)時(shí)油料運(yùn)輸；車(chē)輛路徑問(wèn)題；遺傳算法

中圖分類(lèi)號(hào): U116.2文獻(xiàn)標(biāo)識(shí)碼：A

Abstract: In this paper, the author firstly analyses the vehicle routing problem of POL transporting during wartime, states the optimization goals of VRP and build a multi-object optimization model. Then the author briefly introduces the genetic algorithm and constructs an improved genetic algorithm which is used to solve the problem. At last, an example is given to prove the efficiency of the model and the algorithm.

Key words: POL transporting during wartime; vehicle routing problem; improved genetic algorithm

1問(wèn)題分析

戰(zhàn)時(shí)油料運(yùn)輸車(chē)輛路徑問(wèn)題（VRP），是指在戰(zhàn)時(shí)一個(gè)油料供應(yīng)點(diǎn)保障多個(gè)部隊(duì)用油的情況下，尋找一條最優(yōu)的巡回路徑。傳統(tǒng)意義上的最短路程巡回路線(xiàn)在戰(zhàn)時(shí)并不具有很大的實(shí)際意義，決策者需要的是能夠在規(guī)定時(shí)限內(nèi)完成任務(wù)，且運(yùn)輸代價(jià)（主要指損失、時(shí)間和路程）最小的方案。

2模型的建立與求解

2.1遺傳算法簡(jiǎn)介

遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索方法。它首先對(duì)問(wèn)題的可行解進(jìn)行編碼，組成染色體，然后通過(guò)模擬自然界的進(jìn)化過(guò)程，對(duì)初始種群中的染色體進(jìn)行選擇、交叉和變異，通過(guò)一代代進(jìn)化來(lái)找出最優(yōu)適應(yīng)值的染色體，它具有很強(qiáng)的全局搜索能力和較強(qiáng)的自適應(yīng)性，適合解決連續(xù)變量函數(shù)優(yōu)化問(wèn)題和離散變量的優(yōu)化組合問(wèn)題[1]。

然而，遺傳算法仍具有很多問(wèn)題，如早熟、收斂慢等，本文對(duì)遺傳算法進(jìn)行一定的改進(jìn)，并將其運(yùn)用到戰(zhàn)時(shí)油料運(yùn)輸車(chē)輛路徑問(wèn)題中。

2.2模型的建立

將油料運(yùn)輸網(wǎng)絡(luò)抽象，構(gòu)建網(wǎng)絡(luò)圖G=V，E，W。權(quán)重集W=T，L，D，其中，T表示時(shí)間集，tij表示路段i，j通過(guò)時(shí)間，L表示損失集，lij表示路段i，j油料運(yùn)輸損耗率，D表示路程集，dij表示路段i，j的路程。

根據(jù)優(yōu)化目標(biāo)，可以建立模型如下：

minC=?YLx+?Dx+?Tx

s.t.Y=Y?1-Lx≥T=Tx≤x∈0,1

式中：

（1）Yi、Ti表示到達(dá)第i個(gè)節(jié)點(diǎn)時(shí)的油料運(yùn)輸量和經(jīng)歷的時(shí)間；

（2）、、分別表示損失率和路程在優(yōu)化目標(biāo)中所占的權(quán)重；

（3）i、i分別表示第i個(gè)節(jié)點(diǎn)處的指定的運(yùn)輸量和時(shí)限；

（4）xij是0-1變量，當(dāng)路段i,j在所選路線(xiàn)上時(shí)，xij=1，否則，xij=0。

2.3模型的求解

（1）、的值可由決策者根據(jù)戰(zhàn)時(shí)要求并參考專(zhuān)家意見(jiàn)確定。

（2）為簡(jiǎn)化計(jì)算和統(tǒng)一量綱，對(duì)數(shù)據(jù)進(jìn)行歸一化處理。設(shè)起點(diǎn)的運(yùn)輸量為1個(gè)單位，即Y1=1；設(shè)Dmax=maxD=1，則Dij∈0,1。

（3）采用改進(jìn)的遺傳算法求解。

3改進(jìn)遺傳算法的設(shè)計(jì)

3.1染色體編碼

根據(jù)油料運(yùn)輸車(chē)輛路徑問(wèn)題的特點(diǎn)，本文采用簡(jiǎn)單直觀(guān)的自然數(shù)編碼方式構(gòu)造染色體，染色體的基因表示油料運(yùn)輸網(wǎng)絡(luò)中的節(jié)點(diǎn)，基因的排列順序即表示由起點(diǎn)到終點(diǎn)的路線(xiàn)。

設(shè)油料運(yùn)輸網(wǎng)絡(luò)中有一個(gè)供應(yīng)點(diǎn)和n各保障點(diǎn)（用油部分隊(duì)），用0表示供應(yīng)點(diǎn)，1,n之間的自然數(shù)表示保障點(diǎn)。若供應(yīng)點(diǎn)有m個(gè)運(yùn)油分隊(duì)參與油料運(yùn)輸, 則需要尋找m條巡回路線(xiàn)，即一種路線(xiàn)選擇方案。如染色體0120345607890表示的路線(xiàn)選擇方案是：0-1-2-0、0-3-4-5-6-0、0-7-8-9-0。

3.2種群初始化

種群初始化是產(chǎn)生表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。隨機(jī)生成1,n之間n個(gè)自然數(shù)的一個(gè)全排列，再將m+1個(gè)0隨機(jī)插入到生成的排列中，排列的頭部和尾部都必須有且只有一個(gè)0，這樣就構(gòu)成了需要的染色體。

3.3適應(yīng)度計(jì)算

遺傳算法中以個(gè)體適應(yīng)度的大小來(lái)評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳機(jī)會(huì)的大小。在本問(wèn)題中，是以求函數(shù)最小值為優(yōu)化目標(biāo)且目標(biāo)函數(shù)C非負(fù)，故可用目標(biāo)函數(shù)的倒數(shù)作為個(gè)體的適應(yīng)度，即：

F==

3.4染色體選擇

選擇運(yùn)算是把當(dāng)前群體中適應(yīng)度較高的個(gè)體按某種規(guī)則或模型遺傳到下一代群體中。常用的方法是輪盤(pán)賭選擇法，但輪盤(pán)賭的選擇方式使每個(gè)個(gè)體都有被選中的機(jī)會(huì)，降低了進(jìn)化的效率。本文對(duì)算法進(jìn)行了改進(jìn)，采用依個(gè)體適應(yīng)度比例選擇的方法，使適應(yīng)度高的個(gè)體有更多的機(jī)會(huì)遺傳到下一代種群中。具體算法是先求出某個(gè)體的適應(yīng)度占種群中全部個(gè)體適應(yīng)度總和的比例，則此比例與種群數(shù)目的乘積即是該個(gè)體在下一代種群中復(fù)制的數(shù)量。

3.5染色體交叉

交叉運(yùn)算是遺傳算法中產(chǎn)生新個(gè)體的主要操作過(guò)程，它以某一概率相互交換某兩個(gè)個(gè)體之間的部分染色體。常用的交叉方法有很多種，不同的方法適用于不同的情況。針對(duì)本問(wèn)題的特點(diǎn)采用類(lèi)OX法[2]。其算法基本操作過(guò)程是：

（1）生成隨機(jī)數(shù)，若隨機(jī)數(shù)小于交叉概率，則進(jìn)行下面的步驟；

（2）對(duì)種群中的個(gè)體進(jìn)行隨機(jī)配對(duì)；

（3）隨機(jī)選擇兩個(gè)交叉點(diǎn)的位置（不包括0基因），兩交叉點(diǎn)之間的部分稱(chēng)為匹配區(qū)域段；

（4）將匹配區(qū)域段分別加到另一個(gè)個(gè)體的前面；

（5）刪除每個(gè)個(gè)體中的重復(fù)基因。

為了加快種群的進(jìn)化速度，本文對(duì)上述交叉算法進(jìn)行了改進(jìn)，即按照上述的算法將每對(duì)配對(duì)個(gè)體進(jìn)行多次交叉，從產(chǎn)生的多個(gè)新個(gè)體中選擇兩個(gè)最優(yōu)個(gè)體遺傳到下一代種群中。

3.6染色體變異

變異運(yùn)算是對(duì)個(gè)體的某一個(gè)或某一些位置的基因值按某一較小的概率進(jìn)行改變，它也是產(chǎn)生新個(gè)體的一種操作方法。

本文采用的染色體變異方式有兩種：

（1）隨機(jī)選擇某個(gè)個(gè)體的兩個(gè)基因，將其調(diào)換位置；

（2）隨機(jī)改變0基因的插入點(diǎn)。

同時(shí)比較變異前后染色體適應(yīng)度的變化，若適應(yīng)度提高，則將變異后的染色體保留到種群中，否則，保留原來(lái)的染色體。

3.7參數(shù)的選擇

遺傳算法中的控制參數(shù)包括種群規(guī)模、染色體長(zhǎng)度、交叉概率、變異概率和進(jìn)化代數(shù)等。參數(shù)的選擇非常關(guān)鍵，過(guò)大或過(guò)小都會(huì)對(duì)算法的性能產(chǎn)生不良的影響。一般來(lái)說(shuō)，種群規(guī)模取20～100、交叉概率取0.4～0.9、變異概率取0.001～0.01、進(jìn)化代數(shù)取100～500比較合適[2]。

4實(shí)例分析

某油料供應(yīng)點(diǎn)A負(fù)責(zé)對(duì)其周邊的8個(gè)部隊(duì)進(jìn)行油料保障，已知該供應(yīng)點(diǎn)到各部隊(duì)之間的路程、行駛時(shí)間、可能的損失率以及各部隊(duì)的油料需求量（見(jiàn)表1～表4），有2支運(yùn)油分隊(duì)可以使用，要求24小時(shí)之內(nèi)完成對(duì)所有用油部隊(duì)的油料補(bǔ)充，試選擇最優(yōu)的運(yùn)輸路線(xiàn)[3]。

（1）求解。取種群規(guī)模為20，交叉概率為0.8，變異概率為0.01，進(jìn)化代數(shù)為100。通過(guò)模擬計(jì)算，在第65代時(shí)得到最優(yōu)結(jié)果（表5所示為搜索尋優(yōu)過(guò)程）。最優(yōu)路線(xiàn)為：A-8-2-1-A、A-4-3

-7-5-6-A，兩只運(yùn)油分隊(duì)分別承擔(dān)0.30和0.70的任務(wù)。方案適應(yīng)度為0.9871，損失為0.4438，時(shí)間為16小時(shí)，路程為82公里。

（2）結(jié)果分析。下面對(duì)2支分隊(duì)共同參與油料運(yùn)輸?shù)那闆r做以分析，得出在不同任務(wù)量下不同的最優(yōu)路線(xiàn)，這些路線(xiàn)的適應(yīng)度差別不大，在戰(zhàn)時(shí)遇到敵人襲擊或其他突發(fā)事件時(shí)可以作為備用路線(xiàn)替換。

5結(jié)束語(yǔ)

本文建立的模型和改進(jìn)的算法較好地解決戰(zhàn)時(shí)油料運(yùn)輸車(chē)輛路徑問(wèn)題，得到了既能按時(shí)完成任務(wù)又能使損失盡量小的方案，在實(shí)際應(yīng)用中具有一定的參考價(jià)值。

參考文獻(xiàn)：

[1]陳國(guó)梁, 王煦法, 莊鎮(zhèn)泉,等. 遺傳算法及其應(yīng)用[M]. 北京: 人民郵電出版社, 1996.

[2]王小平, 曹立明. 遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安: 西安交通大學(xué)出版社, 2002.

[3]姜大力, 王豐, 張劍芳.軍事物流系統(tǒng)模型及應(yīng)用[M]. 北京: 中國(guó)物資出版社, 2006.