侯 玲，張治國，徐英展

（1.四川大學(xué)錦城學(xué)院，四川 成都 611731；2.成都信息工程大學(xué) 物流學(xué)院，四川 成都 610103）

1 引言

隨著經(jīng)濟(jì)發(fā)展和生活水平的逐漸提高，人們對生鮮產(chǎn)品的需求逐年增加，冷鏈配送得到高速發(fā)展。冷鏈物流需要在整個供應(yīng)鏈環(huán)節(jié)對溫度進(jìn)行控制，以保證配送產(chǎn)品的質(zhì)量，因此冷鏈配送有較強(qiáng)的時效性和質(zhì)量要求。如何在降低物流成本的情況下優(yōu)化配送車輛路徑，實(shí)現(xiàn)快速準(zhǔn)時配送，受到廣泛關(guān)注。

Dantzig和Ramser[1]在1959年率先提出了車輛路徑問題的數(shù)學(xué)模型，并對模型進(jìn)行求解分析；Pedro Amorim[2]等研究了葡萄牙產(chǎn)品配送車輛路徑優(yōu)化問題，但沒有涉及貨物在運(yùn)輸中的損耗問題。我國對生鮮物流配送車輛路徑的研究要滯后于國外，但仍然有很多學(xué)者取得了相應(yīng)的成果：如李雅萍[3]研究了鮮活農(nóng)產(chǎn)品的冷鏈物流車輛路徑問題，將固定成本、運(yùn)輸成本和時間窗約束進(jìn)行整合處理；潘璠，等[4]將物流及時性和客戶配送與客戶服務(wù)公平性考慮到生鮮產(chǎn)品配送車輛路徑問題中，但是并沒有引入時間窗等針對生鮮特殊屬性的約束要求；葛顯龍，等[5]提出帶有時間窗的生鮮物流配送車輛路徑問題，并設(shè)計自適應(yīng)遺傳算法求解了該模型。

通過以上分析總結(jié)可以看到，國內(nèi)外學(xué)者們對VRP問題進(jìn)行了許多探討，由于生鮮產(chǎn)品的特有屬性，其配送問題涉及到運(yùn)輸方案、模型目標(biāo)等不同，因此在建模和求解算法上存在很大區(qū)別，已有文獻(xiàn)多是沿用傳統(tǒng)VRP問題的研究方法，沒有充分考慮生鮮物流配送的損耗、客戶的時間窗要求和需求動態(tài)性。

本文對冷鏈配送進(jìn)行分析，充分考慮配送成本最小化和客戶滿意度最大化，在配送路徑優(yōu)化模型基礎(chǔ)上為每個客戶設(shè)置時間窗，在模型中加入時間窗約束，規(guī)定配送車輛必須在時間窗范圍內(nèi)到達(dá)客戶位置并對其進(jìn)行服務(wù)，若超過時間窗規(guī)定則會舍棄掉該規(guī)劃方案；同時引用冷鏈產(chǎn)品腐蝕模型來評價配送產(chǎn)品的新鮮程度，在提高客戶滿意度的同時，優(yōu)化后的路徑使配送成本最小。在模型求解過程中，設(shè)計自適應(yīng)遺傳算法，通過MATLAB編程運(yùn)算，得到全局最優(yōu)解，并通過算例進(jìn)行驗證。

2 問題描述

本文所描述的冷鏈配送車輛路徑優(yōu)化問題是指一個配送中心有若干冷藏車，已知多個冷鏈配送需求點(diǎn)，且冷藏車能滿足多個配送點(diǎn)的需求。冷藏車從配送中心出發(fā)，按照規(guī)劃的配送順序，將貨品依次送至客戶手中。其中，配送的貨物為冷鏈生鮮產(chǎn)品，配送中心與各需求點(diǎn)以及各需求點(diǎn)之間的距離已知，配送中心的貨物容量能滿足所有需求點(diǎn)的貨量需求，冷藏車的容量、運(yùn)輸費(fèi)率、冷藏費(fèi)率已知，生鮮產(chǎn)品的損耗系數(shù)已知，各冷藏車的載貨量及費(fèi)用相同，客戶的需求量、要求運(yùn)達(dá)時間窗已知。在上述條件已知的情況下，科學(xué)合理的對配送車輛進(jìn)行路徑優(yōu)化，合理規(guī)劃派送順序，在產(chǎn)品配送滿足所有客戶時間窗要求的前提下，使配送總成本達(dá)到最小。

3 模型建立

3.1 建模思路

本文以配送總成本最小為前提，在總成本的計算中加入產(chǎn)品腐敗成本和時間窗限制。不同客戶有不同的時間窗要求，當(dāng)一種配送方案的配送到達(dá)時間無法滿足所有客戶的時間窗要求時，將這種配送方案舍去。在客戶滿意度達(dá)到最大的情況下，得到最優(yōu)的配送方案。

該冷鏈配送車輛路徑優(yōu)化模型主要考慮以下幾點(diǎn)：

（1）冷鏈產(chǎn)品因其易腐特性，無法長時間保鮮，因產(chǎn)品腐敗產(chǎn)生的費(fèi)用是配送總成本的重要組成。本模型加入貨損成本，更具現(xiàn)實(shí)意義。

（2）由于冷鏈產(chǎn)品易變質(zhì)的特性，客戶對配送時間都會有較嚴(yán)格的要求，而且貨品配送至客戶位置后，一般都會進(jìn)行二次加工，不能在規(guī)定時間內(nèi)將貨物配送至客戶手中就會大大降低客戶滿意度。本文路徑優(yōu)化模型加入客戶時間窗要求，滿足不同客戶的時間要求，提升了客戶滿意度。

（3）模型以總成本最小化為目標(biāo)函數(shù)，其中總成本包括車輛的派遣成本、運(yùn)輸成本、制冷成本以及冷鏈產(chǎn)品的變質(zhì)損耗成本。在合理前提以及約束限制下，通過合理規(guī)劃車輛配送順序，使得在配送總成本最小的同時滿足所有客戶的時間窗要求。

（4）合理使用車輛資源。盡量以較少的冷藏車輛滿足所有客戶需求，減少車輛派遣費(fèi)用，同時要求一輛冷藏車服務(wù)的客戶不能過多，防止車輛超載和因服務(wù)時間過長而造成超時配送。

（5）減少單個客戶的被服務(wù)次數(shù)。指一個客戶僅由一輛冷藏車進(jìn)行配送，避免客戶的貨品需求被分割，減少客戶操作次數(shù)的同時降低配送環(huán)節(jié)總成本。

3.2 模型的一般假設(shè)

在冷鏈配送環(huán)節(jié)中存在很多不可避免的復(fù)雜因素，如道路狀況、車輛狀況、天氣等復(fù)雜因素，這些因素?zé)o法避免并會導(dǎo)致計算結(jié)果存在一些細(xì)微誤差，但不影響優(yōu)化合理性。因此，本文進(jìn)行以下合理假設(shè)：

（1）假設(shè)配送道路均為暢通，冷藏車在配送中視為勻速運(yùn)動；

（2）冷藏車的載重量可以滿足若干個需求點(diǎn)的需求量；

（3）冷藏車載重量等參數(shù)均相同且狀況良好；

（4）客戶的需求量、位置、時間要求等參數(shù)已知；

（5）配送中心的容量可以滿足所有需求；

（6）所運(yùn)載貨品為單一類型的貨品；

（7）在配送過程中，冷藏車車廂內(nèi)外的溫度保持恒定不變。

3.3 模型的約束條件

本文配送路徑優(yōu)化模型必須在滿足一定約束條件下進(jìn)行，在約束條件的限制下求得總成本最低方案。根據(jù)冷鏈配送的實(shí)際情況，針對模型的基本條件，提出約束條件如下：

（1）冷藏車配送路徑起點(diǎn)和終點(diǎn)均為冷藏庫；

（2）規(guī)劃方案要滿足所有需求點(diǎn)的需求量；

（3）冷藏車的裝載量必須小于冷藏車的額定裝載量；

（4）一輛冷藏車可以負(fù)責(zé)多個配送點(diǎn)的配送任務(wù)；

（5）每個配送點(diǎn)只能由一輛冷藏車一次性完成配送；

（6）車輛必須在需求點(diǎn)的時間窗內(nèi)送達(dá)。

3.4 模型的參數(shù)設(shè)置

O表示冷鏈配送中心；

M={i=1,2,...,M0}表示配送需求點(diǎn)即客戶的集合；

N={n=1,2,…,N0}表示冷藏車的集合；

P表示冷藏車的最大容量；

Fn表示第n臺冷藏車的派遣成本，Cp為總派遣成本；

c0為冷藏車每公里運(yùn)輸成本，C0為冷藏車總運(yùn)輸成本；

α為制冷劑單價,β為單位時間制冷劑消耗量，Cf表示配送過程總制冷成本；

price為配送貨品單價，η為冷鏈配送中貨品的

U=O?M表示所有節(jié)點(diǎn)的集合，包括冷鏈配送中心和需求點(diǎn)；

Qi表示第i個客戶的冷藏品配送量；損耗系數(shù)；

dij表示從需求點(diǎn)i到需求點(diǎn)j的路程長度；

tij表示從需求點(diǎn)i到需求點(diǎn)j的運(yùn)輸時長，其中i,j∈U；

ti1表示客戶的時間窗上限，ti2表示客戶的時間窗下限，其中i∈U；

V為冷藏車行駛的平均速度；

Ctotal表示冷鏈物流配送總成本。

決策變量：

Xijn表示第n(n ∈N )輛冷藏車是否從需求點(diǎn)i到需求點(diǎn)j(i ,j∈M )間進(jìn)行派送，值為1時表示是，值為0時表示否；

Yin表示第i(i∈M)個需求點(diǎn)是否由第n輛冷藏車進(jìn)行派送，值為1時表示是，值為0時表示否；

3.5 冷鏈產(chǎn)品物流配送成本分析

（1）車輛派遣費(fèi)用。車輛派遣費(fèi)用主要包括車輛保養(yǎng)、維護(hù)以及人力資本費(fèi)用等，包含哪些費(fèi)用及如何計算費(fèi)用視具體情況而定，為方便計算，不進(jìn)行展開細(xì)化，車輛派遣成本可以表示為：

（2）運(yùn)輸成本。運(yùn)輸成本指在配送環(huán)節(jié)中，因車輛行駛而產(chǎn)生的費(fèi)用，一般指油耗費(fèi)用?？傔\(yùn)輸成本C0可表示為：

（3）制冷成本。冷鏈配送環(huán)節(jié)中，冷藏車通過一些措施來控制車內(nèi)溫度，使貨品一直保存在低溫環(huán)境中。在配送過程中，一直會有制冷費(fèi)用的產(chǎn)生，制冷費(fèi)用與運(yùn)輸時間有關(guān)，本文用β表示制冷劑單位時間的消耗量，冷鏈配送運(yùn)輸過程中制冷成本費(fèi)用可表示為：

（4）冷鏈產(chǎn)品損耗成本。由于冷鏈產(chǎn)品的易腐敗特性，在低溫配送過程中，雖然處于相對低溫的狀態(tài)，但仍然存在腐蝕變質(zhì)過程。本文在冷鏈產(chǎn)品配送環(huán)節(jié)成本中增加了因冷鏈產(chǎn)品腐敗而帶來的腐敗損耗成本。

因本文討論的冷鏈產(chǎn)品配送一般為市內(nèi)配送，配送時間相對較短，并且冷藏車車廂內(nèi)部處于相對低溫環(huán)境，冷鏈產(chǎn)品的腐敗速率大大減小，運(yùn)用簡單的常速連續(xù)型質(zhì)變曲線來描述冷鏈產(chǎn)品配送過程中的品質(zhì)變化情況，如圖1所示。

圖1 常速質(zhì)變連續(xù)型質(zhì)變曲線

運(yùn)輸過程中貨品的損耗系數(shù)為η，冷鏈產(chǎn)品單價為price，則運(yùn)輸過程中冷鏈產(chǎn)品的損耗成本Cs可以表示為：

因冷鏈產(chǎn)品品類眾多，大多數(shù)包裝良好，如紅酒、牛奶等生鮮產(chǎn)品，在配送環(huán)節(jié)中基本不會發(fā)生腐敗情況，所以損耗成本計算要根據(jù)實(shí)際情況而定。

3.6 模型建立

模型中各表達(dá)式含義如下：

目標(biāo)函數(shù)（5）為冷鏈配送的總成本，包括車輛派遣成本、運(yùn)輸成本、制冷成本與貨品損耗成本，模型以總成本最小化為決策目標(biāo)；式（6）限制冷藏車不能超載；式（7）表示出發(fā)冷藏車總數(shù)不得大于最大車輛數(shù)N0；式（8）表示配送起點(diǎn)和終點(diǎn)均為配送中心；式（9）表示一個需求點(diǎn)只能由一輛冷藏車完成配送；式（10）為流量守恒限制，即到達(dá)需求點(diǎn)的車輛必須離開需求點(diǎn)；式（11）為各需求點(diǎn)間行駛時間的計算公式；式（12）表示冷藏車需要在規(guī)定時間內(nèi)到達(dá)客戶位置；式（13）、式（14）為決策變量。

4 基于遺傳算法的模型求解

由于問題的復(fù)雜性，本文采用遺傳算法求解，具體算法流程如圖2所示。

4.1 染色體編碼

進(jìn)行染色體編碼時，需要將所有車輛的線路選擇情況轉(zhuǎn)化為遺傳算法的染色體集合，每條染色體代表著不同的車輛路徑選擇方案，通過對每條染色體的適應(yīng)度評價和遺傳操作，篩選出較優(yōu)的線路方案。

本文采用實(shí)數(shù)編碼的方法，以需求點(diǎn)的個數(shù)即客戶數(shù)量M0作為基因長度，第M個基因位即代表第M個需求點(diǎn)。用車輛數(shù)量N0作為基因位的基因值，即1到N0的隨機(jī)整數(shù)，代表每個需求點(diǎn)被分配到的配送車輛。如染色體4242113表示第5、6個需求點(diǎn)由車輛1配送，第2、4個需求點(diǎn)由車輛2進(jìn)行配送，第7個需求點(diǎn)由車輛3進(jìn)行配送，第1、3個需求點(diǎn)由車輛4進(jìn)行配送。

這種編碼方式只體現(xiàn)了冷藏車需要對哪幾個配送需求點(diǎn)進(jìn)行配送，而沒有將具體的配送順序體現(xiàn)出來，所以在后續(xù)的適應(yīng)度計算中，會將不同車輛的需求點(diǎn)按時間窗排序，以時間窗排序的結(jié)果進(jìn)行適應(yīng)度計算。

圖2 遺傳算法流程圖

4.2 種群初始化

種群初始化是遺傳操作的開始，初始種群由一定規(guī)模的不同個體組成，通過適應(yīng)度的計算、選擇、交叉、變異等操作生成子代群體，之后不斷進(jìn)行迭代計算，直到達(dá)到模型算法的終止條件。所以，初始種群的個體數(shù)量影響著后續(xù)遺傳操作過程，由于模型程序的特殊性，當(dāng)初始種群過小時，可能出現(xiàn)種群中無可適應(yīng)環(huán)境的個體的情況，無法進(jìn)行后續(xù)的遺傳操作；當(dāng)初始種群過大時，則會導(dǎo)致運(yùn)算時間過長，降低計算效率。

本文討論的冷鏈產(chǎn)品配送，一般為市內(nèi)短途配送，所涉及需求點(diǎn)較少，不需要很大的初始種群規(guī)模，因此，初始群體中的染色體數(shù)定為100個，運(yùn)用MATLAB程序生成100行、M0列的矩陣，使用實(shí)數(shù)編碼生成初始種群。

4.3 適應(yīng)度函數(shù)處理

適應(yīng)度用來表示每條染色體的生存概率，用適應(yīng)度函數(shù)求出每一代種群中所有染色體的生存概率，從而根據(jù)每條染色體的生存概率進(jìn)行比較和篩選。由于本文的目標(biāo)函數(shù)為配送總成本最小，因此，在目標(biāo)函數(shù)的處理上以總成本的倒數(shù)作為適應(yīng)度函數(shù)，即f=1/Ctotal。如果染色體所對應(yīng)的配送方案違反了模型的約束條件，則將該方案的配送成本Ctotal設(shè)為inf，即無限大，使得該染色體的適應(yīng)度f=0。

4.4 遺傳操作

（1）選擇算子。選擇操作的目的是選擇較好的個體進(jìn)入下一代，淘汰掉適應(yīng)度差的個體。選擇操作以適應(yīng)度的大小為依據(jù)判斷個體是否能進(jìn)入下一代，即種群基因的優(yōu)勝劣汰。本文選擇輪盤賭策略和最大保留策略相結(jié)合的方法來選擇算子。輪盤賭策略是通過個體適應(yīng)度占群體總適應(yīng)度的比例計算出來，通過個體適應(yīng)度的占比來選擇個體，但是當(dāng)種群數(shù)量過大時，往往不能選擇合適的算子，即相當(dāng)于隨機(jī)選擇個體，所以結(jié)合最大保留策略，即將群體中適應(yīng)度最高的個體保存到下一代，并且保留的個體不進(jìn)行交叉變異操作，以確保目前較好的染色體會保留到子代，提高算法的有效性，促進(jìn)算法收斂。

（2）交叉操作。交叉操作是生成新染色的主要途徑，通過將兩條染色體的部分基因互換來生成新的染色體，參加交叉的染色體由交叉概率來確定，本文采取單點(diǎn)交叉的方法隨機(jī)選擇一個位置作為交叉點(diǎn)進(jìn)行配對交叉，如圖3所示。

圖3 交叉操作示意圖

（3）變異操作。為了擴(kuò)大遺傳算法的搜索空間，對部分染色體進(jìn)行變異操作，通過改變某個染色體的部分基因來生成新的染色體，進(jìn)行變異操作的個體通過變異概率進(jìn)行選擇。本文采用產(chǎn)生隨機(jī)數(shù)的方法進(jìn)行變異，即隨機(jī)選擇一個基因位進(jìn)行變異，如圖4所示。

4.5 終止條件

當(dāng)整個基因流程操作循環(huán)次數(shù)達(dá)到迭代次數(shù)上限時，即可得到最優(yōu)染色體，從而得出最優(yōu)的行車線路方案。

圖4 變異操作示意圖

5 算例分析

5.1 算例數(shù)據(jù)

以某牛奶公司部分配送訂單為例，該公司對市內(nèi)12個配送點(diǎn)進(jìn)行配送，配送出發(fā)點(diǎn)和終點(diǎn)為0，配送需求點(diǎn)為12家超市，配送中心與12個配送點(diǎn)的間距見表1。

表1 配送中心及配送點(diǎn)間距表（單位：km）

每天運(yùn)載奶制品的冷藏車從配送中心出發(fā)的時間為上午8:00，出發(fā)后，依次到達(dá)各個配送需求點(diǎn)位置進(jìn)行配送。每個客戶的時間窗和需求量各不相同，為方便程序計算，將客戶要求到貨時間轉(zhuǎn)換為發(fā)車時間的差值的時間窗，當(dāng)天客戶的時間窗和需求量見表2。

公司的冷藏車采用耗油制冷，通過計算即可得出單位時間內(nèi)的制冷成本αβ=7元/h。冷藏車每公里的運(yùn)輸成本c0=0.75元/km。以客戶數(shù)目換算人力資源使用費(fèi)用為車輛派遣成本，車輛派遣成本為Cp=60元。冷藏車在市區(qū)中的行駛速度V=40km/h，因運(yùn)輸產(chǎn)品為包裝較好的牛奶，所以在計算成本的過程中不計算貨品的損耗成本，所以η=0。

每輛冷藏車能裝載100件牛奶，客戶的需求量訂單也以件數(shù)為單位，故以牛奶的件數(shù)為冷藏車裝載量和客戶需求量單位，車輛載重P=100。

表2 配送點(diǎn)的需求量與時間窗

5.2 參數(shù)設(shè)定

需求點(diǎn)數(shù)量M0=12；配送站點(diǎn)閑置冷藏車數(shù)N0=5；冷藏車的額定載重量P=100；冷藏車每公里的運(yùn)輸成本c0=0.75；冷藏車單位時間的制冷成本αβ=7；貨品的損耗系數(shù)η=0；冷藏車行駛的平均速度V=40；遺傳算法交叉概率jc=0.9；遺傳算法變異概率by=0.1；遺傳算法每代個體數(shù)gan=100；遺傳算法迭代次數(shù)gn=100。

5.3MATLAB求解

本文運(yùn)用MATLAB2013a進(jìn)行編程求解冷鏈產(chǎn)品配送路徑優(yōu)化問題，設(shè)定好參數(shù)后在MATLAB2013a中導(dǎo)入程序代碼，即可得出最佳路線方案。

冷藏車1：配送中心→配送點(diǎn)1→配送點(diǎn)3→配送點(diǎn)7→配送點(diǎn)9→配送中心；

冷藏車2：配送中心→配送點(diǎn)8→配送點(diǎn)11→配送中心；

冷藏車3：未發(fā)車；

冷藏車4：配送中心→配送點(diǎn)12→配送點(diǎn)4→配送點(diǎn)5→配送點(diǎn)2→配送點(diǎn)6→配送點(diǎn)10→配送中心；

冷藏車5：未發(fā)車。

具體各配送點(diǎn)到達(dá)時間見表3。

冷藏車返回配送站點(diǎn)的時間也做了記錄，記錄情況如下：

冷藏車1：發(fā)車時間8:00，返回配送站點(diǎn)時間10:04，耗時124min；

表3 配送點(diǎn)到達(dá)時間

冷藏車2：發(fā)車時間8:00，返回配送站點(diǎn)時間9:08，耗時68min；

冷藏車3：未發(fā)車；

冷藏車4：發(fā)車時間8:00，返回配送站點(diǎn)時間10:19，耗時139min；

冷藏車5：未發(fā)車。

5.4 優(yōu)化結(jié)果分析

本文運(yùn)用數(shù)學(xué)模型和遺傳算法，通過MATLAB編程進(jìn)行求解運(yùn)算，并以某牛奶公司的部分配送數(shù)據(jù)為例，規(guī)劃了一套新的冷鏈配送車輛路徑規(guī)劃方案，可以從以下兩個方面檢驗方案的可行性：

（1）配送路徑的合理性。被選中的3輛冷藏車從配送中心出發(fā)，按照各自的配送順序依次對客戶完成配送服務(wù)，完成所有配送服務(wù)后返回配送中心。

（2）配送的時間窗約束。本文的配送模型加入了時間窗的約束條件，目的是讓所有冷藏車都能在客戶規(guī)定的時間內(nèi)到達(dá)客戶位置，若算例的優(yōu)化結(jié)果發(fā)生了提前配送或者超時配送的情況，則說明模型算法不合理。由表3可知，冷藏車到達(dá)客戶位置對客戶進(jìn)行服務(wù)的時間均在客戶的時間窗要求內(nèi)，3條配送線路均沒有出現(xiàn)提前配送或者超時配送的情況，滿足了所有客戶的時間窗要求，對客戶滿意度有很大的提升。

綜上所述，通過本文的模型與算法得出的配送車輛路徑規(guī)劃方案科學(xué)合理，路徑無交叉、重復(fù)的現(xiàn)象，同時，得出的車輛路徑規(guī)劃方案滿足了所有客戶的時間窗，有效提升了客戶滿意度。

6 結(jié)語

本文綜合考慮了冷鏈物流的易腐敗特點(diǎn)、客戶的時間窗要求等，以總成本最低為數(shù)學(xué)模型的決策目標(biāo)，提出產(chǎn)品冷鏈物流配送路徑優(yōu)化的數(shù)學(xué)模型，然后合理使用并改進(jìn)遺傳算法，使用MATLAB數(shù)學(xué)軟件進(jìn)行編程求解，合理規(guī)劃冷鏈配送車輛的行駛路徑。最后以某牛奶公司的配送情況為算例，優(yōu)化配送路線，使配送車輛都能在規(guī)定時間窗內(nèi)對客戶進(jìn)行服務(wù)，提升了客戶滿意度，真實(shí)反映最小化配送總成本的同時達(dá)到全局優(yōu)化。

本文設(shè)計的數(shù)學(xué)模型與算法編程仍有一定的局限性。如當(dāng)訂單過多、約束條件過多時，可能出現(xiàn)無法進(jìn)行遺傳操作的情況，所以當(dāng)出現(xiàn)訂單過多的情況時，要結(jié)合實(shí)際情況，對遺傳算法的部分參數(shù)進(jìn)行修改，如種群數(shù)量、迭代次數(shù)以及交叉變異的概率，從而使模型算法更加高效地運(yùn)行。