改進遺傳算法下的車輛路徑問題研究

陳 果（天津大學(xué)管理與經(jīng)濟學(xué)部，300072）

?

改進遺傳算法下的車輛路徑問題研究

陳 果
（天津大學(xué)管理與經(jīng)濟學(xué)部，300072）

摘要：車輛路徑問題是一種典型的組合優(yōu)化類問題，隨著客戶對物流要求的不斷提升，基本的遺傳算法已經(jīng)很難滿足客戶的需求。基本的遺傳算法在求解這類問題的時候，經(jīng)常會出現(xiàn)早熟收斂，以及對車輛的運送時間存在限制等方面的缺陷，不能夠?qū)@類問題進行最優(yōu)化求解，所以本文采用改進的遺傳算法就車輛路徑問題進行研究，并探究改進下的遺傳算法在求解車輛路徑問題時的有效性。

關(guān)鍵詞：遺傳算法；車輛；路徑問題

0　引言

隨著我國經(jīng)濟的快速發(fā)展，市場變得越來越開放，同時競爭也變得越來越激烈。面對日益競爭激烈的今天，企業(yè)要想獲得生存空間，就需要不斷提升自身實力，努力適應(yīng)不斷變化的環(huán)境需要，這樣才能夠保證對市場變化及時作出反應(yīng)，以快的速度、低的成本來滿足消費者的需求，才能夠在競爭中獲得優(yōu)勢。物流的協(xié)調(diào)高效運行一直都是獲得競爭優(yōu)勢的關(guān)鍵所在，對運輸工具進行合理有效的利用，不斷優(yōu)化運輸路線，能夠在很大程度上降低企業(yè)的物流成本，同時它也是物流管理的一項重要功能。

1　遺傳算法基本思想與操作流程

1.1遺傳算法的基本思想

遺傳算法的基本思想中的重要一點就是首先要對遺傳算法的種群進行初始化，創(chuàng)建一個初始種群。整個進化過程是通過一代群體向下一代群體演化完成的，同時每一代的群體都是由若干個體組成，這些組成群體的個體被稱之為染色體，而每一個染色體又都是由不同序列的基本組成的基因串。基因的排列方式多種多樣，基因排列方式的不同造就了不同性能的染色體，所以在遺傳算法中使用適應(yīng)度函數(shù)度量解的性能，個體的適應(yīng)度可以借助對周圍環(huán)境的適應(yīng)度來加以表示。下一代的個體通過上一代的繁殖產(chǎn)生，并且個體也是不斷變化的，繁殖的過程和DNA傳遞過程相似，傳遞過程包括交叉、選擇以及變異。遺傳算法可以和DNA傳遞過程進行類別，它同樣也遵循生物進化過程，按照達爾文的生物進化原則“優(yōu)勝劣汰”不斷更新最優(yōu)解，遺傳算法的具體實現(xiàn)過程如下所示：首先初始化種群，在初始化種群中挑選出表現(xiàn)優(yōu)異的個體，然后借助生物進化過程中DNA傳遞原則，通過交配獲得具有優(yōu)良特點的子代，使得所獲得的具有優(yōu)良性狀的子代更能夠適應(yīng)環(huán)境。通過不斷的這樣選擇，直到存在收斂，到最后所獲得優(yōu)良子代個體就有可能是問題的最優(yōu)解。

1.2遺傳算法的操作流程

遺傳算法它受到自然界生物遺傳的啟發(fā)，所以為了能夠更加清楚的對遺傳算法原理進行闡述，在闡述的過程中也就不可避免的會用到一些重要的遺傳學(xué)術(shù)語。在遺傳算法中它四個基本的操作環(huán)節(jié)分別為：染色體編碼、染色體選擇、染色體交叉、染色體變異。

第一、染色體編碼。遺傳算法中的染色體編碼流程它決定了染色的格式，同時它對解碼也進行了一定程度上的確定。一個好的編碼方案能夠極大提升交配的表現(xiàn)能力，能夠極大提升種群的進化效率。可以這樣說編碼方案的優(yōu)劣最終會決定問題求解的質(zhì)量，在進行編碼方案設(shè)計時通常會遵循以下原則：完備性、健全性、最小字符集。當前來看遺傳算法中采用最多的編碼方案總的來講有三類，分別為：二進制編碼、符號編碼以及實數(shù)編碼。

第二、染色體選擇。從種群中選擇具有優(yōu)異性狀的個體就稱之為選擇，選擇的目的就是把有效個體中所具有的優(yōu)良基因保存下去，以便能夠通過遺傳產(chǎn)生更加優(yōu)秀的后代。選擇操作依據(jù)的是個體適應(yīng)度的優(yōu)劣性，然后再根據(jù)一定的原則對個體進行選擇，不同的選擇策略、原則都會對算法的性能起著不同的影響。比較常見的染色體選擇方法有：輪盤賭法、個體精英保留法、排序法、聯(lián)賽選擇法等。

第三、染色體交叉。在自然界中生物的進化通過的是染色體基因重組，同理遺傳算法所依據(jù)的也是染色體重組，對問題空間所進行的不斷搜索就會通過染色體的交叉完成的，交叉指的就是將親代部分基因相互交互然后在子代基因中呈現(xiàn)出來的過程。

2　基于改進遺傳算法的車輛路徑問題研究

2.1有時間窗約束的車輛路徑問題模型

第一、問題描述。設(shè)某一城市有一個配送中心，擁有足夠多載重量為q的車輛，需要向n個需求點送貨，我們設(shè)運輸中心為0，其它需求點分別為（ii＝0，1...n），并且每一個需求點所需貨物為，配送中心有K輛車，位置和需求點都是已知量，要求每一個需求點只能由一輛車，i到j(luò)距離表示為，一輛車最大歷程為D，目標是配送路線最短。

第二、數(shù)學(xué)模型。設(shè)第k輛車行車路徑稱為第k條路徑，它經(jīng)過的需求點目標數(shù)目為，表示第k條路徑包含個需求點所構(gòu)成的集合，元素表示第k條子路徑中i的需求點，si是車輛到達i需求點的時刻。根據(jù)上述描述建立模型如下：

2.2改進的遺傳算法設(shè)計

第一、染色體編碼。結(jié)合具體情況，本文采用自然數(shù)編碼方式，也就是所謂的實數(shù)編碼。為了區(qū)分染色體的每一條子路徑，在生產(chǎn)染色體的時候就對不同路徑之間添加了隔離基因，也就是說車輛路徑問題一條可行路線編成的染色體長度可以為n＋m。如染色體021304505370所表示的行車路徑為：子路徑1，運輸中心0→需求點2→需求點1→需求點3→運輸中心；子路徑2，運輸中心0→需求點5→需求點3→需求點7→運輸中心；子路徑3，運輸中心0→需求點4→需求點5→運輸中心0。

第二、適應(yīng)度函數(shù)。這里問題，目標函數(shù)值越小越好，個體適應(yīng)度越大，表示個體性能越好。本算法采用排序適應(yīng)度函數(shù)，將同一代m個染色體按目標函數(shù)進行排序，取分布概率作為目標函數(shù)

第三、遺傳算子。采用輪盤賭復(fù)制法進行熱色體復(fù)制，將個體的適應(yīng)度作為個體在下一代存活的概率。本文按照概率進行反轉(zhuǎn)變異，即隨機選取染色體的兩個不同位置，將兩個位置中基因進行交換，判斷交換后的染色體是否符合約束條件，如果不滿足即推出這一操作，進行下一操作。

第四、終止條件。遺傳算法是一種迭代搜索算法，在搜索過程中存在很多隨機性，需要通過多次進化逐漸趨近最優(yōu)解，所以一定要設(shè)立確定的終止條件。本文設(shè)計三個終止條件，滿足一個即停止算法：（1）迭代過程如果優(yōu)良性狀能夠連續(xù)最佳保持到M代；（2）受機器容量以及計算時間限制，代數(shù)不能夠無限長，當?shù)螖?shù)達到預(yù)設(shè)代數(shù)Y時，算法終止；（3）最佳染色體的適應(yīng)度值達到給定要求。

2.3實驗結(jié)果及討論

第一、實驗結(jié)果。遺傳算法應(yīng)用如下：設(shè)實例有需求點8個和配送中心一個，每一個需求點需求量為，服務(wù)時間為，服務(wù)時間范圍為[a，b]。固定車輛能力時，算法參數(shù)設(shè)置為：50群體數(shù)量、迭代次數(shù)100，、交叉概率0。8、變異概率0.02、早到懲罰4、晚到懲罰6.

第二、分析討論。通過對改進的遺傳算法和標準遺傳算法的對比，我們從最優(yōu)解、實現(xiàn)最優(yōu)解的代數(shù)、車輛數(shù)、運行時間四個

方面進行分析，在兩種算法分別運行10次，參數(shù)均值比較如下圖所示。

表一：改進遺傳算法和標準遺傳算法比較表

綜合來看在所需車輛相同的情況下，改進遺傳算法收斂速度更快，并且所求的最優(yōu)解質(zhì)量也越高，通過改進遺傳算法所求的結(jié)果也更加穩(wěn)定；另外改進遺傳算法所求得的最優(yōu)路徑長度小于標準算法求得的路徑長度；運行時間上改進遺傳算法要小于一般遺傳算法。

3　結(jié)語

在對物流進行配送時，合理的分配配送路徑能夠在很大程度提升服務(wù)的質(zhì)量，并且降低配送成本，提升經(jīng)濟效益。由于車輛路徑優(yōu)化問題屬于NP難題，所以可以借助算法求解，其中的遺傳算法在解決這類問題時發(fā)揮了非常重要的作用，體現(xiàn)了它自身的優(yōu)良性能。

參考文獻

[1]魏凱. 改進遺傳算法在軟時間窗車輛路徑問題中的應(yīng)用[D].安徽工業(yè)大學(xué)，2013.

[2]蔡菂迪. 改進遺傳算法在車輛路徑問題中的研究應(yīng)用[D].哈爾濱工程大學(xué)，2013.

陳果，男，1979-12，廣東興寧，高級工程師， 研究方向應(yīng)用基礎(chǔ)

Research on Vehicle Routing Problem Based on Improved Genetic Algorithm

Chen Guo
（Tianjin university of management and economic department，300072）

Abstract：The vehicle routing problem is a typical combinatorial optimization problem.With the continuous improvement of logistics requirements， the basic genetic algorithm has been difficult to meet the needs of customers.The basic genetic algorithm in solving this kind of problem，often appear premature convergence，and delivery time of the vehicle has the defects of limited，can not to solve the optimization of this kind of problem，so this paper uses improved genetic algorithm on vehicle routing problem were studied，and explore the improved genetic algorithm in solving the vehicle routing problem is effective.

Keywords：genetic algorithm;vehicle;path problem

作者簡介