多精英協(xié)同進化遺傳算法求解外賣送餐路線優(yōu)化問題

劉競遙,趙歡歡

滁州學院計算機與信息工程學院， 滁州,239000

隨著信息化時代的到來，傳統(tǒng)的餐飲業(yè)已經(jīng)慢慢向O2O方式靠攏，商家通過第三方訂餐軟件獲取訂餐信息，實時配送。對于商家來說，服務員接待和打掃衛(wèi)生的成本減少了，但卻增加了配送成本，需要雇傭專門的送餐人員。針對訂餐源廣、配送不及時的情況，提出一種多商家聯(lián)合成立送餐隊、集中配送、統(tǒng)一管理的方法。并且在就餐高峰期雇用臨時工，可大大節(jié)約成本。送餐過程中采用遺傳算法進行路徑優(yōu)化，再次節(jié)約時間，提高效率。

帶時間窗的路徑優(yōu)化問題(VRPTW)是一個NP問題[1]，顧客有一個等待時間約束，在規(guī)定時間內(nèi)送餐隊統(tǒng)一分配送餐任務，每個小區(qū)隨時都可能有訂單產(chǎn)生，送餐員在有限的時間內(nèi)送出最多的外賣，就能節(jié)約勞動成本，每個送餐員送完一趟回來還可以繼續(xù)接單送餐。城市外賣送餐路徑問題目標是尋找雇傭人員最少、利潤最大、等待時間合理的方案。由此，本文提出了一種基于多精英協(xié)同進化遺傳算法求解城市外賣送餐路徑優(yōu)化問題的方案。

1 多精英協(xié)同進化遺傳算法

遺傳算法解決實際尋優(yōu)問題的能力強大、發(fā)展迅速并且受到人們的普遍關注，自其確立以來就成立了每兩年一屆的國際遺傳算法學會。遺傳算法的相關研究在各大雜志上屢有發(fā)表，并且研究成果顯著。

目前遺傳算法已經(jīng)廣泛應用于模糊模式識別、人工生命、進化神經(jīng)網(wǎng)絡等領域。但是，傳統(tǒng)的遺傳算法也有它的缺陷：優(yōu)化不夠徹底、收斂速度慢、易于陷入早熟收斂等問題[2]。而多精英協(xié)同進化遺傳算法(簡稱MCGA)主要運用了精英策略和協(xié)同進化的思想，在優(yōu)良的精英個體被保存的情況下，不斷地從其他個體中進化出精英個體并再次被保存。通過不同的選擇策略進化子種群，多個子種群采用不同的進化方式[3]。實驗數(shù)據(jù)表明，該種多精英協(xié)同進化遺傳算法每一次運行都能尋找到最優(yōu)解，并且用時短，提高了收斂速度，操作簡單，多樣性圖示表明該種遺傳算法還增加了種群多樣性，可以跳出局部最優(yōu)解，提高尋優(yōu)能力。傳統(tǒng)的遺傳算法操作流程：(1)采用二進制編碼方式對問題進行描述；(2)隨機產(chǎn)生n個個體的種群；(3)設置適應度函數(shù)并且通過計算適應度值進行個體評價；(4)用輪盤賭選擇法選擇個體進行進化，個體的選擇隨機并可以重復；(5)通過對交叉概率判定進行單點交叉；(6)通過變異算子進行變異；(7)尋找最優(yōu)解。

多精英協(xié)同進化遺傳算法流程如圖1所示。

用多精英協(xié)同進化遺傳算法和傳統(tǒng)遺傳算法(SGA)對多個函數(shù)進行測試比較，運行參數(shù)一致，交叉概率(pc)為0.6，變異概率(pm)為0.01，測試使用如下函數(shù)：

圖1 多精英協(xié)同進化遺傳算法流程圖

種群大小為70，最大進化代數(shù)為150代，基因長度為20位二進制數(shù)[4]。對同一種函數(shù)分別用兩種方法各仿真60次。MCGA對函數(shù)f1求解成功57次，SGA求解成功26次。圖2為兩種算法的平均適應度值比較。可以看出，在進化過程中，SGA比MCGA平均適應度值進化快。圖3、圖4、圖5為種群多樣性統(tǒng)計數(shù)據(jù)對比。可以看出，MCGA種群多樣性比SGA好，不容易陷入?yún)^(qū)域極值，容易得到最優(yōu)解，MCGA的best收斂速度相對更快一些。

與雙精英協(xié)同進化遺傳算法(DECGA)[5]相比，MCGA對函數(shù)的平均收斂代數(shù)優(yōu)于DECGA。因此多精英協(xié)同進化遺傳算法在傳統(tǒng)遺傳算法的基礎上有了較大改進，能快速找到最優(yōu)解，對子種群進行分組，不同的分組采用不同的交叉策略，使各個分組都擁有種群多樣性的特點，又能提高進化速度。

2 問題描述

城市外賣送餐路徑問題可以描述如下：

有n個訂單m個送餐員，每個送餐員每次去送一次餐回到原點，然后再次出發(fā)，每個送餐員最多送餐量為Q，訂單點編號為i(i=1,2,3,…,n),dij為i訂單點在j時刻產(chǎn)生的訂單，wij為i訂單最晚配送時間，sij為i到j的送餐時間，其中sij

定義變量如下:

此問題的數(shù)學模型：

minz=xwijyijw

(1)

約束條件：

Ywi=1 (i=0,1,…,n)

(2)

其中，式(2)表示每一份外賣只能有一個送餐員派送。

3 多精英遺傳算法求解

3.1 構造初始種群

外賣送餐路線VRPTW問題按照訂單產(chǎn)生的先后順序用整數(shù)表示，原點用0表示，訂單點p用1,2,3…n表示。送餐員x用1,2,3…m表示，每次訂單從送餐員列中隨機選擇序號，形成n個由m數(shù)中抽取組成的路徑。

通過對每個訂單產(chǎn)生的時間及送餐員速度路程的合理判斷形成了點到點的路徑，將一段時間內(nèi)的點分成組，本組只能跟前一組和后一組的個體相連，這樣就省去了相隔時間過長的兩個個體進行連接，也就不會有訂單有過長時間的等待。根據(jù)事件發(fā)生時間先后個體本身事件發(fā)生后，其后邊的個體事件才可以發(fā)生，整個路徑合理則作為初始種群。如圖6所示。

圖6 4個送餐員外賣送餐路徑AOE路徑圖

3.2 多精英交叉策略

第一組優(yōu)良精英組進行單點交叉，可以把優(yōu)秀個體的性狀遺傳給下一代的同時又有新個體產(chǎn)生。單點交叉運算如下所示：

交叉前 ：Aa0,a1,a2,a3,a4,a5,a6,a7,a8,a9

Bb0,b1,b2,b3,b4,b5,b6,b7,b8,b9

第二組使用兩點交叉，運算如下所示：

交叉前 ：Aa0,a1,a2,a3,a4,a5,a6,a7,a8,a9

Bb0,b1,b2,b3,b4,b5,b6,b7,b8,b9

第三組最差組我們選擇逆轉交叉，交叉后實現(xiàn)逆轉，逆轉后個體差異大，可以盡量多的產(chǎn)生新個體，增加種群多樣性，跳出局部最優(yōu)解得到適應度值高的個體[2]。逆轉算子交叉運算如下所示：

交叉前 ：Aa0,a1,a2,a3,a4,a5,a6,a7,a8,a9

Bb0,b1,b2,b3,b4,b5,b6,b7,b8,b9

3.3 變異算子

變異是在滿足變異概率的情況下隨機生成兩個位置，將兩個位置上的基因交換。例如：

變異前：Aa0,a1,a2,a3,a4,a5,a6,a7,a8,a9

4 仿真實驗

對6家附近的餐廳聯(lián)合配送，總共有10個訂餐小區(qū)點，時間從11：00點開始記為0，后一個小時進行統(tǒng)計，訂餐高峰期第一、二個訂餐點每隔60分鐘產(chǎn)生一個訂單，第三個訂餐點每隔65分鐘產(chǎn)生一個訂單，第四、五個訂餐點每隔70分鐘產(chǎn)生一個訂單，第六、七個訂餐點每隔80分鐘產(chǎn)生一次訂單，第八個訂餐點每隔90分鐘產(chǎn)生一個訂單，第九、十個訂餐點每隔100分鐘產(chǎn)生一個訂單。這樣就會有87個訂單，把每一個訂單作為一個個體，按照產(chǎn)生時間早晚進行順序排序，通過每個點距離原點(餐廳)的距離和食物加工時間可以求得當前訂單滯留時間。各個訂餐點離原點的距離位置如圖7所示。

種群大小為50，最大進化代數(shù)為50代，圖8為6輛車完成運輸任務情況下MCGA和SGA路徑安排下的食物滯留時間對比；圖9為使用MCGA進行路徑優(yōu)化后分別用4、6、8、10個電動車完成送餐后店鋪的收入情況對比。

5 結 論

本文通過具體的實例數(shù)據(jù)證實，進行集中配送要比每個商店雇傭專門配送人員更符合實際要求，并且多精英協(xié)同進化遺傳算法在尋找到最優(yōu)路徑時比傳統(tǒng)的遺傳算法更加省時省力，所以應該選擇MCGA進行路徑優(yōu)化。通過數(shù)據(jù)可以看出，在保證規(guī)定時間內(nèi)送到的前提下，采用多精英協(xié)同進化遺傳算法，為商店節(jié)省了一筆可觀的人力開支。

圖7 訂餐點離原點的距離位置圖

圖8 食物滯留時間對比

圖9 不同車輛數(shù)送餐帶來的收入情況對比