改進(jìn)遺傳算法求解帶時(shí)間窗的外賣配送車輛路徑規(guī)劃

趙家儒，譚代倫

(1.西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川南充 637009；2.西華師范大學(xué)計(jì)算方法及應(yīng)用軟件研究所，四川南充 637009)

0 引言

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

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

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

1 問(wèn)題描述與數(shù)學(xué)模型

1.1 問(wèn)題描述

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

1.2 數(shù)學(xué)模型

上述外賣配送車輛路徑規(guī)劃問(wèn)題，從配送人員行走路徑來(lái)看，具有旅行商問(wèn)題(Travelling Salesman Problem,TSP)的基本特征，即從某一個(gè)節(jié)點(diǎn)出發(fā)，經(jīng)歷所有的節(jié)點(diǎn)一次且只經(jīng)過(guò)一次，最終回到出發(fā)點(diǎn)，因此可借鑒TSP問(wèn)題來(lái)建立本類問(wèn)題的數(shù)學(xué)模型.

設(shè)在配送人員所承接的一組外賣訂單中餐飲商家有n1個(gè)、客戶有n2個(gè)，則配送人員從配送中心0出發(fā)，取餐和送餐需要經(jīng)過(guò)的節(jié)點(diǎn)總數(shù)為n=n1+n2.按一定順序?qū)λ泄?jié)點(diǎn)統(tǒng)一編號(hào)，記第i個(gè)路徑節(jié)點(diǎn)及其平面坐標(biāo)為pi(xi,yi)，相應(yīng)的時(shí)間窗上限為bi.又有配送人員在配送過(guò)程中的行駛速度記為v，且始終是勻速行駛的，任意兩個(gè)節(jié)點(diǎn)pi,pj之間的距離記為dij，所耗費(fèi)的行駛時(shí)間記為tij，取歐式距離公式進(jìn)行計(jì)算，則有

(1)

對(duì)由所有路徑節(jié)點(diǎn)按一定順序構(gòu)成的一條回路P={p0→p1→p2→...→pn→p0}，就是配送人員的一條配送路徑.當(dāng)配送人員始終以勻速行駛時(shí)，配送路徑總長(zhǎng)度最短與配送行駛時(shí)間最短是等價(jià)的，并且配送總是要受時(shí)間窗限制的約束，于是可建立如下數(shù)學(xué)模型：

(2)

(3)

上述模型的約束條件表示配送人員沿某個(gè)回路行駛時(shí)，每到達(dá)一個(gè)路徑節(jié)點(diǎn)所花費(fèi)的時(shí)間之和應(yīng)不超過(guò)該節(jié)點(diǎn)的時(shí)間窗上限.

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

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

2.1 編碼方案

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

2.2 基于修復(fù)算子的種群初始化

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

(1)種群個(gè)體的第一個(gè)基因均設(shè)置為0，其余基因按均勻分布隨機(jī)產(chǎn)生[1,n]區(qū)間內(nèi)的不重復(fù)自然數(shù)；

(2)對(duì)每個(gè)個(gè)體，按訂單依次查找商家編號(hào)以及與之對(duì)應(yīng)的顧客編號(hào)；

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

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

2.3 基于超時(shí)懲罰的適應(yīng)度函數(shù)

遺傳算法的適應(yīng)度函數(shù)用于評(píng)估和區(qū)分種群個(gè)體的優(yōu)劣，適應(yīng)度值是進(jìn)行遺傳選擇的依據(jù).由于上述問(wèn)題是有約束優(yōu)化問(wèn)題，因此構(gòu)造適應(yīng)度函數(shù)時(shí)，將原目標(biāo)函數(shù)作為適應(yīng)度函數(shù)的一個(gè)分量，如下：

(4)

對(duì)約束條件，采用懲罰函數(shù)的方法將其變換為適應(yīng)度函數(shù)的另一個(gè)分量.在實(shí)際生活中，客戶的耐心會(huì)隨著配送人員所超過(guò)的時(shí)間呈非線性增長(zhǎng)，由此選取以2為底的指數(shù)函數(shù)對(duì)超時(shí)情形進(jìn)行懲罰，對(duì)應(yīng)的適應(yīng)度函數(shù)分量如下：

(5)

(6)

其中，T0i表示配送人員沿某個(gè)行駛路徑到達(dá)第i個(gè)配送點(diǎn)時(shí)所花費(fèi)的時(shí)間總和，可用式(6)予以計(jì)算.

綜合式(4)(5)(6)，本文遺傳算法所構(gòu)造的適應(yīng)度函數(shù)為：

(7)

其中p為所有路徑節(jié)點(diǎn)構(gòu)成的任意一個(gè)合法的頂點(diǎn)序列，即配送人員的任意一條可行路徑.

2.4 選擇策略

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

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

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

(4)轉(zhuǎn)動(dòng)輪盤，隨機(jī)選擇個(gè)體：隨機(jī)生成一個(gè)[0，1]之間的數(shù)r，若pi≤r

2.5 自適應(yīng)交叉與變異策略

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

設(shè)fi為某個(gè)個(gè)體的適應(yīng)度值，favg為個(gè)體適應(yīng)度值的平均值，fmin為個(gè)體適應(yīng)度的最小值，由于外賣配送路徑規(guī)劃問(wèn)題是極小值問(wèn)題，這里將它們?nèi)〉箶?shù)，記為：

(8)

又設(shè)交叉概率值的范圍為[pc1,pc2]，變異概率值的范圍為[pm1,pm2]，自適應(yīng)變化的交叉概率值和變異概率值記為pc和pm，則構(gòu)造自適應(yīng)變化公式如下：

(9)

(10)

其中α稱為自適應(yīng)增量因子，其公式為：

(11)

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

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

2.6 算法流程圖

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

3.1 數(shù)據(jù)準(zhǔn)備

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

表1 外賣訂單詳情

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

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

表2 各點(diǎn)之間的行駛時(shí)間(分鐘)

3.2 實(shí)驗(yàn)結(jié)果及比較

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

圖3 改進(jìn)遺傳算法的流程圖

表3 三種算法的參數(shù)設(shè)置及求解結(jié)果

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

圖4 三種算法的適應(yīng)度進(jìn)化曲線

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

3.3 算法性能分析

為進(jìn)一步測(cè)試本文改進(jìn)遺傳算法(IGA)的性能，將三種算法程序在MATLAB2016b環(huán)境中獨(dú)立運(yùn)行100次，各算法的參數(shù)仍按表3進(jìn)行設(shè)置.記錄并統(tǒng)計(jì)各個(gè)算法程序100次求解所得的最大值、最小值、平均值、方差，結(jié)果如表4所示.

表4 三種算法獨(dú)立運(yùn)行100次的統(tǒng)計(jì)結(jié)果

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

4 結(jié)束語(yǔ)

針對(duì)帶時(shí)間窗的外賣路徑規(guī)劃問(wèn)題，在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，將取值固定的交叉變異概率值改進(jìn)為具有余弦變化特征的自適應(yīng)概率值，進(jìn)而提出改進(jìn)遺傳算法.仿真實(shí)例結(jié)果表明，改進(jìn)遺傳算法比標(biāo)準(zhǔn)遺傳算法、標(biāo)準(zhǔn)蟻群算法的求解效率更高、求解結(jié)果更加穩(wěn)定，算法的魯棒性也更強(qiáng).