基于改進(jìn)遺傳算法的同城快遞配送模型

宋 娟，崔 艷

（1.寧夏大學(xué) 物理電氣信息學(xué)院，寧夏 銀川 750021；2.河南廣播電視大學(xué) 理工學(xué)院，河南 鄭州 450008）

0 引言

電子商務(wù)與連鎖商業(yè)的興起推動(dòng)了物流業(yè)的發(fā)展[1]，近年來(lái)同城快遞配送問(wèn)題已經(jīng)成為現(xiàn)代物流系統(tǒng)中微觀層次的熱點(diǎn)問(wèn)題[2]。

目前，基于同城快遞配送方案的研究多集中在算法優(yōu)化上，遺傳算法在求解組合優(yōu)化問(wèn)題[3-4]上所表現(xiàn)出的良好特性，被廣泛地應(yīng)用于快遞配送領(lǐng)域。本文針對(duì)傳統(tǒng)遺傳算法的收斂慢、全局搜索能力差等不足，提出了一種改進(jìn)的遺傳算法。該算法采用了2-OPT(2-optimization)與翻轉(zhuǎn)變異相結(jié)合的變異方法，并結(jié)合了模擬退火機(jī)制[5]，經(jīng)實(shí)驗(yàn)驗(yàn)證，在解決同城快遞配送問(wèn)題方面有較高的效率。

1 快遞配送問(wèn)題的建模

1.1 快遞配送問(wèn)題的描述

同城快遞配送問(wèn)題可描述如下：某快遞公司要從一個(gè)配送中心向若干個(gè)配貨點(diǎn)配送快遞，配送中心擁有若干輛配送車(chē)輛，每輛車(chē)的承重量相同并已知，選取的車(chē)輛數(shù)和每輛車(chē)的路線是未知的。配送車(chē)輛從該中心出發(fā)，在車(chē)輛負(fù)載范圍內(nèi)進(jìn)行配送，并在任務(wù)完成后返回配送中心，如圖1所示是4條車(chē)輛行駛路線的配送圖。本文采用車(chē)隊(duì)行駛的總距離衡量快遞配送的代價(jià)。總距離越小，表明配送方案越優(yōu)。

圖1 車(chē)輛行駛路線的配送圖

1.2 快遞配送問(wèn)題的數(shù)學(xué)模型

以最短配送距離為目標(biāo)，針對(duì)同城快遞問(wèn)題，建立數(shù)學(xué)模型。模型中，配送中心編號(hào)為0，快遞提貨點(diǎn)編號(hào)為 1，2，…，n，配送中心和客戶點(diǎn)均用 i(i=0，1，2，…，n)來(lái)表示，cij表示從客戶i到客戶j的運(yùn)輸成本（這里指距離），xijk表示車(chē)輛 k從 i到 j，yik表示需求點(diǎn) i由 k服務(wù)，如式(1)、(2)所示。 約束條件如式(3)～式(10)所示。

目標(biāo)函數(shù)(3)表示車(chē)隊(duì)總的最短配送距離；約束(4)為車(chē)輛裝載能力約束，即每條配送線路k的送貨量不能超過(guò)車(chē)的最大載重量；約束(5)保證每個(gè)客戶都被服務(wù)；約束(6)保證車(chē)輛都從配送中心出發(fā)并返回到配送中心；約束(7)、(8)保證如果客戶點(diǎn)i、j在車(chē)輛k的行駛線路上，那么客戶點(diǎn) i、j將由車(chē)輛 k服務(wù)；約束(9)、(10)定義了 xijk和yik的范圍。

2 改進(jìn)的遺傳算法求解同城快遞問(wèn)題

2.1 改進(jìn)遺傳算法的設(shè)計(jì)

本文中提出的改進(jìn)遺傳算法將模擬退火機(jī)制與傳統(tǒng)的選擇算子相結(jié)合，有效避免“早熟收斂”，本文采用改進(jìn)的遺傳算法求解快遞配送的具體流程如圖2所示。

圖2 改進(jìn)遺傳算法設(shè)計(jì)流程

2.2 染色體編碼方案

本文采用的是基于配貨點(diǎn)編號(hào)的自然數(shù)編碼，采用“先排序，后聚類(lèi)”的方法，染色體的編碼為包含全部配貨點(diǎn)編號(hào)的一個(gè)不重復(fù)排列，路徑的分割要求滿足每輛車(chē)配送的所有配貨點(diǎn)的總貨物需求量不超過(guò)該車(chē)載重。即在一個(gè)染色體中，按照從左到右的順序，將達(dá)到車(chē)輛載重的配貨點(diǎn)序列確定為一條車(chē)輛路線。這種編碼方式占用存儲(chǔ)量較小，而且產(chǎn)生的配送方案會(huì)覆蓋所有配貨點(diǎn)，因而編碼效率較高。

2.3 適應(yīng)度函數(shù)

適應(yīng)度是用來(lái)區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn)[6]，本文中以車(chē)隊(duì)行駛總距離為成本衡量標(biāo)準(zhǔn)，適應(yīng)度函數(shù)如式(11)所示，其中F(x)表示染色體對(duì)應(yīng)的路徑距離。

2.4 初始群體生成

[7]表明，雖然初始群體的解分布不影響最優(yōu)解，但是如果初始群體的解是均勻分布的，會(huì)減少算法陷入局部最優(yōu)的可能性，因而本文中在保證多樣性的前提下隨機(jī)生成初始群體。

2.5 選擇算子

本文采用的是適應(yīng)度比例法（又稱(chēng)輪盤(pán)賭法）與模擬退火算法相結(jié)合的方法。適應(yīng)度比例法的優(yōu)點(diǎn)是簡(jiǎn)單易操作，基于適應(yīng)度比例選擇算子。經(jīng)典的適應(yīng)度比例算子易實(shí)現(xiàn)，但是選擇誤差比較大，容易導(dǎo)致最優(yōu)配送方案流失，未進(jìn)入下一代，從而導(dǎo)致結(jié)果收斂于局部最優(yōu)解。本文采用輪盤(pán)賭法與模擬退火機(jī)制相結(jié)合的方法，引入模擬退火機(jī)制的配送選擇操作。

2.6 交叉算子

由于采用配貨點(diǎn)全排列方式進(jìn)行編碼，即配送方案會(huì)覆蓋全部配貨點(diǎn)，并不會(huì)對(duì)同一配貨點(diǎn)重復(fù)配送，若直接選用部分匹配交叉算法，交叉結(jié)果代表的配送路線可能會(huì)遺漏部分配貨點(diǎn)，使得交叉結(jié)果的存活率過(guò)低。因此，本文采用改進(jìn)的部分匹配交叉法，對(duì)交叉后的結(jié)果進(jìn)行調(diào)整優(yōu)化，使得交叉結(jié)果代表的快遞配送方案均可完成對(duì)所有配貨點(diǎn)的快遞配送任務(wù)。具體操作過(guò)程如下：(1)根據(jù)選擇概率選擇進(jìn)行交叉的父代配送方案A、B；(2)通過(guò)隨機(jī)函數(shù)生成交叉片段首末下標(biāo)a、b；

(3)將A、B染色體下標(biāo)a與b之間的片段進(jìn)行交叉，得到A1、B1，同時(shí)使用兩個(gè)標(biāo)記數(shù)組flag1、flag2記錄每個(gè)配貨點(diǎn)編號(hào)交換后對(duì)應(yīng)的配貨點(diǎn)編號(hào)，未發(fā)生交換則置為 0；

(4)對(duì) A1、B1的未交叉基因段進(jìn)行遍歷，若對(duì)應(yīng)的flag1、flag2有交換記錄，則將對(duì)應(yīng)的配貨點(diǎn)編號(hào)置換，直到對(duì)應(yīng)flag1、flag2無(wú)交換記錄；

(5)得到最終交叉后代 An、Bn，進(jìn)入下一代。

2.7 變異算子

傳統(tǒng)遺傳算法的變異算子可能會(huì)導(dǎo)致出現(xiàn)配送路徑大量交叉的現(xiàn)象，一旦發(fā)生交叉現(xiàn)象，一定會(huì)增大解路徑的長(zhǎng)度，因而消除臨近交叉顯得尤為重要。本文采用了翻轉(zhuǎn)變異和2-OPT相結(jié)合的變異方法，使得變異向更優(yōu)的方向趨近。2-OPT具體方法為：對(duì)于選中的長(zhǎng)度為n的個(gè)體（起始下標(biāo)為0），使用隨機(jī)函數(shù)確定一個(gè)下標(biāo) i(i+3＜n)，若臨近配貨點(diǎn)的配送路徑滿足式(12)，則將基因串中下標(biāo)為i+1和下標(biāo)為i+2上的配貨點(diǎn)編號(hào)交換。 其中 d(i，j)表示配貨點(diǎn) i與 j之間的距離，2-OPT原理如圖3所示。經(jīng)過(guò)優(yōu)化后，可以最大限度地消除配送方案中臨近配貨點(diǎn)的路徑交叉現(xiàn)象，從而提高算法求解性能。

圖3 2-OPT原理示意圖

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

3.1 算例說(shuō)明

本節(jié)中采用一組國(guó)際標(biāo)準(zhǔn)測(cè)試數(shù)據(jù) E-n51-k5[8]進(jìn)行實(shí)際測(cè)算，并與其他方法的性能進(jìn)行比較。假設(shè)同城快遞配送公司目前擁有1個(gè)配送中心和50個(gè)客戶點(diǎn)，配送中心編號(hào)為0，客戶點(diǎn)編號(hào)為 1～50，車(chē)輛的容量為160單位，配送中心坐標(biāo)為(30,40)，各客戶的坐標(biāo)及客戶快遞需求量如表1所示。

采用本文提出的改進(jìn)的遺傳算法進(jìn)行運(yùn)輸方案求解，利用MATLAB構(gòu)建算法實(shí)現(xiàn)。為了兼顧算法性能和效率，取種群規(guī)模N=100，最大進(jìn)化代數(shù) 2 000，交叉率 Pc=0.8，變異率 Pm=0.05。

表1 同城快遞公司客戶點(diǎn)位置坐標(biāo)

3.2 實(shí)驗(yàn)結(jié)果與分析

采用改進(jìn)遺傳算法得到如表2的運(yùn)輸計(jì)劃，最優(yōu)解序列為配貨點(diǎn)編號(hào)的的全排列，根據(jù)配貨點(diǎn)貨物需求量和車(chē)輛載重可知，需要5輛車(chē)進(jìn)行快遞配送，配送距離的總和(即最小成本)是 548。

表2 本文遺傳算法得到的運(yùn)輸計(jì)劃

接著對(duì)此快遞配送問(wèn)題進(jìn)行了100次仿真實(shí)驗(yàn)，以驗(yàn)證算法的穩(wěn)定性。每10次的平均結(jié)果如圖4所示。可收斂到的最優(yōu)解為 548，最差解為562，平均解的值為555.5，最優(yōu)結(jié)果與最差結(jié)果之間相差不超過(guò)6%，結(jié)果相對(duì)穩(wěn)定，這樣本文的算法穩(wěn)定性得到了驗(yàn)證。

圖4 仿真每10次的平均結(jié)果

對(duì)于大規(guī)模的快遞配送問(wèn)題，不合理的解可能會(huì)導(dǎo)致配送方案代價(jià)很大，如圖5所示為初始解的配送路徑圖。圖中橫軸、縱軸分別代表了位置坐標(biāo)軸，中心交點(diǎn)代表配送中心，其余點(diǎn)代表配貨點(diǎn)。傳統(tǒng)遺傳算法雖然可得到較優(yōu)解，但極易陷入局部最優(yōu)解，并出現(xiàn)大量的配送路徑交叉現(xiàn)象，如圖6所示。本文提出的改進(jìn)遺傳算法使用模擬退火機(jī)制避免局部最優(yōu)，同時(shí)使用了2-OPT與翻轉(zhuǎn)變異相結(jié)合的變異方法消除了臨近配貨點(diǎn)之間配送路線的交叉現(xiàn)象，極大降低了快遞配送的代價(jià)，如圖7所示。

圖5 初始解的配送路徑圖

圖6 傳統(tǒng)遺傳算法的配送路徑圖

圖7 本文改進(jìn)遺傳算法的配送路徑圖

4 結(jié)論

針對(duì)同城快遞配送問(wèn)題，本文提出了一種改進(jìn)的遺傳算法對(duì)快遞運(yùn)輸路線規(guī)劃進(jìn)行優(yōu)化。將遺傳算法與模擬退火機(jī)制相結(jié)合，并引入了2-OPT方法消除交叉路徑。經(jīng)過(guò)仿真實(shí)驗(yàn)可知，本算法可以跳出局部最優(yōu)得到全局最優(yōu)解，并且最大程度上減少了交叉路徑的出現(xiàn)，同時(shí)具有很高的穩(wěn)定性。因而本文所提出的改進(jìn)遺傳算法對(duì)于求解同城快遞問(wèn)題有很強(qiáng)的有效性和可行性。

在后續(xù)的研究中，本文的同城快遞模型將考慮時(shí)間等其他次要因素，使得模型更加豐滿、更接近現(xiàn)實(shí)，因而多目標(biāo)的同城快遞配送優(yōu)化是今后的工作重心。

參考文獻(xiàn)

[1]周慧，羅小瓊.物流電子商務(wù)[M].北京：清華大學(xué)出版社，2006.

[2]曹淑艷，李振欣.跨境電子商務(wù)第三方物流模式研究[J].電子商務(wù)，2013(3)：23-25.

[3]HOLLAND J H.Adaptation in natural and artificial systems：an introductory analysis with applications to biology，control and artificial intelligence[M].MIT press，1992.

[4]劉鯖潔，陳桂明，劉小方，等.基于遺傳算法的SVM參數(shù)組合優(yōu)化[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29(4)：94-96.

[5]段謨意.基于免疫克隆模擬退火算法的網(wǎng)絡(luò)生存性研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，33(12)：4436-4439.

[6]張永，朱林杰.基于遺傳禁忌搜索的分類(lèi)器選擇集成方法[J].Computer Engineering，2011，37(8)：183-185.

[7]何娟，涂中英，牛玉剛.一種遺傳蟻群算法的機(jī)器人路徑規(guī)劃方法[J].計(jì)算機(jī)仿真，2010(3)：170-174.

[8]BALDACCI R，MINGOZZI A，ROBERTI R，et al.An exact algorithm for the two-echelon capacitated vehicle routing problem[J].Operations Research，2013，61(2)：298-314.