改進的遺傳算法在戰時油料運輸車輛路徑問題中的應用研究

蔣敬東　周慶忠　李　凌　楊　方

摘要：文章首先對戰時油料運輸車輛路徑問題（VRP）進行了分析，闡述了戰時油料運輸車輛路徑問題的優化目標，并建立了多目標的優化模型；接著簡介了遺傳算法的優缺點，并設計了一種改進的遺傳算法運用到問題的求解中；最后舉例進行了計算和分析，驗證了模型和算法的有效性。

關鍵詞：戰時油料運輸；車輛路徑問題；遺傳算法

中圖分類號: U116.2文獻標識碼：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問題分析

戰時油料運輸車輛路徑問題（VRP），是指在戰時一個油料供應點保障多個部隊用油的情況下，尋找一條最優的巡回路徑。傳統意義上的最短路程巡回路線在戰時并不具有很大的實際意義，決策者需要的是能夠在規定時限內完成任務，且運輸代價（主要指損失、時間和路程）最小的方案。

2模型的建立與求解

2.1遺傳算法簡介

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

然而，遺傳算法仍具有很多問題，如早熟、收斂慢等，本文對遺傳算法進行一定的改進，并將其運用到戰時油料運輸車輛路徑問題中。

2.2模型的建立

將油料運輸網絡抽象，構建網絡圖G=V，E，W。權重集W=T，L，D，其中，T表示時間集，tij表示路段i，j通過時間，L表示損失集，lij表示路段i，j油料運輸損耗率，D表示路程集，dij表示路段i，j的路程。

根據優化目標，可以建立模型如下：

minC=?YLx+?Dx+?Tx

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

式中：

（1）Yi、Ti表示到達第i個節點時的油料運輸量和經歷的時間；

（2）、、分別表示損失率和路程在優化目標中所占的權重；

（3）i、i分別表示第i個節點處的指定的運輸量和時限；

（4）xij是0-1變量，當路段i,j在所選路線上時，xij=1，否則，xij=0。

2.3模型的求解

（1）、的值可由決策者根據戰時要求并參考專家意見確定。

（2）為簡化計算和統一量綱，對數據進行歸一化處理。設起點的運輸量為1個單位，即Y1=1；設Dmax=maxD=1，則Dij∈0,1。

（3）采用改進的遺傳算法求解。

3改進遺傳算法的設計

3.1染色體編碼

根據油料運輸車輛路徑問題的特點，本文采用簡單直觀的自然數編碼方式構造染色體，染色體的基因表示油料運輸網絡中的節點，基因的排列順序即表示由起點到終點的路線。

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

3.2種群初始化

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

3.3適應度計算

遺傳算法中以個體適應度的大小來評定各個個體的優劣程度，從而決定其遺傳機會的大小。在本問題中，是以求函數最小值為優化目標且目標函數C非負，故可用目標函數的倒數作為個體的適應度，即：

F==

3.4染色體選擇

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

3.5染色體交叉

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

（1）生成隨機數，若隨機數小于交叉概率，則進行下面的步驟；

（2）對種群中的個體進行隨機配對；

（3）隨機選擇兩個交叉點的位置（不包括0基因），兩交叉點之間的部分稱為匹配區域段；

（4）將匹配區域段分別加到另一個個體的前面；

（5）刪除每個個體中的重復基因。

為了加快種群的進化速度，本文對上述交叉算法進行了改進，即按照上述的算法將每對配對個體進行多次交叉，從產生的多個新個體中選擇兩個最優個體遺傳到下一代種群中。

3.6染色體變異

變異運算是對個體的某一個或某一些位置的基因值按某一較小的概率進行改變，它也是產生新個體的一種操作方法。

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

（1）隨機選擇某個個體的兩個基因，將其調換位置；

（2）隨機改變0基因的插入點。

同時比較變異前后染色體適應度的變化，若適應度提高，則將變異后的染色體保留到種群中，否則，保留原來的染色體。

3.7參數的選擇

遺傳算法中的控制參數包括種群規模、染色體長度、交叉概率、變異概率和進化代數等。參數的選擇非常關鍵，過大或過小都會對算法的性能產生不良的影響。一般來說，種群規模取20～100、交叉概率取0.4～0.9、變異概率取0.001～0.01、進化代數取100～500比較合適[2]。

4實例分析

某油料供應點A負責對其周邊的8個部隊進行油料保障，已知該供應點到各部隊之間的路程、行駛時間、可能的損失率以及各部隊的油料需求量（見表1～表4），有2支運油分隊可以使用，要求24小時之內完成對所有用油部隊的油料補充，試選擇最優的運輸路線[3]。

（1）求解。取種群規模為20，交叉概率為0.8，變異概率為0.01，進化代數為100。通過模擬計算，在第65代時得到最優結果（表5所示為搜索尋優過程）。最優路線為：A-8-2-1-A、A-4-3

-7-5-6-A，兩只運油分隊分別承擔0.30和0.70的任務。方案適應度為0.9871，損失為0.4438，時間為16小時，路程為82公里。

（2）結果分析。下面對2支分隊共同參與油料運輸的情況做以分析，得出在不同任務量下不同的最優路線，這些路線的適應度差別不大，在戰時遇到敵人襲擊或其他突發事件時可以作為備用路線替換。

5結束語

本文建立的模型和改進的算法較好地解決戰時油料運輸車輛路徑問題，得到了既能按時完成任務又能使損失盡量小的方案，在實際應用中具有一定的參考價值。

參考文獻：

[1]陳國梁, 王煦法, 莊鎮泉,等. 遺傳算法及其應用[M]. 北京: 人民郵電出版社, 1996.

[2]王小平, 曹立明. 遺傳算法——理論、應用與軟件實現[M].西安: 西安交通大學出版社, 2002.

[3]姜大力, 王豐, 張劍芳.軍事物流系統模型及應用[M]. 北京: 中國物資出版社, 2006.