基于軟時間窗的多車艙生鮮品配送路徑優化

溫廷新，李可昕，胡迎春

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

0 引言

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

在考慮碳排放的車輛路徑優化研究上，國內外學者已針對低碳視角下的生鮮品冷鏈配送路徑優化問題做出了相應的研究。韓颯[4]根據車聯網技術，提出一種道路交叉口環保駕駛汽車路徑優化控制模型；任慧等[5]根據車輛行駛狀態定義道路擁堵情況，以不同時段下擁堵概率和預期擁堵距離作為路況決定因素，構建碳排放量和經濟成本都最小的兩目標模型；魯建廈等[6]為了提升子母式飛梭集散倉庫的運行效能，針對該集散倉庫組合操作中的立體路線優化問題展開了研究；劉枚蓮等[7]研究了帶碳排放和時間窗雙重約束的車輛路徑優化問題；張旭等[8]針對需求與碳交易價格雙重不確定下的多式聯運路徑優化問題建立了混合魯棒隨機優化模型；Guo等[9]考慮到車輛的負載和驅動距離，建造了相應的碳排放模型并將其設為優化目標。

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

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

1 多車艙生鮮品路徑優化模型建立

1.1 問題描述

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

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

(2)每個車艙只能裝對應溫層的生鮮品；

(3)物品的配送流向為單向；

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

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

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

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

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

(9)各個節點的距離已知。

1.2 配送成本及碳排放計算

1.2.1 配送成本計算

本研究中的多車艙生鮮品路徑優化問題對運輸車輛的配送成本進行了全面分析，包括固定成本、運輸成本、貨損成本、時間窗的機會與懲罰成本、制冷成本。

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

在生鮮品配送過程中，配送車輛會產生一部分固定成本，包括蓄冷箱的購買及損耗成本、車輛折舊費、車輛派遣費用、司機駕駛費、裝卸工人工資等。

C1=H×f，

(1)

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

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

車輛的運輸成本，即車輛在物流配送過程中從一名顧客到下一名顧客途中所產生的費用，與車輛行駛的距離成正比，使用V代表配送網絡，其中G={0，1，2，…，m}表示網格中的節點，{0}表示配送中心。

(2)

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

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

配送車輛在運輸過程中會產生兩部分的貨損：一部分是在車輛正常行駛過程中產生的貨損，另一部分是由于配送車輛在服務顧客過程中打開蓄冷箱時導致溫度驟然升高，使生鮮品的新鮮程度降低，導致品質下降產生一定的貨損。

P2yjh(w2dij+w4tj2)，

(3)

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

(4)配送時間窗的機會成本及懲罰成本

配送車輛要在特定時間范圍內進行配送以保證生鮮品的質量，在時間窗之前到達則會產生部分的機會成本，而在時間窗之后到達會產生部分懲罰成本。

(4)

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

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

配送車輛采用蓄冷箱進行冷藏及冷凍產品運輸。蓄冷箱由蓄冷板構成，采用充電的方式進行蓄冷。蓄冷箱在運輸過程中損失掉多少的冷量，就相當于蓄冷箱在之前要儲存多上的冷量，而蓄冷需要消耗很多的電，所謂的制冷成本也就是蓄冷箱蓄冷時所耗的電。

C5=Q·E·P3，

(5)

tj1+b2×tj2)，

(6)

式中，Q為損失掉的熱量；E為每單位熱量需要的電；P3為單位用電價格；a1，a2分別為在運輸過程中冷凍區和冷藏區單位時間冷量損失；b1，b2分別為在服務顧客時單位時間冷量損失；

1.2.2 碳排放計算

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

CE=λ×Z，

(7)

C6=P4×Z，

(8)

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

(9)

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

1.3 模型建立

建立多車艙生鮮品多溫共配路徑優化模型：

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

(10)

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

(11)

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

(12)

僅對每一名顧客提供一次服務，并且沒有多次提供的情況：

(13)

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

(14)

為顧客提供的服務應在顧客所能承受的范圍內：

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

(15)

2 算法設計

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

2.1 編碼方式

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

(1)當n=4時，路徑為0-4-2-1-3-0，表示為配送車輛從配送中心出發進經過4，2，1，3，最后回到配送中心；

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

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

2.2 知識模型指導下的禁忌搜索算子設計

在傳統的蟻群算法對當代個體求解后，設置禁忌搜索對象S為算法的最優解，并初始化搜素計數器C，然后生成鄰域，選取較為合適的解對比，更新禁忌表和操作對象。當計數器C達到最大時，輸出找到的最優解，當算法找到最優解時，將計數器初始化并繼續搜索。在此基礎上，提出了一種新的優化方法，并利用該方法引導禁忌搜索算法對該方法進行了求解。它的指導性作用主要體現在兩方面：所記錄的歷史最優解將大概率在搜索過程中作為搜索對象，歷史最優解以動態選擇概率替換較差鄰域解。

2.3 算法流程

本研究在傳統的蟻群算法基礎上融入了知識型精英決策下的禁忌搜索算子，所設計的知識型蟻群算法的優化分析流程見圖1。

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

3 實例求解及分析

3.1 算例驗證

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

表1 各節點位置(單位：km)Tab.1 Positions of each node(unit：km)

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

表3 相關參數Tab.3 Related parameters

3.2 結果分析

3.2.1 試驗1

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

表4 最優配送路線Tab.4 Optimal distribution routes

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

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

3.2.2 試驗2

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

表6 算法收斂對比Tab.6 Algorithm convergence contrast

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

4 結論

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

(1)提出了一種由傳統車輛路徑優化模型拓展的多車艙多溫共配路徑優化模型。在配送成本及碳排放量方面，多車艙多溫共配方式的總成本近似于傳統的運輸方式總成本的1/3?？梢?，采用多車艙多溫共配的運輸方式是一種既環保又節省成本的運輸方式。

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

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