基于混合啟發(fā)式算法的快遞末端選址路徑優(yōu)化研究*

孫睿男,初 翔,陳 昱,閆明寧

(1.大連海事大學(xué)航運(yùn)經(jīng)濟(jì)與管理學(xué)院,遼寧 大連 116026;2.大連海事大學(xué)綜合交通運(yùn)輸協(xié)同創(chuàng)新中心,遼寧 大連 116026)

1 引言

近年,快遞數(shù)量快速增長(zhǎng),給快遞末端網(wǎng)點(diǎn)及末端配送環(huán)節(jié)帶來(lái)了巨大的壓力。目前,快遞配送末端由于各自為政的配送模式,導(dǎo)致配送成本居高不下,而共同配送模式可以有效降低末端配送成本[1]。因此,在共同配送模式下,合理規(guī)劃快遞網(wǎng)點(diǎn)選址及配送路徑問(wèn)題具有重要的研究意義。

有關(guān)選址路徑問(wèn)題研究中,王琪瑛等[2]研究了電動(dòng)車輛選址路徑問(wèn)題;胡大偉等[3]研究了兩階段的選址路徑問(wèn)題;Arslan[4]從客戶覆蓋范圍的角度研究了選址路徑問(wèn)題。Kinay等[5]對(duì)充電站選址問(wèn)題進(jìn)行了研究。Ozbaygin等[6]對(duì)動(dòng)態(tài)路徑問(wèn)題進(jìn)行了研究。上述選址路徑研究多假設(shè)客戶需求為已知的情況,而在快遞實(shí)際配送過(guò)程中,一般其派件量為已知,而收件量為不確定的情形,關(guān)于隨機(jī)選址路徑問(wèn)題相關(guān)文獻(xiàn)也較為豐富,如需求不確定型[7-9]、時(shí)間不確定型[10]、距離不確定型[11]、場(chǎng)景不確定型[12]及多重因素不確定型[13]。

針對(duì)末端快遞選址路徑的研究文獻(xiàn)也較為豐富,如de Giovanni等[14]針對(duì)快遞貨運(yùn)路徑規(guī)劃問(wèn)題進(jìn)行研究,建立了綜合考慮車輛容量、時(shí)間窗約束的數(shù)學(xué)模型。Bergmann等[15]對(duì)城市配送最后一公里問(wèn)題進(jìn)行研究,建立了考慮車輛容量的數(shù)學(xué)模型。許闖來(lái)等[16]對(duì)快遞配送網(wǎng)絡(luò)進(jìn)行研究,在建立模式時(shí)考慮了配送車輛載荷約束。裴利奇等[17]研究了快遞中轉(zhuǎn)站選址問(wèn)題,建立了考慮快遞中轉(zhuǎn)站容量和配送車輛載荷約束的數(shù)學(xué)模型。Li等[18]對(duì)快遞企業(yè)配送包裹問(wèn)題進(jìn)行了研究,在建模時(shí)加入了載具容量約束。Yan等[19]建立了城市動(dòng)態(tài)快遞調(diào)度模型,在模型中也考慮了容量約束。姬楊蓓蓓等[19]針對(duì)快遞末端配送網(wǎng)絡(luò)優(yōu)化,建立了考慮車輛載荷約束的選址路徑模型。可以看出,以上對(duì)快遞末端網(wǎng)點(diǎn)配送的研究都只考慮配送車輛的載重約束,均未考慮快遞配送與物流配送之間的差異。快遞配送與物流配送之間的區(qū)別主要有以下2點(diǎn):(1)快遞配送除了對(duì)快件重量有限制之外,對(duì)快件的體積也有一定的約束。如賀冰倩等[21]對(duì)快遞收派路徑規(guī)劃問(wèn)題進(jìn)行了研究,在建立模型時(shí)同時(shí)考慮了快件容量和體積約束。(2) 在物流配送中,末端配送基本使用輕型廂式貨車作為配送載具;而快遞配送方式大多為快遞員進(jìn)行末端配送,配送成本多為人工成本。

梳理上述文獻(xiàn)可知,相關(guān)研究已取得一定成果,但還存在以下幾點(diǎn)不足:(1)大部分文獻(xiàn)并未考慮到快遞同時(shí)收派件,且需求隨機(jī)的情況;(2)配送車輛返回策略均為返回原出發(fā)網(wǎng)點(diǎn),該返回策略易造成較高的配送成本;(3)所建模型大部分未考慮快遞末端配送的實(shí)際特性,即快遞配送與物流配送之間的差異性。

因此,基于以上幾點(diǎn),本文結(jié)合共同配送模式特點(diǎn),考慮快遞配送與物流運(yùn)輸之間差異性,以人工成本為目標(biāo)函數(shù),引入隨機(jī)機(jī)會(huì)約束解決需求隨機(jī)問(wèn)題,基于最近網(wǎng)點(diǎn)返回策略,建立包含快件重量、體積以及配送員最大時(shí)長(zhǎng)等約束的數(shù)學(xué)規(guī)劃模型;并設(shè)計(jì)基于遺傳算法和自適應(yīng)大鄰域搜索ALNS(Adaptive Large Neighborhood Search algorithm)算法的混合啟發(fā)式算法,對(duì)隨機(jī)需求下快遞網(wǎng)點(diǎn)選址路徑問(wèn)題進(jìn)行研究。所得結(jié)論可為快遞企業(yè)提供相應(yīng)管理啟示,并為后續(xù)對(duì)隨機(jī)需求選址路徑研究提供方法參考。

2 共同配送隨機(jī)LRP模型建立

2.1 問(wèn)題描述

本文所研究問(wèn)題可描述為在某區(qū)域內(nèi)存在多家快遞企業(yè)的快遞網(wǎng)點(diǎn),后文簡(jiǎn)稱為網(wǎng)點(diǎn),客戶點(diǎn)和網(wǎng)點(diǎn)的位置已知,所有節(jié)點(diǎn)集合A=W∪C,網(wǎng)點(diǎn)集合為W={1,2,…,n},si為網(wǎng)點(diǎn)i的建設(shè)成本,1≤i≤n,網(wǎng)點(diǎn)最大容量為Qw(w∈W),實(shí)際容量為Qi,客戶點(diǎn)集合為C={n+1,n+2,…,n+m}。每個(gè)客戶點(diǎn)派件量是確定的,收件量為不確定的情況,dwj和dvj分別為客戶點(diǎn)j(n+1≤j≤n+m)的派件重量和體積,rwj和rvj分別為客戶點(diǎn)j的收件重量和體積,假設(shè)每個(gè)客戶的收件量相互獨(dú)立且均服從相同泊松分布,E(rwj)和E(rvj)分別為收件重量和體積的期望值。dij為任意網(wǎng)點(diǎn)i和客戶點(diǎn)j之間的距離,dj(j+1)為任意客戶點(diǎn)j和客戶點(diǎn)j+1間的距離,其余變量均用此方法表示。K={1,2,…,α}為配送車輛集合,V為配送車輛行駛速度。假設(shè)配送時(shí),車輛一直保持勻速行駛,Qk和Vk分別為配送車輛k(1≤k≤a)的最大容量和最大體積,Qijk為配送車輛k在網(wǎng)點(diǎn)i和客戶點(diǎn)j之間的載量,Vijk為車輛k在網(wǎng)點(diǎn)i和客戶點(diǎn)j之間的配送體積。cd和cr分別為配送員派件和收件的單位人工成本,cs為單位時(shí)間配送的人工成本,Tp為配送員單次最大配送時(shí)長(zhǎng)。決策變量Zi∈{0,1},若Zi=1,表示在網(wǎng)點(diǎn)i建立快遞網(wǎng)點(diǎn),否則相反;決策變量Yij∈{0,1},若Yij=1,表示客戶點(diǎn)j被網(wǎng)點(diǎn)i服務(wù),否則相反;決策變量Xijk∈{0,1},若Xijk=1,表示配送車輛k從網(wǎng)點(diǎn)i經(jīng)過(guò)客戶點(diǎn)j,否則相反。快遞員從網(wǎng)點(diǎn)出發(fā)進(jìn)行派送,派送完成后返回距離最近的網(wǎng)點(diǎn)。

如何合理地選擇快遞網(wǎng)點(diǎn)及安排派送路徑是本文研究核心,主要目的是降低成本,因此以網(wǎng)點(diǎn)選址路徑總成本為目標(biāo)函數(shù),建立兩階段雙層規(guī)劃模型。第1階段中上層模型考慮網(wǎng)點(diǎn)選址成本最低,包含建設(shè)成本和人工成本,下層模型考慮配送距離最短。因客戶點(diǎn)收件量為不確定的隨機(jī)變量,所以有可能出現(xiàn)第1階段所選網(wǎng)點(diǎn)容量無(wú)法滿足客戶點(diǎn)的實(shí)際需求量或配送車輛容量和體積無(wú)法滿足客戶點(diǎn)的需求量的情況,從而導(dǎo)致預(yù)優(yōu)化階段方案失效。此時(shí)就需要第2階段重新優(yōu)化,重優(yōu)化階段采用失敗點(diǎn)前序點(diǎn)重優(yōu)化策略,以此確定末端快遞網(wǎng)點(diǎn)建設(shè)及配送路徑規(guī)劃,減少物流整體配送成本。

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

2.2.1 上層模型

假設(shè)某一預(yù)優(yōu)化方案中客戶點(diǎn)集合C,均由某一網(wǎng)點(diǎn)對(duì)其派送,在服務(wù)完前j-1個(gè)客戶點(diǎn)后,現(xiàn)要確定客戶點(diǎn)j+1是否也由該網(wǎng)點(diǎn)進(jìn)行派送,采用隨機(jī)機(jī)會(huì)約束機(jī)制進(jìn)行判斷,此時(shí)該網(wǎng)點(diǎn)的剩余載荷量Qj=Qw-(dw1+dw2+…+dwj)-(rw1+rw2+…+rwj),因收件量rj為隨機(jī)變量,此時(shí)通過(guò)隨機(jī)機(jī)會(huì)約束機(jī)制判斷是否由該網(wǎng)點(diǎn)服務(wù)客戶點(diǎn)j,即P{rwj≤Qj-dwj}≥α,α為預(yù)先設(shè)定的風(fēng)險(xiǎn)偏好值,其表示決策者在不確定情況下對(duì)風(fēng)險(xiǎn)的可接受程度。若決策者對(duì)風(fēng)險(xiǎn)的接受程度不高,更想保證預(yù)方案的成功率,則α應(yīng)取較高值;反之,α應(yīng)取較低值,α∈(0,1],dj和rj分別為客戶點(diǎn)j的派件量和收件量。式(1)表示上層模型目標(biāo)函數(shù),包含了快遞網(wǎng)點(diǎn)的建設(shè)成本和人工成本;式(2)表示網(wǎng)點(diǎn)建設(shè)數(shù)量的約束條件;式(3)表示網(wǎng)點(diǎn)載荷量的隨機(jī)規(guī)劃約束;式(4)表示決策變量,為0-1變量。目標(biāo)函數(shù)式中Z、Y和X均為所求的決策變量。

(1)

s.t.

(2)

P{rwj≤∑i∈WYijQj-dwj}≥α,?j∈C

(3)

Yij∈{0,1},Zi∈{0,1},?i∈W,?j∈C

(4)

2.2.2 上層模型隨機(jī)機(jī)會(huì)約束等價(jià)處理

上層規(guī)劃模型中,約束條件式(3)可以推導(dǎo)為確定型等價(jià)形式,式(3)可變?yōu)?

(5)

(6)

假設(shè)常數(shù)τ為α的分位點(diǎn),則式(6)可轉(zhuǎn)化為:

(7)

因此,由式(5)和式(7)可知:

Sv·τ+Ev≤T

(8)

T=Q-∑i∈W∑j∈CdwjYij

(9)

將期望和標(biāo)準(zhǔn)差均代入式(8),得:

(10)

(11)

(12)

2.2.3 下層模型

同樣地,車輛k按順序?qū)蛻暨M(jìn)行配送,現(xiàn)判斷客戶點(diǎn)j+1是否由車輛j服務(wù),則車輛在客戶點(diǎn)j和客戶點(diǎn)j+1之間的實(shí)際載荷量Qj(j+1)=∑j∈CQ0jk-(dw1+dw2+…+dwj)-(rw1+rw2+…+rwj),其中∑j∈CQ0jk為車輛k初始載荷和體積,即車輛所需配送的所有點(diǎn)派件量之和。此時(shí),若車輛繼續(xù)對(duì)客戶j進(jìn)行服務(wù)需滿足rwj≤Qj(j+1)k-Qojk+dwj,引入隨機(jī)機(jī)會(huì)約束,即P{rwj≤Qj(j+1)k-Qojk+dwj}≥α,α∈(0,1]。同理,其體積隨機(jī)約束為P{rvj≤Vj(j+1)k-Vojk+dvj}≥α。

式(13)為下層規(guī)劃目標(biāo)函數(shù),以總配送距離最小為目標(biāo);式(14)和式(15)分別表示配送車輛的載荷與體積的隨機(jī)機(jī)會(huì)約束;式(16)表示配送員最長(zhǎng)配送時(shí)間約束;式(17)表示每個(gè)客戶僅被服務(wù)一次;式(18)表示避免網(wǎng)點(diǎn)之間相互配送;式(19)表示每個(gè)客戶僅被一個(gè)快遞網(wǎng)點(diǎn)服務(wù);式(20)表示節(jié)點(diǎn)流量平衡約束;式(21)表示配送車輛從網(wǎng)點(diǎn)出發(fā)時(shí)的負(fù)載量等于該網(wǎng)點(diǎn)所服務(wù)客戶的派件需求總和;式(22)表示配送車輛在各節(jié)點(diǎn)負(fù)載量;式(23)表示配送車輛回到快遞網(wǎng)點(diǎn)時(shí)的負(fù)載量等于該網(wǎng)點(diǎn)所服務(wù)客戶的收件量需求總和;式(24)和式(25)表示車輛負(fù)載量約束;式(26)和式(27)為決策變量之間的關(guān)系,分別表示當(dāng)點(diǎn)i被選為建設(shè)快遞網(wǎng)點(diǎn),則必有客戶點(diǎn)j由網(wǎng)點(diǎn)i配送和只要存在客戶點(diǎn)j由網(wǎng)點(diǎn)i配送,則網(wǎng)點(diǎn)i必被選為建設(shè)快遞網(wǎng)點(diǎn);式(28)表示決策變量,為0-1變量。

(13)

s.t.

P{rwj≤∑i∈W∑j∈C(XijkQijk+Xj(j+1)kQj(j+1)k)-

Q0jk+dwj}≥α,?k∈K

(14)

P{rvj≤∑i∈W∑j∈C(XijkQijk+Xj(j+1)kQj(j+1)k)-

Q0jk+dvj}≥α,?k∈K

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

0≤Qijk≤QkXijk,?i∈W,?j∈C,?k∈K

(24)

0≤Qj(j+1)k≤QkXi(j+1)k,?j∈C,?k∈K

(25)

(26)

Yij≤Zi,?i∈W,?j∈C

(27)

Xijk,Xj(j+1)k∈{0,1},?i∈W,?j∈C,?k∈K

(28)

2.2.4 下層模型隨機(jī)機(jī)會(huì)約束等價(jià)處理

隨機(jī)約束規(guī)劃式(14)可轉(zhuǎn)化為:

P{rwj≤Qk-∑i∈W(XijkQijk+Xj(j+1)kQj(j+1)k)+

?j∈C,?k∈K

(29)

推導(dǎo)過(guò)程與上層模型推導(dǎo)過(guò)程中式(5)～式(12)同理,快件重量的隨機(jī)機(jī)會(huì)約束確定型等價(jià)形式可轉(zhuǎn)化為:

(30)

T=Qk-∑j∈CQ0jk+

∑i∈W(Xijkdwj+Xj(j+1)kdwj)

(31)

同理,快件體積的隨機(jī)機(jī)會(huì)約束確定型等價(jià)形式可轉(zhuǎn)化為:

(32)

T=Vk-∑j∈CV0jk+

∑i∈W(Xijkdvj+Xj(j+1)kdvj)

(33)

2.2.5 重優(yōu)化階段

重優(yōu)化階段中,對(duì)于選址問(wèn)題網(wǎng)點(diǎn)容量無(wú)法滿足的情況,選擇添加新的網(wǎng)點(diǎn)進(jìn)行后續(xù)配送,而現(xiàn)有對(duì)隨機(jī)需求路徑問(wèn)題失敗點(diǎn)處理方法主要有失敗點(diǎn)返回策略、失敗點(diǎn)前序點(diǎn)返回策略和失敗點(diǎn)重優(yōu)化策略3種。

如圖1所示,A、B為快遞網(wǎng)點(diǎn),圖中實(shí)線為預(yù)優(yōu)化階段路徑,虛線為重優(yōu)化階段路徑,8個(gè)客戶點(diǎn)中,客戶點(diǎn)2,4和6為失敗點(diǎn),預(yù)優(yōu)化階段路徑如圖1a所示。

Figure 1 Failure point return policy圖1 失敗點(diǎn)返回策略

(1)失敗點(diǎn)返回策略,如圖1b所示,配送車輛在客戶點(diǎn)2,4和6不滿足條件無(wú)法配送時(shí),車輛返回原快遞網(wǎng)點(diǎn),再按預(yù)優(yōu)化安排進(jìn)行后續(xù)配送。

(2)失敗點(diǎn)前序點(diǎn)返回策略,如圖1c所示,配送車輛在失敗點(diǎn)4的前序點(diǎn)1,預(yù)先對(duì)車輛剩余載荷能否滿足失敗點(diǎn)4的需求進(jìn)行判斷,若車輛剩余載荷能滿足后序點(diǎn)需求則對(duì)其服務(wù),否則,在失敗點(diǎn)前序點(diǎn)就返回原配送網(wǎng)點(diǎn)再繼續(xù)配送,這種情況下,其配送路徑長(zhǎng)度一定小于失敗點(diǎn)返回策略。

(3)失敗點(diǎn)重優(yōu)化策略,如圖1d所示,配送車輛在失敗點(diǎn)返回原出發(fā)網(wǎng)點(diǎn),對(duì)于失敗點(diǎn)及其預(yù)優(yōu)化方案中后續(xù)客戶點(diǎn)進(jìn)行重新統(tǒng)一規(guī)劃,設(shè)計(jì)配送方案生成重優(yōu)化路徑,再按重優(yōu)化階段路徑方案進(jìn)行配送。

總結(jié)以上幾種返回策略中,失敗點(diǎn)返回策略操作最為簡(jiǎn)單,但其配送路徑距離較長(zhǎng),前序點(diǎn)返回策略未考慮到后續(xù)點(diǎn)的統(tǒng)一優(yōu)化,無(wú)法保證整體路徑最優(yōu)。因此,將失敗點(diǎn)前序點(diǎn)返回策略和失敗點(diǎn)重優(yōu)化策略相結(jié)合組成失敗點(diǎn)前序點(diǎn)重優(yōu)化策略,并在返回規(guī)則上進(jìn)行改善,結(jié)合共同配送模式特點(diǎn),配送車輛在返回網(wǎng)點(diǎn)時(shí),無(wú)需返回原配送網(wǎng)點(diǎn),選擇距離最近的網(wǎng)點(diǎn)返回,可縮短配送路徑的距離。

如圖1e所示,配送車輛在失敗點(diǎn)4的前序點(diǎn)7通過(guò)判斷其后序點(diǎn)無(wú)法滿足配送需求時(shí)進(jìn)行返回,統(tǒng)計(jì)所有失敗點(diǎn)及其后續(xù)點(diǎn),重新設(shè)計(jì)后續(xù)客戶點(diǎn)配送方案,生成重優(yōu)化階段路徑安排。

3 混合自適應(yīng)大鄰域搜索遺傳算法

針對(duì)雙層模型解空間大、計(jì)算復(fù)雜等特性,本文設(shè)計(jì)混合自適應(yīng)大鄰域搜索遺傳算法進(jìn)行求解。將自適應(yīng)大鄰域搜索算法嵌入遺傳算法中,每一代進(jìn)化時(shí)先用遺傳算法尋優(yōu);再將遺傳算法種群中最優(yōu)個(gè)體作為自適應(yīng)大鄰域搜索算法的初始解進(jìn)行求解;最后,通過(guò)“個(gè)體替換”操作將自適應(yīng)大鄰域搜索算法所得的新解替換掉遺傳算法種群中適應(yīng)度最低的解,生成新一代種群,以達(dá)到改善種群質(zhì)量的目的,以此不斷迭代,直至算法結(jié)束。

本文所設(shè)計(jì)的混合自適應(yīng)大鄰域搜索遺傳算法結(jié)合了2種算法的優(yōu)點(diǎn),即通過(guò)遺傳算法的選擇算子、交叉算子和變異算子等來(lái)提升自適應(yīng)大鄰域搜索算法的全局搜索能力,降低算法陷入局部最優(yōu)解的概率;而自適應(yīng)大鄰域搜索算法的破壞算子和修復(fù)算子也可以加強(qiáng)遺傳算法的局部搜索能力,并通過(guò)引入自適應(yīng)機(jī)制,自適應(yīng)更新算子權(quán)重,使其在每次迭代的時(shí)候都可以選擇當(dāng)前最優(yōu)的算子進(jìn)行解的變換,強(qiáng)化每一代的求解質(zhì)量。改進(jìn)后的混合自適應(yīng)大鄰域搜索遺傳算法可以更好地在全部解空間中尋優(yōu),得到更滿意的解。具體的算法流程如圖2所示。

Figure 2 Flow chart of hybrid adaptive large neighborhood search genetic algorithm圖2 混合自適應(yīng)大鄰域搜索遺傳算法流程

3.1 編碼及解碼方式

算法采用整數(shù)編碼的方式,將全部客戶需求編號(hào)點(diǎn)打亂順序存入染色體編碼方案列表中,作為配送的服務(wù)順序。

解碼過(guò)程包括2步:第1步根據(jù)隨機(jī)機(jī)會(huì)約束機(jī)制及快件的重量、體積約束將客戶分配給配送員,如不滿足該約束條件,則為該需求點(diǎn)增加新的快遞員進(jìn)行服務(wù),直至為所有需求點(diǎn)都分配好快遞員;第2步根據(jù)每輛配送車輛首尾客戶到快遞網(wǎng)點(diǎn)的距離確定車輛的出發(fā)網(wǎng)點(diǎn)和返回網(wǎng)點(diǎn)。

具體以圖3為例,其中1～10為客戶需求點(diǎn),a、b和c為3個(gè)配送網(wǎng)點(diǎn),將客戶點(diǎn)打亂順序加入列表中,即為染色體編碼方案;解碼首先根據(jù)編碼方案列表中的順序?yàn)榕渌蛦T分配客戶,當(dāng)分配到第4個(gè)客戶,即客戶6時(shí),發(fā)現(xiàn)不滿足約束條件,為客戶6及后續(xù)客戶點(diǎn)安排新的配送員進(jìn)行配送服務(wù);將已分配好的配送路徑{1,3,2}以列表的形式加入二維列表route中,并根據(jù)配送路徑中起始客戶和末尾客戶,選擇最近的網(wǎng)點(diǎn)作為其始末網(wǎng)點(diǎn),加入二維列表depot中,確定最終的始末配送中心,即配送員從網(wǎng)點(diǎn)a出發(fā)進(jìn)行派送,先后服務(wù)客戶點(diǎn)1,3和2后返回最近網(wǎng)點(diǎn)b;以此類推,確定最終的染色體解碼方案。

Figure 3 Coding and decoding modes圖3 編碼及解碼方式

3.2 初始種群生成

隨機(jī)生成一個(gè)種群規(guī)模為popesize的初始種群,popesize為預(yù)先設(shè)定好的數(shù)值,通過(guò)計(jì)算每個(gè)個(gè)體的適應(yīng)度,將適應(yīng)度最大的個(gè)體作為自適應(yīng)大鄰域搜索算法的初始解,對(duì)該個(gè)體進(jìn)行鄰域搜索。全部初始種群就作為遺傳算法的初始解進(jìn)行迭代,再通過(guò)個(gè)體替換,即將自適應(yīng)大鄰域搜索算法所得的新個(gè)體替換掉遺傳算法所得新種群中適應(yīng)度最小的個(gè)體,生成新一代種群。

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

先給出上層選址模型的初始解,將其代入下層模型進(jìn)行求解,得出的配送路徑規(guī)劃方案再反饋到上層模型中,以上層模型的目標(biāo)函數(shù)式(1)的倒數(shù)作為算法個(gè)體的適應(yīng)度函數(shù)fs,如式(34)所示:

(34)

由式(34)可知,目標(biāo)函數(shù)值F1越優(yōu),其染色體個(gè)體適應(yīng)度f(wàn)s越大。

3.4 遺傳操作

遺傳操作在整體算法中起到全局搜索的作用,通過(guò)選擇、交叉和變異等操作,可以避免整體算法陷入局部最優(yōu)解的情況:

(1)選擇算子:采用二元錦標(biāo)賽選擇策略,即每次在父代種群中隨機(jī)選擇2個(gè)不同的個(gè)體,通過(guò)比較2個(gè)個(gè)體的適應(yīng)度大小,將適應(yīng)度較大的個(gè)體加入新的種群中,重復(fù)n_select次數(shù)。

(2)交叉算子:需考慮到子代染色體中是否包含重復(fù)基因,考慮到該因素,下層模型采用OX交叉法。即隨機(jī)選擇2個(gè)染色體作為父代染色體,選擇其中一個(gè)染色體的一串基因直接復(fù)制到子代染色體相同位置,再?gòu)牧硗庖粋€(gè)父代染色體中按順序?qū)⒉煌谧哟旧w中已有的基因復(fù)制到子代染色體中,所得的新染色體即為子代染色體。該方法巧妙地避免了子代中出現(xiàn)重復(fù)基因的情況。

(3)變異算子:在變異過(guò)程中,同樣考慮子代染色體重復(fù)基因的情況,采用二元突變的方式,即隨機(jī)從種群中選取一個(gè)染色體作為父代染色體。在已選擇的父代染色體中隨機(jī)選擇2個(gè)不處于相同位置的基因點(diǎn),然后交換該2點(diǎn)的基因值,得到的新染色體即為子代染色體。

3.5 自適應(yīng)大鄰域搜索操作

自適應(yīng)大鄰域搜索算法主要是增強(qiáng)算法的鄰域搜索能力,其中鄰域搜索算子有很多種,本文引入2種破壞算子及3種修復(fù)算子,通過(guò)不斷地破壞和修復(fù)個(gè)體來(lái)搜索鄰域解。

(1)破壞算子。

① 隨機(jī)破壞算子:即在個(gè)體染色體中隨機(jī)選取寬度在[d_min,d_max]中的一段基因序列,存入remove_list中,以備修復(fù)操作時(shí)使用。

② 最差破壞算子:即移除一定范圍引起目標(biāo)函數(shù)增大的需求點(diǎn),通過(guò)分別計(jì)算移除每一個(gè)需求點(diǎn)后目標(biāo)函數(shù)的減少量,對(duì)需求點(diǎn)進(jìn)行排序,按照一定比例移除需求點(diǎn)集合。

(2)修復(fù)算子。

① 隨機(jī)修復(fù)算子:與隨機(jī)破壞算子原理相同,即在已破壞個(gè)體中,隨機(jī)將remove_list中的基因序列插入到個(gè)體中,形成新解。

② 貪婪修復(fù)算子:根據(jù)remove_list中需求點(diǎn)順序,依次將列表中需求點(diǎn)插入使目標(biāo)函數(shù)增量最小的位置,直至remove_list列表為空。

③ 后悔修復(fù)算子:計(jì)算remove_list中需求點(diǎn)插入到待插入個(gè)體序列中L個(gè)次優(yōu)位置時(shí)目標(biāo)函數(shù)的變化,選擇使目標(biāo)函數(shù)變化最大的需求節(jié)點(diǎn)及其最優(yōu)位置。

(3)算子權(quán)重更新策略。

每次迭代都更新權(quán)重在處理大規(guī)模問(wèn)題時(shí)所需時(shí)間太長(zhǎng),可以通過(guò)合理設(shè)置p的值來(lái)平衡求解時(shí)間和權(quán)重更新的及時(shí)性之間的關(guān)系。因此,每迭代p次更新一次算子權(quán)重作為混合大鄰域搜索遺傳算法的權(quán)重更新策略。權(quán)重更新表達(dá)式如式(35)所示:

(35)

其中,W(α)表示算子α每次更新權(quán)重;p表示算子更新衰降系數(shù);S(α)表示算子α的總獎(jiǎng)勵(lì)得分,與算子的被選擇次數(shù)和使用該算子后產(chǎn)生的鄰域解的質(zhì)量有關(guān);t(α)表示算子被選擇的次數(shù)。

4 數(shù)值實(shí)驗(yàn)與實(shí)例分析

4.1 算法參數(shù)及性能對(duì)比

(1)參數(shù)確定。

本文研究的隨機(jī)選址路徑問(wèn)題目前沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)通用算例,因此選擇Prodhon提出的經(jīng)典選址路徑問(wèn)題標(biāo)準(zhǔn)測(cè)試集(http://prodhonc.free.fr/Instances/instances_us.htm)中部分算例對(duì)算法參數(shù)及性能進(jìn)行測(cè)試。分別選取測(cè)試集中名稱為coord20-5-1(算例包含20個(gè)客戶點(diǎn),5個(gè)備選中心)、coord50-5-1(算例包含50個(gè)客戶點(diǎn),5個(gè)備選中心)和coord100-5-1(算例包含100個(gè)客戶點(diǎn),5個(gè)備選中心)的算例對(duì)算法進(jìn)行參數(shù)分析,通過(guò)調(diào)整參數(shù)取不同的值,用算法對(duì)上述3個(gè)算例分別求解5次,對(duì)3個(gè)算例中最優(yōu)解對(duì)應(yīng)的參數(shù)求平均數(shù),取該平均數(shù)作為最終的參數(shù)值。最終確定的參數(shù)最優(yōu)值如表1所示。

表1中包含以下參數(shù):PC為交叉算子概率;PM為選擇算子概率;N_select為進(jìn)行選擇操作時(shí),選擇種群的比例;Rand_d_max為隨機(jī)破壞算子的最大上限,Rand_d_min為隨機(jī)破壞算子的最低下限;Worst_d_max為最壞破壞算子的最大上限,Worst_d_min為最壞破壞算子的最低下限;Regret_n為后悔修復(fù)算子中取次優(yōu)位置的個(gè)數(shù)。

Table 1 Optimal values of parameters表1 參數(shù)最優(yōu)值

(2)算法性能對(duì)比。

為了測(cè)試混合算法性能,設(shè)置目標(biāo)函數(shù)包含配送中心和車輛的固定成本及運(yùn)輸成本,分別用自適應(yīng)大鄰域搜索(ALNS)算法、傳統(tǒng)遺傳算法GA(Genetic Algorithm)以及本文設(shè)計(jì)的混合自適應(yīng)大鄰域搜索遺傳算法ALGA(Adaptive Large neighborhood search and Genetic Algorithm)運(yùn)行5次,對(duì)運(yùn)行結(jié)果進(jìn)行對(duì)比。所得結(jié)果如表2所示,其中,BS表示已知最優(yōu)解,Best表示算法運(yùn)行5次的最優(yōu)解,Gap表示當(dāng)前算法所得結(jié)果與最優(yōu)解之間的差距,Ave表示平均數(shù)據(jù)。

由表2可知,本文所設(shè)計(jì)的ALGA算法在客戶規(guī)模為20時(shí)可找到最優(yōu)解;對(duì)比各算法的Gap值衡量算法性能,ALGA算法的Gap值平均為1.50%,相對(duì)于GA算法的2.40%和ALNS算法的2.89%,說(shuō)明ALGA算法性能相對(duì)其他2種啟發(fā)式算法更優(yōu)。

(3)算法收斂性對(duì)比。

為了分析算法的收斂情況,選取coord20-5-1算例,記錄每一代種群最優(yōu)解并繪制算法收斂圖,進(jìn)行算法收斂性分析。

從圖4可以看出,在50代以內(nèi),GA算法和ALGA算法收斂速度相近,但其在50代后陷入了局部最優(yōu)解;ALNS算法雖然一直穩(wěn)步收斂,但整體迭代速度較慢;本文提出的ALGA算法結(jié)合GA和ALNS 2種算法的優(yōu)點(diǎn),不僅在求解初期迭代速度快,并且全程持續(xù)穩(wěn)步收斂,在400代附近找到最優(yōu)解。相比于改進(jìn)前的算法,本文的ALGA算法收斂到最優(yōu)解的速度最快。

Figure 4 Comparison of algorithm convergences圖4 算法收斂對(duì)比圖

4.2 實(shí)例驗(yàn)證

本文選取某市范圍內(nèi)快遞網(wǎng)點(diǎn)作為研究對(duì)象,對(duì)數(shù)據(jù)進(jìn)行整理,可描述為該區(qū)域內(nèi)有3家快遞企業(yè),6個(gè)已有網(wǎng)點(diǎn)作為備選網(wǎng)點(diǎn)(如表3所示),20個(gè)配送需求點(diǎn)(如表4所示),網(wǎng)點(diǎn)容量均為1 000 kg,配送車輛載重為200 kg,容量為1.5 m3,單位時(shí)間配送的人工成本為15元,車輛行駛速度為15 km/h,收派件單件提成為0.5元。在進(jìn)行選址路徑規(guī)劃時(shí),需求點(diǎn)收件量是不確定的,只有派送到該點(diǎn)才能知道具體的量。根據(jù)收派件的數(shù)據(jù)預(yù)先設(shè)置需求點(diǎn)的收件量服從λ=10的泊松分布。

采用標(biāo)準(zhǔn)遺傳算法(GA)和改進(jìn)的混合自適應(yīng)鄰域搜索遺傳算法(ALGA)對(duì)上述實(shí)例數(shù)據(jù)分別計(jì)算10次,對(duì)比運(yùn)算結(jié)果。

由表5的實(shí)驗(yàn)結(jié)果可以看出,改進(jìn)的混合自適應(yīng)鄰域搜索遺傳算法的最優(yōu)解和平均解都優(yōu)于標(biāo)準(zhǔn)遺傳算法,并且,混合自適應(yīng)大鄰域搜索算法的標(biāo)準(zhǔn)差值較標(biāo)準(zhǔn)遺傳算法低了2.23,由此可知混合自適應(yīng)鄰域搜索遺傳算法的穩(wěn)定性更強(qiáng)。

Table 3 Parameters of alternative outlets表3 備選網(wǎng)點(diǎn)參數(shù)表

Table 4 Customer point parameter 表4 客戶點(diǎn)參數(shù)

Table 5 Example results comparison表5 結(jié)果對(duì)比

上述各組算例及實(shí)例結(jié)果表明,改進(jìn)后的混合算法相對(duì)于標(biāo)準(zhǔn)遺傳算法及自適應(yīng)大鄰域搜索算法,在求解質(zhì)量和求解速度方面都有明顯提升。這是因?yàn)檫z傳算法局部搜索能力較弱,而在遺傳算法中引入局部搜索能力較強(qiáng)的鄰域搜索算法來(lái)提升算法種群質(zhì)量,可以結(jié)合2種算法的優(yōu)點(diǎn),增強(qiáng)算法的全局搜索能力。該算法可以有效解決物流配送選址路徑求解耗時(shí)長(zhǎng)和求解質(zhì)量差的問(wèn)題。采用本文改進(jìn)的混合遺傳算法,在同等客戶規(guī)模情況下,能夠有效減少快遞配送物流成本,提升整體配送效益。

4.3 靈敏度分析

實(shí)驗(yàn)1風(fēng)險(xiǎn)偏好值α的取值影響。

研究隨機(jī)問(wèn)題時(shí),通常采用引入隨機(jī)機(jī)會(huì)約束的方法進(jìn)行求解,因而預(yù)設(shè)置的風(fēng)險(xiǎn)值α值得探討,α的設(shè)定既要保證模型成本在可接受的范圍內(nèi),同時(shí)也要滿足模型中的載荷等約束。因此,本節(jié)采用上述實(shí)例數(shù)據(jù),設(shè)置α的值從0.1到1.0,分別對(duì)模型進(jìn)行求解,根據(jù)求解結(jié)果分析風(fēng)險(xiǎn)值α對(duì)模型成本的影響。

實(shí)驗(yàn)結(jié)果如表6所示,可以看出當(dāng)偏好值α在0.4～0.7時(shí),模型總成本較低,當(dāng)偏好值α為0.6時(shí),模型成本最優(yōu)。分析其原因,可能是由于當(dāng)α值設(shè)置較小時(shí),更趨向于一次派送較多的客戶,導(dǎo)致配送路徑失敗,從而產(chǎn)生更多的成本;當(dāng)風(fēng)險(xiǎn)值α設(shè)置較大時(shí),隨機(jī)機(jī)會(huì)概率較小,一次配送所服務(wù)的客戶數(shù)量較少,造成成本較大。因此,過(guò)大或者過(guò)小的偏好值都會(huì)引起配送成本的升高,所以建議物流企業(yè)決策者在制定配送方案時(shí)要根據(jù)實(shí)際情況選取風(fēng)險(xiǎn)偏好值,避免選取較高或較低的偏好值,保證物流配送成本最優(yōu)。

Table 6 Influence of preference value on the results表6 偏好值對(duì)結(jié)果的影響

實(shí)驗(yàn)2收派件數(shù)量的影響。

在實(shí)際的快遞派送過(guò)程中,顧客的收派件數(shù)量經(jīng)常發(fā)生變化,因此,本文探究收件與派件的數(shù)量對(duì)網(wǎng)點(diǎn)選址路徑?jīng)Q策的影響。以上文中實(shí)例數(shù)據(jù)為例,控制收派比為不同值,分別對(duì)其求解,根據(jù)結(jié)果進(jìn)而分析收派比的影響。

由表7中數(shù)據(jù)的變化可以看出,隨著收派比的增加,模型整體成本呈先下降后上升趨勢(shì)。分析其原因,本文所研究的問(wèn)題為收件數(shù)量為不確定的情況,因此當(dāng)收派比較高時(shí),隨著實(shí)際收件量的增加,預(yù)先規(guī)劃的路徑失敗的概率增大,從而導(dǎo)致成本上漲;而當(dāng)收派比較低時(shí),實(shí)際收件量較少,低于所設(shè)收件量的期望值,并且在總量不變的情況下,一定的收件量可以提高派送車輛空間利用率,所以在總量不變的情況下,過(guò)低的收件量也會(huì)導(dǎo)致成本升高。由此可以得出收派件數(shù)量比值的變化對(duì)配送方案的制訂有著重要意義,建議物流決策者在制定路徑配送方案時(shí)應(yīng)充分考慮收件與派件之間的數(shù)量關(guān)系。

Table 7 Influence of dispatch ratio on results表7 收派比對(duì)結(jié)果的影響

實(shí)驗(yàn)3不同返回策略的影響。

為驗(yàn)證最近網(wǎng)點(diǎn)返回策略的合理性,以實(shí)例數(shù)據(jù)為例,對(duì)不同返回策略下實(shí)例求解結(jié)果進(jìn)行分析。表8給出了2種不同返回策略下的結(jié)果,其中,Best為總成本的最優(yōu)值,CL為總成本,D為配送距離,Gap為CL與Best的偏差值。

Table 8 Influence of different strategies on results表8 不同策略對(duì)結(jié)果的影響

根據(jù)表8結(jié)果可知,在對(duì)本文實(shí)例求解中,2種返回策略對(duì)比,最近網(wǎng)點(diǎn)返回策略的成本最優(yōu);返回原網(wǎng)點(diǎn)策略相比最近網(wǎng)點(diǎn)返回策略,其實(shí)際配送距離較長(zhǎng),因此其末端物流成本也高于最近網(wǎng)點(diǎn)返回策略。以本文數(shù)據(jù)為例,采用最近網(wǎng)點(diǎn)返回策略可使末端成本降低1.5%,因此本文所采用的最近網(wǎng)點(diǎn)返回策略可以有效降低物流企業(yè)配送成本。

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

本文對(duì)共同配送模式下收件量隨機(jī)的同時(shí)收派件的快遞網(wǎng)點(diǎn)選址路徑問(wèn)題進(jìn)行研究。首先,建立所研究問(wèn)題的數(shù)學(xué)規(guī)劃模型,針對(duì)模型中的收件量不確定性,引入隨機(jī)機(jī)會(huì)約束,生成第1階段選址路徑規(guī)劃,并提出新的失敗點(diǎn)重優(yōu)化策略解決第1階段優(yōu)化失敗問(wèn)題。然后,提出一種混合自適應(yīng)鄰域搜索遺傳算法,改進(jìn)傳統(tǒng)遺傳算法的局部搜索能力不足的問(wèn)題,并通過(guò)算例證實(shí)了混合遺傳算法的高求解效率和快速收斂能力。最后,通過(guò)數(shù)值實(shí)驗(yàn),分析模型風(fēng)險(xiǎn)偏好值、收派件數(shù)量之比及返回策略對(duì)網(wǎng)點(diǎn)選址路徑規(guī)劃的影響,形成相應(yīng)的管理啟示。并得到如下結(jié)論:

(1)所建立的數(shù)學(xué)優(yōu)化模型,綜合考慮了共同配送、收件需求隨機(jī)、快遞配送的特征,以及最近網(wǎng)點(diǎn)返回策略,雖然使模型求解更為復(fù)雜,但更符合快遞服務(wù)的實(shí)際需求。

(2)所設(shè)計(jì)的混合啟發(fā)式算法,在傳統(tǒng)遺傳算法的基礎(chǔ)上引入自適應(yīng)鄰域搜索算法來(lái)改善每一代種群的質(zhì)量,有效提升了算法全局搜索和局部搜索的能力,較傳統(tǒng)啟發(fā)式算法具有更好的求解質(zhì)量和更快的收斂速度。

(3)對(duì)風(fēng)險(xiǎn)偏好值的靈敏度分析表明,過(guò)高或者過(guò)低的偏好值取值都會(huì)導(dǎo)致物流成本上升;對(duì)收派件比值靈敏度分析表明,隨著收派比的增加,模型整體成本呈先下降后上升趨勢(shì);對(duì)不同返回策略的實(shí)驗(yàn)分析表明,多個(gè)配送網(wǎng)點(diǎn)在共同配送的基礎(chǔ)上,采用最近網(wǎng)點(diǎn)返回策略可以有效地降低快遞企業(yè)配送成本。

物流企業(yè)可以綜合考慮以上因素進(jìn)行配送方案制定,降低末端配送成本。

本文的研究可以為多個(gè)快遞企業(yè)實(shí)施多網(wǎng)點(diǎn)共同配送提供較好的選址配送方案,但需要指出的是,研究中并未考慮快遞企業(yè)可能會(huì)受到多重不確定環(huán)境及客戶時(shí)間窗因素的影響。如何在時(shí)間窗約束下及多重不確定因素下規(guī)劃好快遞末端配送問(wèn)題是未來(lái)的研究方向。