改進遺傳算法求解帶時間窗的外賣配送車輛路徑規劃

趙家儒，譚代倫

(1.西華師范大學數學與信息學院，四川南充 637009；2.西華師范大學計算方法及應用軟件研究所，四川南充 637009)

0 引言

隨著現代制造業和物流業的快速發展，車輛路徑規劃問題(Vehicle Routing Problem，VRP)[1]得到重視和研究，Dantzig等在1954年研究汽油運輸卡車的最優路徑時首次提出該類問題[2]，并將其描述為:對給定的一組客戶，為從某個特定配送中心出發的運輸車輛規劃出最優行駛路線，使得在滿足一定約束條件下行駛成本(如里程數、耗費時間等)盡量少.

針對VRP問題的約束條件，國內外學者提出了車輛容量約束、滿足客戶時間需求的時間窗約束等典型情形.尤其是后者，在現代社會的快節奏生活中，越來越被社會大眾所重視，因此帶時間窗的車輛路徑規劃問題(Vehicle Routing Problem with Time Window，VRPTW)成為VRP問題的一種典型擴展情形.對此類問題，Larsen首次將時間窗和車輛路徑問題相聯系，并進行了分析和研究[3].

隨著現代餐飲企業開啟O2O服務新模式，餐飲外賣的最優配送引起了研究者的濃厚興趣，部分研究者將VRPTW問題遷移到這類問題中，形成了帶時間窗的外賣配送車輛路徑規劃問題(Delivery Vehicle Routing Problem with Time Window，DVRPTW).目前對該類問題的研究取得了一些成果，余建軍等針對生鮮外賣配送,設計了模糊時間窗，用遺傳算法對配送路徑進行規劃[4]；吳球軍在硬時間窗的約束下設計了路徑規劃滯后法和路徑規劃優先法兩種不同思路來進行路徑規劃[5]；劉曉扣等運用遺傳算法求解了在外賣員人數和外賣提供能力均無限制的前提下滿足時間窗約束的配送路徑規劃[6]；李雪妍為了減少配送平臺的人工成本和超時時間，提高配送效率，探究了在派單模式下的配送路徑規劃[7]；黃心等通過蟻群算法對不同地址的收貨點進行路徑規劃，為送貨人員規劃了最短時間的路徑[8]；陳火根等針對帶時間窗的路徑規劃問題，提出了遺傳算法與啟發式算法相結合的求解方法[9]；Sophie對一般配送貨物類問題進行了綜述，歸納和總結了不同的取送貨路徑問題的特點[10]；李卓等提出螢火蟲算法與蟻群算法相結合來求解路徑規劃問題，提高了這類問題的求解效率[11]；韓亞娟等以遺傳算法作為上層搜索算法，以3種啟發式算法—CW節約法、MJ插入法和Kilby插入法作為底層搜索規則，并通過預排序、局部搜索和全局優化來優化算法[13].從現有文獻可以看到，DVRPTW問題在求解算法上研究成果還比較少，為此本文提出一種改進遺傳算法對該類問題進行求解.

1 問題描述與數學模型

1.1 問題描述

某企業負責城市內餐飲外賣配送業務，企業將一定時間內產生的一組外賣訂單分配給某一個配送人員去完成，現考慮為其規劃一條最佳路徑.在一組外賣訂單中，餐飲商家和客戶具有一一對應的關系，他們的地圖位置也是已知的.配送人員需要從企業特定的配送中心出發，配送的基本規則是同一訂單必須先取餐再送餐，即先到指定商家處取得某客戶的餐飲外賣食品，再送到該客戶處，期間不考慮取餐和送餐時的交接時間.由于外賣餐飲的時效性，取餐和送餐均有時間范圍要求，稱為時間窗限制，即從訂單成立開始計時要盡量在給定的時間范圍內取到外賣餐飲或送到客戶處，否則配送人員和企業將遭受信用或經濟損失.配送過程中不考慮車輛的載重限制，配送人員可以先到多個商家取得多份外賣餐飲，再陸續配送到多個客戶手中.配送期間不再接受新的訂單，完成全部訂單后，配送人員需要回到企業的配送中心，以接受下一批訂單.

1.2 數學模型

上述外賣配送車輛路徑規劃問題，從配送人員行走路徑來看，具有旅行商問題(Travelling Salesman Problem,TSP)的基本特征，即從某一個節點出發，經歷所有的節點一次且只經過一次，最終回到出發點，因此可借鑒TSP問題來建立本類問題的數學模型.

設在配送人員所承接的一組外賣訂單中餐飲商家有n1個、客戶有n2個，則配送人員從配送中心0出發，取餐和送餐需要經過的節點總數為n=n1+n2.按一定順序對所有節點統一編號，記第i個路徑節點及其平面坐標為pi(xi,yi)，相應的時間窗上限為bi.又有配送人員在配送過程中的行駛速度記為v，且始終是勻速行駛的，任意兩個節點pi,pj之間的距離記為dij，所耗費的行駛時間記為tij，取歐式距離公式進行計算，則有

(1)

對由所有路徑節點按一定順序構成的一條回路P={p0→p1→p2→...→pn→p0}，就是配送人員的一條配送路徑.當配送人員始終以勻速行駛時，配送路徑總長度最短與配送行駛時間最短是等價的，并且配送總是要受時間窗限制的約束，于是可建立如下數學模型：

(2)

(3)

上述模型的約束條件表示配送人員沿某個回路行駛時，每到達一個路徑節點所花費的時間之和應不超過該節點的時間窗上限.

2 改進遺傳算法設計

外賣配送車輛路徑規劃是一類組合優化問題，也是NP-hard問題，求解這類問題的主要方法是現代智能算法.其中遺傳算法通過模仿自然界生物的選擇與遺傳機理來尋求最優解,遺傳算法相比于其他算法具有優異的自適應性、并行性和全局尋優能力.已經被廣泛應用于求解組合優化問題和NP-hard問題.為此，本文也選擇遺傳算法進行求解，通過種群修復、自適應交叉與變異等改進策略，進一步提高算法的求解性能.

2.1 編碼方案

將上述外賣配送車輛路徑規劃問題轉化為旅行商問題(TSP)后，配送人員取餐和送餐所要經過的商家或客戶，就是TSP問題的每一個路徑頂點，所有頂點按一定順序的不重復排列{p1,p2,...,pn}就是配送人員完成全部訂單的一條行走路徑.為此，本文采用由{1,2,...,n}構成的不重復自然數編碼方案，每一個數字對應于一個路徑頂點的編號，不同的排列對應于不同的行走路徑.由于配送人員總是要從配送中心出發，完成全部訂單后要回到配送中心，因此將配送中心也看作是一個路徑頂點，編號為0，它始終位于編碼序列的起始位置，于是本文算法所采用的最終編碼方案形如{0,1,2,...,n}，其中經過最后一個頂點后還需要返回到起始頂點處.

2.2 基于修復算子的種群初始化

根據上述編碼方案，第一個自然數固定為0，種群初始化時只需生成{1,2,...,n}的任意隨機序列即可.由于外賣配送需要滿足先到商家取貨再到對應客戶送貨的順序限制，而在隨機初始種群可能會產生不滿足順序限制的個體，因此需要對這部分不滿足要求的個體進行修復，其修復步驟如下

(1)種群個體的第一個基因均設置為0，其余基因按均勻分布隨機產生[1,n]區間內的不重復自然數；

(2)對每個個體，按訂單依次查找商家編號以及與之對應的顧客編號；

(3)判斷兩者基因位置的先后關系，若商家基因位置處于顧客基因位置之后，則將這兩個基因位置交換；

(4)重復(2)與(3)，直到所有個體和所有訂單全部修復完.

2.3 基于超時懲罰的適應度函數

遺傳算法的適應度函數用于評估和區分種群個體的優劣，適應度值是進行遺傳選擇的依據.由于上述問題是有約束優化問題，因此構造適應度函數時，將原目標函數作為適應度函數的一個分量，如下：

(4)

對約束條件，采用懲罰函數的方法將其變換為適應度函數的另一個分量.在實際生活中，客戶的耐心會隨著配送人員所超過的時間呈非線性增長，由此選取以2為底的指數函數對超時情形進行懲罰，對應的適應度函數分量如下：

(5)

(6)

其中，T0i表示配送人員沿某個行駛路徑到達第i個配送點時所花費的時間總和，可用式(6)予以計算.

綜合式(4)(5)(6)，本文遺傳算法所構造的適應度函數為：

(7)

其中p為所有路徑節點構成的任意一個合法的頂點序列，即配送人員的任意一條可行路徑.

2.4 選擇策略

選擇操作是模擬生物種群的“適者生存、優勝劣汰”的自然生存法則，在算法中其目的是選出較優的個體，淘汰部分較差的個體.這里選擇比較成熟的輪盤賭策略，它的基本思路是依據適應度值的大小，通過輪盤賭的方式進行隨機選擇，這樣個體適應度值越大，則被選中的的概率越大，其基本步驟為：

(2)計算每個個體適應度與總適應度的比值，得到個體的入選概率pi=fi/F；

(3)將所有個體的入選概率拼成一個輪盤；

(4)轉動輪盤，隨機選擇個體：隨機生成一個[0，1]之間的數r，若pi≤r

2.5 自適應交叉與變異策略

遺傳算法的選擇操作只能將種群較優的個體篩選出來，遺傳到子代種群中，并沒有新個體產生.為保持種群的多樣性，避免陷入早熟，真正實現全局尋優，還必須借助交叉和變異操作，前者是將種群中某兩個個體的部分基因進行隨機互換，后者是將某個個體的部分基因產生隨機突變，因此兩種操作本質上都產生了新個體，增強了種群的多樣性.遺傳算法的交叉和變異操作除了選取合適的交叉變異方式外，還需要設置交叉概率值和變異概率值，其中后者對算法進行全局尋優效果的影響也是非常明顯的.為此，本文著重對交叉概率值和變異概率值的設置進行改進，采取自適應策略，使交叉和變異概率值能隨著個體的平均適應度而改變，而不是取固定的取值.

設fi為某個個體的適應度值，favg為個體適應度值的平均值，fmin為個體適應度的最小值，由于外賣配送路徑規劃問題是極小值問題，這里將它們取倒數，記為：

(8)

又設交叉概率值的范圍為[pc1,pc2]，變異概率值的范圍為[pm1,pm2]，自適應變化的交叉概率值和變異概率值記為pc和pm，則構造自適應變化公式如下：

(9)

(10)

其中α稱為自適應增量因子，其公式為：

(11)

根據式子(9)(10)(11)，自適應交叉與變異概率值變化規律如圖1圖2所示：

由于外賣配送路徑既包含商家節點，又包含客戶節點，一旦個體的某個基因發生變異，則需要再次調用個體修復算子，檢查并修復個體中異常的基因，使其成為合法個體(可行路徑).為此，本文采用單點交叉和單點變異操作，一旦發生交叉或變異操作，必定會產生新的個體，在自適應交叉和變異概率控制下，能根據迭代進度保持合適的種群多樣性，使收斂效果更好.

2.6 算法流程圖

3 實驗仿真與分析

3.1 數據準備

以某城市某區域的外賣配送情況為例[7]，取某個外賣配送員的一次訂單，如表1所示.

表1 外賣訂單詳情

表1中，同一行的商家和客戶構成一組配送關系.外賣公司的配送中心編號為0，地址為(1.02，5.56).

外賣配送人員的平均行駛速度為v=200m/min，根據公式(1)計算出外賣配送員在兩點之間行駛所需的時間，如表2所示.其中任意兩點之間的距離以歐式距離公式來計算.

表2 各點之間的行駛時間(分鐘)

3.2 實驗結果及比較

按圖3算法流程編寫改進遺傳算法(IGA)程序.為便于比較，同時還按照標準遺傳算法(SGA)和標準蟻群算法(SACO)進行編程求解，其中蟻群算法是基于螞蟻覓食行為和過程的仿生學智能算法，在求解路徑規劃類問題時也有良好的效果.三種算法的參數設置及求解結果如表3所示.

圖3 改進遺傳算法的流程圖

表3 三種算法的參數設置及求解結果

從表3可以看到，種群規模與迭代次數均相同時，改進遺傳算法(IGA)得到的最優適應度值均明顯優于其余兩種算法.所求得的最優路徑為0→5→3→6→1→2→9→4→7→12→8→11→10→0.對應于表3，三種算法求解時的適應度進化曲線如圖4所示.

圖4 三種算法的適應度進化曲線

由圖4可知，本文的改進遺傳算法(IGA)由于采用了自適應交叉變異策略，大大增加了子代種群的多樣性，加快了算法的收斂速度，迭代次數約15次時，適應度值已經趨于最優，表現出具有更強的尋優能力和收斂性.

3.3 算法性能分析

為進一步測試本文改進遺傳算法(IGA)的性能，將三種算法程序在MATLAB2016b環境中獨立運行100次，各算法的參數仍按表3進行設置.記錄并統計各個算法程序100次求解所得的最大值、最小值、平均值、方差，結果如表4所示.

表4 三種算法獨立運行100次的統計結果

從表4可以看到，本文改進遺傳算法(IGA)所求得最優值的平均值明顯優于另外兩種算法，最大值和最小值偏離均值的幅度也更小，對應的方差更是遠小于另外兩種算法.由此可見，本文改進遺傳算法在修復算子和自適應策略的共同作用下，獲得最優解的收斂速度更快、效率更高，求解過程更加穩定.

4 結束語

針對帶時間窗的外賣路徑規劃問題，在標準遺傳算法的基礎上，將取值固定的交叉變異概率值改進為具有余弦變化特征的自適應概率值，進而提出改進遺傳算法.仿真實例結果表明，改進遺傳算法比標準遺傳算法、標準蟻群算法的求解效率更高、求解結果更加穩定，算法的魯棒性也更強.