梁勤歐

(浙江師范大學(xué)地理與環(huán)境科學(xué)學(xué)院，浙江 金華 321004)

車輛路徑問題(vehicle routing problem，VRP)是指為服務(wù)于需求已知的一組客戶的車隊(duì)，設(shè)計從中心倉庫出發(fā)并返回的最小費(fèi)用路徑，約束條件包括客戶只能被服務(wù)一次，且車輛的載重能力有限［1］，或具有時間窗限制［2］等，并隨約束條件的拓展可以衍生出許多新的問題。VRP自從1959年由 DANTZIG 和 RAMSER［3］提出以來，迅速成為運(yùn)籌學(xué)、物流管理、交通規(guī)劃管理、地理區(qū)位等領(lǐng)域的研究熱點(diǎn)。VRP的研究屬于組合優(yōu)化中的NP難問題，即隨著問題的規(guī)模增加，計算機(jī)求解所耗費(fèi)的時間迅速增加。針對VRP的特點(diǎn)，國內(nèi)外學(xué)者引入各種優(yōu)化算法對其進(jìn)行求解，其中應(yīng)用較多的是各種智能算法，如遺傳算法［4-5］、進(jìn)化計算［6］等。

人工免疫系統(tǒng)(artificial immune system，AIS)是近年來興起的一種新的智能計算方法［7］。免疫系統(tǒng)的記憶功能(疫苗)常被作為遺傳算法種群更新中的一種機(jī)制而使用，以便改進(jìn)遺傳算法的性能［8］。傳統(tǒng)的遺傳算法在進(jìn)行VRP求解時，常出現(xiàn)在局部最優(yōu)解附近徘徊的問題［9-10］。應(yīng)用免疫系統(tǒng)與遺傳算法相結(jié)合的新算法進(jìn)行VRP的研究，因其吸收了兩種算法的優(yōu)點(diǎn)，在研究效率上比傳統(tǒng)的遺傳算法有所提高。筆者在實(shí)驗(yàn)研究VRP初期，采用了免疫記憶功能與信息熵相結(jié)合的免疫遺傳算法，結(jié)果出現(xiàn)計算量大且常早熟收斂的現(xiàn)象?；谝陨蠁栴}，筆者提出了一種改進(jìn)的免疫遺傳算法，并通過有能力約束的VRP實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

1 有能力約束VRP數(shù)學(xué)模型

有能力約束VRP一般描述為［11］:某一配送中心M(用i=0表示)有P輛車(p=1，2，…，P)，需要配送的客戶(或倉庫)為 N(i=1，2，…，N)個，每輛車的載重能力為 Bp(p=1，2，…，P)，客戶的需求為qi(i=1，2，…，N)，客戶之間以及客戶與配送中心的距離為 dij(i，j=1，2，…N)。VRP的優(yōu)化目標(biāo)是時間、距離和費(fèi)用等運(yùn)輸成本最小。筆者以運(yùn)輸距離最短構(gòu)造數(shù)學(xué)模型，首先定義變量如下:

則有能力約束的VRP數(shù)學(xué)模型如下:

其中:式(1)為目標(biāo)函數(shù);式(2)為車輛載重能力約束;式(3)～式(5)保證了每個客戶都被服務(wù)，且只有一輛車來完成任務(wù);式(6)為消除子回路;式(7)和式(8)為變量取值約束。

2 免疫遺傳算法的改進(jìn)

基于信息熵的免疫遺傳算法考慮了抗體濃度，并利用信息熵公式計算每個個體基因位置的信息熵大小，通過設(shè)定抗體濃度閾值來保證抗體的多樣性。許多學(xué)者利用該算法進(jìn)行了相關(guān)問題的研究，得到不錯的結(jié)果。但該算法的缺陷是運(yùn)行時間長，搜索速度較慢，且比較容易早熟收斂。為了克服這些缺點(diǎn)，筆者采用新的種群個體多樣性保持策略，提出一種改進(jìn)的免疫遺傳算法［12］。

改進(jìn)的免疫遺傳算法的計算過程如下:

(1)初始化種群。系統(tǒng)初始化為一組隨機(jī)解。

(2)計算所有個體的適應(yīng)度，并選擇出適應(yīng)值最好的兩個個體存入抗體記憶庫。

(3)對種群進(jìn)行遺傳算法操作。該操作包括選擇、交叉和變異等。

(4)更新抗體記憶庫。如果抗體記憶庫未滿，選擇最好的兩個新個體更新補(bǔ)充記憶庫;如果抗體記憶庫已滿，選擇最好的兩個新個體替換抗體記憶庫中最差的兩個個體。

(5)產(chǎn)生新種群。如果抗體記憶庫未滿，則抗體記憶庫替換同等數(shù)量種群中最差個體組成新種群;如果抗體記憶庫已滿，優(yōu)秀記憶抗體的數(shù)量越來越多，繼續(xù)循環(huán)下去，抗體種群很容易達(dá)到局部最優(yōu)，因此應(yīng)該檢查種群的多樣性程度(第(6)步)。如果抗體多樣性指數(shù)小于設(shè)定閾值，則隨機(jī)生成新種群，然后讓所有抗體記憶庫的個體替換新種群中同樣數(shù)量的最差個體，這樣既大量保留了歷代免疫遺傳運(yùn)算得到的優(yōu)秀個體，又在傳統(tǒng)優(yōu)勢個體中加入大批新生個體，新種群會在很大程度上避免局部最優(yōu)解的出現(xiàn);如果抗體多樣性指數(shù)大于設(shè)定閾值，則按照記憶庫未滿時的方式產(chǎn)生新種群。

(6)檢查所有個體的多樣性程度，個體多樣性程度用下式計算:

式中:H(i)為第i代種群的多樣性指數(shù);N為種群總個數(shù);K(i)為第i代種群的一致性約簡統(tǒng)計后的種群個數(shù)。具體計算方法為:在第i代種群中如果某個個體在種群中重復(fù)了多次，則該個體約簡統(tǒng)計為1個，依此類推，種群中總共有K(i)個完全不同的個體。

從式(9)中可看出，所有個體都不相同時，H(i)最大為1。只有一種個體時，H(i)為1/N，達(dá)到最小。隨著免疫遺傳進(jìn)化，優(yōu)秀個體的數(shù)量重復(fù)率越來越高，H(i)也隨著逐漸減小。這時設(shè)定H(i)的一個閾值，再對種群重新進(jìn)行多樣化操作。

(7)達(dá)到最大迭代次數(shù)則算法停止，最優(yōu)秀的個體即為最優(yōu)解;否則轉(zhuǎn)回第(3)步。

改進(jìn)的免疫遺傳算法的最大特點(diǎn)是保留了免疫記憶機(jī)制，采用新的種群多樣性程度的檢測方法，減少了檢測抗體之間親和力的步驟。其計算量比傳統(tǒng)的基于信息熵的免疫遺傳算法大大減小。

3 能力約束VRP問題求解

根據(jù)上述改進(jìn)的免疫遺傳算法，給出了如圖1所示的應(yīng)用該算法解決有能力約束VRP問題的流程圖。

圖1 改進(jìn)免疫遺傳算法求解VRP的算法流程圖

(1)配送系統(tǒng)基本數(shù)據(jù)輸入?；緮?shù)據(jù)包括配送系統(tǒng)客戶與中心倉庫的坐標(biāo)或距離值、車輛載質(zhì)量和客戶運(yùn)輸需求量等，也包括改進(jìn)免疫遺傳算法的參數(shù)初始設(shè)置，如交叉率、變異率、記憶庫容量參數(shù)、迭代次數(shù)和種群個數(shù)等。

(2)隨機(jī)生成種群。針對VRP有不同的編碼方式生成種群，筆者分別采取兩種編碼方案進(jìn)行實(shí)驗(yàn)。第1種為客戶隨機(jī)排列方式，如有8個客戶，則隨機(jī)排列為1～8之間的整數(shù);第2種為整數(shù)編碼方式隨機(jī)生成車輛分配方式，如兩輛車8個客戶，則整數(shù)隨機(jī)排列為1～16之間的整數(shù)。每輛車最多可以服務(wù)的客戶數(shù)就是總客戶數(shù)。

(3)車輛能力約束評估。對隨機(jī)生成的種群個體進(jìn)行車輛能力的約束評估，對于第1種編碼方式，依次判斷排列車輛需求是否超出車輛載質(zhì)量限制，如超出則換另外一輛車;不滿足則為不可行解，通過懲罰的方式來盡快淘汰不可行個體。對于第2種編碼，首先確定客戶與路徑的關(guān)系，然后判斷客戶需求是否滿足，在車輛載重能力的約束下分配客戶。如所有客戶需求得到滿足，則種群個體形成一個可行解;若不滿足，則產(chǎn)生的個體是不可行解，通過懲罰的方式來盡快淘汰該個體。

(4)種群中抗體與抗原之間的親和力適應(yīng)值計算與評估?？贵w與抗原之間的親和力可以直接應(yīng)用可行解的路徑總和表示。由于有能力約束VRP是求總目標(biāo)的最小值，為了程序設(shè)計方便，用總路徑的倒數(shù)表示抗體與抗原之間的親和力，即F=1/f，這樣，程序的目標(biāo)值就轉(zhuǎn)化為求最大值問題，不可行解懲罰為最小實(shí)數(shù)。

(5)抗體記憶庫初始化?？贵w記憶庫大小由種群個體的多少決定，一般設(shè)定為種群大小的20%～40%。記憶庫每次從種群中選擇最好的兩個個體進(jìn)行存儲?？贵w記憶庫初始化是從初始化種群中選擇抗體抗原親和力適應(yīng)值最好的兩個個體進(jìn)行存儲。

(6)種群選擇。按照抗原與抗體之間的親和力選擇進(jìn)行遺傳操作的個體一般采用輪盤賭的方式進(jìn)行。

(7)交叉變異產(chǎn)生新種群。對選擇出的個體采取循環(huán)交叉［13］的方法產(chǎn)生新的種群再以變異率為選擇機(jī)制，對每個個體進(jìn)行隨機(jī)點(diǎn)變異，產(chǎn)生新的種群。

(8)車輛能力約束評估、親和力適應(yīng)值評估。對遺傳操作后產(chǎn)生的種群再進(jìn)行種群個體車輛能力的約束評估。對于不可行解，同樣通過懲罰的方式將其淘汰。計算新種群的適應(yīng)值和親和力。

(9)更新抗體記憶庫。如果抗體記憶庫未滿，更新補(bǔ)充記憶庫;如果抗體記憶庫已滿，選擇最好的兩個新個體替換抗體記憶庫中最差的兩個個體。

(10)抗體記憶庫未滿，則抗體記憶庫已有n個記憶抗體代替遺傳操作后產(chǎn)生的新種群的前n個個體，從而組成新的種群。

(11)抗體記憶庫已滿時，首先，選擇最好的兩個新個體更新抗體記憶，然后進(jìn)行多樣性檢測。如果抗體多樣性指數(shù)小于設(shè)定閾值，則隨機(jī)生成新種群，抗體記憶庫和隨機(jī)生成新種群重新組合成一個種群;如果抗體多樣性指數(shù)大于設(shè)定閾值，則同步驟(10)。

(12)達(dá)到最大代數(shù)。如果達(dá)到設(shè)定的最大迭代次數(shù)則停止;否則，在新產(chǎn)生的種群中重新開始選擇、遺傳等操作。

4 實(shí)驗(yàn)研究

選用文獻(xiàn)［5］中的配送系統(tǒng)，該配送系統(tǒng)中8個客戶分別表示8個分倉庫，另外有1個中心倉庫。車輛限制為兩輛，每輛車的載質(zhì)量為8 t。表1中“0”代表中心倉庫，其余表示中心倉庫與客戶之間的單位距離。

筆者分別應(yīng)用兩種編碼方案進(jìn)行實(shí)驗(yàn)研究。編碼1為客戶隨機(jī)排列方式，編碼2為車輛分配方式。

遺傳算法的參數(shù)設(shè)定分別為:初始種群數(shù)量為50;交叉率pc=0.5;變異率pm=0.4;停止迭代次數(shù)為100。

表1 中心倉庫、客戶與客戶之間的單位距離

客戶運(yùn)輸需求量如表2所示。

表2 客戶運(yùn)輸需求量

免疫遺傳算法的參數(shù)設(shè)定分別為:初始種群數(shù)量為50;交叉率pc=0.5;變異率pm=0.4;抗體記憶庫容量為RM=20;抗原抗體調(diào)節(jié)系數(shù)分別為a=0.7，b=0.2;停止迭代次數(shù)為100。

改進(jìn)免疫遺傳算法的參數(shù)設(shè)定分別為:初始種群個體為50;交叉率pc=0.5;變異率pm=0.4;抗體記憶庫容量為RM=20;多樣性閾值h=0.2;停止迭代次數(shù)為100。

實(shí)驗(yàn)最優(yōu)解為67.5。路徑排列次序?yàn)?—6—7—4—0;0—2—8—5—3—1—0。

圖2為改進(jìn)免疫遺傳算法求解實(shí)驗(yàn)數(shù)據(jù)的一次結(jié)果?？梢钥闯觯?1代就達(dá)到了最優(yōu)值，解的搜索也比較穩(wěn)定。

圖2 改進(jìn)免疫遺傳算法求解VRP適應(yīng)值變化

表3列出了針對實(shí)例問題兩種編碼方案，采用3種不同算法進(jìn)行50次隨機(jī)試驗(yàn)的統(tǒng)計結(jié)果。從搜索成功率和最優(yōu)解平均值可以看出，不管使用哪種編碼方式，改進(jìn)免疫遺傳算法的計算效率都是最優(yōu)的，特別是在采用第1種編碼方案時，改進(jìn)免疫遺傳算法搜索最優(yōu)解的成功率為100%。因此，筆者改進(jìn)的免疫遺傳算法在解決有能力約束VRP中是成功的。

表3 幾種算法結(jié)果比較

5 結(jié)論

人工免疫系統(tǒng)作為一種新興算法，其應(yīng)用領(lǐng)域需要進(jìn)一步拓寬。選取VRP這個組合優(yōu)化難題進(jìn)行了實(shí)驗(yàn)研究，說明人工免疫系統(tǒng)算法的優(yōu)勢還是明顯的。VRP隨約束條件的拓展所產(chǎn)生的許多新問題也逐漸引起許多學(xué)者的重視，如大規(guī)模 VRP、有時間窗的 VRP［14］等，是下一步研究工作的重點(diǎn)。

［1］BODIN L，GOLDEN B，ASSAD A，et al.Routing and scheduling of vehicles and crew:the state of the art［J］.Computers and Operations Researth，1983，10(2):63-212.

［2］KOLEN A W J，RINNOOY KAN A H G.Vehicle routing with time windows［J］.Operations Research，1987，35(2):266-273.

［3］DANTZIG G B，RAMSER J H.The truck dispatching problem［J］.Management Science，1959，4(6):80-91.

［4］CHENG R，GEN M.Fuzzy vehicle routing and scheduling problem using genetic algorithms［M］.［S.l.］:Spinger-Verlag，1996:683-709.

［5］姜大立，楊西龍.車輛路徑的遺傳算法研究［J］.系統(tǒng)工程理論與實(shí)踐，1999(6):40-44.

［6］趙燕偉，彭典軍.有能力約束車輛路徑問題的量子進(jìn)化算法［J］.系統(tǒng)工程理論與實(shí)踐，2009(2):159-166.

［7］DE CASTRO L N，VON ZUBEN F J.Artificial immune systems:basic theory and applications［R］.Campinas:State University of Campinas，1999.

［8］焦李成，杜海峰.免疫優(yōu)化計算、學(xué)習(xí)與識別［M］.北京:科學(xué)出版社，2006:59-90.

［9］郎茂祥.配送車輛優(yōu)化調(diào)度模型與算法［M］.北京:電子工業(yè)出版社，2009:68-103.

［10］CHUN J，KIM M，JUN H.Shape optimization of electromagnetic devices using immune algorithm［J］.IEEE Transactions on Magnetics，1997，33(2):1876-1879.

［11］梁勤歐.人工免疫系統(tǒng)與GIS空間分析應(yīng)用［M］.武漢:武漢大學(xué)出版社，2011:235-236.

［12］梁勤歐，周曉艷.基于免疫遺傳算法的設(shè)備布局問題研究［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2011，33(4):643-646.

［13］OLIVER I M，SMITH D J，HOLLAND J R C.A study of permutation crossover operators on the traveling salesman problem［C］//Proceedings of the Second International Conference on Genetic Algorithm.New Jersey:［s.n.］，1987:224-230.

［14］黃樟燦，蔣文霞，李書淦.有時間窗車輛路徑問題的混合算法［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2008，30(1):48-51.