基于禁忌搜索算法的生鮮農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究

唐 瓊，李 翠，劉石洋

（衡陽師范學(xué)院 經(jīng)濟(jì)與管理學(xué)院， 湖南 衡陽 421001）

一、引言

生鮮農(nóng)產(chǎn)品具有易腐的特殊性，在配送過程中對時(shí)間、環(huán)境等要求苛刻，加之現(xiàn)代社會的人們越來越關(guān)注產(chǎn)品的品質(zhì)、對產(chǎn)品的新鮮程度要求越來越高，冷鏈物流配送越來越受到重視。合理安排冷鏈物流配送路徑，不僅可以降低生鮮產(chǎn)品的配送時(shí)間、節(jié)約配送里程，而且可以降低配送過程中的貨損及能耗損失，節(jié)約配送成本，增加客戶對配送服務(wù)的好感度和滿意度。

許多學(xué)者對該類問題做了一些研究，婁丹建立考慮固定成本、運(yùn)輸成本、貨損成本、懲罰成本和能源成本等五個(gè)部分之和的配送總成本最小為目標(biāo)函數(shù)的冷鏈物流車輛配送路徑優(yōu)化模型，設(shè)計(jì)了蜂群算法?？祫P等構(gòu)建考慮碳排放的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化模型，設(shè)計(jì)了蟻群算法。張璇在傳統(tǒng)生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化的基礎(chǔ)上，結(jié)合軟硬時(shí)間窗約束，考慮配送過程帶取送的雙向作業(yè)模式，建立非線性混合整數(shù)規(guī)劃模型，設(shè)計(jì)了遺傳算法。鄭義彬等構(gòu)建了考慮運(yùn)輸成本、貨損成本及懲罰成本之和最小化的優(yōu)化模型，設(shè)計(jì)了遺傳算法。任騰等構(gòu)建了運(yùn)輸成本、懲罰成本及碳成本之和最小化的優(yōu)化模型，設(shè)計(jì)了蟻群算法。

本文旨在對當(dāng)前生鮮農(nóng)產(chǎn)品冷鏈配送存在的配送路徑選擇不當(dāng)、配送時(shí)間窗得不到滿足、產(chǎn)品腐損率較高等問題的研究，提出配送優(yōu)化生鮮農(nóng)產(chǎn)品的路徑方案。

二、模型建立

(一)模型假設(shè)

某生鮮農(nóng)產(chǎn)品冷鏈物流配送中心對多個(gè)客戶進(jìn)行生鮮農(nóng)產(chǎn)品配送，且滿足以下條件：(1)每個(gè)客戶點(diǎn)需求已知，被車輛訪問一次。(2)車輛從配送中心出發(fā)，完成運(yùn)輸工作后空車返回配送中心。(3)車輛經(jīng)過任何客戶點(diǎn)時(shí)的載運(yùn)量不能大于其最大裝載容量。(4)客戶有規(guī)定的時(shí)間窗，若配送達(dá)到時(shí)間不在客戶要求的配送時(shí)間窗內(nèi)，則產(chǎn)生相應(yīng)的懲罰成本。

(二)成本分析

本文考慮的冷鏈物流配送成本主要包括運(yùn)輸成本、懲罰成本、貨損成本及碳排放成本，目標(biāo)函數(shù)是最小化配送總成本。

參數(shù)描述：N：客戶點(diǎn)的集合；N：點(diǎn)的集合，包括客戶點(diǎn)(用 i 表示)和車場(用 0 表示)；變量 x(0-1 變量)：如果車輛經(jīng)過點(diǎn)i 到點(diǎn)j，為1，否則為0。Q：車輛的最大裝載容量；M：非常大的數(shù)；G：用來避免子環(huán)的輔助變量。

冷鏈物流配送的運(yùn)輸成本與運(yùn)輸距離相關(guān)，由式(1)計(jì)算：

其中：t：車輛從點(diǎn) i 到點(diǎn) j 需要的運(yùn)輸時(shí)間；v：車輛從點(diǎn)i 到點(diǎn)j 行駛的速度。

如果車輛未在客戶i 規(guī)定的時(shí)間窗[ET,LT]范圍內(nèi)送達(dá)貨物，將產(chǎn)生懲罰成本。計(jì)算公式如下：

其中：T為到達(dá)客戶點(diǎn)i 的時(shí)間；P表示沒按客戶要求提前將貨物送到平均單位時(shí)間的懲罰成本；P表示沒按客戶要求延遲將貨物送到平均單位時(shí)間的懲罰成本。

考慮與車輛運(yùn)輸時(shí)間、車輛門開關(guān)次數(shù)有關(guān)的貨損成本，計(jì)算公式如(3)：

其中：D：客戶點(diǎn) i 的需求；P：表示單位時(shí)間運(yùn)輸造成的貨物損失；P：表示單次開門造成的貨物損失。

考慮與車輛運(yùn)輸距離、車輛運(yùn)輸速度、車輛載重相關(guān)的碳排放成本，計(jì)算公式如(4)：

其中：ω：單位碳排放成本；d：車輛從 i 點(diǎn)到 j 點(diǎn)行駛的距離；q：從 i 點(diǎn)行駛至 j 點(diǎn)的車輛載重量；ɑ、β：碳排放成本系數(shù)，m∈{0，1，2，3}。

(三)數(shù)學(xué)模型構(gòu)建

基于以上描述，構(gòu)建了生鮮農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化數(shù)學(xué)模型，如式(5)所示，目標(biāo)函數(shù)是最小化車輛運(yùn)輸成本C、懲罰成本C、貨損成本C和碳排放成本C之和。

目標(biāo)函數(shù)(4)最小化配送總成本。等式(5-7)確保車輛最多只能訪問客戶點(diǎn)一次。約束(8)是避免子環(huán)條件，確保不出現(xiàn)不經(jīng)過車場的回路。約束(9)確保車輛上的負(fù)荷不能大于車輛的最大裝載容量。等式(10)表示車輛到達(dá)客戶點(diǎn)的時(shí)間關(guān)系等式。約束(11)確保輔助變量為非負(fù)整數(shù)。約束(12)定義變量x為二元變量。

三、算法設(shè)計(jì)

本文使用禁忌搜索求解上述數(shù)學(xué)模型，具體的流程如Algorithm1。本文采用實(shí)數(shù)編碼，使用交換、插入、2-opt 三種領(lǐng)域算子，每種算子使用獨(dú)立的禁忌列表(TABU、TABU、TABU)，禁忌長度分別為 l1、l2 和 l3。在該TS 過程中，設(shè)s表示初始解，s 表示當(dāng)前解，s表示當(dāng)前可搜索到的最優(yōu)解，TABU、TABU和 TABU表示三個(gè)禁忌列表，N(s)表示由當(dāng)前解s 生成的鄰域解的集合，TC(s)表示當(dāng)前解s 的總懲罰成本，TC(s)表示到目前為止的最小總懲罰成本，ConsIter 表示當(dāng)前最優(yōu)解沒有改進(jìn)的連續(xù)迭代次數(shù)，MaxConsIter 表示當(dāng)前最優(yōu)解沒有改進(jìn)的最大連續(xù)迭代次數(shù)。

四、算例分析

本節(jié)采用Matlab2014a 對算法進(jìn)行編碼并求解。采用文[5]中算例驗(yàn)證提出的模型與算法的科學(xué)性和有效性。采取1-34 號的數(shù)據(jù)，包括點(diǎn)坐標(biāo)、需求量及客戶服務(wù)時(shí)間窗信息，其中配送中心為編號1，2-34 為客戶點(diǎn)。本文問題參數(shù)中設(shè)置如下：Q=15；P=3；P=2；P=10；P=10；ω=1；ɑ=1.576；ɑ=17.6；ɑ=0.00117；ɑ=36.067；ɑ=10；β=1。

本文設(shè)計(jì)的禁忌搜索算法中的參數(shù)設(shè)置如下：l=l=l=20；ConsIter=500，MaxConsIter=100。

圖1 最優(yōu)配送路徑

圖2 總成本收斂情況

利用禁忌搜索算法進(jìn)行計(jì)算，對應(yīng)的最優(yōu)配送路線如圖1 所示，總成本為40403.71，算法求解時(shí)間為1.6s。圖2 為總成本收斂迭代曲線，從圖2 可以看出，迭代超過50 次后，曲線基于平穩(wěn)，逐漸收斂域最優(yōu)值。

通過算例分析，可以看出本文設(shè)計(jì)的禁忌搜索算法可以快速地規(guī)劃最優(yōu)路線，同時(shí)算法也可以快速收斂到最優(yōu)解。

五、結(jié)語

本文對生鮮農(nóng)產(chǎn)品冷鏈物流配送各部分成本進(jìn)行分析，以運(yùn)輸成本、懲罰成本、貨損成本及碳排放成本最小為目標(biāo)建立了生鮮冷鏈物流配送路徑優(yōu)化模型，并設(shè)計(jì)了禁忌搜索算法對模型求解，通過算例分析驗(yàn)證了模型與算法的科學(xué)性，可以為冷鏈配送路徑優(yōu)化問題決策提供理論依據(jù)。