求解物流路徑優(yōu)化的改進(jìn)遺傳算法研究

張禮華，廖聞劍，彭艷兵

（1.武漢郵電科學(xué)研究院湖北武漢430074；2.烽火通信科技股份有限公司江蘇南京210019）

求解物流路徑優(yōu)化的改進(jìn)遺傳算法研究

張禮華1，2，廖聞劍2，彭艷兵2

（1.武漢郵電科學(xué)研究院湖北武漢430074；2.烽火通信科技股份有限公司江蘇南京210019）

為了解決傳統(tǒng)遺傳算法中易早熟和陷入局部最優(yōu)，造成收斂慢，效率低的問(wèn)題，提出了一種改進(jìn)的遺傳算法GBLSA（Genetic Based on Link_State A1gorithm）。對(duì)遺傳算法的基本算子進(jìn)行改進(jìn)，其中將鏈路狀態(tài)算法強(qiáng)大的尋優(yōu)能力融入交叉算子中，保證個(gè)體逐代進(jìn)化。引入與遺傳代數(shù)相關(guān)的自適應(yīng)概率，提高了遺傳算法的搜索效率和收斂速度。仿真實(shí)驗(yàn)表明，與傳統(tǒng)遺傳算法和TSPLIB標(biāo)準(zhǔn)值相比，提出的方法得到的結(jié)果路徑更優(yōu)，效率更高。

路徑優(yōu)化；遺傳算法；鏈路狀態(tài)算法；自適應(yīng)概率

隨著阿里巴巴在美國(guó)的成功上市，網(wǎng)絡(luò)購(gòu)物已成了人們?cè)絹?lái)越關(guān)注的話題，而物流配送業(yè)務(wù)在當(dāng)今這個(gè)網(wǎng)購(gòu)的生態(tài)圈內(nèi)起著舉足輕重的作用。作為一個(gè)企業(yè)追求利益毋庸置疑，因此通過(guò)對(duì)有限的資源進(jìn)行適當(dāng)?shù)恼{(diào)度和優(yōu)化，為客戶帶來(lái)更好的服務(wù)成了物流公司爭(zhēng)相討論的一個(gè)熱門話題。目前主流物流公司配送流程大都是將貨物發(fā)往各地分撥中心后進(jìn)行人力配送，一個(gè)快遞公司的總成本主要由人力配送成本決定。有效降低配送路徑的距離能提高人力配送的效率，這對(duì)于公司實(shí)現(xiàn)利益最大化有著極大的貢獻(xiàn)作用［2］。

物流配送問(wèn)題可概括為旅行商問(wèn)題（Trave1ing Sa1esman Prob1em，TSP），又叫貨郎擔(dān)問(wèn)題，人們通常采取借助大量的公式和約束條件去解決多項(xiàng)式時(shí)間內(nèi)可解決的問(wèn)題，所以被戲稱為“NP_hard”。對(duì)于這類問(wèn)題普遍通過(guò)尋求最優(yōu)解或者近似最優(yōu)解的方法來(lái)代替全局遍歷搜索求得最優(yōu)解［1］。目前對(duì)于該問(wèn)題的有效解決手段大體可分為兩類，一類是以仿生學(xué)算法為代表，諸如人工魚群算法、蛙跳算法、蟻群算法［2］、螢火蟲算法［3］等；另一類是以啟發(fā)式算法為代表，比如模擬退火算法［4］、遺傳算法［5_7］、免疫算法、禁忌搜素算法、爬山算法等。其中以遺傳算法為代表的全局搜索算法解決NP完全問(wèn)題效果顯著。

但傳統(tǒng)遺傳算法也存在收斂速度緩慢和容易陷入局部最優(yōu)解的問(wèn)題。為了加快遺傳算法的收斂速度和防止過(guò)早陷入最優(yōu)解情況的產(chǎn)生，本文提出了一種基于鏈路狀態(tài)算法的改進(jìn)遺傳算法GBLSA（Genetic Based on Link_State A1gorithm），將鏈路狀態(tài)算法（Link_State A1gorithm，LSA）強(qiáng)大的尋優(yōu)能力巧妙地融入遺傳算法的交叉算子中，不僅成功克服了鏈路狀態(tài)算法需要較大存儲(chǔ)空間的缺點(diǎn)，而且有效地解決了傳統(tǒng)遺傳算法慢收斂的問(wèn)題。并提出基于基因值的倒位算子和引入自定義的自適應(yīng)概率，對(duì)物流配送路徑優(yōu)化問(wèn)題進(jìn)行了深入探討和研究，并通過(guò)Mat1ab仿真進(jìn)行了實(shí)驗(yàn)和性能上的分析。同算例仿真不難發(fā)現(xiàn)，該算法在路徑優(yōu)化與時(shí)間上都取得了令人滿意的效果，大都提高了物流配送的工作效率，節(jié)省了經(jīng)營(yíng)成本，為企業(yè)創(chuàng)造了巨大的經(jīng)濟(jì)效益。

1　數(shù)學(xué)模型的建立

1.1路徑優(yōu)化問(wèn)題模型

物流配送路徑優(yōu)化問(wèn)題可描述為：從某配送中心通過(guò)多輛汽車將貨物送到多個(gè)客戶手中，每個(gè)客戶需求量和地理位置一定，汽車的載重量一定，要求合理安排汽車的行徑軌跡，使總的運(yùn)送距離最短。同時(shí)還應(yīng)滿足一下條件：

1）每條配送路徑上各需求點(diǎn)的需求量之和不超過(guò)汽車載重量；

2）每條配送距離長(zhǎng)度不超過(guò)汽車的最大行駛距離；

3）每個(gè)客戶的需求必須滿足且只能有一輛汽車完成配送任務(wù)。

由于多輛車的配送路徑優(yōu)化問(wèn)題可以按照一定的策略加以分解成單輛汽車的路徑優(yōu)化。通過(guò)求得單輛車的最短路徑，并加以組合就能得到整個(gè)物流配送路徑的最短距離。為了便于問(wèn)題更進(jìn)一步地討論與展開，本文將基于上述分析對(duì)單輛車的最短路徑優(yōu)化展開的討論與研究。

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

TSP問(wèn)題具體可以描述為：一個(gè)旅行商人即將拜訪n座城市，要求他先后通過(guò)這n座城市，并且每座城市有且只能經(jīng)過(guò)一次，最后再回到原來(lái)出發(fā)的那個(gè)城市。路徑選擇的要求是在滿足上述約束條件的情況下，選擇出所有符合條件的路徑中的最小路徑值。定義城市i和城市j之間的距離用d（i，j）表示，城市總數(shù)目為n，V包含所有城市的一個(gè)集合，即V=｛v1，v2，…，vn｝，則目標(biāo)路徑為：

約束條件為：

其中U是V的非空子集。

公式（2）表示當(dāng)該旅行商所走路線經(jīng)過(guò)包含城市i到城市j時(shí)變量fij=1，否則為0；公式（3）表明每座城市只能經(jīng)過(guò)一次；公式（4）要求該旅行商在任何一個(gè)城市子集中不能形成回路。

TSP問(wèn)題是一類組合優(yōu)化問(wèn)題，其可能路徑隨著城市數(shù)目的增多成指數(shù)型增長(zhǎng)，因此常常利用遺傳算法強(qiáng)大的尋優(yōu)能力來(lái)解決這一類問(wèn)題。

遺傳算法（Genetic A1gorithm，GA）是一種基于生物進(jìn)化中的自然選擇和優(yōu)勝劣汰的游戲規(guī)則所產(chǎn)生的一種啟發(fā)式算法。該算法通過(guò)每一代的適應(yīng)度（fitness）大小按照適者生存的原則從每一代中選出個(gè)體，并通過(guò)模擬生物進(jìn)化中基因雜交和變異的方式來(lái)產(chǎn)生下一代種群。遺傳算法在解決TSP問(wèn)題的運(yùn)算過(guò)程步驟如下：

1）初始化：設(shè)置此代進(jìn)化數(shù)g=0，最大進(jìn)化數(shù)為G，隨機(jī)產(chǎn)生初始種群P（g），種群中每個(gè)個(gè)體即表示一條路徑。

2）計(jì)算適應(yīng)度：計(jì)算種群P（g）中每個(gè)個(gè)體的值，即路徑總長(zhǎng)，取長(zhǎng)度的倒數(shù)值為該個(gè)體的適應(yīng)度值。

3）選擇運(yùn)算：按照步驟2中的方法通過(guò)選擇算子對(duì)種群P（g）進(jìn)行篩選，保證盡可能多地將適應(yīng)度高的個(gè)體保留，完成優(yōu)良基因的延續(xù)。

4）交叉運(yùn)算：對(duì)本代種群中任意兩個(gè)個(gè)體通過(guò)交叉算子產(chǎn)生兩個(gè)新的個(gè)體作為下一代的種群個(gè)體。

5）變異運(yùn)算：對(duì)種群中的個(gè)體串的基因通過(guò)變異算子作局部的變動(dòng)。

6）截止條件：如果g≤G，則返回步驟2），否則停止運(yùn)算。此時(shí)適應(yīng)度值最高的個(gè)體即為所求的最短路徑。

2　算法設(shè)計(jì)及改進(jìn)

2.1算法設(shè)計(jì)

2.1.1編碼的選擇和適應(yīng)度函數(shù)的確定

遺傳算法的編碼大體分為二進(jìn)制編碼和實(shí)數(shù)編碼。由于二進(jìn)制編碼在城市數(shù)過(guò)多的情況下會(huì)使數(shù)據(jù)冗長(zhǎng)，而且二進(jìn)制表示還會(huì)造成“漢明懸崖”的產(chǎn)生，因此本文采用實(shí)數(shù)編碼的形式。假設(shè)種群中的某一個(gè)體X的基因表現(xiàn)型為（3251647），數(shù)字i表示編號(hào)為i的城市，則該個(gè)體所表示含義為從編號(hào)為3號(hào)的城市出發(fā)，按照3→2→5→1→6→4→7的順序依次經(jīng)過(guò)各個(gè)城市，此表達(dá)方式更為直觀。

適應(yīng)度函數(shù)是評(píng)判一個(gè)個(gè)體好壞的標(biāo)準(zhǔn)。取fitness（X）= 1/F（X），由公式可求得個(gè)體X的路徑值F（X）。

2.1.2初始群體的選取

初始群體的選擇是遺傳算法中很重要的一環(huán)，初始群體的好壞直接影響著整個(gè)算法的收斂速度為了防止個(gè)體的好壞過(guò)于集中，造成種群個(gè)體極端化的產(chǎn)生，本文將首先隨機(jī)產(chǎn)生一個(gè)規(guī)模為初始種群3倍的初始種群集。假設(shè)初始種群個(gè)體個(gè)數(shù)為N，則初始種群集個(gè)數(shù)為3*N，對(duì)初始種群集的個(gè)體進(jìn)行量化排序，選出其中名次（N+1，2N）的N個(gè)體作為初始種群，一定程度上阻止了個(gè)體極端化的產(chǎn)生。

2.1.3選擇算子設(shè)定

為了使個(gè)體選擇相對(duì)均勻，采用一種新的選擇機(jī)制，具體操作如下：首先將種群中個(gè)體的按照適應(yīng)度值的大小進(jìn)行降序排列，如果兩個(gè)個(gè)體的適應(yīng)度值大小相同則順序任意。對(duì)排序好的N個(gè)體按照1，2，…，N的方式對(duì)排名第一的個(gè)體到排名最后的個(gè)體進(jìn)行編號(hào)。該編號(hào)作為個(gè)體新的適應(yīng)度值。則個(gè)體m被選擇的概率是：

2.1.4融合鏈路狀態(tài)算法的交叉算子

遺傳算法中起核心作用的是交叉算子，但單點(diǎn)交叉、多點(diǎn)交叉等交叉算子只是簡(jiǎn)單地將父代的基因進(jìn)行重新排列產(chǎn)生兩個(gè)新的子代，在豐富種群多樣性的同時(shí)無(wú)法保證子代的表現(xiàn)型一定要優(yōu)于父代，因此會(huì)造成慢收斂的現(xiàn)象產(chǎn)生。

鏈路狀態(tài)算法則是是每個(gè)參與鏈路狀態(tài)選路的路由器都具有一份完整的全網(wǎng)拓?fù)浣Y(jié)構(gòu)圖，通過(guò)拓?fù)鋱D可以得出與本節(jié)點(diǎn)距離最近的下一件點(diǎn)的位置，從而求出最短路徑。但該算法要求節(jié)點(diǎn)必須有完整的網(wǎng)絡(luò)拓?fù)湫畔?，因而造成?jì)算工作量巨大。本文將鏈路狀態(tài)算法強(qiáng)大的尋優(yōu)能力融入遺傳算法的交叉算子中，在彌補(bǔ)二者不足的同時(shí)也加快了收斂速度。設(shè)一個(gè)7座城市的距離矩陣如表1所示，父代個(gè)體A和B分別為（6574231）和（1372456），具體做法如下：

表1　7座城市的距離矩陣

步驟1：隨機(jī)選取一個(gè)交叉點(diǎn)的值為i作為子代a的第一位基因值，即a1=i；

步驟2：對(duì)父代A和B進(jìn)行遍歷，找到基因值為i的位置，假設(shè)父代A所在基因序列中的位置為m，父代B中為n，即Am=Bn=i；

步驟3：向右依次找到位于父代A和B中交叉點(diǎn)的下一個(gè)基因位置，比較d（Am，Am+1）和d（Bn，Bn+1）的大??；

步驟4：根據(jù)鏈路狀態(tài)算法中求最短路徑的方法求出子代a的第二位基因值，如果d（Am，Am+1）≤d（Bn，Bn+1），則a2=Am+1，如果d（Am，Am+1）＞d（Bn，Bn+1），則a2=Bn+1；

步驟5：假設(shè)現(xiàn)已確定a2=Am+1，把a(bǔ)2作為交叉點(diǎn)，重復(fù)步驟1到5，得到子代a；

步驟6：隨機(jī)選取一個(gè)交叉點(diǎn)的值為j（j≠i）作為子代b的第一位基因值，重復(fù)步驟1到5得到子代b。

由已知父代A和父代B的基因型，根據(jù)表1的距離矩陣表由公式（1）求得相應(yīng)的表現(xiàn)型為：F（A）=10+24+21+18+16+ 14=103，F(xiàn)（B）=14+17+31+18+23+10=113。

隨機(jī)選擇交叉點(diǎn)為1按照上述步驟求得子代a的基因型為（1374256），其表現(xiàn)型為：F（a）=14+17+21+18+11+10=91，不難發(fā)現(xiàn)其子代表現(xiàn)型優(yōu)于父代，加快了種群的收斂速度。

在該方法中鏈路狀態(tài)算法的整個(gè)搜索空間有原來(lái)的整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)縮減為現(xiàn)在的兩個(gè)父代個(gè)體，極大簡(jiǎn)化了每個(gè)城市需要存儲(chǔ)的信息量，同時(shí)通過(guò)交叉算子的實(shí)現(xiàn)使整個(gè)遺傳算法朝著最優(yōu)解的方向發(fā)展。

2.1.5基于基因值倒位的變異算子

變異算子在整個(gè)遺傳算法中的作用是改變某些個(gè)體的基因值，豐富種群的多樣性，防止未成熟收斂的出現(xiàn)。本文基于此目的提出了一種基于基因值倒位的變異算子。規(guī)定城市數(shù)為n，首先在1～n之間隨機(jī)選擇一個(gè)數(shù)q作為變異點(diǎn)，其次找到基因值為n+1_q的基因，將該基因與之前基因值為q的基因位置交換即完成變異操作。對(duì)于上述子代a而言，如果變異點(diǎn)為1，則變異后a′的基因型為（7314256），相應(yīng)的表現(xiàn)型為F（a′）=17+14+19+18+11+10=89。

該操作僅能極大豐富種群的多樣性，而且也有效避免了在實(shí)數(shù)編碼環(huán)境下，對(duì)于單一基因值進(jìn)行變異后造成基因值重復(fù)的情況。

2.1.6改進(jìn)自適應(yīng)概率的設(shè)定

從群體整個(gè)進(jìn)化過(guò)程看，在算法初期，由于隨機(jī)生成，適應(yīng)度值相對(duì)離散，這時(shí)交叉概率應(yīng)相對(duì)較高以便產(chǎn)生新的個(gè)體。在算法中后期，由于適應(yīng)度值逐漸趨于穩(wěn)定，最優(yōu)解也逐漸收斂，這時(shí)應(yīng)該降低交叉概率，以保證最優(yōu)解不會(huì)被破壞?；诖四康谋疚脑O(shè)計(jì)的與進(jìn)化代數(shù)相關(guān)的自適應(yīng)概率，其中交叉概率如下：

式中n表示最大迭代次數(shù)，x表示進(jìn)化代數(shù)，α∈（0，1］，一般為0.5。fmax為當(dāng)前種群最大適應(yīng)度值，favg為當(dāng)前種群平均適應(yīng)度值，f′為參與交叉操作的父代個(gè)體中較大的適應(yīng)度值。

變異概率如下：

式中β∈（0，1］，一般為0.01，f為參與變異的個(gè)體適應(yīng)度值。

2.2算法步驟

算法具體步驟如下：

步驟1：隨機(jī)產(chǎn)生規(guī)模為初始種群3倍的隨機(jī)種群，通過(guò)量化排序選出初始種群；

步驟2：通過(guò)公式（1）計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度函數(shù)值；

步驟3：由公式（5）計(jì)算種群中每個(gè)個(gè)體被選擇的概率，并借助輪盤賭的選擇機(jī)制選出相應(yīng)的個(gè)體；

步驟4：對(duì)選出的個(gè)體進(jìn)行交叉操作，交叉算子采用基于改進(jìn)的鏈路狀態(tài)算法，保證了算法收斂性的同時(shí)提高了算法效率；

步驟5：采用基于基因值倒位的變異算子對(duì)個(gè)體進(jìn)行變異操作，交叉和變異操作通過(guò)自適應(yīng)概率對(duì)個(gè)體進(jìn)行控制，保證優(yōu)質(zhì)個(gè)體進(jìn)入下一代；

步驟6：產(chǎn)生新一代種群，通過(guò)終止條件判斷算法是否終止，如果終止則轉(zhuǎn)入步驟7；反之，則轉(zhuǎn)入步驟2。

步驟7：輸出最短路徑值。

流程圖如圖1所示。

改進(jìn)后的遺傳算法流程圖如圖1所示，首先通過(guò)對(duì)初始種群進(jìn)行量化排序選出初始種群，利用公式計(jì)算每個(gè)個(gè)體被選擇的概率進(jìn)行選擇操作。然后通過(guò)改進(jìn)的交叉算子對(duì)個(gè)體進(jìn)行交叉操作。利用鏈路狀態(tài)算法強(qiáng)大的尋優(yōu)能力很好地保障了算法那的收斂性。利用基于基因值的倒位算子，極大地豐富了多樣性，破壞了遺傳算法容易陷入局部最優(yōu)解的局限性，更好地得到了理想值。

圖1　GBLSA算法流程圖

3　仿真驗(yàn)證與性能分析

為了更好的證明算法可行性和高效性，文中選用國(guó)際上通用的TSP測(cè)試庫(kù)中的多個(gè)實(shí)例來(lái)對(duì)算法進(jìn)行檢驗(yàn)。

實(shí)驗(yàn)中的參數(shù)設(shè)置為：最大遺傳代數(shù)G=200，種群大小popsize=50，交叉概率Pc和變異概率Pm有自適應(yīng)概率得出。

使用GBLSA算法那和傳統(tǒng)遺傳算法對(duì)TSPLIB中的實(shí)例ei176、o1iver30、rat99和rand75進(jìn)行仿真，經(jīng)過(guò)10測(cè)試后算得的最優(yōu)路徑值與TSPLIB提供的最優(yōu)路徑值進(jìn)行比較，對(duì)比情況見表2。

上述實(shí)例ei176、o1iver30、rat99和rand75經(jīng)本算法仿真后所得的最優(yōu)路徑圖如圖2～5所示。

從表2中的實(shí)驗(yàn)數(shù)據(jù)可以看出經(jīng)過(guò)GBLSA算法仿真所得出的最優(yōu)路徑值均優(yōu)于TSPLIB所提供的最優(yōu)路徑值，這也得益于改進(jìn)后的交叉算子強(qiáng)大的尋優(yōu)能力，加上改進(jìn)的自適應(yīng)概率，使得能在短時(shí)間內(nèi)尋找到最短路徑值。

表2　改進(jìn)遺傳算法、傳統(tǒng)遺傳算法與TSPLIB提供最優(yōu)路徑值比較表

圖2　實(shí)例ei176通過(guò)GBLSA得到的最優(yōu)路徑圖

圖3　實(shí)例o1iver30通過(guò)GBLSA得到的最優(yōu)路徑圖

圖4　實(shí)例rat99通過(guò)GBLSA得到的最優(yōu)路徑圖

圖5　實(shí)例rand75通過(guò)GBLSA得到的最優(yōu)路徑圖

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

通過(guò)對(duì)遺傳算法和鏈路狀態(tài)算法進(jìn)行了改進(jìn)，將兩種算法結(jié)合到一起，取長(zhǎng)補(bǔ)短，形成了一種基于鏈路狀態(tài)算法的改進(jìn)遺傳算法那（GBLSA）。該算法對(duì)遺傳算法中起關(guān)鍵作用的交叉算子改進(jìn)明顯，引入鏈路狀態(tài)算法中最短路徑優(yōu)先的原則來(lái)產(chǎn)生子代個(gè)體，大都提升了算法的收斂速度；對(duì)選擇算則進(jìn)行概率的重新定義，加大了優(yōu)質(zhì)個(gè)體存活率；提出基于基因值倒位的變異算子豐富了種群的多樣性。經(jīng)試驗(yàn)證明GBLSA算法的高效性，能更快更好地找到最優(yōu)解，有效地結(jié)局了傳統(tǒng)遺傳算法中易早熟、收斂慢、耗時(shí)長(zhǎng)等問(wèn)題。

同時(shí)本文也存在一些問(wèn)題。改進(jìn)自適應(yīng)概率中參數(shù)的選擇，以及在城市數(shù)目過(guò)大的情況下該算法的效率是否與小規(guī)模下的效率同樣優(yōu)秀，這些問(wèn)題都是值得未來(lái)進(jìn)一步研究的。

［1］Sun H.A Genetic A1gorithm for Trave11ing Sa1esman Prob-1ems［J］.Journa1 of Southwest Jiaotong University，2011（2）：25.

［2］孫力娟，王良俊，王汝傳.改進(jìn)的蟻群算法及其在TSP中的應(yīng)用研究［J］.通信學(xué)報(bào)，2004，25（10）：111_116.

［3］周永權(quán)，黃正新，劉洪霞.求解TSP問(wèn)題的離散型螢火蟲群優(yōu)化算法［J］.電子學(xué)報(bào)，2012，40（6）：1164_1170.

［4］王銀年，葛洪偉.求解TSP問(wèn)題的改進(jìn)模擬退火遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010（46）：44_47.

［5］Min H，Dazhi P，Song Y.An improved hybrid ant co1ony a1-gorithm and its app1ication in so1ving TSP［C］//Information Techno1ogy and Artificia1 Inte11igence Conference（ITAIC），2014：423_427.

［6］Ye C，Yang Z，Yan T.An efficient and sca1ab1e a1g_orithm for thetrave1ingsa1esmanprob1em［C］//20145thIEEE Internationa1ConferenceonSoftwareEngineeringand Service Science（ICSESS），2014：335_339.

［7］羅勇，陳治亞.基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化［J］.系統(tǒng)工程，2012（8）：118_122.

ZHANG Li_hua1，2，LIAO Wen_jian2，PENG Yan_bing2
（1.Wuhan Research Institute of Posts and Telecommunications，Wuhan 430074，China；2.FiberHome Telecommunication Technologies Co.，Ltd.Nanjing 210019，China）

the traditiona1 genetic a1gorithm exists the disadvantage of premature and easy to fa11 into a 1oca1 optimum，so it has 1ow convergence and 1ow efficiency.To address this prob1em，we propose an improved genetic a1gorithm GBLSA（Genetic Based on Link_State A1gorithm）.We improve the basic operation of genetic a1gorit_hm，the main method is making fu11 use of the abi1ity of 1ink_state a1gorithm for g1oba1 optimization of popu1ati_ons into cross_operation，aiming at improving the individua1 generation by generation.Introducing adaptive prob_abi1ity to further improve the searching efficiency and the speed of convergence.The experiment suggested that，GBLSA has better resu1ts and higher efficiency in comparison with traditiona1 genetic a1gorithm and the resu1ts of TSPLIB.

routing optimization；genetic a1gorithm；1ink_state a1gorithm；adaptive probabi1ity

TP301.6

A

1674_6236（2016）10_0013_04

2015_06_09稿件編號(hào)：201506089

國(guó)家863計(jì)劃資助項(xiàng)目（2012AA013002）

張禮華（1989—），男，湖北武漢人，碩士。研究方向：互聯(lián)網(wǎng)技術(shù)。

Research on lmProVed genetlc algorlthm for solVlng oPtlmlzatlon of loglstlcs dlstrlbutlon route