隨著新零售時(shí)代的到來(lái),傳統(tǒng)生鮮電商的單一線上模式已經(jīng)難以滿足顧客即時(shí)配送和生鮮品質(zhì)等全方位的需求,于是生鮮電商企業(yè)開(kāi)始由單一線上模式轉(zhuǎn)化為線上平臺(tái)+線下體驗(yàn)的新模式來(lái)滿足顧客多樣化的需求,提出了一種新的倉(cāng)配模式——前置倉(cāng)。前置倉(cāng)是在生鮮貨物送往目的地前的最后一個(gè)倉(cāng)庫(kù)和站點(diǎn),也是最靠近消費(fèi)者的一個(gè)節(jié)點(diǎn),為了滿足分鐘級(jí)的配送,前置倉(cāng)的服務(wù)半徑通常約為3~5公里,采用這種模式能夠大幅度縮短生鮮貨物的運(yùn)輸時(shí)間,盡可能保證商品的新鮮度,提升商品的品質(zhì)[1-3]。
前置倉(cāng)屬于末端物流配送中心,與傳統(tǒng)物流配送中心不同的是,前置倉(cāng)對(duì)時(shí)效性要求更高,目前對(duì)于前置倉(cāng)的研究主要聚焦在前置倉(cāng)模式分析層面上,在具體實(shí)施層面上關(guān)于前置倉(cāng)選址問(wèn)題的研究較少[4]。近年來(lái)關(guān)于物流配送中心選址問(wèn)題主要從單目標(biāo)、多目標(biāo)及求解算法等方面進(jìn)行了研究。肖建華等引入了非等覆蓋半徑的思想建立了生鮮農(nóng)產(chǎn)品配送中心選址模型并提出了一種基于自適應(yīng)遺傳算法的動(dòng)態(tài)膜進(jìn)化算法[5],魏潔等建立了最小距離約束的生鮮農(nóng)產(chǎn)品多配送中心連續(xù)選址模型并設(shè)計(jì)了由模糊C均值聚類(lèi)算法與改進(jìn)模擬退火算法嵌套而成的FCM-ISA算法[6],Dou等針對(duì)冷藏食品易腐爛的特點(diǎn)引入新鮮度和時(shí)間窗等約束條件建立了冷鏈物流配送中心選址問(wèn)題的數(shù)學(xué)優(yōu)化模型,并提出了一種免疫狼群混合算法[7];隨著研究復(fù)雜度的提升,有學(xué)者將單目標(biāo)選址問(wèn)題延伸至多目標(biāo)選址問(wèn)題,Zhang等從顧客對(duì)生鮮商品需求不確定性的角度建立了生鮮配送中心選址模型并提出了一種改進(jìn)的果蠅優(yōu)化算法[8],宋英華等綜合考慮了災(zāi)后應(yīng)急物資動(dòng)態(tài)需求和實(shí)際道路狀況建立了多周期多目標(biāo)應(yīng)急物資配送中心快速選址模型并采用耦合Dijkstra算法的分層序列法進(jìn)行求解[9],黃露等針對(duì)延誤情境下配送中心選址問(wèn)題提出了雙層規(guī)劃模型,并利用層次遺傳算法進(jìn)行求解[10]。從對(duì)配送中心選址的研究成果來(lái)看,目前關(guān)于選址的模型多為考慮成本的單目標(biāo)選址模型,且從顧客時(shí)間需求的角度來(lái)考慮的配送中心選址研究還較少。
基于時(shí)效性對(duì)前置倉(cāng)的重要程度,本文將時(shí)間滿意度引入前置倉(cāng)選址問(wèn)題中,建立了配送成本最小和時(shí)間滿意度最大的雙目標(biāo)優(yōu)化模型,在傳統(tǒng)的遺傳算法基礎(chǔ)上基于進(jìn)化逆轉(zhuǎn)的思想提出了進(jìn)化突變操作并引入了精英保留策略[11],用于提高遺傳算法的尋優(yōu)能力與收斂速度,最后通過(guò)算例對(duì)模型和算法進(jìn)行驗(yàn)證。
本文研究的生鮮前置倉(cāng)選址問(wèn)題可描述為,在由前置倉(cāng)、顧客需求點(diǎn)構(gòu)成的二級(jí)物流網(wǎng)絡(luò)中,已知顧客需求點(diǎn)的位置與需求量,在滿足兩個(gè)目標(biāo)函數(shù)總配送成本最小和時(shí)間滿意度最大并達(dá)到最優(yōu)的情況下,從候選點(diǎn)中選出P個(gè)前置倉(cāng)建設(shè)點(diǎn)。
(1)每個(gè)需求點(diǎn)的顧客對(duì)時(shí)間滿意感知程度是一樣的,時(shí)間滿意度只與配送時(shí)間有關(guān)且時(shí)間滿意度函數(shù)是呈嶺形分布,不考慮因配送時(shí)間所造成的生鮮貨物的損耗。
(2)每個(gè)需求點(diǎn)的位置和需求量已知,并且需求量保持不變,前置倉(cāng)配送可以直接送達(dá)每個(gè)需求點(diǎn),由于前置倉(cāng)的建設(shè)成本為固定成本,所以不必算入成本目標(biāo)函數(shù)中。
(3)配送成本與運(yùn)輸距離成正比,所有生鮮貨物的單位距離運(yùn)輸成本相同,且擁有足夠的運(yùn)力進(jìn)行運(yùn)輸,不考慮競(jìng)爭(zhēng)因素。
表1 符號(hào)含義說(shuō)明
(1)配送成本
配送成本是由從前置倉(cāng)運(yùn)送生鮮貨物至顧客需求點(diǎn)所產(chǎn)生的物流運(yùn)輸費(fèi)用,配送成本與生鮮貨物運(yùn)輸量、運(yùn)輸距離、單位運(yùn)輸費(fèi)用有關(guān)。由于本文給出的前置倉(cāng)與需求點(diǎn)的距離為兩點(diǎn)之間的歐氏距離,所以乘以城市道路非直線系數(shù)來(lái)轉(zhuǎn)換為貨物的運(yùn)輸路程。配送成本計(jì)算方式如公式(1)所示。
(2)時(shí)間滿意度函數(shù)
時(shí)間滿意度函數(shù)為生鮮貨物從前置倉(cāng)運(yùn)送至顧客需求點(diǎn)所花費(fèi)時(shí)間的滿意程度,當(dāng)所花費(fèi)的配送時(shí)間越長(zhǎng),滿意度就越低。配送時(shí)間與配送距離和配送速度有關(guān),配送時(shí)間的計(jì)算如公式(2)所示,本文選取的是余弦分布時(shí)間滿意度函數(shù)[12],函數(shù)式如公式(3)所示。
本文建立了配送成本最小和時(shí)間滿意度最大的雙目標(biāo)優(yōu)化模型:
約束條件為:
目標(biāo)函數(shù)式(4)表示最小化總配送成本,目標(biāo)函數(shù)式(5)表示最大化總的顧客需求點(diǎn)的時(shí)間滿意度,目標(biāo)函數(shù)式(6)表示使用極大極小歸一化與線性加權(quán)處理將雙目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù),約束式(7)表示每一個(gè)需求點(diǎn)最多只能被一個(gè)前置倉(cāng)服務(wù),約束式(8)表示擬建設(shè)的前置倉(cāng)數(shù)量為P個(gè),約束式(9)表示需求點(diǎn)不能被沒(méi)有選中的前置倉(cāng)候選點(diǎn)服務(wù),約束式(10)表示需求點(diǎn)的滿意度水平達(dá)到了α?xí)r才能被覆蓋,約束式(11)表示每個(gè)前置倉(cāng)所覆蓋的需求點(diǎn)的需求量之和必須達(dá)到總需求量的β倍,約束式(12)表示總覆蓋需求必須達(dá)到θ以上,約束式(13)表示對(duì)決策變量Xj、Yij的0~1約束。
針對(duì)前置倉(cāng)選址問(wèn)題,本文給出了兩種前置倉(cāng)候選點(diǎn)的選取方式并設(shè)計(jì)出相應(yīng)的求解方法。第一種為將需求點(diǎn)通過(guò)聚類(lèi)算法進(jìn)行聚類(lèi),將聚類(lèi)后得到的聚類(lèi)中心作為候選點(diǎn),運(yùn)用CPLEX求解器求解整數(shù)規(guī)劃模型。第二種為將顧客需求點(diǎn)本身作為候選點(diǎn),由于CPLEX不適合求解大規(guī)模問(wèn)題,所以本文設(shè)計(jì)了改進(jìn)的遺傳算法對(duì)其進(jìn)行求解。
利用K-means聚類(lèi)算法將分散的需求點(diǎn)聚為K簇,將每一簇的聚類(lèi)中心作為前置倉(cāng)的候選點(diǎn),通過(guò)MATLAB調(diào)用CPLEX對(duì)所建立的模型進(jìn)行求解。聚類(lèi)操作可以簡(jiǎn)述為三步:
Step1:首先隨機(jī)抽取K個(gè)需求點(diǎn)作為最初的聚類(lèi)中心。
Step2:將每個(gè)需求點(diǎn)分配到離他們最近的聚類(lèi)中心,生成K簇。
Step3:對(duì)于每個(gè)簇,計(jì)算出所有被分到該簇的需求點(diǎn)的平均值作為新的聚類(lèi)中心,重復(fù)步驟2和步驟3,當(dāng)聚類(lèi)中心的位置不再發(fā)生改變時(shí),迭代停止,聚類(lèi)完成。
(1)編碼及解碼操作
編碼方式采用的是實(shí)數(shù)編碼,染色體的長(zhǎng)度為待建前置倉(cāng)數(shù)量加1,每一段染色體對(duì)應(yīng)著前置倉(cāng)候選點(diǎn)的編號(hào),0代表所有未能被待建前置倉(cāng)所服務(wù)的需求點(diǎn)集合,例如{9,12,47,68,78,31,64,0}為一個(gè)完整的染色體。
染色體解碼操作如下:
Step1:判斷需求點(diǎn)是否能滿足當(dāng)前染色體下任意前置倉(cāng)候選點(diǎn)的最低時(shí)間滿意度約束。
Step2:若無(wú)法滿足,則將該需求點(diǎn)歸為未能被待建前置倉(cāng)所服務(wù)的需求點(diǎn)集合。若能夠滿足,則查找出大于最低時(shí)間滿意度的前置倉(cāng)候選點(diǎn)集合,按照距離遠(yuǎn)近的劃分原則,將需求點(diǎn)分給集合中距離需求點(diǎn)最近的前置倉(cāng)候選點(diǎn)。
Step3:重復(fù)上述步驟直至所有染色體完成解碼。
(2)選擇、交叉、變異
選擇算子操作,通過(guò)適應(yīng)度函數(shù)可以評(píng)判各個(gè)個(gè)體的優(yōu)劣程度,本文的選擇算子通過(guò)輪盤(pán)賭的方式來(lái)進(jìn)行操作,個(gè)體的適應(yīng)度越大,該個(gè)體的基因遺傳到子代的概率也就越大。
交叉是產(chǎn)生新個(gè)體基因的主要來(lái)源,交叉的操作如下[13]:
Step1:在任意兩個(gè)基因之間隨機(jī)選擇兩個(gè)切點(diǎn),被選中的兩個(gè)基因稱(chēng)之為父代1和父代2。
Step2:從父代1中將兩個(gè)切點(diǎn)之間的基因片段復(fù)制給子代1。
Step3:從父代2中排除父代1遺傳給子代1的基因,以此避免重復(fù),之后從父代2中按照基因出現(xiàn)的順序,逐個(gè)復(fù)制基因給子代1,直到子代1的所有位置被填滿。
Step4:將上述操作的父代1和父代2進(jìn)行角色互換,得到子代2。
交叉操作示例如圖1所示。
圖1 交叉操作示例
變異操作有利于維持種群的多樣性,避免算法過(guò)早陷入局部最優(yōu),變異操作為隨機(jī)選擇兩個(gè)基本位,按照變異概率將兩個(gè)基本位上的基因值替換為個(gè)體中從未出現(xiàn)過(guò)的基因值。變異操作示例如圖2所示。
圖2 變異操作示例
(3)進(jìn)化突變
基于進(jìn)化逆轉(zhuǎn)的思想,本文提出了進(jìn)化突變操作,進(jìn)化突變是指隨機(jī)替換基因個(gè)體上的片段,新替換的基因片段為替換之前個(gè)體中所沒(méi)有出現(xiàn)過(guò)的基因,進(jìn)化體現(xiàn)在,當(dāng)進(jìn)化突變過(guò)后的基因個(gè)體適應(yīng)度變高,則進(jìn)行突變,否則不進(jìn)行突變。進(jìn)化突變示例如圖3所示。
圖3 進(jìn)化突變示例
(4)精英保留
采用精英保留可以確保優(yōu)良的個(gè)體能夠保留得以延續(xù)至下一代,保證子代不會(huì)比父代差,精英保留的操作步驟如下:
Step1:將經(jīng)過(guò)選擇、交叉、變異、進(jìn)化突變操作后形成的子代與父代放在一起,按照適應(yīng)度高低進(jìn)行排序,遵循從適應(yīng)度高到低的選擇原則,選擇出一定比例適應(yīng)度高的基因。
Step2:將選擇出來(lái)的適應(yīng)度高的基因等量替換步驟1中所形成的子代中適應(yīng)度低的子代,此時(shí)重新形成的子代為真正的子代,精英保留操作完成。
本文通過(guò)算例來(lái)證明模型和改進(jìn)的遺傳算法的有效性以及候選點(diǎn)選取方式的優(yōu)劣性,算例的需求點(diǎn)坐標(biāo)來(lái)自于文獻(xiàn)[14],每個(gè)需求點(diǎn)的年度需求量的數(shù)值為隨機(jī)生成,取值范圍為0.2千噸到5千噸,需求量數(shù)據(jù)如表2所示。本文是在Windows10系統(tǒng)下進(jìn)行的求解操作,模型采用CPLEX 12.80來(lái)進(jìn)行求解,算法使用的是MATLAB 2018a軟件來(lái)進(jìn)行編寫(xiě)。遺傳算法的種群規(guī)模為300,迭代次數(shù)為500,交叉概率為0.9,變異概率為0.1,精英保留比例為0.3。其他相關(guān)參數(shù)如表3所示。
表2 各需求點(diǎn)的需求量數(shù)據(jù)
表3 其他相關(guān)參數(shù)
采用傳統(tǒng)的遺傳算法與本文改進(jìn)之后的遺傳算法分別求解單目標(biāo)下的時(shí)間滿意度的最大值,兩種算法的求解次數(shù)均為10次,取10次中的最優(yōu)結(jié)果作為最終時(shí)間滿意度的最大值,兩種算法的優(yōu)化過(guò)程如圖4所示,通過(guò)對(duì)比可以發(fā)現(xiàn)本文改進(jìn)后的遺傳算法的尋優(yōu)能力與收斂速度均優(yōu)于傳統(tǒng)的遺傳算法。
圖4 改進(jìn)遺傳算法的時(shí)間滿意度迭代過(guò)程
通過(guò)K-means聚類(lèi)算法將130個(gè)需求點(diǎn)聚成11類(lèi),得到11個(gè)聚類(lèi)中心,聚類(lèi)結(jié)果如圖5所示。
圖5 需求點(diǎn)聚類(lèi)結(jié)果
運(yùn)用CPLEX對(duì)模型進(jìn)行求解,最終從11個(gè)聚類(lèi)中心中選出聚類(lèi)中心1、3、4、5、6、8、9作為前置倉(cāng)建設(shè)點(diǎn),最終前置倉(cāng)覆蓋結(jié)果如圖6所示。運(yùn)用改進(jìn)之后的遺傳算法對(duì)模型進(jìn)行求解,得到將需求點(diǎn)17、26、47、61、72、102、117作為前置倉(cāng)建設(shè)點(diǎn),最終前置倉(cāng)覆蓋結(jié)果如圖7所示。
圖6 運(yùn)用CPLEX模型求解前置倉(cāng)覆蓋結(jié)果
圖7 運(yùn)用改進(jìn)后的遺傳算法模型求解前置倉(cāng)覆蓋結(jié)果
根據(jù)上述所給參數(shù),分別計(jì)算出CPLEX軟件與改進(jìn)之后的遺傳算法(下文簡(jiǎn)稱(chēng)“GA”)在兩個(gè)目標(biāo)函數(shù)各自為單目標(biāo)函數(shù)情況下的極值,求解結(jié)果如表4所示。
表4 單目標(biāo)求解結(jié)果
將計(jì)算出的數(shù)值帶入公式(6)中,ω的取值為0.1~0.9,取值間隔為0.1,CPLEX與GA的計(jì)算結(jié)果見(jiàn)表5所示。
表5中CPLEX的求解結(jié)果均為雙目標(biāo)優(yōu)化的帕累托最優(yōu)解,決策者可根據(jù)自身的偏好,選擇相應(yīng)的最優(yōu)解。本文選取ω=0.4、0.6時(shí),成本為171.8327萬(wàn)元,時(shí)間滿意度為240.2521作為CPLEX的最終求解結(jié)果。在GA的求解結(jié)果中,當(dāng)ω=0.5時(shí)的結(jié)果要優(yōu)于ω=0.4、0.6、0.7時(shí)的求解結(jié)果,所以ω=0.4、0.6、0.7時(shí)的解為劣解,應(yīng)予以淘汰,本文選取ω=0.5時(shí),成本為167.9798萬(wàn)元,時(shí)間滿意度為227.2361作為GA的最終求解結(jié)果。
表5 不同ω取值下CPLEX與GA的計(jì)算結(jié)果
在ω相同的條件下,將CPLEX與GA計(jì)算出的成本與時(shí)間滿意度的結(jié)果進(jìn)行對(duì)比,除了ω的取值為0.5和0.6的情況下,CPLEX求出的成本不僅比GA小,并且時(shí)間滿意度還比GA大,求解結(jié)果完全優(yōu)于GA。在ω=0.5和0.6時(shí),雖然CPLEX所計(jì)算出的成本與時(shí)間滿意度均高于GA,但仔細(xì)比較來(lái)看,在成本上CPLEX與GA的成本差異幅度較小,在時(shí)間滿意度上CPLEX與GA差異的幅度要高于成本的差異幅度,說(shuō)明CPLEX求解的將聚類(lèi)中心作為候選點(diǎn)的選址方案成本效用更高。綜上分析,將聚類(lèi)中心作為候選點(diǎn)的選址效果要優(yōu)于將需求點(diǎn)作為候選點(diǎn)的選址效果。
本文針對(duì)前置倉(cāng)選址問(wèn)題,在分析現(xiàn)有物流配送中心選址模型的特點(diǎn)和不足的基礎(chǔ)上,從滿足顧客時(shí)間需求的角度來(lái)考慮前置倉(cāng)選址問(wèn)題,引入了時(shí)間滿意度這一概念,建立了以總配送成本最小,總顧客需求點(diǎn)的時(shí)間滿意度最大的雙目標(biāo)選址模型。在傳統(tǒng)的遺傳算法之上引入了精英保留策略并基于進(jìn)化逆轉(zhuǎn)的思想提出了進(jìn)化突變操作,并用算法對(duì)模型進(jìn)行了求解,從理論和具體實(shí)施兩個(gè)層面分析了所建模型及算法的有效性。通過(guò)對(duì)比兩種候選點(diǎn)選取方式的最終求解結(jié)果,發(fā)現(xiàn)以聚類(lèi)中心作為候選點(diǎn)的方式要優(yōu)于將需求點(diǎn)本身作為候選點(diǎn)的方式?,F(xiàn)有關(guān)于物流配送中心選址和前置倉(cāng)選址研究較少考慮時(shí)間滿意度因素和不同候選點(diǎn)選取方式的優(yōu)劣性,本文在一定程度上豐富了相關(guān)的設(shè)施選址理論及應(yīng)用,為前置倉(cāng)選址布局提供了決策參考。