基于遺傳算法和破壞重組算法的外賣配送研究

唐傳茵 劉春龍

摘 ?要：文章針對有大量訂單的外賣商家，解決外賣騎手高效配送外賣的問題，應(yīng)用遺傳算法和破壞重組算法對外賣配送路線進行分析;首先利用遺傳算法對配送路線進行自然數(shù)編碼，隨后進行選擇交叉變異操作，通過迭代優(yōu)化得到次優(yōu)配送路線，在遺傳算法的基礎(chǔ)上再與破壞重組算法結(jié)合，使配送路線圖進一步優(yōu)化;通過MATLAB工具，對外賣配送進行仿真，得到迭代優(yōu)化圖和配送方案路線圖。通過對算法結(jié)合前后得到的配送路線性能指標(biāo)的比較，驗證遺傳算法和破壞重組算法結(jié)合的優(yōu)越性。

關(guān)鍵詞：遺傳算法;破壞重組算法;外賣配送;配送路線

?中圖分類號：F252.14 ? ?文獻標(biāo)識碼：A

Abstract： In this paper， the delivery route is analyzed by genetic algorithm and destruction recombination algorithm to solve the problem of efficient delivery by delivery drivers for takeaway merchants with large quantities of orders. Firstly， genetic algorithm was used to encode the natural numbers of the distribution route， and then the selection crossover mutation operation was carried out to obtain the sub-optimal distribution route through iterative optimization. On the basis of genetic algorithm， combined with the destruction recombination algorithm， the distribution route was further optimized. Through MATLAB tools， the external distribution simulation， iteration optimization diagram and distribution scheme roadmap. By comparing the performance indexes of distribution routes before and after the combination of genetic algorithm and destruction recombination， the superiority of the combination of genetic algorithm and destruction recombination is verified.

Key words： genetic algorithm; destruction recombination algorithm; take-out delivery; delivery routes

0 ?引 ?言

?在外賣平臺系統(tǒng)的設(shè)置中，配送時間是最重要的指標(biāo)，超時是不被允許的，一旦發(fā)生，騎手便有可能收到差評，這會導(dǎo)致他們收入降低，甚至淘汰。在外賣平臺給生活帶來極大便利的同時，外賣騎手的安全問題，如何合理規(guī)劃配送路線，高效率完成配送任務(wù)是重要的研究課題。

?外賣配送問題，實質(zhì)上是帶有時間窗的VRP問題，針對VRP問題和外賣配送問題，國內(nèi)外學(xué)者們進行了大量的相關(guān)研究。文獻[1]建立了一種改進型的單場站、多輛車車輛路徑數(shù)學(xué)模型，將分枝界定法加以改進，設(shè)計出了一種車輛調(diào)度問題的精確算法，并對算法進行編程驗證。文獻[2]將可行解空間以恰當(dāng)?shù)姆椒ǚ殖梢粋€個的子集，在對各可行解子集計算出目標(biāo)下界的基礎(chǔ)上，重復(fù)分支與定界操作，以求出最終目標(biāo);另一種求解VRP問題的方法是現(xiàn)代啟發(fā)式優(yōu)化算法，以自然仿真算法為主，其中對遺傳算法的研究較多，文獻[3-5]都是對研究的問題先建立VRP模型，然后利用改進的遺傳算法從初始種群中找到最優(yōu)解。還有一些學(xué)者利用其他的現(xiàn)代啟發(fā)式優(yōu)化算法解決VRP問題，文獻[6]引入節(jié)約矩陣作為先驗信息引導(dǎo)螞蟻搜索，通過不同搜索時段采用不同的信息素揮發(fā)因子，使算法更好地在“探索”和“利用”之間達到平衡，并對較優(yōu)解進行優(yōu)化。文獻[7]分析供應(yīng)商，客戶和碼頭三者組成的VRP問題，給出了該問題的一個混合整數(shù)非線性數(shù)學(xué)公式，提出了一種蟻群系統(tǒng)與模擬退火相結(jié)合的混合元啟發(fā)式算法。文獻[8]將解決VRP問題的思路應(yīng)用到外賣配送中，分正常路況和擁堵路況兩種情況，將利潤最大、客戶滿意度最高和總里程最小作為優(yōu)化目標(biāo)函數(shù)，運用禁忌搜索算法進行求解。文獻[9]從配送模式的角度出發(fā)，實現(xiàn)一個多起點啟發(fā)式的規(guī)劃路徑來解決沃爾瑪和亞馬遜的“最后一英里”和“當(dāng)天送達”問題。

?本文從外賣騎手的角度出發(fā)，將遺傳算法和破壞重組算法結(jié)合，得到最優(yōu)配送路線，并通過MATLAB仿真驗證。

1 ?配送路徑規(guī)劃分析

1.1 ?基本遺傳算法的組成要素

1.1.1 ?染色體編碼方法

?遺傳算法的編碼方法有自然數(shù)編碼、二進制編碼和格雷碼編碼等。

?自然數(shù)編碼中由“1”“2”…“n”組成，每一個基因位代表一個顧客，基因序列代表配送的順序，由于需要多名配送人員對所有訂單進行處理，所以用數(shù)字“0”將各個配送員的配送路線分開，以此表示多條配送路線。二進制編碼由“1”“0”組成，較為簡單，具有編碼、解碼操作簡單易行，交叉、變異等遺傳操作便于實現(xiàn)，符合最小字符集編碼原則等優(yōu)點，但是由于時間窗約束的限制，此外賣配送路徑優(yōu)化問題是基于次序的組合優(yōu)化問題，且染色體二進制編碼方式的基因位數(shù)目多、交叉與變異結(jié)果數(shù)值范圍控制難度大、存在漢明懸崖（Hamming Cliff）現(xiàn)象等問題;格雷碼方法連續(xù)兩個整數(shù)所對應(yīng)的編碼值之間僅僅只有一個碼位是不同的，如表1所示。

格雷碼方法提高遺傳算法的局部搜索能力;交叉變異易于實現(xiàn)等優(yōu)點，結(jié)合本文研究問題，采用自然數(shù)編碼方法。

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

?通過染色體自然數(shù)的編碼，可以保證騎手具有明確的行駛路線，但是不能保證解碼的各條路徑都滿足載重量約束和時間窗約束，所以為了尋求最優(yōu)值，引入懲罰函數(shù)對不符合約束的路徑進行懲罰，懲罰函數(shù)如下式所示：

fs=cs+αqs+βws ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1）

其中：cs是配送員行駛的距離，qs是各條路徑違反容量約束之和，ws是各條路徑違反時間窗約束之和。由于違反載重量約束相比違反時間窗約束情節(jié)較輕，因此α=10， β=100。

?由于配送員的行駛距離，違反容量約束之和，違反時間窗約束之和單位不統(tǒng)一，因此需要對其進行數(shù)據(jù)歸一化處理。本文擬用公式（3）對其進行數(shù)據(jù)歸一化。

1.1.3 ?種群初始化

在初始化階段，由于有最大載重量的約束，顧客數(shù)目一般遠超最大載重量，因此配送路徑的產(chǎn)生需要兩個過程：初始化配送路徑數(shù)目k=1，當(dāng)?shù)?條路徑滿足載重量要求時，則將遍歷的顧客序號根據(jù)時間窗填到路徑當(dāng)中;如果第k條路徑不滿足載重量要求，則先儲存前k條滿足最大載重量約束的路徑之后，更新k=k+1。

?等所有顧客遍歷完，將得到多條路徑，將各路徑之間用數(shù)字“0”收尾連接，得到一個包含所有顧客序號的染色體編號，這個染色體編號就是一個完整的配送方案。將種群個數(shù)設(shè)置為100，即會產(chǎn)生相應(yīng)的100條染色體，至此，種群的初始化完成。

1.1.4 ?選擇操作

通過輪盤賭法進行選擇操作，輪盤賭法又叫比例選擇算法，其基本思想就是適應(yīng)度值越大，個體被選擇的概率就越大。具體步驟如下：

?步驟一：根據(jù)公式（4）計算出初始化后每個個體的適應(yīng)度值。

?步驟二：通過公式（5）計算出每個個體被遺傳到下一代的概率。

i=1，2，3，…，n，n為種群數(shù)目。

?步驟三：計算每個個體的累計概率如公式（6）所示：

1.1.5 ?交叉操作

對選擇的父代進行交叉操作產(chǎn)生新的子代。

對染色體進行交叉操作如圖1所示，首先確定基因交叉點，父代1的基因交叉點為3、4、5、6、7，父代2的基因交叉點為7、6、5、4、3，經(jīng)過交叉操作得到圖1（b）所示的子代染色體，子代染色體中含有重復(fù)的染色體，因此進行刪除操作，最終得到圖1（c）所示的子代染色體，從而完成交換染色體的操作。

1.1.6 ?變異操作

變異操作比較簡單，隨機選擇父代的兩個基因位置后交換，即可得到子代。

1.1.7 ?破壞重組算法

將遺傳算法與破壞重組算法結(jié)合，用破壞重組算法進行進一步的完善。破壞重組算法的實質(zhì)是通過交替的對基因位進行選擇破壞和重置修復(fù)操作來改善初始解。

?假設(shè)通過遺傳算法得到的較優(yōu)配送路線的罰函數(shù)值為S0，則用解決該類問題的流程圖如圖2所示。

1.2 ?算法流程圖

如圖3所示為基于破壞重組算法，解決帶載重量約束和時間窗約束的新型外賣配送模式。

2 ?仿 ?真

?分別利用算法結(jié)合前后對110位下單顧客進行仿真，通過對仿真結(jié)果進行分析比較來驗證遺傳算法和破壞重組算法結(jié)合的優(yōu)越性。

2.1 ?遺傳算法仿真

當(dāng)對110位下單顧客在傳統(tǒng)配送模式下進行仿真時，只允許騎手到商家和顧客的次數(shù)為1，每個顧客和商家對應(yīng)的配送時間窗在30～70分鐘之間，時間窗從0開始，一直到遍歷完所有的顧客和商家，服務(wù)時間為5分鐘。

通過MATLAB工具對遺傳算法進行仿真，得到如圖4、圖5所示的優(yōu)化過程圖和最優(yōu)配送方案路線圖。

得到的配送總距離為1 332.768米，配送結(jié)束時間為1 340分鐘，違反載重量和時間窗約束的路線為0。

2.2 ?遺傳算法和破壞重組算法結(jié)合的仿真

?通過MATLAB對新型配送模式進行仿真，得到如圖6、圖7所示的優(yōu)化過程圖和最優(yōu)配送方案路線圖。

得到的配送總距離為828.8186米，結(jié)束配送時間為1 236分鐘，違反載重量和時間窗約束的路線為0。配送路線為：

?配送路線1：0→67→65→63→62→74→72→61→64→48→51→52→47→0

?配送路線2：0→13→17→18→19→37→38→39→36→34→22→21→0

?配送路線3：0→43→42→41→40→44→46→45→50→49→0

? 配送路線4：0→32→33→31→35→29→15→16→14→12→99→2→75→0

? 配送路線5：0→20→24→25→27→30→28→26→23→0

?配送路線6：0→5→90→>87→86→83→82→84→85→88→89→91→0

?配送路線7：0→3→7→8→10→11→9→0

? 配送路線8：0→98→96→95→94→92→93→97→100→6→4→1→0

?配送路線9：0→81→78→76→71→70→73→77→79→80→0

?配送路線10：0→57→55→54→53→56→58→60→59→68→66→69→0

得到違反約束的路徑隨著迭代次數(shù)變化圖如圖8所示：

得到違反顧客時間窗數(shù)目隨著迭代次數(shù)變化圖如圖9所示：

3 ?仿真結(jié)果分析

3.1 ?優(yōu)化過程圖和最優(yōu)配送方案路線圖分析

?首先對優(yōu)化過程圖進行分析，上圖4和圖6分別為種群數(shù)目100，迭代100次得到的遺傳算法優(yōu)化過程圖和遺傳算法與破壞重組算法結(jié)合的優(yōu)化過程圖。

?在優(yōu)化過程圖中，橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示歸一化后的罰函數(shù)值，罰函數(shù)值越小代表規(guī)劃的路線越合理。由于開始的路線圖是隨機的，因此違反載重量和時間窗約束的路線較多，再加有權(quán)重的存在，所以開始的罰函數(shù)值較大。隨著不斷的優(yōu)化，加之違反載重量和時間窗口的懲罰成本高，當(dāng)?shù)畮状沃?，違反載重量和時間窗的路線變?yōu)?，只有騎手的行駛路程起作用，如圖4和圖6在迭代次數(shù)為10左右所示。隨著迭代次數(shù)的再度增加，遺傳算法與破壞重組算法結(jié)合的適應(yīng)度函數(shù)的最優(yōu)值也都慢慢收斂到0～1之間穩(wěn)定不變，即表示已找到最優(yōu)配送路線。

?在圖5遺傳算法下得到的最優(yōu)配送方案路線圖中，橫縱坐標(biāo)分別代表顧客點地理位置的橫縱坐標(biāo)，每根顏色的折線代表不同騎手的配送路線，帶序號的圓圈表示顧客的位置。

在遺傳算法模式下得到的配送路線中，12條配送路線表示有12名配送員參與此次配送任務(wù)，以紫色配送路線為例，該騎手從接到訂單任務(wù)后出發(fā)，依次給顧客序號90，87，81，78，76，71，70和73配送外賣，最后返回商家。

圖7遺傳算法與破壞重組算法結(jié)合模式下得到的最優(yōu)配送方案路線圖中。以配送路線1為例，該名騎手從商家出發(fā)，按照如下所示的配送路線0→67→65→63→62→74→72→61→64→48→51→52→47→0依次給顧客配送外賣，最后返回商家另外9條配送路線同理，另外該兩種算法的結(jié)合減少了配送員數(shù)量的使用，更加降低了成本。

?圖8和圖9反映了違反容量約束路徑數(shù)目和違反時間窗數(shù)目隨著迭代次數(shù)變化圖。違反容量約束指的是每個配送員為了勞動強度要求，一次外出配送有最大載貨量要求，超過這個數(shù)目是不被允許的，這是保障了騎手的勞動強度，從外賣騎手角度出發(fā)提出的要求;違反時間窗約束是指每個顧客點完外賣之后具有一定的時間窗要求，配送員需要在這個時間窗將外賣送到顧客手中，超過這個時間窗或者過早都是不被允許的，這是從顧客的角度出發(fā)提出的要求。迭代次數(shù)為0時，對應(yīng)遺傳算法初始化操作，通過圖8和圖9直觀看到，隨著迭代次數(shù)增加，違反容量約束數(shù)目和違反時間窗數(shù)目都在減小，并且最終收斂到0。

3.2 ?性能指標(biāo)比較

如表2所示為兩種仿真情況下配送時間和配送距離性能的比較。

通過表2可以直觀看到，遺傳算法和破壞重組算法結(jié)合的模式相較于只運用遺傳算法得到的配送路線，配送時間減少了7.76%，配送距離減少了27.21%，配送外賣員從12個減少到10個，因此整體效率更高，成本更低，表現(xiàn)出了很好的優(yōu)越性。

4 ?總 ?結(jié)

?通過聯(lián)系社會熱點，從外賣平臺騎手的安全利益角度出發(fā)，兼顧企業(yè)的效率和顧客的時間保障，針對具有大量外賣訂單的商家，將遺傳算法和破壞重組算法結(jié)合，對外賣配送路線進行規(guī)劃。

?為了比較遺傳算法和破壞重組算法求得的配送路線的優(yōu)越性，本文分別對遺傳算法和遺傳算法與破壞重組算法結(jié)合的配送路線進行了編碼，并且利用MATLAB平臺進行仿真，并對得到的優(yōu)化過程圖和最優(yōu)配送方案路線圖做了分析與比較，通過比較可以直觀地看到遺傳算法和破壞重組算法結(jié)合求得的配送路線無論是在配送時間還是配送距離都有很明顯的性能提升。

參考文獻：

[1] 曹平方，李靈，李詩珍. 基于分枝界定的VRP模型精確算法研究及應(yīng)用[J]. 包裝工程，2014，35（17）：97-101.

[2] ?Errico F， Desaulniers G， Gendreau M， et al. A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times[J]. European Journal of Operational Research， 2016，249（1）：55-66.

[3] 周生偉，蔣同海，張榮輝. 改進遺傳算法求解VRP問題[J]. 計算機仿真，2013，30（12）：140-143，157.

[4] 范厚明，耿靜，李陽，等. 模糊需求與時間窗的VRP及混合遺傳算法求解[J]. 系統(tǒng)管理學(xué)報，2020（1）：107-118.

[5] 冉崇善，張妍. 基于混合遺傳算法的大規(guī)模VRP問題算法研究[J]. 電腦知識與技術(shù)，2016，12（18）：182-184.

[6] 王曉東，張永強，薛紅. 基于改進蟻群算法對VRP線路優(yōu)化[J]. 吉林大學(xué)學(xué)報（信息科學(xué)版），2017，35（2）：198-203.

[7] ?Moghadam S S， Ghomi S M T F， Karimi B. Vehicle Routing Scheduling Problem with Cross Docking and Split Deliveries[J]. Computers & Chemical Engineering， 2014，69：98-107.

[8] ?Allahyari S， Salari M， Vigo D. A Hybrid Metaheuristic Algorithm for the Multi-Depot Covering Tour Vehicle Routing Problem[J]. European Journal of Operational Research， 2015，242（3）：756-768.

[9] ?Archetti C， Savelsbergh M， Speranza M G. The Vehicle Routing Problem with Occasional Drivers[J]. European Journal of Operational Research， 2016，254（2）：472-480.

[10] 王荃菲. 快餐外賣配送路徑方案研究[D]. 北京：北京交通大學(xué)（碩士學(xué)位論文），2017.

[11] ?Taha Yassen E， Ayob M， Ahmad Nazri M Z， et al. Meta-harmony search algorithm for the vehicle routing problem with time windows[J]. Information Sciences， 2015，325：140-158.

[12] ?H？觓， Bostel， Langevin， Rousseau， et al. An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices[J]. European Journal of Operational Research， 2013，226：211-220.

[13] ?Karaoglan， Altiparmak， Kara， et al. The location-routing problem with simultaneous pickup and delivery[J]. Formulations and a heuristic approach Omega， 2012，40：465-477.

[14] ?Lopes， Souza， da Cunha， et al. A branch-and-price algorithm for the multi-vehicle covering tour problem[J]. Electronic Notes in Discrete Mathematics， 2013，44：61-66.

[15] ?Baldacci， Mingozzi， Roberti， et al. New route relaxation and pricing strategies for the vehicle routing problem[J]. Operations Research， 2011，59（5）：1269-1283.

收稿日期：2021-12-20

基金項目：中央高校基本科研業(yè)務(wù)費項目（N2103028）

作者簡介：唐傳茵（1979-），女，遼寧沈陽人，東北大學(xué)機械工程與自動化學(xué)院，博士，碩士生導(dǎo)師，研究方向：群智能優(yōu)化算法、自動駕駛、車輛動力學(xué);劉春龍（1997-），男，山東臨沂人，東北大學(xué)機械工程與自動化學(xué)院碩士研究生，研究方向：群智能優(yōu)化算法、自動駕駛。