宋 娟，崔 艷

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

0 引言

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

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

1 快遞配送問題的建模

1.1 快遞配送問題的描述

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

圖1 車輛行駛路線的配送圖

1.2 快遞配送問題的數(shù)學模型

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

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

2 改進的遺傳算法求解同城快遞問題

2.1 改進遺傳算法的設計

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

圖2 改進遺傳算法設計流程

2.2 染色體編碼方案

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

2.3 適應度函數(shù)

適應度是用來區(qū)分群體中個體好壞的標準[6]，本文中以車隊行駛總距離為成本衡量標準，適應度函數(shù)如式(11)所示，其中F(x)表示染色體對應的路徑距離。

2.4 初始群體生成

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

2.5 選擇算子

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

2.6 交叉算子

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

(3)將A、B染色體下標a與b之間的片段進行交叉，得到A1、B1，同時使用兩個標記數(shù)組flag1、flag2記錄每個配貨點編號交換后對應的配貨點編號，未發(fā)生交換則置為 0；

(4)對 A1、B1的未交叉基因段進行遍歷，若對應的flag1、flag2有交換記錄，則將對應的配貨點編號置換，直到對應flag1、flag2無交換記錄；

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

2.7 變異算子

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

圖3 2-OPT原理示意圖

3 仿真實驗

3.1 算例說明

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

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

表1 同城快遞公司客戶點位置坐標

3.2 實驗結果與分析

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

表2 本文遺傳算法得到的運輸計劃

接著對此快遞配送問題進行了100次仿真實驗，以驗證算法的穩(wěn)定性。每10次的平均結果如圖4所示?？墒諗康降淖顑?yōu)解為 548，最差解為562，平均解的值為555.5，最優(yōu)結果與最差結果之間相差不超過6%，結果相對穩(wěn)定，這樣本文的算法穩(wěn)定性得到了驗證。

圖4 仿真每10次的平均結果

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

圖5 初始解的配送路徑圖

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

圖7 本文改進遺傳算法的配送路徑圖

4 結論

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

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

參考文獻

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

[2]曹淑艷，李振欣.跨境電子商務第三方物流模式研究[J].電子商務，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].計算機應用與軟件，2012，29(4)：94-96.

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

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

[7]何娟，涂中英，牛玉剛.一種遺傳蟻群算法的機器人路徑規(guī)劃方法[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.