帶回收過程的冷鏈物流車輛路徑優化

郭金明，楊孔雨

（北京信息科技大學 信息管理學院，北京 100192）

帶回收過程的冷鏈物流車輛路徑優化

郭金明，楊孔雨

（北京信息科技大學 信息管理學院，北京 100192）

分析了帶有退貨回收過程的冷鏈物流配送路徑優化問題，考慮到在服務客戶時已經回收的貨物存在二次裝卸的可能，根據運輸配送過程中存在的固定成本、折舊成本、裝卸成本、油耗成本和制冷成本等因素建立配送路徑優化模型，并結合改進的免疫蟻群混合算法對模型求解，最后通過實驗算例分析得出求得的解是滿意的，從而為冷鏈運輸配送企業的決策運營提供參考。

冷鏈物流；逆向回收；免疫蟻群算法；路徑優化

1 引言

隨著我國經濟的發展，人們的食品消費需求逐漸轉向營養調劑型，對新鮮果蔬、水產、肉、蛋、奶類的需求量不斷增加，質量要求也越來越高，使得冷鏈配送行業迅速發展[1]。當前眾多冷鏈配送企業以客戶滿意為導向，投入大量成本，不僅浪費了大量資源，也對環境造成了一定的影響。對于帶有回收過程的冷鏈配送的研究既貼合了客戶的需求，也降低了食品安全和環境污染的風險，對可持續發展具有重要意義。當前已有眾多學者對冷鏈配送的相關問題進行研究。李玉鵬等提出一種基于復雜網絡的“最后一公里”物流配送區域劃分方法，建立了一套完整的物流配送體系，有效提高了末端節點配送效率，降低了物流成本[2]。白燾等考慮到農產品的腐敗成本并設計了一種蜂群算法來分析冷鏈物流車輛路徑優化方法[3]。何琴飛考慮了道路交通狀況，基于道路阻抗函數的相關理論建立路徑優化模型，分析比較得出道路暢通狀況對冷鏈配送的重大影響[4]。

2 問題模型建立與分析

2.1 問題描述

冷藏車從配送中心出發，經過需要服務的客戶點后回到配送中心，形成一條閉環的運輸路線。本文中考慮的是一個配送中心服務于多個客戶點，且配送中心和客戶位置已知。根據客戶需求，在進行服務時將客戶需要的貨物量（Qreq）卸下同時將退貨（Qret）回收裝車。在進行貨物搬卸的過程中遵循“先下再上”的原則，即在把客戶需要的貨物卸下后再裝退還的貨物，如果退還的貨物過多則下次配送時再裝。送貨客戶的優先級高于取貨客戶，即允許收貨客戶被安排在退貨客戶之前獲得服務。考慮實際情況，車輛從配送中心出發假定都為滿載或接近滿載狀態，因此設定配送車輛不第一服務于只存在取貨服務的客戶。假定配送中心貨物、配送車輛和配送人員充足，可隨時裝貨配送。每輛冷藏車和配送員除編號不同外無其他差異。每輛冷藏車從配送中心出發后，對應行駛于一條線路并服務于該線路上的多個客戶，且每個客戶只被一輛車服務。在配送過程中不考慮道路平整度、紅綠燈等待、天氣原因、道路擁堵等不確定因素的影響，因此假定車輛在運輸途中勻速()Vm行駛。不考慮存在約定時間窗因素及其違反時產生的懲罰成本。

2.2 模型建立

2.2.1 目標函數

（1）固定成本。購（租）車輛成本、人員基本工資、維修費用等構成的車輛固定成本（折舊成本另計）。由此M輛車的固定成本Cm:

式中，M為配送所需車輛數，G為冷藏車的固定成本。

（2）車輛折舊成本。車輛使用過程中產生的車輛磨損成本，根據車輛的報廢里程數dm和購車成本pm，來確定使用折舊成本系數τm。制冷設備折舊損耗產生的單位時間折舊成本為，為完成一次完整的配送過程所需時間，由此第M輛車的折舊成本為：

（3）油耗成本。油耗與車輛行駛路程和載重成正相關關系，行駛路程越遠，輪胎承重負荷越大，油耗量越多。通常情況下，道路平整度、拐角轉彎次數、車輛啟停次數等也都會額外增加油耗，在這里不考慮這些因素對油耗的影響。由此油耗成本可表示為：

α表示滿載時單位燃油成本；dij表示兩點間距離；βm表示負載油耗比例系數；Xij表示車輛是否經過(i,j)路段，經過則Xij=1，否則為Xij=0。其中，負載油耗比例系數包括空載時的油耗比例和運貨時的油耗比例，那么 βm為：

（4）裝卸成本。在貨物裝卸過程中除了規范的一次性裝卸操作產生裝卸成本（固定裝卸成本）外，也會存在多次裝卸的情況。由于在每個服務點存在卸貨之后裝貨（回收的貨物）的可能，繼而在下一個服務點就會存在將已經裝車的回收貨物再進行一次裝卸操作的可能，由此就會額外產生裝卸成本。由此，考慮這兩點因素,裝卸成本為：

δ表示質量成本系數；Gq表示第q件貨物的質量；Ymiqj表示第m輛車在完成服務點i時車上已經回收到的第q件貨物在j服務點是否需要額外裝卸，若需要額外裝卸則Ymiqj=1，否則Ymiqj=0。

（5）制冷成本。貨物從裝上冷藏車的那一刻起，車廂就處于溫控狀態。車輛在運輸途中外部熱源會傳入熱負荷到車廂內對制冷劑造成消耗。另外，在裝卸貨物過程中，車廂門開啟也會造成大量熱負荷傳入，造成制冷劑的消耗。車廂門開啟的程度越大，熱負荷傳入越多，進而制冷劑的消耗也會越大，因此車門開啟程度與制冷成本是正相關的。考慮這兩個方面的制冷劑消耗，制冷成本表示為：

①運輸過程中由車廂壁熱傳導產生的制冷成本CQ1：

②在服務j點客戶的裝卸過程中產生的制冷成本CQ2：

Qb表示單位時間車廂門敞開面積下傳遞的熱負荷量；ρ*表示空氣介質下的熱傳導系數；S*表示車廂門面積；φm表示第m輛車的車廂門敞開系數；ΔT表示車廂內外溫度差；tb表示車廂門敞開時間；Zjm表示第m輛車是否服務j點客戶，若服務則Zjm=1，否則Zjm=0。

2.2.2 目標優化和條件約束。以運輸過程中最小成本為目標函數建立數學模型如下：

上述約束條件中，式（1）表示送貨的重量不超過M輛車的最大載重量；式（2）表示取送貨的重量不超過M輛車的最大載重量；式（3）表示在路段()i,j中，待送貨的重量、待取貨的重量和已取貨的重量的和不能超過該車的載重量；式（4）表示每個客戶只能由一輛車服務；式（5）表示車輛從配送中心出發服務完成后回到配送中心。

3 改進型免疫蟻群融合算法

3.1 免疫蟻群算法基本思想

本文中免疫蟻群算法是把免疫算法和蟻群算法經過改進融合后的智能混合算法，是以蟻群算法為主算法，將免疫算法嵌入到蟻群算法的過程中去。把蟻群算法求解的問題看作是抗原，通過提取疫苗來對信息素賦初值，由蟻群算法產生抗體給各參數賦值，并將問題中求得的第一個結果作為抗體的適應度值，然后通過免疫算法的疫苗接種、交叉、變異、親和度選擇等操作后淘汰親和度差的抗體，保留親和度較好的抗體作為新的初始蟻群再進行迭代，經過數次迭代后得到最終抗體，也就是蟻群算法對問題求得的最優結果。

算法中通過疫苗來給信息素賦初值，這樣避免了初始解的隨機性，加快了收斂速度；并采用接種疫苗、交叉、變異等操作在加快收斂速度的同時保證種群的多樣性。最后通過親和度來選擇更新群體，有效防止“早熟”現象，從而減小了陷入局部最優的可能。

3.2 免疫蟻群算法的基本流程

（1）初始化。提取疫苗，并給信息素賦初值；確定各參數的值，如螞蟻個數，交叉規則、變異概率等。

（2）由蟻群算法產生初始螞蟻群A。

（3）更新局部信息素的值。當一只螞蟻走完后用公式（6）更新局部信息素的值。

（4）更新全局信息素的值。當所有螞蟻走完所選路徑后，對每條路徑用公式（7）來更新信息素的值，其中pg是全局信息素的揮發系數，0≤pg≤1。

（5）對螞蟻群A進行交叉變異操作得到新的螞蟻（抗體）群B。

（6）對B中的螞蟻進行接種疫苗生成螞蟻（抗體）群C。

（7）從螞蟻B和C進行選擇操作，保留適應度好的螞蟻，淘汰適應度差的螞蟻，得到螞蟻（抗體）群D。

（8）判斷是否滿足終止條件。如果滿足則停止迭代，輸出最優解；否則跳轉第（9）。

（9）隨機生成螞蟻群E，對D?E中螞蟻進行選擇，用輪盤賭的方式來生成螞蟻群F。選擇時遵循濃度越高的被選擇的概率越低，以保證群體多樣性。完成后跳轉至（3）進行新一輪的迭代循環。

免疫蟻群算法的基本流程圖如圖1所示。

圖1 免疫蟻群算法的基本流程

4 實驗算例

根據某公司鮮奶配送中心的歷史配送相關資料來對各參數值進行合理設定。冷藏車從配送中心出發，向同城的10個需求點配送鮮牛奶。冷藏車額定載重為3t，一輛冷藏車配送一次的固定成本是150元，配送時車廂內溫度控制在0°C，車外溫度是28°C，滿載時單位里程油耗成本是2元。各需求點的需求量和退貨量情況見表1，各節點間距離情況見表2。

表1 各需求點的需求量和退貨量(t)

利用免疫蟻群算法通過對數學模型的計算得到最終結果為：此次配送需要3輛冷藏車。第一輛車出發時裝貨3t，返回時收貨0.5t，行駛路線為2-5-9；第二輛車出發時裝貨3t，返回時收貨0.65t，行駛路線為7-1-4-3；第三輛車出發時裝貨2.7t，返回時收貨0.8t，行駛路線為10-6-8。

5 結束語

本文針對帶有回收過程的冷鏈物流配送中涉及的主要因素進行建模分析，并通過改進的免疫蟻群混合算法結合算例對實際問題進行求解，最終結果是滿意的。但在實際配送過程中還存在交通擁堵、信號燈等待、天氣等很多不確定因素沒有考慮進去，另外若退貨量超出車輛額定載重量時又該如何決策來進行合理的安排配送以實現客戶的最大滿意等問題還需要更進一步的研究。

表2 配送中心及各需求點間距離(km)

[1]劉曉娜.我國鮮農產品冷鏈物流現狀與對策研究[J].物流工程與管理,2017,(2):93-94.

[2]李玉鵬,魏俊美,王召同,張昕.冷鏈物流“最后一公里”快速配送方法研究[J].工業技術經濟,2017,(1).

[3]白燾,李鳴,嚴良濤.蜂群算法在冷鏈物流配送車輛路徑規劃中的應用[J].湖北農業科學,2016,(22).

[4]何琴飛.考慮道路暢通狀況的冷鏈物流配送優化問題[D].大連:大連海事大學,2015.

[5]姜昌華,戴樹貴,胡幼華.求解車輛路徑問題的混合遺傳算法[J].計算機集成制造系統,2007,(10).

[6]張金鳳.帶模糊時間窗的冷鏈物流車輛路徑優化[D].武漢:武漢理工大學,2013.

[7]步燕芳.免疫蟻群算法及其應用[D].南京:南京理工大學,2009.

[8]章鏞初.冷藏車熱負荷計算[J].專用汽車,1988,(2):12-15.

[9]P Amoeim,B Almada-Lobo.The impact of food perishability issues in the vehicle routing problem[J].Computer&Industrial Engineering,2014,67:223-223.

[10]Yong-Ju Kwon,Young-Jae Choi,Dong-Ho Lee.Heterogeneous fixed fleet vehicle routing considering carbon emission[J].Transportation Research Part D,2013,23:81-89.

Route Optimization of Cold Chain Logistics Trucks Considering Recycling Process

Guo Jinming,Yang Kongyu
(School of Information Management,Beijing Information Science&Technology University,Beijing 100192,China)

In this paper,we analyzed the route optimization problem in cold chain logistics distribution process with product return and recycling considered,then in view of the probability of the secondary loading/unloading for the recycled products during customer service,we built the distribution route optimization model for the fixed cost,discount cost,loading/unloading cost,fuel cost and refrigeration cost,etc.,in the distribution process,then solved it using the modified immunity ant colony algorithm and at the end,through a numerical example,proved the ability of the model to yield satisfactory solutions.

coldchainlogistics;reverse recycling;immunity ant colony algorithm;path optimization

U16;F713.2

A

1005-152X(2017)07-0077-04

10.3969/j.issn.1005-152X.2017.07.017

2017-06-04

北京市自然科學基金項目（4132024）；北京市社會科學基金重點項目（15ZHA004）

郭金明（1991-），男，山東棗莊人，北京信息科技大學研究生，研究方向：物流系統規劃與設計；楊孔雨（1967-），男，山東巨野人，北京信息科技大學教授，研究生導師，研究方向：智能決策和優化計算的理論應用。