多級(jí)正向變異的遺傳算法提高求解VRP問(wèn)題效率

胡中棟，謝金偉

（江西理工大學(xué)信息工程學(xué)院，江西贛州341000）

多級(jí)正向變異的遺傳算法提高求解VRP問(wèn)題效率

胡中棟，謝金偉

（江西理工大學(xué)信息工程學(xué)院，江西贛州341000）

應(yīng)用遺傳算法對(duì)車輛路徑問(wèn)題（VRP）求解時(shí)，由于遺傳算法在解決VRP問(wèn)題時(shí)，交叉操作難以保留優(yōu)秀基因片段，可能導(dǎo)致算法收斂較慢等問(wèn)題.在一定程度上影響了遺傳算法解決VRP問(wèn)題的實(shí)用性.在前人的基礎(chǔ)上，通過(guò)一種多級(jí)正向變異方法，使變異最大程度向好的方向進(jìn)行，拆除基因片段中較差的基因連接并建立新基因連接，從而得到較優(yōu)的新基因片段，重復(fù)一定的變異次數(shù)，讓變異達(dá)到最優(yōu)效果.通過(guò)實(shí)驗(yàn)表明多級(jí)正向變異明顯提高了遺傳算法解決此類問(wèn)題的效率.

車輛調(diào)度；遺傳算法；多級(jí)正向變異；基因片段；算法設(shè)計(jì)

0 引言

車輛路徑問(wèn)題（VRP）是1959年由Dantzig和Ramser首次提出，它是指一定數(shù)量的客戶，各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由一個(gè)車隊(duì)負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足，并能在一定的約束下，達(dá)到如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的[1].旅行商問(wèn)題是VRP的特例，Gaery[2]已證明TSP問(wèn)題是NP難題，所以VRP也屬于NP難題，已經(jīng)有多種方法來(lái)求解VRP問(wèn)題[3-9]，但啟發(fā)式算法成為車輛運(yùn)輸問(wèn)題求解的主要方法.遺傳算法是其中一種方法，遺傳算法是一類借鑒生物界的進(jìn)化規(guī)律演化而來(lái)的隨機(jī)化搜索方法.

應(yīng)用遺傳算法解決車輛路線問(wèn)題（VRP）時(shí)，發(fā)現(xiàn)遺傳算法進(jìn)行交叉操作時(shí)易破壞原來(lái)較好的基因片段[10]，從而導(dǎo)致算法效率降低.基于以上事實(shí)

提出多級(jí)正向變異的方法來(lái)提高效率.

1 車輛路徑問(wèn)題描述

設(shè)車輛的數(shù)量為M（m=1,2,…,M），單個(gè)車的容量為w.客戶的個(gè)數(shù)為N,需求量為pi（i=1,2,…,N），且pi≤w.頂點(diǎn)集合為V={1,2,…,N}.用cij表示i點(diǎn)到j(luò)（j=1,2,…,N）的運(yùn)輸距離.xijm=1表示車輛m由客戶i行駛到客戶j，xijm=0表示車輛m沒(méi)有經(jīng)過(guò)這條路徑.yim=1表示客戶i的任務(wù)由車輛m來(lái)完成，yim=0則表示客戶i的任務(wù)不由車輛m完成.

車輛調(diào)度的路徑優(yōu)化問(wèn)題可建立數(shù)學(xué)模型[11]如下：

1）所有車輛以相同的起點(diǎn)同時(shí)向客戶運(yùn)輸貨物互不干擾.

2）車輛路徑問(wèn)題（VRP）的目標(biāo)函數(shù)可定義為：

3）每一條路徑上各個(gè)客戶所需要的貨物總重量不超過(guò)單輛車的載重量.

4）每個(gè)客戶的需求只能讓一輛車來(lái)完成，并且所有任務(wù)由K輛車完成.

5）每一個(gè)客戶只能被一輛車服務(wù)一次.

2 多級(jí)正向變異遺傳算法基本思想與設(shè)計(jì)

2.1 基本思想

由于遺傳算法解決VRP問(wèn)題時(shí)存在編碼問(wèn)題，使得交叉操作可能無(wú)法保留優(yōu)秀基因片段[10].針對(duì)因此而導(dǎo)致的算法效率較低的問(wèn)題，經(jīng)過(guò)算法分析與大量實(shí)驗(yàn)，提出利用多級(jí)正向變異的算法來(lái)提高解決VRP問(wèn)題的效率.分析了傳統(tǒng)遺傳算法的變異過(guò)程，提出了改進(jìn)為多級(jí)正向變異的方法.

1）自然界中的交叉操作是基因片段的重組，在解決VRP問(wèn)題時(shí)的染色體交叉基因片段后，還需刪除染色體中重復(fù)的基因.因此交叉操作有時(shí)可能會(huì)破壞原來(lái)相對(duì)較優(yōu)的局部基因.從而造成遺傳算法解決本問(wèn)題時(shí)表現(xiàn)出不穩(wěn)定并且收斂較慢的特點(diǎn).

自然界中的變異是隨機(jī)的，如果變異向壞的方向進(jìn)行，就會(huì)產(chǎn)生更差的個(gè)體.差的個(gè)體將被淘汰，使問(wèn)題達(dá)到最優(yōu)解就要增加進(jìn)化代數(shù).在解決實(shí)際問(wèn)題時(shí)，如果能通過(guò)某種簡(jiǎn)單的方法讓變異盡可能向好的方向發(fā)展，那么進(jìn)化的速度將加快，能夠更快的收斂到全局最優(yōu)解.

2）多級(jí)正向變異思想用以解決上述問(wèn)題，具體問(wèn)題是交叉操作導(dǎo)致優(yōu)秀基因片段難以保留，而用多級(jí)正向變異的思想可以讓變異盡可能多的向好的方向發(fā)展，減少進(jìn)化代數(shù)，更快收斂到全局最優(yōu)解.

多級(jí)正向變異的方法是在變異之前檢查染色體中基因片段，如果該基因片段較差，則進(jìn)行變異，隨機(jī)生成新的基因片段；如果該基因片段較好，則不變異；對(duì)染色體重復(fù)合適的變異次數(shù)，使得變異的效果最好.變異產(chǎn)生更優(yōu)染色體的概率大，且染色體的質(zhì)量更高.這樣，變異就最大可能性向好的方向發(fā)展了.

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

應(yīng)用遺傳算法解決VRP問(wèn)題時(shí)要進(jìn)行編碼、選擇、交叉和變異等操作.

1）編碼采用客戶序號(hào)（序號(hào)是自然數(shù)1~L，L為客戶數(shù)）的十進(jìn)制編碼方法.這種表示方法是直接產(chǎn)生L個(gè)1~L間的互不重復(fù)的自然數(shù)的排列，該客戶排列就構(gòu)成一個(gè)解，并對(duì)應(yīng)一種配送路徑方案.設(shè)客戶排列（染色體）為41287635，設(shè)兩輛車可以完成配送，每輛車為4個(gè)客戶配送貨物，則配送路線為第一輛車：0→4→1→2→8→0，第二輛車：0→7→6→3→5→0（其中0表示起始點(diǎn)）[12].

2）適應(yīng)度計(jì)算方法采用某條染色體的配送方案中要經(jīng)過(guò)的客戶點(diǎn)（或起始點(diǎn)）之間的路徑長(zhǎng)度之和的倒數(shù)為其個(gè)體的適應(yīng)值，設(shè)個(gè)體的適應(yīng)值為f1=1/z（z為車輛所需行走路程的總和）[12].

3）選擇操作采用輪盤賭的方式，首先計(jì)算種群中每個(gè)個(gè)體在該種群中的相對(duì)適應(yīng)值隨機(jī)生成一個(gè)[0，1]之間的數(shù)a，如果p1+…+pi-1

4）交叉采用順序交叉法，開始選擇一個(gè)匹配區(qū)域，設(shè)兩父代個(gè)體及其匹配區(qū)域（設(shè)第3到第5基

因位，如A中的‘128’)為：A=34|128|765、B=52|847| 613；將兩父代的匹配區(qū)域移動(dòng)到對(duì)方的末尾得到A′=34|128|765847、B′=52|847|613128；去除原染色體中與A′和B′相同的數(shù)字得到新一代的染色體A′′=31265847、B′′=54763128.

5）傳統(tǒng)變異方法與多級(jí)正向變異方法對(duì)比.傳統(tǒng)變異為在同一個(gè)染色體內(nèi)隨機(jī)選取兩個(gè)不同客戶（基因）或多個(gè)客戶進(jìn)行交換或者插入到其他地方.例如將A=47856321的第二個(gè)客戶“7”和最后一個(gè)客戶“1”交換得到新的染色體B=41856327.

當(dāng)Ci>Li時(shí)，則將i基因位處的客戶移動(dòng)到染色體末端，將i基因位標(biāo)記為0，然后到i+2基因位處繼續(xù)比較.當(dāng)Ci≤Li時(shí)不進(jìn)行任何操作，直接到i+1基因位處進(jìn)行比較.重復(fù)以上操作直到染色體的最后一個(gè)客戶，最后將標(biāo)記為0的地方去掉，將客戶（基因）順序向前平移，得到新的染色體.

對(duì)每一條染色體重復(fù)上述過(guò)程一定的次數(shù)（通過(guò)實(shí)驗(yàn)確定次數(shù)），使得變異達(dá)到最優(yōu)效果.

假設(shè)任一客戶到其他客戶之間的距離符合標(biāo)準(zhǔn)正態(tài)分布，單輛車來(lái)完成所有任務(wù)，f[i]表示i基因位的客戶與i-1基因位處客戶的連接.由標(biāo)準(zhǔn)正態(tài)分布的特點(diǎn)可知，Pm為標(biāo)準(zhǔn)正態(tài)分布的路徑長(zhǎng)度的期望，則隨機(jī)兩個(gè)客戶間的距離有50%的概率大于Pm，有50%的概率小于Pm.若以Pm來(lái)作為標(biāo)準(zhǔn)，則如果連接長(zhǎng)度比Pm大就認(rèn)定為較差連接，比Pm小則認(rèn)定為較優(yōu)連接.可假設(shè)新形成的連接有50%是較優(yōu)的，50%是較差的.本算法雖然會(huì)少量增加單代進(jìn)化需要的時(shí)間，卻能較大幅度減少收斂的代數(shù)和收斂時(shí)間.

以10客戶點(diǎn)為例，圖1~圖4中圓圈表示客戶點(diǎn)，帶箭頭的線表示線的起始點(diǎn)客戶到終點(diǎn)客戶之間的連接，五角星表示染色體連接中的較優(yōu)連接，下方的數(shù)字表示染色體中的連接序號(hào)（即有向線段），假設(shè)原始染色體如圖1所示.

圖1 原始染色體

一級(jí)正向變異后如圖2所示.

圖2 一級(jí)正向變異后染色體

二級(jí)正向變異后如圖3所示.

圖3 二級(jí)級(jí)正向變異后染色體

三級(jí)正向變異后如圖4所示.

圖4 三級(jí)正向變異后染色體

綜上所示，可以看到經(jīng)過(guò)多級(jí)正向變異，10客戶點(diǎn)的染色體已經(jīng)很可能接近最優(yōu)解.上述過(guò)程是單染色體特例，對(duì)一個(gè)群體來(lái)說(shuō)這個(gè)過(guò)程會(huì)更長(zhǎng)，一定級(jí)數(shù)正向變異后將不能繼續(xù)優(yōu)化染色體.

表1 各客戶對(duì)貨物的需求量/t

3 仿真實(shí)驗(yàn)

實(shí)驗(yàn)的環(huán)境：i5cpu筆記本電腦，8GB內(nèi)存.在虛擬機(jī)（VMware）中安裝2GB內(nèi)存、單核cpu的ubuntu12.04系統(tǒng).用C語(yǔ)言編寫程序，數(shù)據(jù)分析與作圖在R語(yǔ)言軟件平臺(tái)進(jìn)行.

設(shè)Vi代表客戶i,Qi表示Vi對(duì)貨物的需求量，V0為起始點(diǎn)，則各客戶對(duì)貨物的需求量如表1所示.

各個(gè)客戶間的距離如表2所示.

實(shí)驗(yàn)取客戶數(shù)為10，初始隨機(jī)產(chǎn)生數(shù)目為1000的種群，交叉長(zhǎng)度為5，交叉概率為0.8，變異概率選擇1（經(jīng)實(shí)驗(yàn)確定），每輛車的最大載重量設(shè)為10 t，且車的數(shù)量不限.采用傳統(tǒng)遺傳算法與改進(jìn)的多級(jí)正向變異遺傳算法求解，在成功求解的概率都為98%以上的情況下，比較成功求解所用計(jì)

算的平均代數(shù)和平均所用時(shí)間（通過(guò)預(yù)先設(shè)定合理固定進(jìn)化代數(shù)，傳統(tǒng)變異設(shè)為1000，多級(jí)正向變異設(shè)為100，算法自動(dòng)記錄每一次成功求解所需代數(shù)和時(shí)間來(lái)實(shí)現(xiàn)）.實(shí)驗(yàn)的數(shù)據(jù)均為運(yùn)行程序1000次的平均結(jié)果.從圖5與圖6可知改進(jìn)的多級(jí)正向變異遺傳算法優(yōu)勢(shì)較明顯.

表2 各個(gè)客戶間的距離/km

圖5 變異級(jí)數(shù)成功求解所需代數(shù)關(guān)系圖

圖6 變異級(jí)數(shù)成功求解所需時(shí)間關(guān)系圖

設(shè)變異級(jí)數(shù)為K（K為0代表傳統(tǒng)變異），傳統(tǒng)變異平均成功求解代數(shù)為OG，平均成功求解時(shí)間為OT.多級(jí)正向變異平均成功求解代數(shù)為NG.平均成功求解時(shí)間為NT.表3為不同變異級(jí)數(shù)和平均得到最優(yōu)結(jié)果所用計(jì)算代數(shù)的關(guān)系，表4為變異級(jí)數(shù)與平均得到最優(yōu)結(jié)果所用時(shí)間關(guān)系.由于表格寬度的限制，在表1與表2中省略了P=2、4、6、8、10時(shí)的計(jì)算結(jié)果.圖5、圖6中的小圓圈連接的曲線表示傳統(tǒng)變異的遺傳算法運(yùn)算結(jié)果，三角形連接的曲線表示本文設(shè)計(jì)的正向變異遺傳算法的運(yùn)算結(jié)果.

可以看到當(dāng)變異級(jí)數(shù)為0時(shí)，即采用傳統(tǒng)的變異方法求解時(shí)，收斂速度非常慢，成功求解所需的代數(shù)和時(shí)間都比較大.而采用本文設(shè)計(jì)的多級(jí)正向變異算法時(shí)，算法效率有較大幅度的提高，原因就在于設(shè)計(jì)的算法充分的利用了數(shù)據(jù)內(nèi)部的聯(lián)系，使得遺傳算法向較合理的方向進(jìn)行進(jìn)化.通過(guò)實(shí)驗(yàn)表明，當(dāng)采用多級(jí)正向變異算法時(shí)，僅在1級(jí)的情況下，提高的幅度已經(jīng)非常明顯，在8級(jí)變異時(shí)，算法的效率最高，找到最優(yōu)解僅需要0.022 s，而傳統(tǒng)變異方法則需要0.21 s左右.

表3 變異級(jí)數(shù)成功求解所需代數(shù)關(guān)系

表4 變異級(jí)數(shù)成功求解所需時(shí)間關(guān)系

4 總結(jié)

經(jīng)過(guò)10客戶數(shù)不同正向變異級(jí)數(shù)情況下問(wèn)題求解效率的分析，可以確定多級(jí)正向變異的方法對(duì)VRP問(wèn)題的改進(jìn)效果是非常明顯的.多級(jí)正向變異方法可以最大程度的減少隨機(jī)變異產(chǎn)生的較差結(jié)果所多耗費(fèi)的時(shí)間和資源，從而提高遺傳算法求解VRP問(wèn)題的效率.

[1]Paolo Toth，Daniele Vigo.The vehicle routing problem[M].Beijing: Tsinghua university Press,2011.[2]祝崇俊,劉民,吳澄.供應(yīng)鏈中車輛路徑問(wèn)題的研究進(jìn)展及前景[J].計(jì)算機(jī)集成制造系統(tǒng)，2001,7(11):1-6.

[3]Christofides N,Mingozzi A,Toth P.Exact algorithms for the vehicle routing problem,based on spanning tree and shortest path relaxations[J].Mathematical Programming,1981,20(1):255-282.

[4]Achuthan N,Caccetta L,Hill S.An improved branch-and-cut algorithmforthecapacitatedvehicleroutingproblem[J]. Transportation Science,2003,37(2):153-169.

[5]張麗萍，柴躍廷，曹瑞．有時(shí)間窗車輛路徑問(wèn)題的改進(jìn)遺傳算法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2002，8(6)：451-454．

[6]宋厚冰，蔡遠(yuǎn)利．帶時(shí)間窗的車輛路徑混合遺傳算法[J]．交通運(yùn)輸工程學(xué)報(bào)，2003，3(4)：112-115．

[7]Ball M O,Golden B L,Assad A A,et a1.Planning for truck fleet size in the presence of a common carrier operation[J].Decision Sciences,1983,14(1):103-120.

[8]趙燕偉，吳斌，蔣麗，等．車輛路徑問(wèn)題的雙種群遺傳算法求解方法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2004，10(3)：303-306．

[9]肖健梅，李軍軍，王錫淮．求解車輛路徑問(wèn)題的改進(jìn)微粒群優(yōu)化算法[J]．計(jì)算機(jī)集成制造系統(tǒng)，2005，11(4)：577-581．

[10]鄔開俊,王鐵君.基于改進(jìn)差分進(jìn)化的車輛路徑優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(13)：17-20.

[11]張瑞鋒,汪同三.新型遺傳算法求解車輛路徑問(wèn)題研究[J].湖北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，34(2)：239-242.

[12]郎茂祥.物流配送車輛調(diào)度問(wèn)題的模型和算法研究[D].北京：北方交通大學(xué)，2002.

[13]王曉博,李一軍.多車型單配送中心混合裝卸車輛路徑問(wèn)題研究[J].系統(tǒng)工程學(xué)報(bào)，2010，25(5)：629-636.

Multi-level forward mutation genetic algorithm to improve the efficiency for VRP

HU Zhongdong，XIE Jinwei
(School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou 341000,China)

When using genetic algorithm to solve VRP problem,a slower convergence problem may be generated because the crossover operation could not keep good genes,which affects the usefulness of genetic algorithms to solve the VRP problem to a certain extent.On the basis of our predecessors,we have created a multi-level forward mutation method which dismantles poor gene fragment connection and creates a new connection to get a better gene.A large number of experiments show that forward mutation can greatly improve the genetic algorithm to solve such problems efficiently.

vehicle scheduling;genetic algorithm;multi-level forward mutation;gene fragment;algorithm design

TP301.6

A

2014-07-15

胡中棟（1958-），男，教授，主要從事智能計(jì)算和無(wú)線傳感器網(wǎng)絡(luò)等方面的研究，E-mail：jxhzd@163.com.

2095-3046（2014）05-0069-04

10.13265/j.cnki.jxlgdxxb.2014.05.013