帶回收過程的冷鏈物流車輛路徑優(yōu)化

郭金明，楊孔雨

（北京信息科技大學(xué) 信息管理學(xué)院，北京 100192）

帶回收過程的冷鏈物流車輛路徑優(yōu)化

郭金明，楊孔雨

（北京信息科技大學(xué) 信息管理學(xué)院，北京 100192）

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

冷鏈物流；逆向回收；免疫蟻群算法；路徑優(yōu)化

1 引言

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

2 問題模型建立與分析

2.1 問題描述

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

2.2 模型建立

2.2.1 目標(biāo)函數(shù)

（1）固定成本。購（租）車輛成本、人員基本工資、維修費(fèi)用等構(gòu)成的車輛固定成本（折舊成本另計(jì)）。由此M輛車的固定成本Cm:

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

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

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

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

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

δ表示質(zhì)量成本系數(shù)；Gq表示第q件貨物的質(zhì)量；Ymiqj表示第m輛車在完成服務(wù)點(diǎn)i時(shí)車上已經(jīng)回收到的第q件貨物在j服務(wù)點(diǎn)是否需要額外裝卸，若需要額外裝卸則Ymiqj=1，否則Ymiqj=0。

（5）制冷成本。貨物從裝上冷藏車的那一刻起，車廂就處于溫控狀態(tài)。車輛在運(yùn)輸途中外部熱源會(huì)傳入熱負(fù)荷到車廂內(nèi)對(duì)制冷劑造成消耗。另外，在裝卸貨物過程中，車廂門開啟也會(huì)造成大量熱負(fù)荷傳入，造成制冷劑的消耗。車廂門開啟的程度越大，熱負(fù)荷傳入越多，進(jìn)而制冷劑的消耗也會(huì)越大，因此車門開啟程度與制冷成本是正相關(guān)的?？紤]這兩個(gè)方面的制冷劑消耗，制冷成本表示為：

①運(yùn)輸過程中由車廂壁熱傳導(dǎo)產(chǎn)生的制冷成本CQ1：

②在服務(wù)j點(diǎn)客戶的裝卸過程中產(chǎn)生的制冷成本CQ2：

Qb表示單位時(shí)間車廂門敞開面積下傳遞的熱負(fù)荷量；ρ*表示空氣介質(zhì)下的熱傳導(dǎo)系數(shù)；S*表示車廂門面積；φm表示第m輛車的車廂門敞開系數(shù)；ΔT表示車廂內(nèi)外溫度差；tb表示車廂門敞開時(shí)間；Zjm表示第m輛車是否服務(wù)j點(diǎn)客戶，若服務(wù)則Zjm=1，否則Zjm=0。

2.2.2 目標(biāo)優(yōu)化和條件約束。以運(yùn)輸過程中最小成本為目標(biāo)函數(shù)建立數(shù)學(xué)模型如下：

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

3 改進(jìn)型免疫蟻群融合算法

3.1 免疫蟻群算法基本思想

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

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

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

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

（2）由蟻群算法產(chǎn)生初始螞蟻群A。

（3）更新局部信息素的值。當(dāng)一只螞蟻?zhàn)咄旰笥霉剑?）更新局部信息素的值。

（4）更新全局信息素的值。當(dāng)所有螞蟻?zhàn)咄晁x路徑后，對(duì)每條路徑用公式（7）來更新信息素的值，其中pg是全局信息素的揮發(fā)系數(shù)，0≤pg≤1。

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

（6）對(duì)B中的螞蟻進(jìn)行接種疫苗生成螞蟻（抗體）群C。

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

（8）判斷是否滿足終止條件。如果滿足則停止迭代，輸出最優(yōu)解；否則跳轉(zhuǎn)第（9）。

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

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

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

4 實(shí)驗(yàn)算例

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[6]張金鳳.帶模糊時(shí)間窗的冷鏈物流車輛路徑優(yōu)化[D].武漢:武漢理工大學(xué),2013.

[7]步燕芳.免疫蟻群算法及其應(yīng)用[D].南京:南京理工大學(xué),2009.

[8]章鏞初.冷藏車熱負(fù)荷計(jì)算[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

北京市自然科學(xué)基金項(xiàng)目（4132024）；北京市社會(huì)科學(xué)基金重點(diǎn)項(xiàng)目（15ZHA004）

郭金明（1991-），男，山東棗莊人，北京信息科技大學(xué)研究生，研究方向：物流系統(tǒng)規(guī)劃與設(shè)計(jì)；楊孔雨（1967-），男，山東巨野人，北京信息科技大學(xué)教授，研究生導(dǎo)師，研究方向：智能決策和優(yōu)化計(jì)算的理論應(yīng)用。