王 丹, 讓桂芳

(沈陽(yáng)大學(xué) 裝備制造綜合自動(dòng)化重點(diǎn)實(shí)驗(yàn)室, 遼寧 沈陽(yáng) 110044)

綠色低碳是運(yùn)輸行業(yè)的關(guān)注熱點(diǎn)[1]。隨著電商的飛速發(fā)展,人們?cè)絹?lái)越愿意選擇在線上購(gòu)買生鮮商品,社區(qū)團(tuán)購(gòu)行業(yè)發(fā)展迅速,各大企業(yè)紛紛搶占市場(chǎng)份額與商機(jī)[2]。社區(qū)團(tuán)購(gòu)指的是以各個(gè)社區(qū)為單位,以社交軟件為平臺(tái),用戶通過小程序購(gòu)買商品的新興零售模式[3]。由于配送路徑不合理而造成的運(yùn)輸成本高嚴(yán)重影響著企業(yè)的利潤(rùn)[4],因此,社區(qū)團(tuán)購(gòu)企業(yè)應(yīng)該合理規(guī)劃配送路徑。

車輛路徑問題(vehicle routing problem)指在多個(gè)約束的條件下,為滿足客戶的需求,由配送中心安排調(diào)度,從而給出配送方案,最開始是Dantzig等[5]在1957年提出的。范立南等[6]針對(duì)農(nóng)產(chǎn)品的配送問題,考慮了碳排放成本的加入,使用遺傳算法進(jìn)行求解。張?zhí)烊鸬萚7]在碳稅政策下考慮了疫情原因,引入了消毒成本,并使用細(xì)菌覓食-蟻群算法對(duì)模型求解。社區(qū)團(tuán)購(gòu)是中心倉(cāng)配送到團(tuán)長(zhǎng),團(tuán)長(zhǎng)再配送或用戶自提的倉(cāng)配模式,或者由中心倉(cāng)配送到網(wǎng)格倉(cāng),然后由網(wǎng)格倉(cāng)往團(tuán)長(zhǎng)站點(diǎn)進(jìn)行配送。本文在以往的研究基礎(chǔ)上研究了由中心倉(cāng)配送到團(tuán)長(zhǎng)的過程。與已有研究不同的是,本文綜合考慮了多方面成本,更貼合實(shí)際情況,同時(shí)利用一種新型的智能算法----鯨魚算法,對(duì)配送路徑進(jìn)行優(yōu)化,以追求總成本最小。

1 問題描述

對(duì)社區(qū)團(tuán)購(gòu)來(lái)說,城市中心倉(cāng)為調(diào)度中心,團(tuán)長(zhǎng)為客戶。可以描述為:當(dāng)日車輛統(tǒng)一從城市中心倉(cāng)出發(fā),經(jīng)過運(yùn)輸,在規(guī)定的時(shí)間內(nèi),到達(dá)團(tuán)長(zhǎng)站點(diǎn)的位置進(jìn)行卸貨,并且一個(gè)團(tuán)長(zhǎng)站點(diǎn)只能由一輛車進(jìn)行服務(wù),但同一車輛可為多個(gè)團(tuán)長(zhǎng)站點(diǎn)服務(wù)。調(diào)度中心合理安排配送路徑,既能滿足客戶需求,又能降低配送總成本[8]。圖1為社區(qū)團(tuán)購(gòu)中心倉(cāng)配送示意圖。

圖1 社區(qū)團(tuán)購(gòu)中心倉(cāng)配送示意圖

2 社區(qū)團(tuán)購(gòu)配送路徑優(yōu)化模型

2.1 模型假設(shè)條件

在構(gòu)建模型時(shí),對(duì)問題做如下假設(shè):

① 在單個(gè)區(qū)域內(nèi)有1個(gè)中心倉(cāng),車輛由中心倉(cāng)出發(fā),完成后返回中心倉(cāng);

② 中心倉(cāng)商品庫(kù)存充足,單車配送量不大于車輛的最大載重量;

③ 已知固定的各個(gè)團(tuán)長(zhǎng)站點(diǎn)位置、需求和時(shí)間窗;

④ 貨物到達(dá)時(shí)間不在時(shí)間窗內(nèi),將產(chǎn)生懲罰費(fèi)用,但不考慮卸貨時(shí)間消耗;

⑤ 碳排放成本僅考慮運(yùn)輸時(shí),運(yùn)輸距離取實(shí)際距離且車輛勻速行駛無(wú)特殊情況;

⑥ 團(tuán)長(zhǎng)站點(diǎn)僅能被服務(wù)一次,車輛可以服務(wù)多個(gè)團(tuán)長(zhǎng)站點(diǎn),不考慮逆向物流;

⑦ 中心倉(cāng)擁有數(shù)量充足的配送車輛,車輛為燃油車,載重量相同且燃油和制冷劑充足。

2.2 設(shè)置參數(shù)說明

根據(jù)城市中心倉(cāng)的地點(diǎn)和團(tuán)長(zhǎng)站點(diǎn)的位置進(jìn)行數(shù)學(xué)模型的創(chuàng)建,模型中的符號(hào)定義見表1。

表1 符號(hào)說明

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

根據(jù)實(shí)際配送情況,主要考慮的成本[9]分析如下。

1) 固定成本F1。固定成本與實(shí)際調(diào)度車輛數(shù)目相關(guān),

2) 運(yùn)輸成本F2。運(yùn)輸成本主要與燃油的使用量相關(guān),跟車輛的實(shí)際行駛距離成正比[10],

3) 貨損成本F3。社區(qū)團(tuán)購(gòu)行業(yè)中,包含了大量的生鮮冷鏈商品,此類商品訂單量大且在配送過程中容易發(fā)生商品變質(zhì)、新鮮度降低等情況。本文考慮到商品的價(jià)值損耗,貨損成本主要由貨物總量Q,配送時(shí)間T及損耗系數(shù)ω影響,假設(shè)商品均價(jià)為P,

4) 制冷成本F4。運(yùn)輸生鮮商品時(shí)需要控溫,所以考慮制冷劑的消耗量,

5) 碳排放成本F5。碳排放成本,主要是與運(yùn)輸過程中消耗燃油制冷劑產(chǎn)生的CO2排放造成的,

6) 時(shí)間窗懲罰成本F6。社區(qū)團(tuán)購(gòu)的優(yōu)勢(shì)是快速準(zhǔn)時(shí),所以對(duì)時(shí)間窗的要求比較高,當(dāng)配送車輛為ti,若未在團(tuán)長(zhǎng)站點(diǎn)i預(yù)期的時(shí)間窗[Ei,Li]范圍內(nèi)送達(dá),就會(huì)產(chǎn)生懲罰成本,

因此建立最小總成本(Z)為目標(biāo)的數(shù)學(xué)模型:

minZ=F1+F2+F3+F4+F5+F6。

其余約束條件如下:

(1)

式(1)表示每個(gè)團(tuán)長(zhǎng)站點(diǎn)最多由一輛車提供配送服務(wù);

(2)

式(2)限制了配送車輛的最大載重量;

(3)

式(3)表示每一輛車從城市中心倉(cāng)出發(fā)后又返回中心倉(cāng)。

3 鯨魚優(yōu)化算法

針對(duì)該數(shù)學(xué)模型,采用鯨魚優(yōu)化算法進(jìn)行求解。

鯨魚優(yōu)化算法(whaleoptimizationalgorithm,WOA)是模仿自然界中鯨魚捕捉獵物行為的新型智能優(yōu)化算法,最近幾年被廣泛應(yīng)用在組合優(yōu)化或連續(xù)優(yōu)化問題上[11]。鯨魚優(yōu)化算法搜索過程中,一個(gè)鯨魚個(gè)體代表著一個(gè)解,若干個(gè)鯨魚通過不斷更新迭代自身位置,直到搜索出滿意解為止[12]。鯨魚進(jìn)行優(yōu)化搜索的捕食動(dòng)作主要分為3種:包圍獵物、發(fā)泡網(wǎng)攻擊和搜索捕食[13]。如圖2[14]所示。

圖2 泡泡網(wǎng)捕食法

1) 包圍獵物。座頭鯨在捕食時(shí),首先會(huì)識(shí)別獵物的位置,然后再進(jìn)行對(duì)獵物的圍捕[15]。計(jì)算公式如下:

2) 氣泡攻擊。氣泡攻擊是座頭鯨在捕食時(shí)特有的吐氣泡的行為,當(dāng)前鯨魚個(gè)體選擇螺旋運(yùn)動(dòng)的方式向當(dāng)前最佳鯨魚個(gè)體靠近[17],進(jìn)行位置的更新,

式中:參數(shù)b為對(duì)數(shù)螺旋形狀常數(shù),控制鯨魚個(gè)體進(jìn)行螺旋式移動(dòng)通常取值為1,當(dāng)b=1時(shí),鯨魚的移動(dòng)軌跡表現(xiàn)為普通的對(duì)數(shù)螺旋線;l代表一個(gè)取值范圍為[-1,1]的隨機(jī)數(shù),與螺旋形狀參數(shù)b一起,用于計(jì)算鯨魚個(gè)體在進(jìn)行螺旋移動(dòng)時(shí)的位置更新,L的隨機(jī)性為算法提供了多樣性。座頭鯨在捕食游走時(shí),各以50%的概率選擇包圍圈或選擇以螺旋式向獵物游走[18]。數(shù)學(xué)模型見式(4)。

(4)

3) 搜索捕食。因?yàn)樵跉馀莨魰r(shí),數(shù)學(xué)模型中的A1的取值范圍是[-1,1],也就意味著當(dāng)A1的取值不在此范圍時(shí),當(dāng)前鯨魚個(gè)體有可能不會(huì)向當(dāng)前最佳鯨魚個(gè)體進(jìn)行游動(dòng),而是隨機(jī)選擇搜索其他鯨魚個(gè)體[19]。這樣的搜索捕食過程也就增加了該算法的全局搜索能力。Xrand為隨機(jī)選擇的鯨魚位置。搜索捕食行為的數(shù)學(xué)模型如下:

式中,Xrand為鯨魚群體中隨機(jī)選擇的一個(gè)鯨魚個(gè)體的位置。

綜上所述 ,WOA求解問題的流程圖如圖3所示。

圖3 WOA求解問題流程

4 算例分析

為研究社區(qū)團(tuán)購(gòu)區(qū)域中心倉(cāng)-團(tuán)長(zhǎng)環(huán)節(jié)的配送問題,本文在進(jìn)行算例分析時(shí),考慮到社區(qū)團(tuán)購(gòu)行業(yè)的配送活動(dòng)范圍的有限性,區(qū)域倉(cāng)的配送范圍覆蓋分為200個(gè)左右的小區(qū),單個(gè)小區(qū)團(tuán)長(zhǎng)站點(diǎn)數(shù)量在0～2個(gè)的范圍內(nèi),同時(shí)也會(huì)因訂單需求的不同,來(lái)決定是否需要進(jìn)行配送活動(dòng),所以選取種群數(shù)量N=200,初始種群成員分別選取40、60、80和100,使用WOA進(jìn)行求解,分別選取第7代和第22代的結(jié)果,對(duì)其總?cè)簲?shù)量的敏感性及其收斂性進(jìn)行分析,得到的數(shù)據(jù)如圖4與圖5所示。

圖5 不同種群數(shù)量最優(yōu)解變化曲線(第22代)

分析圖4、圖5發(fā)現(xiàn),無(wú)論是第幾代,當(dāng)初始種群數(shù)量為100時(shí),目標(biāo)函數(shù)取得滿意值的速度更快,收斂性更好;而當(dāng)初始種群數(shù)量為40時(shí),目標(biāo)函數(shù)取得滿意值的速度相對(duì)較慢,即當(dāng)區(qū)域內(nèi)團(tuán)長(zhǎng)站點(diǎn)數(shù)量變得更少時(shí),不易取得滿意解。這也表明隨著種群規(guī)模的增加,不僅能增強(qiáng)搜索能力,還能提升算法向最優(yōu)解逼近的速度,收斂性更強(qiáng)。

在鯨魚優(yōu)化算法求解問題的過程中,一個(gè)鯨魚可以用來(lái)代表一個(gè)解,搜索問題最優(yōu)解的過程就可以看成是若干個(gè)鯨魚個(gè)體不斷地更新個(gè)體的位置,直到搜索出滿意的解為止。鯨魚優(yōu)化算法能夠隨機(jī)選擇其余一些非最優(yōu)解的情況,這能夠有效地避免陷入局部最優(yōu)解。同時(shí),在收斂的過程中也能夠降低遺漏最優(yōu)解情況的發(fā)生。同時(shí)鯨魚優(yōu)化算法具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、搜索能力強(qiáng)、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。種群成員數(shù)量越多,路徑優(yōu)化效果越好。因此,該算法在面向社區(qū)團(tuán)購(gòu)企業(yè)進(jìn)行大規(guī)模配送的場(chǎng)景時(shí)是完全適用的,而且當(dāng)團(tuán)長(zhǎng)站點(diǎn)數(shù)量越多,效果就越好。

5 結(jié) 論

為解決社區(qū)團(tuán)購(gòu)因配送路徑不合理造成的成本增加,同時(shí)響應(yīng)國(guó)家低碳政策的號(hào)召,本文研究了由區(qū)域中心倉(cāng)到團(tuán)長(zhǎng)這一配送環(huán)節(jié)。構(gòu)建了考慮碳排放的路徑優(yōu)化模型,考慮了固定成本、運(yùn)輸成本、貨損成本、制冷成本、碳排放成本和時(shí)間窗懲罰成本等多種因素,將鯨魚優(yōu)化算法應(yīng)用于面向社區(qū)團(tuán)購(gòu)的配送路徑規(guī)劃問題,不僅可以降低二氧化碳的排放量,還能為企業(yè)選擇合理的配送路徑方案,降低配送環(huán)節(jié)的成本,增大利潤(rùn)空間,有利于企業(yè)長(zhǎng)遠(yuǎn)發(fā)展。

配送路徑優(yōu)化問題,就是在多個(gè)約束下,選擇總成本最小方案。而對(duì)于社區(qū)團(tuán)購(gòu)這種線上購(gòu)物平臺(tái)來(lái)說,既要尋求多種成本的降低,又要考慮客戶的滿意度。鯨魚優(yōu)化算法具有搜索范圍廣、結(jié)構(gòu)簡(jiǎn)單、搜索能力強(qiáng)等優(yōu)點(diǎn)。本文驗(yàn)證了鯨魚優(yōu)化算法在種群成員數(shù)量越多的情況下,搜索能力越強(qiáng)和收斂效果越好,并且迭代次數(shù)越多,取得滿意解越早,也就說明鯨魚優(yōu)化算法在區(qū)域內(nèi)團(tuán)長(zhǎng)數(shù)量較多、需求零散的情況下,仍擁有較強(qiáng)的穩(wěn)定性和收斂速度。在總成本最小的目標(biāo)下,能在有限的迭代次數(shù)內(nèi),尋找到滿意解,為配送車輛的提供路徑方案,為社區(qū)團(tuán)購(gòu)企業(yè)提供了車輛配送路徑優(yōu)化的求解方法。