基于改進遺傳算法多車輛同城配送問題

包勝男, 靳文舟

(華南理工大學(xué) 土木與交通學(xué)院, 廣東 廣州 510641)

0 引言

同城速運是O2O電商新模式推動下生成的一種即時配送方式,通常存在“單方收貨多種技術(shù)產(chǎn)品”,或者“多方收貨一種企業(yè)產(chǎn)品”2種模式的差異需求。這種配送方式滿足一對多的服務(wù)需求,采用點對點的配送方式,并且向多品類、多場景的產(chǎn)品配送方向發(fā)展,服務(wù)于更多的B端和C端用戶。

對同城速運的研究,可以把這類問題抽象為帶時間窗的具有同時取送貨特性的車輛路徑問題(vehicle routing problem based on simultaneous pickup and delivery with time window, VRPSPDTW)。國內(nèi)外學(xué)者對VRPSPDTW有較多研究,并且引申出較多的研究方向,但是很少有學(xué)者考慮多車輛情況下的同城物流配送的路徑優(yōu)化問題。Hyungbin等[1]針對VRPPD提出一種等待策略。Agustín等[2]考慮了客戶之間的優(yōu)先級,開發(fā)了一個基于整數(shù)線性規(guī)劃(ILP)的局部搜索過程。Guo等[3]建立了一個根據(jù)操作標(biāo)準(zhǔn)、站點數(shù)量等一系列約束條件確定乘用車分配的模型。李博威等[4]考慮結(jié)合距離、車輛數(shù)、客戶滿意度等因素構(gòu)建了MINLP模型。張慶華等[5]基于逆向物流背景,采用模因算法得到解的性能提升。張思[6]等改進了傳統(tǒng)的禁忌搜索算法,用于考慮碳排放的配送模型。郭放等[7]研究小件物流配送,并考慮可以前往前置倉進行補貨與存貨的場景。馬艷芳等[8]從低碳方面和模糊需求來考慮問題并建立模型。周迅等[9]針對開放式選址路徑問題,設(shè)計了時間窗和同時取送貨約束。張景玲等[10]依據(jù)傳統(tǒng)的禁忌搜索提出了一種超啟發(fā)式算法。欒玉麟等[11]分析快時尚零售業(yè)取送貨提出了頂點拆分的策略。袁雨果[12]提出一種啟發(fā)式算法,結(jié)合了遺傳算法和變鄰域算法。楊東林等[13]提出O2O的不同配送模式中,中央配單有較好的效率。王超等[14]使用離散布谷鳥算法求解VRPSPDTW問題提升求解效率。陳希瓊等[15]結(jié)合貪婪轉(zhuǎn)移準(zhǔn)則改進蟻群算法產(chǎn)生新的帕累托解。徐東洋等[16]建立混合整數(shù)模型設(shè)計兩段啟發(fā)式求解算法。

從同城配送的發(fā)展現(xiàn)狀來看,訂單主要集中在餐飲和生鮮配送,這種訂單具有硬時間窗的要求,時間成本高,但是隨著電子商務(wù)的發(fā)展,多品類多場景的訂單會日益增加。例如服裝、日用品等具有寬松的時間窗的訂單比例逐漸上漲,如果依舊參照生鮮餐飲的配送模式,經(jīng)濟效益達不到最大化，因此基于同城配送的發(fā)展趨勢,本文提出的一種雙模式新型同城速運方案,訂單按照顧客配送時間的要求,分為普通件和急件,普通件集約配送產(chǎn)生效益大,急件的時間成本高優(yōu)先配送,配送過程中滿足每個配送點的同時取送貨需求并符合軟時間窗的約束。電商公司的配送車輛處于隨機位置,不再有回程約束,能夠隨時根據(jù)配送車輛的位置規(guī)劃出最合理的路徑,最大限度地減少物流成本和配送總時間。

1 VRPSPDTW同城配送模型建立

1.1 問題描述

同城速運問題描述如下:同城中有若干個節(jié)點,每一個節(jié)點均有不同取送貨需求,并且服務(wù)時間有規(guī)定,第i個顧客的服務(wù)時間必須滿足時間窗的要求,即第k輛車配送第i個顧客的時間不能晚于ai時刻。訂單根據(jù)顧客送達時間要求分為急件和普通件,普通件在3 h內(nèi)到達,急件在1 h內(nèi)到達,第k輛車由隨機位置出發(fā),采用先取后送的服務(wù)方式分類配送,完成任務(wù)后無需返回始發(fā)點,可以繼續(xù)由車輛所在位置繼續(xù)接收配送任務(wù),車輛不允許超出車容量限制。

普通件、急件的配送路徑分別如圖1、2所示。該模型的最終目標(biāo)是:在客戶取送貨需求、車輛載重能力以及服務(wù)時間等諸多約束條件下,合理安排車輛行駛路線,使得期望行駛總距離最小化。

圖1 普通件配送路徑示意圖

1.2 模型假設(shè)與變量說明

設(shè)G=(V,A)為有向圖,其中V為頂點集,A為弧集。模型變量說明見表1。

表1 模型變量說明

1.3 模型建立

(1)

(2)

(3)

Sik+ti+tij-M(1-xijk)≤Sjk,

(4)

Sik≤ai,

(5)

(6)

(7)

(8)

(9)

yij,zij≥0,?i,j∈V,

(10)

xijk∈{0,1},?i,j∈V,k∈K,

(11)

目標(biāo)函數(shù)(1)表示模型目標(biāo)為規(guī)劃車隊行駛的總成本最低的配送路線；約束(2)限制了每一個客戶點只能有一輛配送車輛訪問；約束(3)表示節(jié)點流量守恒；約束(4)和約束(5)表示快遞配送的時間窗約束；約束(6)表示車隊中的車輛最多只能使用一次；約束(7)保證每個弧上的貨物不能超過車輛容量限制；約束(8)和約束(9)表明提貨和交貨的流量守恒。

2 改進遺傳算法求解VRPSPDTW模型

通過對傳統(tǒng)遺傳算法進行改進來求解基于同時取送貨的多車輛同城配送的問題。傳統(tǒng)的遺傳算法機制的缺陷是在迭代的過程中容易陷入局部最優(yōu),基于此,本文結(jié)合模擬退火算法思想來改進。算法流程如圖3所示。

圖3 算法流程

① 編碼。染色體上的基因是關(guān)于取送貨點的自然數(shù),一條染色體就是全部取送貨點的不重復(fù)排列組合。染色體中編碼的排列位置,表示每一條經(jīng)過取送貨點的車輛路徑。

例如:1-2-(5-6)-3-(4-7),其中1表示車輛的初始點,編號2表示取貨點,編號5、6是取貨點2的送貨點,編號3是另一取貨點,編號4、7是取貨點3的送貨點,以此類推。

② 初始種群生成。隨機生成一定規(guī)模的初始種群。

③ 適應(yīng)度函數(shù)。適應(yīng)度函數(shù)g用來評判個體是否適合生存,結(jié)合模擬退火思想和罰函數(shù)思想,在適應(yīng)度函數(shù)中加入退火懲罰因子為

(12)

式中:g為適應(yīng)度函數(shù)；Sl為目標(biāo)函數(shù)；αi為退火懲罰因子,它和每個狀態(tài)的退火溫度成反比例關(guān)系。

④ 選擇算子。使用精英保留策略和輪盤賭2種方法相結(jié)合,首先對各個染色體的個體適應(yīng)度進行評估,按由大到小的順序排序進行排列,適應(yīng)度高的個體被優(yōu)先進行選擇,剩下個體通過輪盤賭選擇,組成同樣規(guī)模的種群按照適應(yīng)度大小排列后,將適應(yīng)度高的個體保存。由于在遺傳算法中引入模擬退火因子,因此局部最優(yōu)的可能性被降低。

⑤ 交叉算子。在2條染色體上隨機標(biāo)記2個相同位置的交叉點,兩點之間的基因片段互相交換。例如:

父代1:1 5 9|2 7 4 6 3|5 1 8

父代2:4 6 3|8 4 7 2 1|6 7 9

子代1:1 5 9|8 4 7 2 1|5 1 8

子代2:4 6 3|2 7 4 6 3|6 7 9

⑥ 變異算子。傳統(tǒng)遺傳算法的變異算子并未考慮到路徑的交叉問題,配送路徑的長度因此延長。本文在翻轉(zhuǎn)變異加入2-OPT,目的在于減少臨近取送貨點的路徑交叉現(xiàn)象。

加入2-OPT的具體做法:首先選中長度為n的個體,其次使用隨機函數(shù)得到下標(biāo)i(i+3

d(i,i+1)+d(i+2,i+3)

(13)

則將染色體下標(biāo)為i+1和i+2的送貨點編號交換,其中d(i,j)表示路段距離。

3 算例

3.1 算例說明

設(shè)定配送范圍為5 km×5 km的區(qū)域,隨機生成普通件與急件的取貨點和送貨點位置。車輛初始位置隨機,車輛初始位置坐標(biāo)分布見表2,普通件取貨點18個,送貨點38個,急件的取貨點5個。

表2 車輛初始位置坐標(biāo)分布

利用MATLAB編寫程序?qū)Ρ舅憷M行程序模擬,采取模擬退火算法相結(jié)合的改進遺傳算法求解,再與經(jīng)典遺傳算法進行求解質(zhì)量的對比分析。輸入初始參數(shù):初始種群規(guī)模N=200,最大的遺傳代數(shù)為400,交叉概率選擇為Pc=0.8,變異概率選擇為Pm=0.05,代溝設(shè)置為GGAP=0.9。初始溫度設(shè)定T=1 000 ℃,降溫速率為q=0.95。同城配送取送貨點位置圖如圖4所示。

圖4 同城配送取送貨點位置圖

3.2 實驗結(jié)果分析

隨機生成同樣的初始位置和取送貨點,分別采用經(jīng)典遺傳算法和改進遺傳算法求解出車輛路徑分配,算法迭代收斂如圖5、6所示,求解出的車輛配送路徑圖如圖7、8所示。由于目標(biāo)函數(shù)最優(yōu)值為成本最低,運輸成本是由單位距離乘以單位配送距離成本,因此目標(biāo)函數(shù)轉(zhuǎn)化為總體配送距離最短,采用2種遺傳算法解得的每輛車的配送路徑和行駛距離對比結(jié)果見表3。

圖5 經(jīng)典遺傳算法迭代收斂圖

圖6 改進遺傳算法迭代收斂圖

圖7 經(jīng)典遺傳算法求解路徑圖

圖8 改進遺傳算法求解路徑圖

表3 兩種算法求解出車輛配送路徑與行駛距離對比

由以上圖表可以分析得出:

① 圖5、6為算例總距離迭代對比圖,其中橫坐標(biāo)表示算法的迭代次數(shù),縱坐標(biāo)表示距離。由圖中可以看出,經(jīng)典的遺傳算法求解時達到350代后目標(biāo)函數(shù)開始收斂,而改進遺傳算法進行求解,迭代次數(shù)達到150代則開始收斂至最優(yōu)值,改進遺傳算法能在較短的迭代時間向最優(yōu)解靠攏,有較強的全局搜索的能力。

② 經(jīng)典遺傳算法求解出車隊的總體配送距離值最優(yōu)值為224.896 7 km,改進遺傳算法求解出車輛配送總距離124.696 km,配送車隊行駛總里程減少比例為44.6%,有效減少車輛油耗和配送時間,進而節(jié)省成本。

③ 傳統(tǒng)的遺傳算法陷入局部最優(yōu),在此選取最長配送路徑進行分析。經(jīng)典遺傳算法中的最長的配送的總距離已經(jīng)達到32.270 6 km,占比優(yōu)化后的車輛配送路徑總距離的1/4。配送路徑回路較多,整體路徑分配不夠均衡,規(guī)劃路徑的取貨點和送貨點的分配不夠合理。改進遺傳算法車輛載重配比比較均衡,最大限度發(fā)揮車輛的載重限制,有利于節(jié)省成本。

④ 傳統(tǒng)遺傳算法每輛車行駛的平均里程為17.300 km,車輛間的行駛距離極差大,改進遺傳算法求解每輛車的平均行駛里程為9.592 km,單車輛的運輸距離有明顯的減少,車輛的行駛距離更加均衡。

綜上所述,本文的改進遺傳算法在求解車輛的配送路徑和配送成本的性能指標(biāo)上相對于傳統(tǒng)遺傳算法有提升,能夠為同城配送提供有價值的調(diào)度方案。

3.3 敏感度分析

普通件和急件混合配送的模式可以在時間窗的約束下合理安排配送普通件和急件,以滿足配送成本最低的目標(biāo)要求。這種配送模式使得配送能力得到提高,并且節(jié)約了有限的運力資源,因此探究普通件和急件時間窗的閾值范圍,在滿足最低目標(biāo)函數(shù)下,進行時間窗的敏感度分析。

不同時間窗閾值范圍如圖9所示。從圖中可以看出,普通件時間窗和急件時間窗對配送成本均有較為明顯的影響。從普通件時間窗來看,配送成本隨著普通件時間窗增加而降低,這是由于配送普通件時間窗設(shè)置較短,則普通件配送達不到集約化,導(dǎo)致配送成本增加。隨著時間窗長度增加,成本的降低程度趨于平緩,這是由于配送成本對普通件時間窗的敏感程度低,普通件時間窗每增加0.5 h,集約程度已經(jīng)達到較高水準(zhǔn),此時增加配送普通件時間窗長度對配送成本降低效果不明顯。

圖9 不同時間窗閾值范圍

從急件時間窗來看,配送成本隨著時間窗的增加而增加,這是由于急件配送時間價值高,若是時間窗的增加,急件的時間成本增加，并且急件的數(shù)量遠小于普通件的,每輛車都有固定車輛啟動成本,配送急件時間窗增加使得車輛利用率得不到明顯提升,因此總的配送成本會隨急件的時間窗的長度的增加而增加。同時可以看出,配送成本對急件時間窗的敏感程度高于普通件,急件時間窗每增加0.5 h,配送成本急劇升高,因此,在設(shè)定時間窗時,應(yīng)選擇合理的時間窗長度組合,過長或過短都不利于配送成本的最優(yōu)。

4 結(jié)論

本文針對多車輛同時取送貨的同城配送問題,將訂單按照不同的時間窗要求,分為普通件和急件分類配送,并建立VRPSPDTW模型,配送車輛在路網(wǎng)內(nèi)隨機分布,可以繼續(xù)進行下一階段任務(wù)節(jié)省配送成本。

通過改進遺傳算法對VRPSPDTW模型求解,得出每輛車的經(jīng)過優(yōu)化后的配送路徑,總體配送距離得到較為滿意的優(yōu)化結(jié)果。本文通過對經(jīng)典遺傳算法的改進,在適應(yīng)度函數(shù)方面引入了罰函數(shù)因子并結(jié)合了模擬退火機制,加強了對個體適應(yīng)度的判斷。在翻轉(zhuǎn)變異方面加入2-OPT減少臨近配貨點之間路線交叉,通過算例驗證,與經(jīng)典遺傳算法同時對解的質(zhì)量進行分析,得出改進遺傳算法配送路徑較為合理,減少了車輛的配送距離和成本,模型和算法具有有效性和可行性。

未來在模型上可以考慮時間、成本等多目標(biāo)的優(yōu)化,突發(fā)狀態(tài)下的動態(tài)分類配送也可以進行更加深入的研究。