張曉楠,姜 帥,南婧雯
陜西科技大學(xué) 機電工程學(xué)院,西安710021
在區(qū)域經(jīng)濟一體化和互聯(lián)網(wǎng)的背景下,電商物流配送迅猛發(fā)展[1]。其特點在于:(1)直接面對需求量小、品種豐富、位置分散的眾多客戶,電商物流系統(tǒng)復(fù)雜且成本高[2];(2)客戶需求受季節(jié)、天氣、節(jié)假日、促銷手段、產(chǎn)品生命周期等因素影響呈現(xiàn)動態(tài)波動,甚至出現(xiàn)突發(fā)性暴漲(“雙十一”“618”),面對這類擾動,配送網(wǎng)絡(luò)各站點資源無法準(zhǔn)確平衡,易發(fā)生產(chǎn)品爆倉、滯緩等現(xiàn)象,風(fēng)險抵抗力差[3-5]。
在電商物流末端配送決策中,盡管配送需求全年波動,但是對于每一次的配送業(yè)務(wù)來說,因配送需求由客戶網(wǎng)上訂單生成,理論上,決策者可每天針對當(dāng)天需求量規(guī)劃路線以獲得較優(yōu)的配送方案。然而,現(xiàn)實中,每天重新規(guī)劃配送路線可能導(dǎo)致管理復(fù)雜,司機對新路線不熟悉,客戶對司機不熟悉等一系列問題。為簡化管理,保證配送司機對服務(wù)路線和服務(wù)客戶的熟悉度,現(xiàn)有物流運營商仍舊采用“行政區(qū)域劃分”“分區(qū)配送”或“定點服務(wù)”的配送策略。事實上,“行政區(qū)域劃分策略”要求配送中心和配送站的服務(wù)范圍幾乎與行政區(qū)域劃分相一致,可能導(dǎo)致站點/車輛間的服務(wù)范圍劃分不合理,成本浪費嚴(yán)重;“分區(qū)配送策略”雖開放了行政區(qū)域劃分,但仍嚴(yán)格要求每個需求點只隸屬于唯一的一個配送站,每個配送站只隸屬于唯一的一個配送中心,事實上,某些地區(qū)可能同時存在于多個配送中心的服務(wù)半徑內(nèi),存在由多個配送中心為其服務(wù)的可能;“定點服務(wù)策略”要求配送站為司機劃分的服務(wù)范圍是固定不變的,一個司機總是每天服務(wù)固定客戶點。上述三種規(guī)則模式下配送路線與當(dāng)天配送量無關(guān),當(dāng)需求動態(tài)波動時,各站點/車輛業(yè)務(wù)量的不均衡性波動明顯,甚至當(dāng)出現(xiàn)“雙十一”“618”的需求爆漲時,覆蓋需求頻繁度高的配送站容易爆倉,配送車輛供不應(yīng)求,而覆蓋需求頻繁度低的配送站資源過剩。為此,在保持一定程度的系統(tǒng)穩(wěn)定性的基礎(chǔ)上,開放這些規(guī)則策略,或許可提高配送效率和網(wǎng)絡(luò)風(fēng)險抵抗力[6]。
基于此,為應(yīng)對“雙十一”“618”需求突發(fā)性爆漲下物流配送網(wǎng)絡(luò)的爆倉、滯緩等問題,本文嘗試在保持配送系統(tǒng)穩(wěn)定性的基礎(chǔ)上提出“半柔性覆蓋策略”,研究“半柔性覆蓋的多配送中心路線優(yōu)化問題”(Μulti-depots Vehicle Routing Problem with Semi-flexible Service,ΜVRP-SFS)。即根據(jù)地理位置,區(qū)分固定需求點和柔性需求點,定義柔性需求點可由多個配送站協(xié)同服務(wù),建立半柔性覆蓋的多配送中心路線優(yōu)化模型;設(shè)計遺傳算法進行求解,使用Μatlab 進行編譯;以申通快遞在西安北郊地區(qū)的5 個配送站點為例進行實例測試,對比“半柔性覆蓋策略”的求解結(jié)果與原始路線、“全柔性覆蓋策略”和“固定分區(qū)策略”的求解結(jié)果,驗證“半柔性覆蓋策略”的有效性。
目前,已有研究大多是結(jié)合電子商務(wù)環(huán)境下物流配送業(yè)務(wù)特征展開研究,如劉必爭等[7]認為傳統(tǒng)選址模型中假設(shè)“物流設(shè)施到客戶的配送是放射線狀”已經(jīng)不適用于B2C 物流配送模式,必須考慮車輛的巡回訪問特性,并建立帶軟時間窗的選址-路線集成模型(Location Routing Problem with Soft Time Windows,LRPSTW),結(jié)合遺傳算法和退火算法求解;段鳳華等[8]針對電商配送客戶多、分布廣、品種多、批量小的特點,以及配送業(yè)務(wù)的車輛巡回訪問特性,建立了物流配送的基本VRP(Vehicle Routing Problem)模型,設(shè)計了禁忌搜索算法求解;付朝暉等[9]針對生鮮電商配送的“最后一公里”難題,開放車輛必須返回配送中心的規(guī)則,研究生鮮電商配送的開放式時變車輛路徑問題;李琳等[10]考慮訂單的配送時間和時效性要求,建立訂單配送路線優(yōu)化模型,設(shè)計改進禁忌搜索算法進行求解,之后,李琳等[11]又在2011年提出充分利用訂單未來信息,改進了訂單配送路線優(yōu)化模型,并設(shè)計兩階段啟發(fā)式算法求解;Du等[12]考慮客戶需求的動態(tài)波動特征,研究了動態(tài)需求的車輛動態(tài)調(diào)度問題,并設(shè)計了一個模擬系統(tǒng)來仿真該過程;Zhang 等[13]考慮訂單的緊急度等特征,集成訂單處理和配送車輛調(diào)度問題,建立訂單處理和車輛調(diào)度集成模型,并比較了多種算法的求解結(jié)果;Naccache 等[14]提出供應(yīng)商直配模式,研究了供應(yīng)商直接為電商客戶配送的drop-ship配送路線問題,并以最小化運出成本為目標(biāo)函數(shù)建立優(yōu)化模型。此外,韓珣[15]、辜勇[16]、賀韻竹[17]等針對常規(guī)環(huán)境下的配送路線優(yōu)化問題提出了合作覆蓋和協(xié)同配送策略。然而,韓珣等[15]研究考慮合作覆蓋的多級自提點選址問題,其協(xié)同體現(xiàn)在客戶可前往任意自提點取貨;辜勇等[16]研究帶時間窗的多中心半開放式車輛路徑問題,其協(xié)同配送體現(xiàn)在要求車輛完成任務(wù)后從客戶處返回任意配送中心;賀韻竹等[17]研究自營貨車與公交車協(xié)同快件配送優(yōu)化問題,其協(xié)同體現(xiàn)在自營車和公交車的協(xié)同換乘上。
與本文關(guān)注點不同,本文考慮現(xiàn)實中某些地區(qū)可能同時存在于多個配送站的服務(wù)半徑內(nèi),存在由多個配送中心為其服務(wù)的可能,通過借鑒這一可能來平衡站點資源,提高系統(tǒng)應(yīng)對需求暴增的風(fēng)險抵抗力。
半柔性覆蓋的多配送中心路線優(yōu)化問題(ΜVRPSFS)可以描述為:配送網(wǎng)絡(luò)中存在多個配送中心為多個客戶進行服務(wù),配送站集合為D={p|p=1,2,…,P},客戶集合為S={r|r=1,2,…,R},其中S=S1?S2,S1為柔性需求點客戶,S2為固定需求點客戶,所有點集合U=D ?S,車輛集合為V={k|k=1,2,…,M}。對于每個配送站p 而言,其固定客戶集合為S2(p),柔性客戶集合為S1(p),S2={S2(p)|p=1,2,…,P},S1={S1(1)?S1(2)?…?S1(P)}。目的是在每天開展配送任務(wù)時,根據(jù)當(dāng)天任務(wù),以配送成本最小為目標(biāo),規(guī)劃出一條合適的配送方案,以滿足所有客戶點需求。與常規(guī)配送優(yōu)化問題(VRP)不同的是:因?qū)⒖蛻魠^(qū)分為固定需求點和柔性需求點,柔性客戶在優(yōu)化過程中可由其覆蓋的多個協(xié)同配送中心的任意配送中心進行服務(wù),而固定客戶只能由按“固定分區(qū)策略”規(guī)劃的所屬配送站進行服務(wù)。圖1 是問題示意圖,圖中兩個矩形框代表不同配送期,灰色填充點為柔性需求點。在“半柔性覆蓋策略”下,可以兼顧系統(tǒng)穩(wěn)定性和配送效率,同時平衡多配送站剩余資源。
圖1 半柔性覆蓋的多配送中心路線優(yōu)化問題示意圖
其余變量如下:Dp為配送中心p 的存儲量;dr為客戶r 的需求量;Qk是車輛k 的容量;cij是點i 至點j的行駛距離;Fk是車輛k 的使用成本;Fu是單位距離行駛成本。
決策變量為:
為建立模型,做了如下假設(shè):
(1)配送中心與客戶點地理位置均已知;
(2)存在多個配送中心且其服務(wù)能力滿足客戶需求;
(3)從配送中心到客戶以及客戶之間的距離均已知;
(4)車輛統(tǒng)一,且容量已知,并且在配送過程中不得超過其額定載重量;
(5)每個客戶有且僅有一輛車為其服務(wù);
(6)客戶對貨物的需求量或者同一子路徑上的所有客戶需求量之和不超過車輛的容量。建立模型如下:
式(1)為目標(biāo)函數(shù),表示總成本最小;式(2)表示每個配送中心容量大于客戶的總需求量;式(3)表示每個客戶由一個配送中心配送;式(4)表示每個配送中心服務(wù)的需求量之和不大于運力;式(5)表示客戶的需求量小于車容量;式(6)表示每輛車路線上客戶需求量之和小于車容量;式(7)表示每個配送中心有可支配車輛;式(8)表示每個客戶僅被服務(wù)一次;式(9)表示進入某節(jié)點的車須從該節(jié)點離開;式(10)表示每輛車分配給一個配送中心;式(11)表示分配給配送中心的固定客戶不變;式(12)表示靈活分配的客戶可由多個配送中心配送。
本文采用改進遺傳算法求解ΜVRP-SFS模型。
本文包含兩個決策:一是決定客戶服務(wù)順序;二是決定柔性需求點的配送站分配。基于此,本文采用兩行整數(shù)編碼對服務(wù)順序和所屬配送站進行并行編碼。令順序編碼為X ,配送站分配編碼為Y 。需要說明的是,固定需求點配送站分配總是固定不變。解碼方法結(jié)合編碼和最大車容量劃分車輛服務(wù)對象以生成配送路徑。
圖2 是包含3 個配送站和10 個客戶的并行編碼例子,3個配送站編號為1~3,10個客戶編號為4~13。第一行表示客戶服務(wù)順序X :7-8-6-5-10-4-11-9-12-13;第二行對應(yīng)給出每個客戶的所屬配送站Y :1-2-3-3-2-1-3-3-1-2。
圖2 并行編碼例子
具體解碼方式為:
步驟1 根據(jù)編碼得到各配送站服務(wù)對象,如配送站1 服務(wù)客戶7、4、12,配送站2 服務(wù)客戶8、10、13,配送站3服務(wù)客戶6、5、11、9。
步驟2 結(jié)合最大車容量安排配送路徑,舉個例子,若配送站1 安排車輛依次服務(wù)客戶7、4、9,若服務(wù)完客戶4后不能服務(wù)客戶12,則服務(wù)路徑為1-7-4-1-12-1。
隨機選擇幾個未接受服務(wù)的客戶點,達到某輛車的最大容載量,然后不斷地重復(fù)以上步驟,直到所有的客戶點都被服務(wù),得到幾個染色體。將得到的染色體分別代入模型的各個約束中,檢測該染色體的可行性,如果不可行,則刪除該染色體。直到所有的染色體的可行性檢測完畢,所有的染色體都被生成,得到初始種群。
適應(yīng)度函數(shù)是評價每個個體的優(yōu)劣與否的指標(biāo),將適應(yīng)度高的個體保留下來,傳到下一代,淘汰適應(yīng)度低的個體。因此種群的進化程度是根據(jù)個體的適應(yīng)度值來決定的。
適應(yīng)度函數(shù)一般情況下是根據(jù)目標(biāo)函數(shù)來決定的,并且適應(yīng)度值要求是非負的。
表1 配送站坐標(biāo)
本文優(yōu)化目標(biāo)是成本最小化,因此設(shè)置適應(yīng)度函數(shù)為:
其中,Zi為染色體i 的目標(biāo)函數(shù)值,n 為種群大小,目標(biāo)函數(shù)值越大則適應(yīng)度函數(shù)的值就越小,該個體的適應(yīng)度就越小。
選擇算子是將上一代個體中的適應(yīng)度值較大的個體選擇出來,然后對選擇出來的個體進行交叉和變異。本文采用的是遺傳算法中常用的方法輪盤賭來選擇算子。輪盤賭選擇算子就是將種群中的染色體根據(jù)其適應(yīng)度值按比例分配到輪上的各個區(qū)域(對應(yīng)的區(qū)域與個體的適應(yīng)度值成正比),轉(zhuǎn)動輪盤,輪盤停止時指針?biāo)傅膫€體就是要選擇的個體。因此個體i 被遺傳到下一代的概率為:
需要說明的是,在本文的選擇算子中,將對順序編碼X(圖2 中第一行)和所屬站點編碼Y(圖2 中第二行)都分別進行選擇,得到父代XSel 和YSel。
對父代XSel 和YSel 分別采用兩點交叉生成子代XSel1 和YSel1。具體為:在上一代的個體中,隨機確定兩個基因交叉的位置,然后將兩個上一代個體的基因位進行交換,產(chǎn)生新的基因組。兩點交叉能夠保證一定會產(chǎn)生新的個體,保證了種群的多樣性。
例如:若父代為“7-8-6-5-10-4-11-9-12-13”和“13-12-10-5-8-6-9-7-11-4”,隨機產(chǎn)生兩個數(shù)r1=4 和r2=7,則兩個交叉片段為“5-10-4-11”和“5-8-6-9”,將兩個交叉片段進行交換,然后根據(jù)交叉片段的映射關(guān)系合法化染色體得到兩個新的個體“7-10-4-5-8-6-9-11-12-13”和“13-12-8-5-10-4-11-7-6-9”。
設(shè)計交換操作分別對子代XSel1 和YSel1 進行變異,例如,對于種群中的一個染色體XSel1“7-8-6-5-10-4-11-9-12-13”,隨機選擇兩個變異點4和7,則將變異點的基因交換生成新的個體“7-8-6-11-10-4-5-9-12-13”。
這里的“進化”是指逆轉(zhuǎn)算子的單方向性,即只有經(jīng)逆轉(zhuǎn)后,適應(yīng)度值有提高的才接受下來,否則逆轉(zhuǎn)無效。
具體為:產(chǎn)生兩個隨機整數(shù)r1和r2,確定兩個位置,將其對換位置,如r1=4 和r2=7,則“7-8-6-5-10-4-11-9-12-13”逆轉(zhuǎn)后為“7-8-6-11-4-10-5-9-12-13”。
采用的終止條件是達到預(yù)先設(shè)定的迭代次數(shù)。
本文以申通快遞在陜西省西安北郊地區(qū)的5 個配送站點為例,包括北郊一(未央?yún)^(qū)龍崗大道十八號譚家村對面)、北郊二(未央?yún)^(qū)石化大道東18 號華運停車場院內(nèi))、北郊三(未央?yún)^(qū)玄武路大明宮派出所對面)、北郊六(蓮湖區(qū)自強西路217 號干鮮果批發(fā)市場)以及草灘分部。整個配送網(wǎng)絡(luò)共計5個配送站,209個客戶點,站點位置和經(jīng)緯度如表1 所示,客戶點位置、經(jīng)緯度和需求量如表2 所示,圖3 是服務(wù)區(qū)域示意圖。定義位于圖中的交叉區(qū)域的需求點為柔性需求點,可由其交叉的任意站點服務(wù)。
表2 客戶點坐標(biāo)和需求信息
圖3 配送中心位置及配送范圍示意
通過實地調(diào)研、公眾號查詢與電話咨詢等方式,可獲知5 個站點均采取“分區(qū)配送策略”,表3 和圖4 以北郊一為例展示了服務(wù)客戶-路徑服務(wù)關(guān)系。另外,西安草灘分部中包含兩個學(xué)校區(qū)域,這兩個區(qū)域?qū)儆诳蛻糇蕴?,這里將其剔除不考量。其他參數(shù)設(shè)置為:配送車輛選擇電動三輪車,最大容載量為300,運輸成本為6,發(fā)車成本為150,車輛使用成本Fk=150,行駛距離cij直接采用經(jīng)緯度帶入式(15)計算并四舍五入得到。
圖4 西安北郊一線路1的實際路線
為展示本文所提出的“半柔性覆蓋策略”的特性,以兩天的不同需求任務(wù)量為數(shù)據(jù),代入對應(yīng)兩天配送方案(表2 中的“任務(wù)一”和“任務(wù)二”)。采用Μatlab 2016a編程,操作系統(tǒng)為Windows 10,電腦內(nèi)存為8 GB,CPU為Intel i7-6700,主頻3.40 GHz。經(jīng)過實驗,初始條件設(shè)置為:交叉概率0.8,變異概率0.2,種群大小100,迭代次數(shù)5 000。
圖5是本文算法的求解迭代圖,可見算法搜索約在4 000 次時趨于平穩(wěn),尋找到最優(yōu)值為5 406,說明該算法能穩(wěn)定收斂,合理有效。
圖5 進化迭代圖
表4是“任務(wù)一”下“半柔性覆蓋策略”的5個站點的配送路線,共計19 輛車,其中車輛1~4 屬于配送站I,和現(xiàn)狀車輛數(shù)相同;車輛5~9屬于配送站II,相對于現(xiàn)狀少了1 輛車;車輛10~13 屬于配送站III,和現(xiàn)狀車輛數(shù)相同;車輛14~16屬于配送站IV,和現(xiàn)狀車輛數(shù)相同;車輛17~19 屬于配送站V,相較于現(xiàn)狀少了1 輛車。表中邊框標(biāo)注改變配送站的柔性需求點,下劃線標(biāo)注未改變服務(wù)站的柔性需求點。表5 給出了邊框柔性需求點的服務(wù)站變更詳情。圖6對應(yīng)5個站點優(yōu)化后的配送路線。
表3 申通陜西西安北郊一負責(zé)客戶點概況
表4 需求任務(wù)一的求解結(jié)果
表5 柔性需求點的配送站服務(wù)改變情況
表6是“任務(wù)二”下“半柔性覆蓋策略”的5個站點的配送路線,同樣,表中邊框標(biāo)注改變配送站的柔性需求點,下劃線標(biāo)注未改變服務(wù)站的柔性需求點。表7進一步給出了邊框柔性需求點的服務(wù)站變更詳情。與表3和表4對比,可知本文所提出的“半柔性覆蓋策略”是在每次配送到來時,保持“固定需求點”的服務(wù)站點不變,多配送站點協(xié)同對“柔性需求點”確定合適的服務(wù)站點,并最終求解得到符合當(dāng)前配送任務(wù)的配送線路。
為突出本文算法的有效性,表8 給出了“基本遺傳算法”“就近分配+本文算法”和“本文算法”的求解結(jié)果對比。基本遺傳算法不采用本文所設(shè)計的交換變異和逆轉(zhuǎn)進化操作,而采用常規(guī)單點變異,不添加逆轉(zhuǎn)進化。“就近分配+本文算法”采用就近分配將柔性需求點分配到最近配送站,采用本文算法對配送服務(wù)順序進行優(yōu)化。結(jié)果顯示:本文算法求解結(jié)果優(yōu)于基本遺傳算法,算法改進有效;對柔性客戶點的分配決策進行優(yōu)化有利于提高配送效率和平衡站點資源。圖7 是兩種對比方法的收斂圖。
表9 以“任務(wù)一”下的求解結(jié)果方案與現(xiàn)有實際配送方案對比??梢?,在“任務(wù)一”下,現(xiàn)有實際配送成本為6 048元,需要21輛車,而本文策略優(yōu)化后僅需5 406元,所需車輛減少為19 輛,成本降低10.62%,車輛數(shù)減少2輛。
為進一步說明表9 中的成本降低是來自于路線優(yōu)化還是“半柔性覆蓋策略”,同時為進一步展示“半柔性覆蓋策略”的特性,這里繼續(xù)將需求任務(wù)一下“半柔性覆蓋策略”的求解結(jié)果與“固定分區(qū)策略”(可看作“非柔性覆蓋策略”)和“全柔性覆蓋策略”的求解結(jié)果進行對比?!肮潭ǚ謪^(qū)策略”指的是固定客戶和服務(wù)配送站的對應(yīng)關(guān)系,所有客戶點仍由原屬配送站進行配送,側(cè)重于優(yōu)化每個配送站的配送路線;“全柔性覆蓋策略”指的是不固定客戶和配送站的對應(yīng)關(guān)系,客戶可由任意配送站的任意配送員服務(wù),該問題轉(zhuǎn)化為傳統(tǒng)的多中心VRP優(yōu)化問題。對比結(jié)果如表10所示。
圖6 5個站點的配送路線
表6 需求任務(wù)二的求解結(jié)果
表7 柔性需求點的配送站服務(wù)改變情況
表8 與其他方法的結(jié)果對比
圖7 兩種對比方法的收斂圖
表9 與現(xiàn)有實際配送方案的結(jié)果對比
表10 三種策略的結(jié)果對比表
從表10中可知,在“固定分區(qū)策略”下,路徑優(yōu)化結(jié)果為5 580 元,車輛數(shù)為21 輛,成本較現(xiàn)有實際情況優(yōu)化了7.74%,配送司機對服務(wù)路線和服務(wù)客戶的熟悉度較高,客戶服務(wù)穩(wěn)定性100%;在“全柔性覆蓋策略”下,路徑優(yōu)化結(jié)果為5 376 元,車輛數(shù)為19 輛,成本較現(xiàn)有實際情況優(yōu)化了11.11%,但是配送司機對服務(wù)路線和服務(wù)客戶的熟悉度較低,客戶服務(wù)穩(wěn)定性0%,可能導(dǎo)致管理復(fù)雜,司機對新路線不熟悉,客戶對司機不熟悉等一系列問題;在“半柔性覆蓋策略”下,路徑優(yōu)化結(jié)果為5 406元,車輛數(shù)為19輛,成本較現(xiàn)有實際情況優(yōu)化了10.62%,客戶服務(wù)穩(wěn)定性80%。
綜上可見,若完全看重系統(tǒng)穩(wěn)定性(即采用“固定分區(qū)策略”),系統(tǒng)穩(wěn)定性較好,但成本降低會損失約3.37%;若完全看重成本降低(即采用“全柔性覆蓋策略”),配送效率較高,但客戶穩(wěn)定性將可能犧牲較大;在“半柔性覆蓋策略”下,其配送效率近似“全柔性覆蓋策略”的配送效率(全柔性覆蓋下成本降低為11.11%,和“半柔性覆蓋策略”下的成本降低的差值僅0.49 個百分點),且同時能保持80%的客戶服務(wù)穩(wěn)定性,綜合效用較高。另外,將表9 與表8 中的“就近分配+本文算法”對比,可以看出,在“半柔性覆蓋策略”下,即使僅采用最為簡單的就近分配來分配這些柔性需求點,其決策效果仍舊優(yōu)于“固定分區(qū)策略”的決策效果(5 538<5 580)。綜上,“半柔性覆蓋策略”是一種兼顧系統(tǒng)穩(wěn)定性和成本優(yōu)化的較好策略。
本文通過區(qū)分固定需求點和柔性需求點,定義柔性需求點可由多個配送站協(xié)同服務(wù),提出“半柔性覆蓋策略”;以總成本最小為目標(biāo),建立了基于半柔性覆蓋的多配送中心路線優(yōu)化模型,設(shè)計了遺傳算法求解,Μatlab編譯;結(jié)果測試以申通快遞在西安北郊地區(qū)的5個配送站點為例驗證了模型、算法和“半柔性覆蓋策略”的有效性。研究結(jié)果如下:(1)本文建立的模型合理有效,能夠求解出半柔性覆蓋的多配送中心路線優(yōu)化問題的方案;(2)本文對基本遺傳算法的改進合理有效;(3)本文提出的“半柔性覆蓋策略”的配送效率近似“全柔性覆蓋策略”的配送效率,且同時能保持80%的客戶服務(wù)穩(wěn)定性,綜合效用較高;(4)在“半柔性覆蓋策略”下,即使采用最為簡單的就近分配來分配這些柔性需求點,其決策效果仍舊優(yōu)于“固定分區(qū)策略”的決策效果。