基于軟時(shí)間窗的多車艙生鮮品配送路徑優(yōu)化

溫廷新，李可昕，胡迎春

(遼寧工程技術(shù)大學(xué) 工商管理學(xué)院，遼寧 葫蘆島 123000)

0 引言

近年來，隨著工業(yè)的不斷發(fā)展、溫室效應(yīng)的不斷加劇，以“低能源，低消耗，低排放”為基礎(chǔ)的節(jié)能減排理念受到學(xué)者們的廣泛關(guān)注。交通運(yùn)輸業(yè)的碳排放量在總碳排放量中占有很大的比例，為保持生鮮品的質(zhì)量，冷鏈運(yùn)輸會(huì)排放更多的CO2。為此，冷鏈物流的路徑優(yōu)化研究變得更加有意義[1-2]，從綠色物流的視角看，采用多車艙的配送方式更加具有研究意義[3]。

在考慮碳排放的車輛路徑優(yōu)化研究上，國(guó)內(nèi)外學(xué)者已針對(duì)低碳視角下的生鮮品冷鏈配送路徑優(yōu)化問題做出了相應(yīng)的研究。韓颯[4]根據(jù)車聯(lián)網(wǎng)技術(shù)，提出一種道路交叉口環(huán)保駕駛汽車路徑優(yōu)化控制模型；任慧等[5]根據(jù)車輛行駛狀態(tài)定義道路擁堵情況，以不同時(shí)段下?lián)矶赂怕屎皖A(yù)期擁堵距離作為路況決定因素，構(gòu)建碳排放量和經(jīng)濟(jì)成本都最小的兩目標(biāo)模型；魯建廈等[6]為了提升子母式飛梭集散倉(cāng)庫(kù)的運(yùn)行效能，針對(duì)該集散倉(cāng)庫(kù)組合操作中的立體路線優(yōu)化問題展開了研究；劉枚蓮等[7]研究了帶碳排放和時(shí)間窗雙重約束的車輛路徑優(yōu)化問題；張旭等[8]針對(duì)需求與碳交易價(jià)格雙重不確定下的多式聯(lián)運(yùn)路徑優(yōu)化問題建立了混合魯棒隨機(jī)優(yōu)化模型；Guo等[9]考慮到車輛的負(fù)載和驅(qū)動(dòng)距離，建造了相應(yīng)的碳排放模型并將其設(shè)為優(yōu)化目標(biāo)。

此外，也有一些學(xué)者針對(duì)生鮮品的冷鏈運(yùn)輸問題展開研究。任騰等[10]以顧客滿意度為指標(biāo)，以車輛載重、顧客時(shí)間窗口、冷藏食品腐壞速率等為約束條件，建立了以最少碳排放為目標(biāo)，以顧客服務(wù)時(shí)間為限的冷鏈運(yùn)輸路線優(yōu)化模型；方文婷等[11]采用混合蟻群算法對(duì)總成本最小模型進(jìn)行優(yōu)化；余海燕等[12]針對(duì)線上到線下(Online to Offline，O2O)生鮮外賣訂單動(dòng)態(tài)性高和配送服務(wù)時(shí)效性強(qiáng)的特征，建立以配送距離最小為目標(biāo)、帶硬時(shí)間窗的O2O生鮮外賣即時(shí)配送路徑優(yōu)化模型；呂成瑤等[13]通過改進(jìn)蟻群算法對(duì)冷鏈物流成本最小模型進(jìn)行優(yōu)化；姚源果等[14]為了更好地實(shí)現(xiàn)終端柔性配送并有效地減少整體配送費(fèi)用，提出了在供應(yīng)鏈中合理地布置接駁點(diǎn)，并以交通狀況與接駁點(diǎn)為依據(jù)構(gòu)建了農(nóng)產(chǎn)品供應(yīng)鏈的配送路線最優(yōu)的數(shù)學(xué)模型；丁艷[15]針對(duì)傳統(tǒng)多溫共配冷鏈物流車輛配送路徑優(yōu)化方法提出一種新的多溫共配冷鏈物流車輛配送路徑優(yōu)化方法；王旭坪等[16]以車輛能量消耗為切入點(diǎn)，研究多溫度冷鏈物流車輛的碳排放測(cè)算方法并將其與時(shí)間和空間距離相結(jié)合，建立兼顧碳排放和時(shí)間空間距離的冷藏物流車輛運(yùn)輸路徑優(yōu)化模型，并設(shè)計(jì)兩階段啟發(fā)式算法對(duì)其進(jìn)行求解；唐燕等[17]利用薄板樣條法插值分析動(dòng)態(tài)環(huán)境溫度與制冷變量關(guān)系，建立響應(yīng)動(dòng)態(tài)環(huán)境溫度的擴(kuò)展鄰域搜索調(diào)度模型。

綜上所述，許多學(xué)者在低碳物流及冷鏈物流方面作了諸多研究，但罕見學(xué)者對(duì)碳排放下的多車艙多溫共配方式進(jìn)行研究。本研究針對(duì)不同溫層的生鮮品運(yùn)輸問題，從低碳和不同溫層生鮮品貨損2個(gè)角度進(jìn)行分析，綜合考慮配送車輛產(chǎn)生的碳排放量及貨損問題，以帶軟時(shí)間窗的車輛路徑優(yōu)化模型為基礎(chǔ)，構(gòu)建一個(gè)成本及能耗最低的路徑優(yōu)化模型，采用知識(shí)型蟻群算法進(jìn)行優(yōu)化。

1 多車艙生鮮品路徑優(yōu)化模型建立

1.1 問題描述

本研究中的多車艙生鮮品多溫共配問題是傳統(tǒng)車輛路徑優(yōu)化研究的擴(kuò)展類型，問題具體表述為：配送系統(tǒng)包含一個(gè)配送中心和多名顧客需求點(diǎn)，采用一般貨車，在車上放置處于不同溫層的蓄冷箱，配送冷凍及冷藏產(chǎn)品。各顧客點(diǎn)的需求及配送時(shí)間窗已知，對(duì)生鮮品冷鏈多溫共配問題需要做出以下假設(shè)：

(1)配送車輛都是從分配中心出發(fā)并最后返回該配送中心；

(2)每個(gè)車艙只能裝對(duì)應(yīng)溫層的生鮮品；

(3)物品的配送流向?yàn)閱蜗颍?/p>

(4)每名顧客的需求量已知且只被服務(wù)一次，切忌不可重復(fù)服務(wù)，同時(shí)不可遺漏顧客；

(5)運(yùn)輸工具為K輛車，所有客戶由K輛車共同配送，每條配送路線都只有一輛車配送，不可中途換車；

(6)每輛車的不同溫層的裝載量不能超過不同溫層的最大載重量；

(7)每輛車裝載量不可超過車輛的運(yùn)輸能力，須大于單向顧客總需求量；

(8)每名顧客都有自己的配送時(shí)間窗，配送車輛要在限定的配送時(shí)間窗內(nèi)配送；

(9)各個(gè)節(jié)點(diǎn)的距離已知。

1.2 配送成本及碳排放計(jì)算

1.2.1 配送成本計(jì)算

本研究中的多車艙生鮮品路徑優(yōu)化問題對(duì)運(yùn)輸車輛的配送成本進(jìn)行了全面分析，包括固定成本、運(yùn)輸成本、貨損成本、時(shí)間窗的機(jī)會(huì)與懲罰成本、制冷成本。

(1)配送車輛的固定成本

在生鮮品配送過程中，配送車輛會(huì)產(chǎn)生一部分固定成本，包括蓄冷箱的購(gòu)買及損耗成本、車輛折舊費(fèi)、車輛派遣費(fèi)用、司機(jī)駕駛費(fèi)、裝卸工人工資等。

C1=H×f，

(1)

式中，H為車輛總數(shù)；f為車輛的單位固定成本。

(2)配送車輛的運(yùn)輸成本

車輛的運(yùn)輸成本，即車輛在物流配送過程中從一名顧客到下一名顧客途中所產(chǎn)生的費(fèi)用，與車輛行駛的距離成正比，使用V代表配送網(wǎng)絡(luò)，其中G={0，1，2，…，m}表示網(wǎng)格中的節(jié)點(diǎn)，{0}表示配送中心。

(2)

式中，h為第h輛車；B為車輛的單位運(yùn)輸成本；Bijh為第h輛車在路段(Gi，Gj)行駛的單位運(yùn)輸成本；Xijh為0-1變量，若車輛h在路段(Gi，Gj)行駛即Xijh=1，否則Xijh=0；dij為(Gi，Gj)之間的距離。

(3)配送車輛在運(yùn)輸過程中所產(chǎn)生的貨損成本

配送車輛在運(yùn)輸過程中會(huì)產(chǎn)生兩部分的貨損：一部分是在車輛正常行駛過程中產(chǎn)生的貨損，另一部分是由于配送車輛在服務(wù)顧客過程中打開蓄冷箱時(shí)導(dǎo)致溫度驟然升高，使生鮮品的新鮮程度降低，導(dǎo)致品質(zhì)下降產(chǎn)生一定的貨損。

P2yjh(w2dij+w4tj2)，

(3)

式中，P1為冷凍區(qū)貨物的價(jià)格；P2為冷藏區(qū)貨品的價(jià)格；yjh為0-1變量，表示第h輛車服務(wù)j顧客；w1，w2分別為在運(yùn)輸過程中冷凍區(qū)和冷藏區(qū)的單位貨損比例；w3，w4為在服務(wù)顧客過程中冷凍區(qū)和冷藏區(qū)的單位貨損比例；tij為配送車輛從客戶i到客戶j的時(shí)間；tj1，tj2分別為車輛為顧客j服務(wù)時(shí)冷凍區(qū)和冷藏區(qū)所產(chǎn)生的時(shí)間；

(4)配送時(shí)間窗的機(jī)會(huì)成本及懲罰成本

配送車輛要在特定時(shí)間范圍內(nèi)進(jìn)行配送以保證生鮮品的質(zhì)量，在時(shí)間窗之前到達(dá)則會(huì)產(chǎn)生部分的機(jī)會(huì)成本，而在時(shí)間窗之后到達(dá)會(huì)產(chǎn)生部分懲罰成本。

(4)

式中，α，β分別為時(shí)間窗的機(jī)會(huì)成本和時(shí)間窗的懲罰成本；Sj為配送車輛到達(dá)時(shí)間；(L，T)為客戶的配送時(shí)間窗；

(5)配送車輛的制冷成本

配送車輛采用蓄冷箱進(jìn)行冷藏及冷凍產(chǎn)品運(yùn)輸。蓄冷箱由蓄冷板構(gòu)成，采用充電的方式進(jìn)行蓄冷。蓄冷箱在運(yùn)輸過程中損失掉多少的冷量，就相當(dāng)于蓄冷箱在之前要儲(chǔ)存多上的冷量，而蓄冷需要消耗很多的電，所謂的制冷成本也就是蓄冷箱蓄冷時(shí)所耗的電。

C5=Q·E·P3，

(5)

tj1+b2×tj2)，

(6)

式中，Q為損失掉的熱量；E為每單位熱量需要的電；P3為單位用電價(jià)格；a1，a2分別為在運(yùn)輸過程中冷凍區(qū)和冷藏區(qū)單位時(shí)間冷量損失；b1，b2分別為在服務(wù)顧客時(shí)單位時(shí)間冷量損失；

1.2.2 碳排放計(jì)算

傳統(tǒng)的冷鏈運(yùn)輸中碳排放有兩部分，一部分是正常行駛過程中產(chǎn)生碳排放，另一部分是冷藏車為保持車輛內(nèi)部溫度不變，需要不斷地進(jìn)行冷氣輸入，這時(shí)也會(huì)產(chǎn)生一部分碳排放。然而，該方案中采用一般貨車進(jìn)行配送，制冷部分采用蓄冷箱完成大幅減少碳排放的產(chǎn)生。

CE=λ×Z，

(7)

C6=P4×Z，

(8)

Z=(R1+φ(R2-R1))dij，

(9)

式中，CE為碳排放量；Z為總耗油量；R1為車輛空載時(shí)單位距離油耗量；R2為車輛滿載時(shí)單位距離油耗量；φ為車輛貨物裝載率；λ為單位油耗量產(chǎn)生的碳排放因子；P4為單位油耗的價(jià)格。

1.3 模型建立

建立多車艙生鮮品多溫共配路徑優(yōu)化模型：

minc=c1+c2+c3+c4+c5+c6。

(10)

確保車輛的裝載量不會(huì)超出自身最大裝載量：

(11)

式中q為車輛自身最大裝載量。接下來，確保全部顧客得到了服務(wù)，無一遺漏：

(12)

僅對(duì)每一名顧客提供一次服務(wù)，并且沒有多次提供的情況：

(13)

僅有一部車輛為每位顧客提供服務(wù)：

(14)

為顧客提供的服務(wù)應(yīng)在顧客所能承受的范圍內(nèi)：

Lj≤Sj≤Tj，j=1，2，3，…m。

(15)

2 算法設(shè)計(jì)

傳統(tǒng)蟻群算法是以人為方式對(duì)螞蟻覓食的過程進(jìn)行仿真，即個(gè)體間的溝通和合作，最后在食物和棲息地之間找出一條最短的路線。若將傳統(tǒng)的蟻群算法運(yùn)用到本研究的路徑優(yōu)化模型中求最優(yōu)解，對(duì)局部最優(yōu)解的優(yōu)化能力較差，影響最優(yōu)解的質(zhì)量。本研究為了改善算法的品質(zhì)，在傳統(tǒng)的蟻群算法中加入了知識(shí)模型，使得該算法能得到高品質(zhì)的優(yōu)化結(jié)果。與此同時(shí)，為了增強(qiáng)蟻群算法的局部?jī)?yōu)化能力，進(jìn)而提升算法的收斂速度[18]，將知識(shí)型精英策略下的禁忌搜索算子融入到其中。

2.1 編碼方式

本研究根據(jù)多車艙冷鏈物流配送路徑優(yōu)化模型采用自然數(shù)編碼方式，每只螞蟻由多位自然數(shù)編碼組成，其中“0”表示物流配送中心，“1，2，3，…，n”表示顧客節(jié)點(diǎn)編碼。例如：

(1)當(dāng)n=4時(shí)，路徑為0-4-2-1-3-0，表示為配送車輛從配送中心出發(fā)進(jìn)經(jīng)過4，2，1，3，最后回到配送中心；

(2)當(dāng)n=5時(shí)，路徑為0-3-1-5-2-4-0，表示為配送車輛從配送中心出發(fā)進(jìn)經(jīng)過3，1，5，2，4，最后回到配送中心；

(3)當(dāng)n=7時(shí)，路徑為0-3-1-5-7-6-4-2-0，表示為配送車輛從配送中心出發(fā)經(jīng)過3，1，5，7，6，4，2，最后回到配送中心。

2.2 知識(shí)模型指導(dǎo)下的禁忌搜索算子設(shè)計(jì)

在傳統(tǒng)的蟻群算法對(duì)當(dāng)代個(gè)體求解后，設(shè)置禁忌搜索對(duì)象S為算法的最優(yōu)解，并初始化搜素計(jì)數(shù)器C，然后生成鄰域，選取較為合適的解對(duì)比，更新禁忌表和操作對(duì)象。當(dāng)計(jì)數(shù)器C達(dá)到最大時(shí)，輸出找到的最優(yōu)解，當(dāng)算法找到最優(yōu)解時(shí)，將計(jì)數(shù)器初始化并繼續(xù)搜索。在此基礎(chǔ)上，提出了一種新的優(yōu)化方法，并利用該方法引導(dǎo)禁忌搜索算法對(duì)該方法進(jìn)行了求解。它的指導(dǎo)性作用主要體現(xiàn)在兩方面：所記錄的歷史最優(yōu)解將大概率在搜索過程中作為搜索對(duì)象，歷史最優(yōu)解以動(dòng)態(tài)選擇概率替換較差鄰域解。

2.3 算法流程

本研究在傳統(tǒng)的蟻群算法基礎(chǔ)上融入了知識(shí)型精英決策下的禁忌搜索算子，所設(shè)計(jì)的知識(shí)型蟻群算法的優(yōu)化分析流程見圖1。

圖1 多車艙路徑優(yōu)化模型算法流程圖Fig.1 Flow chart of algorithm for multi-compartment routing optimization model

3 實(shí)例求解及分析

3.1 算例驗(yàn)證

以某物流中轉(zhuǎn)站為例，為20名顧客配送貨物，配送中心及顧客的節(jié)點(diǎn)位置已知。 編號(hào)1～20為顧客節(jié)點(diǎn)，編號(hào)0為物流配送中心，共4輛車參與配送，車輛總載重為60 t，每個(gè)區(qū)域的最大載重為20 t，冷凍區(qū)的溫度保持在-18～-20 ℃，冷藏區(qū)保持在3～5 ℃，常溫區(qū)隨室外溫度變化(本研究限定常溫為20 ℃)，在運(yùn)輸途中保證貨物不串味，車輛的行駛速度為45 km/h，在滿足車輛不超載的約束條件下合理安排路線。各個(gè)客戶點(diǎn)位置及限定的時(shí)間窗見表1，每名顧客在不同溫層的需求量及裝卸時(shí)間見表2，相關(guān)參數(shù)設(shè)置見表3。

表1 各節(jié)點(diǎn)位置(單位：km)Tab.1 Positions of each node(unit：km)

表2 顧客的需求量及裝卸時(shí)間Tab.2 Customer demand and loading-unloading time

表3 相關(guān)參數(shù)Tab.3 Related parameters

3.2 結(jié)果分析

3.2.1 試驗(yàn)1

為驗(yàn)證多車艙多溫共配運(yùn)輸方式的有效性，經(jīng)過與傳統(tǒng)運(yùn)輸方式進(jìn)行對(duì)比，通過程序進(jìn)行實(shí)證分析，最大迭代次數(shù)為200次，借助Matlab軟件進(jìn)行優(yōu)化得出多車艙生鮮品路徑優(yōu)化模型的最優(yōu)配送路線(見表4)，最終得出最優(yōu)成本為4 057.24元，該方案產(chǎn)生的碳排放量為17.05 kg(見表5)。

表4 最優(yōu)配送路線Tab.4 Optimal distribution routes

表5 不同運(yùn)輸方式的成本及碳排放量Tab.5 Costs and carbon emissions of different transport modes

由表4～5可知，多車艙多溫共配方式與傳統(tǒng)運(yùn)輸方式相比較，避免了車輛重復(fù)路徑，減少了車輛的配送總路程，提高了配送時(shí)效性。在配送成本及碳排放量方面，多車艙多溫共配方式是傳統(tǒng)運(yùn)輸方式的1/3，極大程度上降低了配送的總成本，減少了碳排放的產(chǎn)生。由此可見，多車艙多溫共配是一種既節(jié)能又節(jié)約的運(yùn)輸方式。

3.2.2 試驗(yàn)2

為了檢驗(yàn)本研究所提出的知識(shí)蟻群算法的正確性，將知識(shí)蟻群算法、改進(jìn)蟻群算法和蟻群算法應(yīng)用于多車艙多溫共配運(yùn)輸路線優(yōu)化問題，并對(duì)該問題的收斂性進(jìn)行了比較和分析(見表6)。

表6 算法收斂對(duì)比Tab.6 Algorithm convergence contrast

由表6可知，改進(jìn)的蟻群算法在25 s時(shí)已經(jīng)完成算法收斂，而知識(shí)型蟻群算法和蟻群算法分別在75 s和130 s才完成算法收斂。但是從運(yùn)輸總成本上看，知識(shí)型蟻群算法的總成本為最小，改進(jìn)蟻群算法和蟻群算法的總成本均高于知識(shí)型蟻群算法。由此可以看出，知識(shí)型蟻群算法雖然在收斂速度上比改進(jìn)蟻群算法慢，但是所求得的總成本是最低的。

4 結(jié)論

本研究為了解決不同溫層生鮮品的物流配送問題，針對(duì)多車艙生鮮品多溫共配方式展開研究，基于低碳及不同溫層生鮮品的角度建立一種基于軟時(shí)間窗的總成本及能耗最低的路徑優(yōu)化模型，將知識(shí)螞蟻算法應(yīng)用于最優(yōu)解，得到如下結(jié)論：

(1)提出了一種由傳統(tǒng)車輛路徑優(yōu)化模型拓展的多車艙多溫共配路徑優(yōu)化模型。在配送成本及碳排放量方面，多車艙多溫共配方式的總成本近似于傳統(tǒng)的運(yùn)輸方式總成本的1/3?？梢姡捎枚嘬嚺摱鄿毓才涞倪\(yùn)輸方式是一種既環(huán)保又節(jié)省成本的運(yùn)輸方式。

(2)本研究介紹了一種知識(shí)型蟻群算法優(yōu)化。這種算法是對(duì)已有蟻群算法的一種改進(jìn)，避免了原有算法的局部最優(yōu)、收斂性較差等缺點(diǎn)。知識(shí)型蟻群算法雖然在收斂速度上比改進(jìn)蟻群算法慢，但是所求得的總成本是最低的。由此可見，根據(jù)多車艙多溫共配路徑優(yōu)化模型的特點(diǎn)，提出的知識(shí)型蟻群算法有效地提高了求解性能，驗(yàn)證了該算法的有效性和實(shí)用性。

(3)當(dāng)前研究中未考慮交通擁堵、極惡劣天氣影響、零碳排放等方面問題，未來將進(jìn)一步對(duì)這些情況展開研究。