基于混合啟發式算法的快遞末端選址路徑優化研究*

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

(1.大連海事大學航運經濟與管理學院,遼寧 大連 116026;2.大連海事大學綜合交通運輸協同創新中心,遼寧 大連 116026)

1 引言

近年,快遞數量快速增長,給快遞末端網點及末端配送環節帶來了巨大的壓力。目前,快遞配送末端由于各自為政的配送模式,導致配送成本居高不下,而共同配送模式可以有效降低末端配送成本[1]。因此,在共同配送模式下,合理規劃快遞網點選址及配送路徑問題具有重要的研究意義。

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

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

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

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

2 共同配送隨機LRP模型建立

2.1 問題描述

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

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

2.2 數學模型

2.2.1 上層模型

假設某一預優化方案中客戶點集合C,均由某一網點對其派送,在服務完前j-1個客戶點后,現要確定客戶點j+1是否也由該網點進行派送,采用隨機機會約束機制進行判斷,此時該網點的剩余載荷量Qj=Qw-(dw1+dw2+…+dwj)-(rw1+rw2+…+rwj),因收件量rj為隨機變量,此時通過隨機機會約束機制判斷是否由該網點服務客戶點j,即P{rwj≤Qj-dwj}≥α,α為預先設定的風險偏好值,其表示決策者在不確定情況下對風險的可接受程度。若決策者對風險的接受程度不高,更想保證預方案的成功率,則α應取較高值;反之,α應取較低值,α∈(0,1],dj和rj分別為客戶點j的派件量和收件量。式(1)表示上層模型目標函數,包含了快遞網點的建設成本和人工成本;式(2)表示網點建設數量的約束條件;式(3)表示網點載荷量的隨機規劃約束;式(4)表示決策變量,為0-1變量。目標函數式中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 上層模型隨機機會約束等價處理

上層規劃模型中,約束條件式(3)可以推導為確定型等價形式,式(3)可變為:

(5)

(6)

假設常數τ為α的分位點,則式(6)可轉化為:

(7)

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

Sv·τ+Ev≤T

(8)

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

(9)

將期望和標準差均代入式(8),得:

(10)

(11)

(12)

2.2.3 下層模型

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

式(13)為下層規劃目標函數,以總配送距離最小為目標;式(14)和式(15)分別表示配送車輛的載荷與體積的隨機機會約束;式(16)表示配送員最長配送時間約束;式(17)表示每個客戶僅被服務一次;式(18)表示避免網點之間相互配送;式(19)表示每個客戶僅被一個快遞網點服務;式(20)表示節點流量平衡約束;式(21)表示配送車輛從網點出發時的負載量等于該網點所服務客戶的派件需求總和;式(22)表示配送車輛在各節點負載量;式(23)表示配送車輛回到快遞網點時的負載量等于該網點所服務客戶的收件量需求總和;式(24)和式(25)表示車輛負載量約束;式(26)和式(27)為決策變量之間的關系,分別表示當點i被選為建設快遞網點,則必有客戶點j由網點i配送和只要存在客戶點j由網點i配送,則網點i必被選為建設快遞網點;式(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 下層模型隨機機會約束等價處理

隨機約束規劃式(14)可轉化為:

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

?j∈C,?k∈K

(29)

推導過程與上層模型推導過程中式(5)～式(12)同理,快件重量的隨機機會約束確定型等價形式可轉化為:

(30)

T=Qk-∑j∈CQ0jk+

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

(31)

同理,快件體積的隨機機會約束確定型等價形式可轉化為:

(32)

T=Vk-∑j∈CV0jk+

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

(33)

2.2.5 重優化階段

重優化階段中,對于選址問題網點容量無法滿足的情況,選擇添加新的網點進行后續配送,而現有對隨機需求路徑問題失敗點處理方法主要有失敗點返回策略、失敗點前序點返回策略和失敗點重優化策略3種。

如圖1所示,A、B為快遞網點,圖中實線為預優化階段路徑,虛線為重優化階段路徑,8個客戶點中,客戶點2,4和6為失敗點,預優化階段路徑如圖1a所示。

Figure 1 Failure point return policy圖1 失敗點返回策略

(1)失敗點返回策略,如圖1b所示,配送車輛在客戶點2,4和6不滿足條件無法配送時,車輛返回原快遞網點,再按預優化安排進行后續配送。

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

(3)失敗點重優化策略,如圖1d所示,配送車輛在失敗點返回原出發網點,對于失敗點及其預優化方案中后續客戶點進行重新統一規劃,設計配送方案生成重優化路徑,再按重優化階段路徑方案進行配送。

總結以上幾種返回策略中,失敗點返回策略操作最為簡單,但其配送路徑距離較長,前序點返回策略未考慮到后續點的統一優化,無法保證整體路徑最優。因此,將失敗點前序點返回策略和失敗點重優化策略相結合組成失敗點前序點重優化策略,并在返回規則上進行改善,結合共同配送模式特點,配送車輛在返回網點時,無需返回原配送網點,選擇距離最近的網點返回,可縮短配送路徑的距離。

如圖1e所示,配送車輛在失敗點4的前序點7通過判斷其后序點無法滿足配送需求時進行返回,統計所有失敗點及其后續點,重新設計后續客戶點配送方案,生成重優化階段路徑安排。

3 混合自適應大鄰域搜索遺傳算法

針對雙層模型解空間大、計算復雜等特性,本文設計混合自適應大鄰域搜索遺傳算法進行求解。將自適應大鄰域搜索算法嵌入遺傳算法中,每一代進化時先用遺傳算法尋優;再將遺傳算法種群中最優個體作為自適應大鄰域搜索算法的初始解進行求解;最后,通過“個體替換”操作將自適應大鄰域搜索算法所得的新解替換掉遺傳算法種群中適應度最低的解,生成新一代種群,以達到改善種群質量的目的,以此不斷迭代,直至算法結束。

本文所設計的混合自適應大鄰域搜索遺傳算法結合了2種算法的優點,即通過遺傳算法的選擇算子、交叉算子和變異算子等來提升自適應大鄰域搜索算法的全局搜索能力,降低算法陷入局部最優解的概率;而自適應大鄰域搜索算法的破壞算子和修復算子也可以加強遺傳算法的局部搜索能力,并通過引入自適應機制,自適應更新算子權重,使其在每次迭代的時候都可以選擇當前最優的算子進行解的變換,強化每一代的求解質量。改進后的混合自適應大鄰域搜索遺傳算法可以更好地在全部解空間中尋優,得到更滿意的解。具體的算法流程如圖2所示。

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

3.1 編碼及解碼方式

算法采用整數編碼的方式,將全部客戶需求編號點打亂順序存入染色體編碼方案列表中,作為配送的服務順序。

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

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

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

3.2 初始種群生成

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

3.3 適應度函數

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

(34)

由式(34)可知,目標函數值F1越優,其染色體個體適應度fs越大。

3.4 遺傳操作

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

(1)選擇算子:采用二元錦標賽選擇策略,即每次在父代種群中隨機選擇2個不同的個體,通過比較2個個體的適應度大小,將適應度較大的個體加入新的種群中,重復n_select次數。

(2)交叉算子:需考慮到子代染色體中是否包含重復基因,考慮到該因素,下層模型采用OX交叉法。即隨機選擇2個染色體作為父代染色體,選擇其中一個染色體的一串基因直接復制到子代染色體相同位置,再從另外一個父代染色體中按順序將不同于子代染色體中已有的基因復制到子代染色體中,所得的新染色體即為子代染色體。該方法巧妙地避免了子代中出現重復基因的情況。

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

3.5 自適應大鄰域搜索操作

自適應大鄰域搜索算法主要是增強算法的鄰域搜索能力,其中鄰域搜索算子有很多種,本文引入2種破壞算子及3種修復算子,通過不斷地破壞和修復個體來搜索鄰域解。

(1)破壞算子。

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

② 最差破壞算子:即移除一定范圍引起目標函數增大的需求點,通過分別計算移除每一個需求點后目標函數的減少量,對需求點進行排序,按照一定比例移除需求點集合。

(2)修復算子。

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

② 貪婪修復算子:根據remove_list中需求點順序,依次將列表中需求點插入使目標函數增量最小的位置,直至remove_list列表為空。

③ 后悔修復算子:計算remove_list中需求點插入到待插入個體序列中L個次優位置時目標函數的變化,選擇使目標函數變化最大的需求節點及其最優位置。

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

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

(35)

其中,W(α)表示算子α每次更新權重;p表示算子更新衰降系數;S(α)表示算子α的總獎勵得分,與算子的被選擇次數和使用該算子后產生的鄰域解的質量有關;t(α)表示算子被選擇的次數。

4 數值實驗與實例分析

4.1 算法參數及性能對比

(1)參數確定。

本文研究的隨機選址路徑問題目前沒有統一的標準通用算例,因此選擇Prodhon提出的經典選址路徑問題標準測試集(http://prodhonc.free.fr/Instances/instances_us.htm)中部分算例對算法參數及性能進行測試。分別選取測試集中名稱為coord20-5-1(算例包含20個客戶點,5個備選中心)、coord50-5-1(算例包含50個客戶點,5個備選中心)和coord100-5-1(算例包含100個客戶點,5個備選中心)的算例對算法進行參數分析,通過調整參數取不同的值,用算法對上述3個算例分別求解5次,對3個算例中最優解對應的參數求平均數,取該平均數作為最終的參數值。最終確定的參數最優值如表1所示。

表1中包含以下參數:PC為交叉算子概率;PM為選擇算子概率;N_select為進行選擇操作時,選擇種群的比例;Rand_d_max為隨機破壞算子的最大上限,Rand_d_min為隨機破壞算子的最低下限;Worst_d_max為最壞破壞算子的最大上限,Worst_d_min為最壞破壞算子的最低下限;Regret_n為后悔修復算子中取次優位置的個數。

Table 1 Optimal values of parameters表1 參數最優值

(2)算法性能對比。

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

由表2可知,本文所設計的ALGA算法在客戶規模為20時可找到最優解;對比各算法的Gap值衡量算法性能,ALGA算法的Gap值平均為1.50%,相對于GA算法的2.40%和ALNS算法的2.89%,說明ALGA算法性能相對其他2種啟發式算法更優。

(3)算法收斂性對比。

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

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

Figure 4 Comparison of algorithm convergences圖4 算法收斂對比圖

4.2 實例驗證

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

采用標準遺傳算法(GA)和改進的混合自適應鄰域搜索遺傳算法(ALGA)對上述實例數據分別計算10次,對比運算結果。

由表5的實驗結果可以看出,改進的混合自適應鄰域搜索遺傳算法的最優解和平均解都優于標準遺傳算法,并且,混合自適應大鄰域搜索算法的標準差值較標準遺傳算法低了2.23,由此可知混合自適應鄰域搜索遺傳算法的穩定性更強。

Table 3 Parameters of alternative outlets表3 備選網點參數表

Table 4 Customer point parameter 表4 客戶點參數

Table 5 Example results comparison表5 結果對比

上述各組算例及實例結果表明,改進后的混合算法相對于標準遺傳算法及自適應大鄰域搜索算法,在求解質量和求解速度方面都有明顯提升。這是因為遺傳算法局部搜索能力較弱,而在遺傳算法中引入局部搜索能力較強的鄰域搜索算法來提升算法種群質量,可以結合2種算法的優點,增強算法的全局搜索能力。該算法可以有效解決物流配送選址路徑求解耗時長和求解質量差的問題。采用本文改進的混合遺傳算法,在同等客戶規模情況下,能夠有效減少快遞配送物流成本,提升整體配送效益。

4.3 靈敏度分析

實驗1風險偏好值α的取值影響。

研究隨機問題時,通常采用引入隨機機會約束的方法進行求解,因而預設置的風險值α值得探討,α的設定既要保證模型成本在可接受的范圍內,同時也要滿足模型中的載荷等約束。因此,本節采用上述實例數據,設置α的值從0.1到1.0,分別對模型進行求解,根據求解結果分析風險值α對模型成本的影響。

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

Table 6 Influence of preference value on the results表6 偏好值對結果的影響

實驗2收派件數量的影響。

在實際的快遞派送過程中,顧客的收派件數量經常發生變化,因此,本文探究收件與派件的數量對網點選址路徑決策的影響。以上文中實例數據為例,控制收派比為不同值,分別對其求解,根據結果進而分析收派比的影響。

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

Table 7 Influence of dispatch ratio on results表7 收派比對結果的影響

實驗3不同返回策略的影響。

為驗證最近網點返回策略的合理性,以實例數據為例,對不同返回策略下實例求解結果進行分析。表8給出了2種不同返回策略下的結果,其中,Best為總成本的最優值,CL為總成本,D為配送距離,Gap為CL與Best的偏差值。

Table 8 Influence of different strategies on results表8 不同策略對結果的影響

根據表8結果可知,在對本文實例求解中,2種返回策略對比,最近網點返回策略的成本最優;返回原網點策略相比最近網點返回策略,其實際配送距離較長,因此其末端物流成本也高于最近網點返回策略。以本文數據為例,采用最近網點返回策略可使末端成本降低1.5%,因此本文所采用的最近網點返回策略可以有效降低物流企業配送成本。

5 結束語

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

(1)所建立的數學優化模型,綜合考慮了共同配送、收件需求隨機、快遞配送的特征,以及最近網點返回策略,雖然使模型求解更為復雜,但更符合快遞服務的實際需求。

(2)所設計的混合啟發式算法,在傳統遺傳算法的基礎上引入自適應鄰域搜索算法來改善每一代種群的質量,有效提升了算法全局搜索和局部搜索的能力,較傳統啟發式算法具有更好的求解質量和更快的收斂速度。

(3)對風險偏好值的靈敏度分析表明,過高或者過低的偏好值取值都會導致物流成本上升;對收派件比值靈敏度分析表明,隨著收派比的增加,模型整體成本呈先下降后上升趨勢;對不同返回策略的實驗分析表明,多個配送網點在共同配送的基礎上,采用最近網點返回策略可以有效地降低快遞企業配送成本。

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

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