基于雙種群混合遺傳算法的車輛調(diào)度問(wèn)題研究

胡云清 （山西交通職業(yè)技術(shù)學(xué)院，山西 太原030031）

HU Yun-qing (Shanxi Traffic Vocational and Technical College, Taiyuan 030031, China)

0 引 言

物流活動(dòng)作為企業(yè)的“第三方利潤(rùn)源泉”，在提高企業(yè)經(jīng)濟(jì)效益、降低企業(yè)成本等方面發(fā)揮著重要作用。而車輛路徑優(yōu)化作為企業(yè)物流活動(dòng)的關(guān)鍵，更是廣受學(xué)者們的關(guān)注[1]。特別是在配送成本較高、嚴(yán)重影響企業(yè)生存發(fā)展和城市交通擁堵越來(lái)越嚴(yán)重的情況下，通過(guò)對(duì)企業(yè)車輛配送路徑的優(yōu)化，降低企業(yè)配送成本、緩解城市交通擁堵，更是意義重大。

分析現(xiàn)有相關(guān)文獻(xiàn)可知，車輛路徑優(yōu)化問(wèn)題的求解算法可以分為精確算法和近似算法。精確算法指能夠求出全局最優(yōu)解的算法，而近似求解算法則無(wú)法求出問(wèn)題最優(yōu)解、只能求得最優(yōu)解的近似值[2]。由于精確算法的計(jì)算量會(huì)隨著問(wèn)題規(guī)模的增大而呈指數(shù)增長(zhǎng)，所以它在實(shí)際問(wèn)題中應(yīng)用較為有限。相比之下，對(duì)于近似算法的研究更為廣泛。其中遺傳算法由于具有搜索空間較大、求解精度較高等優(yōu)點(diǎn)，更是倍受學(xué)者的青睞。如文獻(xiàn)[3-5]均對(duì)車輛路徑問(wèn)題的遺傳算法進(jìn)行了研究。但傳統(tǒng)遺傳算法也存在著容易陷入局部最優(yōu)解、收斂速度較慢等問(wèn)題，影響著算法的求解性能。對(duì)此，本文對(duì)傳統(tǒng)遺傳算法進(jìn)行了改進(jìn)，提出了求解車輛路徑優(yōu)化問(wèn)題的雙種群混合遺傳算法。

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

車輛路徑優(yōu)化問(wèn)題一般可以描述為：企業(yè)配送中心需要用多輛車輛完成不同客戶點(diǎn)的需求配送任務(wù)。配送中心位置已知，客戶點(diǎn)需求量和位置信息已知，每輛車的載重量一定，且具有載重約束，即車輛所載貨物不能超過(guò)車輛最大載重量，要求合理規(guī)劃車輛行駛路徑，使車輛總行駛距離最短，同時(shí)必須滿足如下幾個(gè)條件：（1） 企業(yè)車輛足夠多，能夠完成企業(yè)配送任務(wù)，且車輛類型相同；（2） 每個(gè)客戶的需求量均不超過(guò)車輛的最大載重量；（3） 必須滿足所有客戶的需求，并且一個(gè)客戶只能由一輛車服務(wù)。

設(shè)需要服務(wù)的客戶數(shù)量為K，完成此次配送任務(wù)所需要的車輛數(shù)為m；企業(yè)配送中心用0 表示，各客戶點(diǎn)用表示；每個(gè)客戶的需求量為車輛的最大載重量為q，且gi ＜q；dij表示客戶i到j(luò)的距離。定義模型決策變量如下：

則車輛路徑優(yōu)化問(wèn)題的數(shù)學(xué)模型為：

其中，式（1） 表示車輛總行駛距離最短的優(yōu)化目標(biāo)。式（2） 為車輛載重約束，即車輛不能超載。式（3） 有兩層意義，首先表示每個(gè)需求點(diǎn)只能由一臺(tái)車進(jìn)行配送服務(wù)；其次表示所有車輛從配送中心出發(fā)，且完成配送任務(wù)后必須返回配送中心。式（4） 和式（5） 表示兩決策變量之間的關(guān)系。式（6） 和式（7） 表示0-1 變量約束。

2 雙種群混合遺傳算法

遺傳算法局部尋優(yōu)能力較強(qiáng)，而且并發(fā)性較好。但同人的進(jìn)化一樣，隨著算法的進(jìn)行，種群中的個(gè)體逐漸靠近最優(yōu)解，其特性逐漸穩(wěn)定，種群達(dá)到了一種平衡狀態(tài)。此時(shí)種群的特性基本不再變化。因此在傳統(tǒng)遺傳算法后期，算法往往容易陷入局部最優(yōu)解。本文提出的雙種群混合遺傳算法正是針對(duì)這種情況，在算法中同時(shí)使用兩個(gè)種群進(jìn)行優(yōu)化，并且在每一次迭代結(jié)束后，都將由兩個(gè)種群中選出的小種群進(jìn)行互換，進(jìn)而不斷打破種群的平衡，跳出局部最優(yōu)解，提高算法求解性能。雙種群混合遺傳算法具體的操作為：第一步，建立兩個(gè)規(guī)模相同的種群。第二步，以不同的交叉概率和變異概率分別獨(dú)自進(jìn)行交叉和變異操作。第三步，在每一次迭代完后，從兩個(gè)種群中分別取出由各自最優(yōu)個(gè)體與一定數(shù)量的隨機(jī)個(gè)體組成的小種群，將各自的小種群進(jìn)行交換，進(jìn)入對(duì)方種群中。同時(shí)，為了提高算法的求解速度，本文還利用2-opt 算子將種群中的最優(yōu)個(gè)體進(jìn)行了進(jìn)一步優(yōu)化。

雙種群混合遺傳算法中，每個(gè)種群都是按相同的方式進(jìn)行選擇、交叉和變異等遺傳操作，因此如下的相關(guān)介紹均是針對(duì)兩個(gè)種群同時(shí)進(jìn)行的。

2.1 編碼策略。 參照文獻(xiàn)[3]，采用自然數(shù)串編碼機(jī)制將每條配送路徑編制成長(zhǎng)度為K +m+1 的橫向量（0,i1,i2,…,ie,0,if,…,ik,0,…,0,ip,…,iq,0 ），其中0 為配送中心，ik表示序號(hào)為ik的客戶。

2.2 初始種群生成。在初始種群生成算法上，首先隨機(jī)產(chǎn)生n個(gè)客戶的全排列；然后，在全排列首尾添加0；最后，將m-1 個(gè)0 隨機(jī)插入到全排列中，但兩個(gè)0 不能相鄰。

2.3 適應(yīng)度函數(shù)選取。一般情況下，個(gè)體適應(yīng)度值越高，表示個(gè)體越優(yōu)秀，解的質(zhì)量越高。所以本文對(duì)式（1） 進(jìn)行如下改進(jìn)，作為遺傳算法的適應(yīng)度函數(shù)。

式中，b為常數(shù)，根據(jù)車輛路徑優(yōu)化問(wèn)題的規(guī)模而設(shè)定。

2.4 遺傳算子。遺傳算法的遺傳算子包括選擇算子、交叉算子和變異算子。在選擇算子上，本文采用輪盤賭算子選取優(yōu)秀個(gè)體；交叉算子和變異算子均采用傳統(tǒng)遺傳算法的相應(yīng)算子，由于現(xiàn)有文獻(xiàn)多有闡述，再此就不再一一介紹。

2.5 種群交叉。隨機(jī)從種群A 中選取num個(gè)個(gè)體（num的值根據(jù)具體問(wèn)題設(shè)定） 和最優(yōu)個(gè)體，同時(shí)也從種群B 中選取num個(gè)隨機(jī)個(gè)體和最優(yōu)個(gè)體。將兩個(gè)種群對(duì)應(yīng)的num+1 個(gè)染色體進(jìn)行互換，進(jìn)入對(duì)方種群中。同時(shí)，由于在算法進(jìn)化過(guò)程中，種群中的優(yōu)秀個(gè)體往往存在交叉點(diǎn)，這不僅降低了算法的收斂速度，同時(shí)還影響了算法的全局尋優(yōu)能力。為了加快算法收斂速度、提高算法全局優(yōu)化能力，采用文獻(xiàn)[6]中的2-opt 算子消除最優(yōu)個(gè)體的交叉點(diǎn)，提高優(yōu)秀個(gè)體的質(zhì)量。具體操作如下：

隨機(jī)選精英個(gè)體中的兩條邊，記為（i,j）和（i+1,j+1 ），將其拆分后重新連接起來(lái)組成新的路徑（i,i+ 1 ）和（j,j+ 1 ），如果更新后的路徑滿足車輛載重約束，且使目標(biāo)函數(shù)更小，則說(shuō)明該交叉點(diǎn)可以消除，執(zhí)行上述操作。重復(fù)上述操作，直到所有交叉點(diǎn)消除完為止。

3 算例分析

采用有能力約束的車輛調(diào)度問(wèn)題的標(biāo)準(zhǔn)算例進(jìn)行仿真實(shí)驗(yàn)①。為了驗(yàn)證算法的求解性能，分別利用傳統(tǒng)遺傳算法（GA）、禁忌搜索算法（TS） 和本文算法對(duì)算例進(jìn)行求解，并對(duì)求解結(jié)果進(jìn)行了統(tǒng)計(jì)，結(jié)果如表1 所示。

從表1 中可知，在問(wèn)題規(guī)模較小時(shí)，三個(gè)算法都具有較高的求解精度，但GA 算法和本文算法求解精度更高。而隨著問(wèn)題規(guī)模的逐漸增大，GA 算法和TS 算法明顯陷入局部最優(yōu)解，本文算法在求解精度上雖然有所下降，但仍然能夠取得較好的求解結(jié)果。說(shuō)明通過(guò)對(duì)傳統(tǒng)遺傳算法的改進(jìn)，本文算法在全局優(yōu)化能力上有所提高，優(yōu)于GA 算法和TS 算法。這是由于通過(guò)兩個(gè)種群之間的交叉，使種群始終保持著多樣性，進(jìn)而提高了算法的全局尋優(yōu)能力。

表1 標(biāo)準(zhǔn)算例測(cè)試結(jié)果

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

車輛路徑優(yōu)化問(wèn)題有利降低企業(yè)配送成本，促進(jìn)企業(yè)的發(fā)展。針對(duì)傳統(tǒng)遺傳算法存在的諸如容易陷入局部最優(yōu)解等問(wèn)題，本文提出了求解車輛路徑優(yōu)化問(wèn)題的雙種群混合遺傳算法，為車輛路徑問(wèn)題的求解提供了新的研究思路。當(dāng)然，本文仍然存在一些不足的地方，有待進(jìn)一步改進(jìn)，如：本文假設(shè)企業(yè)擁有的車輛類型相同，這與企業(yè)配送的實(shí)際情況具有一定的差距，論文的下一步研究方向即為考慮多車型的車輛路徑優(yōu)化問(wèn)題。

注：①數(shù)據(jù)來(lái)源于：http://ftp.ics.uci.edu/pub/machine-learning-databases/。

[1] 許茂增，余國(guó)印. 城市配送研究的新進(jìn)展[J]. 中國(guó)流通經(jīng)濟(jì)，2014(11):29-36.

[2] 李娟，余國(guó)印. 綜合成本最小的車輛調(diào)度問(wèn)題及混沌螢火蟲(chóng)優(yōu)化算法[J]. 物流技術(shù)，2015(7):180-183.

[3] 許茂增，余國(guó)印，周翔,等. 綜合成本最小的低碳車輛調(diào)度問(wèn)題及算法[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2015(1):26.

[4] 楊渝華，李敏. 基于改進(jìn)遺傳算法的成品油配送車輛調(diào)度問(wèn)題研究[J]. 物流科技，2015(1):148-153.

[5] 王永，楊曉潔，胥冬川,等. 基于禁忌遺傳算法的郵政運(yùn)輸車輛調(diào)度問(wèn)題[J]. 系統(tǒng)工程，2014(8):102-109.

[6] BIANCHI L, KNOWLES J, BOWLER J. Local search for the probabilistic traveling salesman problem: correction to the 2-ppt and 1-shift algorithms[J]. European Journal of Operational Research, 2005,162(1):206-219.