基于元胞小生境遺傳算法的物流配送路徑優(yōu)化*

朱大林，詹 騰，張 屹，劉 錚

(三峽大學(xué) 機(jī)械與材料學(xué)院，宜昌 443002)

0 引言

近年來(lái)，隨著經(jīng)濟(jì)和社會(huì)的高速迅猛發(fā)展，不斷地促進(jìn)了物流產(chǎn)業(yè)的快速發(fā)展，現(xiàn)在物流業(yè)已經(jīng)成為我國(guó)經(jīng)濟(jì)發(fā)展中的重要領(lǐng)域。現(xiàn)代物流貫穿于各個(gè)領(lǐng)域，包括生產(chǎn)制造領(lǐng)域、消費(fèi)循環(huán)、產(chǎn)品配送等，它已經(jīng)成為企業(yè)降低生產(chǎn)經(jīng)營(yíng)成本，提高市場(chǎng)競(jìng)爭(zhēng)力的重要途徑。作為物流配送優(yōu)化中非常關(guān)鍵的一環(huán)，車輛路徑問(wèn)題(Vehicle Routing Problem，VRP)的研究受到了人們的廣泛的關(guān)注。

帶有時(shí)間窗約束的車輛路徑問(wèn)題(Vehicle Routing Problem with Time Window，VRPTW)是一種帶有約束條件的VRP 問(wèn)題，即對(duì)車輛到達(dá)的時(shí)間有時(shí)間范圍的要求，車輛必須在該時(shí)間范圍內(nèi)到達(dá)服務(wù)點(diǎn)，否則將會(huì)影響顧客對(duì)服務(wù)的滿意度，對(duì)于該問(wèn)題不僅要計(jì)算車輛的行駛成本，而且要考慮早到客戶點(diǎn)需要的等待時(shí)間或晚到要付出懲罰的成本，因此該問(wèn)題較一般的VRP 問(wèn)題更為復(fù)雜，是一個(gè)NP 疑難問(wèn)題［1］。因?yàn)閂RPTW 問(wèn)題更貼近現(xiàn)實(shí)實(shí)際應(yīng)用，所以得到了深入的研究，目前常用的解決VRPTW 問(wèn)題的方法有:禁忌搜索算法［2-3］、模擬退火算法［4］、粒子群算法［5］、免疫算法［6］和一些改進(jìn)的遺傳算法［7-9］等，這些方法用于解決VRPTW 問(wèn)題已經(jīng)取得了一些較好的研究成果。

元胞遺傳算法(Cellular Genetic Algorithm，cGAs)［10］是將元胞自動(dòng)機(jī)機(jī)理和遺傳算法相互結(jié)合得到的一種新型的進(jìn)化算法，其特點(diǎn)在于將種群分布在一種特殊的拓?fù)浣Y(jié)構(gòu)中，一般采用二維環(huán)形結(jié)構(gòu)，且種群的每個(gè)個(gè)體僅限于和其規(guī)定的鄰居之間進(jìn)行遺傳操作，這種結(jié)構(gòu)賦予該算法一個(gè)細(xì)晶度并行功能［11］，并且有較好的全局搜索和局部搜索能力。鑒于此，本文在經(jīng)典元胞遺傳算法的基礎(chǔ)之上，加入小生境技術(shù)，提出了一種元胞小生境遺傳算法(Cellular Niche Genetic Algorithm CNGA)，進(jìn)一步改進(jìn)算法種群多樣性和跳出局部最優(yōu)解的能力。將此算法引入VRPTW 問(wèn)題的求解當(dāng)中，并針對(duì)該問(wèn)題提出一種改進(jìn)的交叉算子，以圖獲得更好的求解效果。

1 物流配送路徑優(yōu)化模型

假設(shè)某公司有M 個(gè)配送中心，N 個(gè)貨物需求點(diǎn)，VRP 的任務(wù)就是將貨物從M 配送中心送到N 個(gè)貨物需求點(diǎn)上，既要滿足需求點(diǎn)貨物量的要求，又要使配送成本最小。將各需求點(diǎn)的任務(wù)分配給距它最近的配送中心，每個(gè)配送中心需負(fù)責(zé)將自己區(qū)域的貨物送達(dá)到，這樣多配送中心將轉(zhuǎn)化為單配送中心問(wèn)題，以下為單配送中心的數(shù)學(xué)模型。

假設(shè)某一配送中心擁有載重量為Gt 的車輛m輛，需要對(duì)n 個(gè)客戶點(diǎn)輸送貨物，即該問(wèn)題為對(duì)n 個(gè)點(diǎn)進(jìn)行排列，使其滿足配送需求且使得總的配送成本最小。

1.1 基本假設(shè)

(1)每個(gè)配送中心所服務(wù)的客戶點(diǎn)和客戶需求量已知;

(2)每個(gè)客戶點(diǎn)和配送中心的距離以及每個(gè)客戶點(diǎn)之間的距離已知;

(3)每個(gè)客戶點(diǎn)只由一輛車服務(wù)一次;

(4)車輛每到一個(gè)客戶點(diǎn)只有卸貨時(shí)間而無(wú)裝貨時(shí)間;

(5)每輛車必須從配送中心出發(fā)，完成任務(wù)再返回配送中心;

(6)配送中心所有車輛種類單一，且額定載荷量已知;

(7)車輛的平均行駛速度已知。

1.2 約束條件

(1)每輛車的載貨重量不能超過(guò)其額定載荷量;

(2)時(shí)間窗約束:分為硬時(shí)間窗和軟時(shí)間窗。對(duì)每個(gè)服務(wù)點(diǎn)i 的任務(wù)，都要求在一定的時(shí)間范圍［STi，ETi］內(nèi)完成，其中STi表示任務(wù)允許開(kāi)始的最早時(shí)間，ETi表示任務(wù)允許的最遲開(kāi)始時(shí)間。如果車輛在STi之前到達(dá)，則車輛在任務(wù)點(diǎn)處要等待;如果到達(dá)時(shí)間晚于ETi，任務(wù)就會(huì)被延遲執(zhí)行。以Ti表示車輛到達(dá)任務(wù)點(diǎn)的時(shí)間，如果是硬時(shí)間窗，則Ti必須滿足STi≤Ti≤ETi;如果是軟時(shí)間窗，則早于STi或者晚于ETi時(shí)將要受到懲罰。

(3)運(yùn)輸過(guò)程的單向性;每一輛車必須以配送中心作為起始點(diǎn)，沿路徑為客戶服務(wù)，要求每個(gè)客戶只能由給定的車輛服務(wù)，且每輛車服務(wù)完后不能又折返回上一個(gè)客戶點(diǎn)，是單向性的路線行駛，最后每輛車終點(diǎn)都是配送中心。

1.3 數(shù)學(xué)模型

約束條件:

式中:D 表示車輛行駛的總距離;i 為客戶編號(hào);j 為客戶編號(hào);n 為客戶數(shù)量;k 表示第k 輛車(k = 1，2，…，m);qi為客戶i 的貨物需求量;G 為車輛額定載荷量;Pij為從客戶i 到客戶j 的運(yùn)輸成本;Ti為車輛到達(dá)客戶i 的時(shí)間;d、f 為參數(shù)。

上述式(1)表示為總的運(yùn)輸成本，包括車輛的運(yùn)輸成本和違反時(shí)間窗約定的懲罰成本;式(2)(3)表示決策變量;式(4)表示每輛車不能超過(guò)其額定載荷;式(5)表示每輛車的起始地點(diǎn)都為配送中心;式(6)每一個(gè)客戶只能被一輛車服務(wù);式(7)表示每輛車服務(wù)完后都必須返回到起始點(diǎn)配送中心;式(8)(9)表示兩個(gè)決策變量之間的關(guān)系。

2 元胞小生境遺傳算法

為了對(duì)上述VRPTW 優(yōu)化模型進(jìn)行優(yōu)化計(jì)算，提出了一種新的元胞遺傳算法CNGA。CNGA 是在經(jīng)典元胞遺傳算法的基礎(chǔ)上引入小生境技術(shù)，使算法能更好地保持種群多樣性，避免過(guò)早出現(xiàn)“早熟”現(xiàn)象。

2.1 元胞遺傳算法

元胞遺傳算法［1］是將元胞自動(dòng)機(jī)作用機(jī)理和遺傳算法有機(jī)的結(jié)合，種群中的個(gè)體按照一定的拓?fù)浣Y(jié)構(gòu)分布，一般情況下采用二維結(jié)構(gòu)，如下圖1 中所示，每個(gè)個(gè)體有相同的鄰居數(shù)，且每個(gè)個(gè)體僅限于和鄰居個(gè)體之間進(jìn)行遺傳操作，這在一定程度上降低了算法的選擇壓力，使得元胞遺傳算法成為解決復(fù)雜問(wèn)題的一種有效方法。

圖1 種群分布示意圖

經(jīng)典元胞遺傳算法的基本步驟如圖2 所示。

圖2 經(jīng)典元胞遺傳算法

圖2 為步驟解析:①將種群分布在二維環(huán)形拓?fù)浣Y(jié)構(gòu)中;②在鄰居結(jié)構(gòu)中選擇一個(gè)元胞個(gè)體作為父代;③將選擇出來(lái)的鄰居元胞和中心元胞進(jìn)行交叉，變異操作;④產(chǎn)生新的個(gè)體;⑤如果新的個(gè)體優(yōu)于中心元胞，在將中心元胞替換，否則，不替換;⑥如果generation ＜MAXGEN，返回至步驟②;⑦輸出當(dāng)前最優(yōu)解。

2.2 小生境技術(shù)

本文采用基于排擠機(jī)制的小生境策略。首先假設(shè)種群(M + N)的組成是父代中優(yōu)秀的N 個(gè)個(gè)體和使用精英保留策略子代種群M 個(gè)個(gè)體，按照下式求出每?jī)蓚€(gè)個(gè)體Ci和Cj之間的海明距離:

小生境過(guò)程為:首先對(duì)種群中兩兩個(gè)體進(jìn)行比較其海明距離，如果這個(gè)距離d(i，j)在預(yù)先設(shè)置的距離L 之內(nèi)，則對(duì)其中的適應(yīng)度較低地個(gè)體施加一個(gè)比較大的罰函數(shù)，使其適應(yīng)度大大地降低，因此其中相對(duì)較差的個(gè)體就很大可能在進(jìn)化的過(guò)程中被淘汰掉。隨著排擠過(guò)程的不斷進(jìn)行，群體中的個(gè)體將會(huì)被逐漸分類，從而生成了許多小的生存環(huán)境，維持了種群的多樣性，使得解空間分布均勻。小生境技術(shù)能夠指引種群的發(fā)展趨勢(shì)，不斷將其指引到更好地方向，有利于全局搜索。

2.3 算法步驟

本文中采用二維環(huán)形拓?fù)浣Y(jié)構(gòu)，其種群結(jié)構(gòu)使用Moore 形(如圖1 中b 所示)，其種群更新方式為同步策略，表1 為CNGA 的偽代碼。

表1 CNGA 的偽代碼

首先產(chǎn)生初始種群，將初始種群分布于二維環(huán)形結(jié)構(gòu)中。隨后使用輪盤賭選擇從中心元胞的鄰居中選擇出一個(gè)個(gè)體，進(jìn)行交叉操作，產(chǎn)生新的個(gè)體，再對(duì)新的個(gè)體進(jìn)行變異操作。隨后進(jìn)行替換操作，對(duì)變異后產(chǎn)生的新個(gè)體與中心元胞進(jìn)行比較，若新個(gè)體優(yōu)于中心元胞，將此個(gè)體替換中心元胞，否則不替換，保留中心元胞。將新生的子代種群個(gè)體，與父代中記憶的N 個(gè)個(gè)體合并在一起，組合成一個(gè)N + M 個(gè)個(gè)體的新種群，然后計(jì)算個(gè)體的適應(yīng)度值并排列，根據(jù)排序選擇相鄰若干個(gè)個(gè)體進(jìn)入一個(gè)小生境。對(duì)適應(yīng)度低的個(gè)體進(jìn)行施加一個(gè)比較大的罰函數(shù)，降低其適應(yīng)度值。保存優(yōu)秀的前M 個(gè)個(gè)體作為下一代種群，其前N 個(gè)個(gè)體作為下一代種群的父代小生境個(gè)體。

3 VRPTW 問(wèn)題的實(shí)例求解與分析

3.1 求解步驟

Step1:隨機(jī)生成初始種群。采用自然數(shù)編碼生成初始種群，編碼個(gè)體即表示為客戶的順序排列，對(duì)于個(gè)體，在其首尾加入“0”，再在其個(gè)體中間位置隨機(jī)的插入n－1 個(gè)“0”，n 代表運(yùn)輸車輛的數(shù)目，如圖3所示表示該運(yùn)輸任務(wù)由三輛車完成8 個(gè)客戶，其中每輛車的運(yùn)輸路徑為:配送中心→客戶(7 →4 →1)→配送中心;配送中心→客戶(8 →3)→配送中心;配送中心→客戶(5 →2 →6)→配送中心。

圖3 個(gè)體編碼結(jié)構(gòu)

Step3:選擇算子。本文采用輪盤賭選擇，在元胞鄰居結(jié)構(gòu)中選擇一個(gè)個(gè)體作為父代個(gè)體。

Step4:交叉算子。本文引入一種新的算子，該算子有一個(gè)很大的優(yōu)勢(shì)就是當(dāng)父代兩個(gè)個(gè)體相同時(shí)，依然能夠產(chǎn)生新的個(gè)體，這樣能夠有效的避免“早熟”現(xiàn)象的發(fā)生。

具體操作如下圖4、圖5 所示:隨機(jī)的產(chǎn)生兩個(gè)切點(diǎn)，其中切點(diǎn)之間的部分進(jìn)行交換保存到下一代中，然后將p1中A2的中數(shù)字內(nèi)容剔除，將余下的部分進(jìn)行逆轉(zhuǎn)排序，同理p2也一樣，將該交叉算子命名為順序逆轉(zhuǎn)交叉算子(ORX):

(1)當(dāng)隨機(jī)兩個(gè)不相同的個(gè)體進(jìn)行交叉(圖4 所示)，得到的結(jié)果如下:

圖4 不同的父代個(gè)體

(2)當(dāng)任意給定兩個(gè)相同的個(gè)體時(shí)(圖5)，仍然可以進(jìn)行迭代進(jìn)化，不會(huì)影響其進(jìn)化過(guò)程，因?yàn)榧词垢复鷥蓚€(gè)個(gè)體相同時(shí)依舊能夠獲得新的子代個(gè)體，這樣就能夠跳出進(jìn)入局部最優(yōu)解，避免出現(xiàn)“早熟”現(xiàn)象。得到的結(jié)果如圖5 所示。

圖5 相同的父代個(gè)體

Step5:變異算子。采用逆轉(zhuǎn)算子進(jìn)行變異操作。其具體操作如圖6 所示。

圖6 逆轉(zhuǎn)算子示意圖

Step6:排擠技術(shù)。設(shè)置排擠因子，采用小生境技術(shù)對(duì)種群重新進(jìn)行排序選擇。

3.2 實(shí)例分析

選取文獻(xiàn)［12］所描述的基于有時(shí)間窗的倉(cāng)庫(kù)配送問(wèn)題為研究對(duì)象，該配送問(wèn)題要求從1 中心倉(cāng)庫(kù)向8 個(gè)客戶送貨，中心倉(cāng)庫(kù)有3 輛車，每車的載重量為8 t，車輛的平均行駛速度為50km/h，且車輛的行駛時(shí)間和距離成正比，各客戶的任務(wù)及要求如表2 所示，中心倉(cāng)庫(kù)與客戶間的距離見(jiàn)表3。

表2 各客戶的任務(wù)及要求

表3 中心倉(cāng)庫(kù)與各客戶間的距離

為了對(duì)比算法的性能，除CNGA 之外，本文還選用了經(jīng)典元胞遺傳算法［10］和小生境遺傳算法［9］兩種算法同時(shí)對(duì)VRPTW 模型進(jìn)行優(yōu)化，三種算法參數(shù)設(shè)置如下:種群規(guī)模為100，交叉概率pc= 0.8，變異概率pm= 0.05，懲罰系數(shù)d = f = 50km，排擠因子為3，終止代數(shù)Generation = 100 對(duì)三種算法獨(dú)立運(yùn)行15 次，所得的優(yōu)化結(jié)果如表4。

表4 求解的結(jié)果

為了觀察逆序交叉算子的性能，在相同的算法環(huán)境以及參數(shù)條件下，分別采用新的交叉算子(ORX)、循環(huán)交叉算子(CX)以及順序交叉(OX)算子構(gòu)建了三種不同的算法，三種算法對(duì)模型進(jìn)行計(jì)算，由表3 結(jié)果顯示使用ORX 交叉算子得到的結(jié)果明顯優(yōu)于CX 和OX 算子，說(shuō)明了ORX 交叉算子的有效性，而且得到的結(jié)果更接近最優(yōu)值。其次通過(guò)表3可得，元胞小生境遺傳算法獲得配送距離平均為933，經(jīng)典元胞遺傳算法為976 和小生境遺傳算法為947，說(shuō)明元胞小生境遺傳算法在求解精度上高于另外兩種算法。由最優(yōu)值次數(shù)和最大/ 最小值兩個(gè)評(píng)價(jià)指標(biāo)比較可得元胞小生境遺傳算法更容易跳出局部最優(yōu)解，而且算法更加穩(wěn)定，由此說(shuō)明元胞小生境遺傳算法對(duì)求解有時(shí)間窗的車輛路徑問(wèn)題有很好的效果。

4 結(jié)論

帶時(shí)間窗的車輛路徑問(wèn)題是一類復(fù)雜的NP 問(wèn)題，為了獲得更好的解決方法，本文在經(jīng)典元胞遺傳算法的基礎(chǔ)之上，引入一種小生境技術(shù)，得到了元胞小生境遺傳算法，并且將該算法應(yīng)用于帶時(shí)間窗的車輛路徑問(wèn)題時(shí)，提出了一種新的順序逆轉(zhuǎn)交叉算子，仿真實(shí)驗(yàn)證實(shí)新的交叉算子的性能優(yōu)于傳統(tǒng)算子，而且將元胞小生境遺傳算法和另外兩種遺傳算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果顯示新算法解的精度和算法穩(wěn)定性上有更好的效果，說(shuō)明該算法是解決物流配送路徑優(yōu)化問(wèn)題的有效方法。

［1］SAVELSBERGH M. Local search for routing problem with time windows［J］. Annals of Operations Research，1985，16(4):285－305.

［2］Ho S C，Haugland D.A tabu search heuristic for the vehicle routing problem with time windows and split deliveries［J］.Computers＆Operations Research，2004，31 (2):1947－1964.

［3］Duhamel C，Potvin J-Y，Rousseau J-M.A tabu search heuristic for the vehicle routing problem with backhauls and time windows［J］.Transportation Science，1997，31(1):49－59.

［4］楊宇棟，朗茂祥，胡思繼. 有時(shí)間窗車輛路徑問(wèn)題的模型及其改進(jìn)模擬退火算法研究［J］. 管理工程學(xué)報(bào)，2006，20(3):104－107.

［5］李寧，鄒彤，孫德寶. 帶時(shí)間窗車輛路徑問(wèn)題的粒子群算法［J］. 系統(tǒng)工程理論與實(shí)踐，2004(4):130－135.

［6］李全亮. 免疫算法在帶時(shí)間窗的車輛路徑問(wèn)題中的應(yīng)用［J］. 系統(tǒng)工程理論與實(shí)踐，2006，26(10):119－124.

［7］張麗萍，柴躍廷，曹瑞. 有時(shí)間窗車輛路徑問(wèn)題的改進(jìn)遺傳算法［J］. 計(jì)算機(jī)集成制造系統(tǒng)——CIMS，2002，8(6):451－454.

［8］張智海，吳星瑋. 帶時(shí)間窗車輛路徑問(wèn)題的并行遺傳算法［J］. 工業(yè)工程，2007，10(3):111－114.

［9］王輝，任傳祥，尹唱唱，等. 基于小生境遺傳算法的物流配送路徑優(yōu)化研究［J］. 計(jì)算機(jī)應(yīng)用，2009，29(10):2862－2864.

［10］Alba Enrique，Bernab＇e Dorronsoro.Cellular Genetic Algorithms［M］，2008 Springer Science，Business Media，LLC，ISBN:978－0－387－77609－5.

［11］Bernab＇e Dorronsoro and Enrique Alba. A Simple Cellular Genetic Algorithm for Continuous Optimization ［C］，2006IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel Vancouver BC Canada，2000(6):16－21.

［12］林清國(guó). 基于混合遺傳算法的有時(shí)間窗車輛路徑問(wèn)題研究［D］. 濟(jì)南:山東大學(xué)，2007.