基于客戶滿意度的生鮮農(nóng)產(chǎn)品末端配送的VRP研究

杜志平 胡永彪 陳永立

摘 要：綜合考慮客戶滿意度、末端大規(guī)?？蛻酎c(diǎn)、時間窗限制和生鮮農(nóng)產(chǎn)品的特點(diǎn)等影響因素，建立以末端物流總配送成本最小為目標(biāo)的生鮮農(nóng)產(chǎn)品末端配送VRP模型。采用改進(jìn)的混合遺傳算法對模型進(jìn)行求解，并通過實(shí)例分析，驗(yàn)證模型的合理性和算法的可行性。結(jié)果表明：當(dāng)客戶滿意度在80%～95%時，客戶的滿意度越高，配送成本目標(biāo)函數(shù)值越大，但配送成本增加的幅度不高。當(dāng)客戶滿意度突破95%時，配送成本的目標(biāo)函數(shù)值會陡然上升。研究提供了新的視角探討基于客戶滿意度的生鮮農(nóng)產(chǎn)品末端配送問題。

關(guān) 鍵 詞：生鮮農(nóng)產(chǎn)品;末端配送路徑;混合遺傳算法

中圖分類號：F326 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-7934（2020）01-0113-16

隨著社會經(jīng)濟(jì)發(fā)展和工作節(jié)奏的加快，人們越來越注重身體的健康，對生鮮農(nóng)產(chǎn)品的需求越來越大。在居民生活質(zhì)量不斷提升和農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化調(diào)整的背景下，我國生鮮農(nóng)產(chǎn)品的生產(chǎn)量和流通量呈逐年增加的趨勢。目前，我國蔬菜生產(chǎn)總量約占全球的60%，水產(chǎn)品和肉類的生產(chǎn)總量分別占40%和30%，是名副其實(shí)的生鮮農(nóng)產(chǎn)品供應(yīng)大國。近年來，我國每年有大約4億噸的生鮮農(nóng)產(chǎn)品通過冷鏈物流進(jìn)入流通領(lǐng)域，2018年我國肉類、水產(chǎn)品和果蔬類農(nóng)產(chǎn)品冷鏈運(yùn)輸率分別為57%、69%和35%，腐損率為8%、10%和15%，冷鏈流通比率分別為15%、23%和5%，生鮮農(nóng)產(chǎn)品物流比例呈上升趨勢。

生鮮農(nóng)產(chǎn)品是一類特殊的易腐產(chǎn)品，具有季節(jié)性、區(qū)域性、時效性、易腐性、生命周期短等特征，導(dǎo)致其加工、儲存、配送和運(yùn)輸過程中損耗率較高;我國每年消費(fèi)的易腐食品將近10億噸，其中需要冷鏈運(yùn)輸?shù)倪_(dá)到一半左右，但我國生鮮農(nóng)產(chǎn)品冷鏈運(yùn)輸率只有10%左右，每年蔬菜腐爛達(dá)到1.3億噸，果品類達(dá)到1200萬噸。我國生鮮農(nóng)產(chǎn)品在運(yùn)輸環(huán)節(jié)中的損耗率為25%～30%，而發(fā)達(dá)國家的生鮮農(nóng)產(chǎn)品損耗率控制在5%。生鮮農(nóng)產(chǎn)品末端配送具有客戶位置分散、訂單多、批量小、配送品種繁多、配送道路網(wǎng)絡(luò)復(fù)雜等一般特點(diǎn)，同時生鮮農(nóng)產(chǎn)品具有一定的時效性，隨著時間的推動，生鮮農(nóng)產(chǎn)品的鮮活度在逐漸下降。因此，如何快速、及時地以較低的配送成本將貨物配送到客戶的手中，是物流中的一個重要問題，也是物流末端配送路徑優(yōu)化的問題。提前規(guī)劃好末端的配送路線，不僅可以降低企業(yè)的配送成本，而且可以提高末端配送的服務(wù)水準(zhǔn)，提高客戶的滿意度。

一、文獻(xiàn)綜述

國外發(fā)達(dá)國家對農(nóng)產(chǎn)品物流的研究比較早。隨著我國綜合國力的提高和人民生活水平的改善，對生鮮農(nóng)產(chǎn)品物流的研究也越來越深入，對適合我國國情的生鮮農(nóng)產(chǎn)品物流配送模式進(jìn)行了有益探索。Ana Osvald與Lidija Zadnik Stirn[1]研究了生鮮蔬菜車輛配送路徑優(yōu)化的問題，考慮了新鮮蔬菜保質(zhì)期短、易腐性的特點(diǎn)、客戶時間窗的約束以及車輛載重等約束條件，建立模型，分析各因素對總成本的影響，最后進(jìn)行實(shí)例分析，驗(yàn)算出新鮮蔬菜的腐壞有很大的減少。Zhang等[2]討論了多種不同特性的產(chǎn)品共同配送的情況，配送成本包括基于不同冷凍食品特性的運(yùn)輸成本、制冷成本、懲罰成本和貨損成本，并且除了通常的時間窗和裝載量的限制，還考慮到與不同冷凍食品單位體積相關(guān)的裝載體積的限制，最后通過遺傳算法對模型進(jìn)行求解。Gong J等[3]運(yùn)用三位數(shù)字仿真技術(shù)在數(shù)值方面分析了冷藏庫的流場對生鮮農(nóng)產(chǎn)品的影響。結(jié)果發(fā)現(xiàn)，冷藏倉庫流場的均勻程度和冷藏效果成正相關(guān)。提出在冷藏倉庫中使流場更加均勻的建議。Song等[4]研究了包含多種易腐食品的冷藏和一般車型的車輛路徑問題，通過兩種車型相比較，確認(rèn)了配送易腐食品的冷藏車型的性能和有效性。李昌兵[5]等通過構(gòu)建以客戶滿意度最大、配送費(fèi)最小為目標(biāo)的物聯(lián)網(wǎng)環(huán)境下多目標(biāo)路徑優(yōu)化模型，提出了物聯(lián)網(wǎng)環(huán)境下的生鮮農(nóng)產(chǎn)品的配送模式。李曉[6]對生鮮農(nóng)產(chǎn)品電商配送中的問題及生鮮農(nóng)產(chǎn)品電商配送大數(shù)據(jù)應(yīng)用所面臨的挑戰(zhàn)進(jìn)行分析，提出了基于大數(shù)據(jù)技術(shù)實(shí)現(xiàn)生鮮農(nóng)產(chǎn)品電商配送優(yōu)化。徐廣姝等[7]運(yùn)用博弈模型分析了常見契約不能有效協(xié)調(diào)供應(yīng)鏈的情況，設(shè)計(jì)了生鮮電商企業(yè)與物流服務(wù)商之間“數(shù)量折扣+成本分擔(dān)+收益共享組合契約”。吳靜旦[8]對生鮮農(nóng)產(chǎn)品O2O模式進(jìn)行分析，提出O2O未來的發(fā)展一定要突出安全性、冷鏈性、高效性、便利化和精細(xì)化等特點(diǎn)。汪旭暉與張其林 [9]發(fā)現(xiàn)生鮮農(nóng)產(chǎn)品電商流通模式對傳統(tǒng)生鮮農(nóng)產(chǎn)品流通體系進(jìn)行了分解與重構(gòu)，能夠確立以實(shí)際信息流帶動商流、物流、資金流協(xié)同流轉(zhuǎn)的新模式，并形成“大供應(yīng)、大市場、小配送”流通格局。楊磊等 [10]認(rèn)為1個供應(yīng)商和1個零售商組成的兩級生鮮農(nóng)產(chǎn)品供應(yīng)鏈，其中兩個成員的決策過程是一個Stackelberg博弈。王淑云等[11]研究了有限期內(nèi)多個生產(chǎn)商、1個配送中心（DC）和多個零售商組成的冷鏈系統(tǒng)庫存一體化決策，建立了考慮DC增值服務(wù)、變質(zhì)率服從三個參數(shù)Weibull分布的多種非即刻變質(zhì)商品三級庫存模型，從系統(tǒng)利潤最大化的角度確定各個成員的最佳補(bǔ)貨策略。

針對車輛路徑的研究，主要根據(jù)實(shí)際需求建立符合問題本身的數(shù)學(xué)模型，并設(shè)計(jì)相關(guān)算法求解模型這兩個方面進(jìn)行。在建立車輛路徑模型時多依據(jù)現(xiàn)實(shí)的約束條件，如車輛數(shù)目、型號、載重量、容積限制等建立特定的數(shù)學(xué)模型，再設(shè)計(jì)算法求解模型。Azi等 [12]為了解決容量約束的車輛路徑問題，列出了所有可行的解決方案，并使用最短路徑算法來求解、排序和選擇最優(yōu)車輛路徑方案。Behnam Vahdani [13]提出了一種新的混合啟發(fā)式算法，并應(yīng)用于交叉分布系統(tǒng)的車輛調(diào)度問題，這種新的算法相結(jié)合的混合粒子群優(yōu)化算法的元素、模擬退火算法、禁忌搜索算法以提高其搜索能力，解決了最優(yōu)訂貨交貨時間的問題。張群、顏瑞 [14]建立了多車型、多產(chǎn)品、多配送中心約束的車輛路徑混合數(shù)學(xué)模型，通過模糊遺傳算法來求解該模型，該算法能夠自動調(diào)節(jié)交叉率和變異率，加快算法的收斂和避免局部最優(yōu)的情況。Hiassat 等[15]考慮易腐品特性，建立配送中心庫存配送路徑問題的優(yōu)化模型，并用遺傳算法和局部搜索啟發(fā)法求解。Woensel 等[16]考慮了動態(tài)行車速度，提出了改進(jìn)的禁忌搜索算法尋找配送服務(wù)質(zhì)量與配送成本之間的平衡點(diǎn)。Alinaghian和Shokouhit[17]采用大規(guī)模鄰域搜索和變鄰域搜索算法解決多隔室多中心的車輛路徑問題。Govindan和Jafarian等 [18]在考慮影響冷鏈物流運(yùn)輸因素的基礎(chǔ)上，加入時間窗的約束，同時考慮冷鏈物流配送和綠色物流的融合，更適應(yīng)可持續(xù)發(fā)展。侯玉梅、賈震環(huán) [19]考慮了時間窗的約束與提高客戶的滿意度，構(gòu)建了車輛路徑模型，采用自適應(yīng)遺傳算法進(jìn)行求解，結(jié)果表明：可以滿足配送商和客戶的需求，減少配送車輛。劉炎寶[20]等考慮生鮮農(nóng)產(chǎn)品在固定成本、燃油成本、時間窗懲罰成本的基礎(chǔ)上增加新鮮度下降懲罰成本和碳排放成本，從而建立生鮮農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化模型。

總之，許多學(xué)者在車輛路徑優(yōu)化上做了較多的研究，但由于生鮮農(nóng)產(chǎn)品易腐性和保質(zhì)期短等特點(diǎn)決定了配送的復(fù)雜性，現(xiàn)有的研究對生鮮農(nóng)產(chǎn)品配送系統(tǒng)的本質(zhì)揭示得還不夠深入，尤其是隨著生鮮農(nóng)產(chǎn)品需求快速增長，其末端配送模式的選擇與系統(tǒng)的構(gòu)建還有待優(yōu)化。生鮮農(nóng)產(chǎn)品物流配送是為眾多的消費(fèi)者提供物流服務(wù)的，不僅要考慮到整個配送流程中的成本控制，還必須考慮到客戶滿意度水平對生鮮農(nóng)產(chǎn)品物流配送效率的影響。在配送路徑優(yōu)化算法上，目前還沒有快速解決大規(guī)?？蛻酎c(diǎn)問題的算法。針對以上不足，本文采用了混合遺傳算法—應(yīng)用聚類分析對多客戶點(diǎn)進(jìn)行聚類，然后運(yùn)用遺傳算法對VRPTW模型進(jìn)行求解。

二、問題的描述和數(shù)學(xué)模型的建立

本文所建立的生鮮農(nóng)產(chǎn)品企業(yè)的末端配送模型，其研究背景為一個冷鏈配送中心向末端大規(guī)?？蛻暨M(jìn)行直接配送，并以末端配送總成本最小和客戶滿意度最大為目標(biāo)建立成本函數(shù)模型。一般研究車輛路徑問題的目標(biāo)是運(yùn)輸總成本，主要包括運(yùn)輸成本、車輛固定成本。生鮮農(nóng)產(chǎn)品車輛路徑問題還具有其他形式的成本：運(yùn)輸過程中貨物貨損成本;由于生鮮農(nóng)產(chǎn)品具有易腐性的特點(diǎn)，運(yùn)輸工具主要是具有冷凍、冷藏的配送貨車，在運(yùn)輸過程中會產(chǎn)生能耗成本;客戶的位置和需求量已知，由于時間窗的限制，如果沒能及時地送達(dá)或者早于客戶的時間窗送達(dá)，會產(chǎn)生一定的懲罰成本。一般車輛路徑所研究的是配送成本最小的單目標(biāo)問題，本文不僅考慮生鮮農(nóng)產(chǎn)品末端配送的總成本最小問題，而且考慮了客戶對服務(wù)時間的滿意度問題。

（一）模型的基本假設(shè)

依據(jù)對某企業(yè)的現(xiàn)實(shí)情況進(jìn)行分析，將現(xiàn)實(shí)問題抽象為數(shù)學(xué)模型，對模型設(shè)置了如下假設(shè)：

（1）本文研究的是單一的冷鏈配送中心與末端大規(guī)?？蛻舻膯栴};

（2）客戶的位置、個數(shù)、需求量以及要求送貨的時間窗確定;

（3）冷鏈配送中心的車輛足夠，車的載重量一定，配送車輛的型號都一致，所有車輛的速度一定;

（4）所有車輛都是從配送中心出發(fā)，服務(wù)完指定的客戶，最終還是回到配送中心;

（5）冷鏈配送中心貨物的類別和儲存量足夠滿足客戶的需求，不會存在缺貨情況;

（6）車輛如果出發(fā)，所服務(wù)的客戶的先后順序確定，不會有新的客戶進(jìn)入規(guī)劃的路線中;

（7）貨物的重量不能超過車的載重量，貨物的體積不超過車的容量;

（8）每個客戶只能由一輛車進(jìn)行服務(wù)，并保證一次性進(jìn)行配送完成;

（9）生鮮農(nóng)產(chǎn)品在配送的過程中一直保持恒溫狀態(tài)，損耗只與配送的時間有關(guān)，所配送產(chǎn)品為同一類產(chǎn)品，產(chǎn)品之間不相互影響。

（二）模型參數(shù)的描述

（1）P={p0，p1，…，pn}：客戶和生鮮農(nóng)產(chǎn)品配送中心的集合;

（2）P0表示冷鏈的配送中心;

（3）n表示客戶的數(shù)量;

（4）Qi表示客戶i的購買量;

（5）Qmax表示車輛的最大載重量;

（6）V代表車輛的容積;

（7）dij是客戶點(diǎn)i到客戶點(diǎn)j的行駛距離;

（8）K表示冷鏈配送中心的配送車輛的數(shù)量;

（9）Vk是車輛K的行駛速度;

（10）a1為貨物在運(yùn)輸過程中的損耗系數(shù);

（11）[E′i，L′i]表示客戶i預(yù)期到達(dá)的時間段;

（12）β1表示早于客戶期望時間的懲罰系數(shù);β2是晚于客戶期望時間的懲罰系數(shù);

（13）Tij表示車輛從客戶點(diǎn)i行駛到客戶點(diǎn)j需要的時間;

（14）T0k 為車輛K從冷鏈配送中心出發(fā)的時間;

（15）Tki 為車輛K從客戶i駛向下一個客戶點(diǎn)或配送中心的時間;

（16）yik=1;客戶i需求的貨物由車輛k配送

0;否則

（17）xijk=1;車輛k從客戶i行駛到客戶j

0;否則

（三）帶時間窗生鮮農(nóng)產(chǎn)品末端配送模型的建立

本文所研究的生鮮農(nóng)產(chǎn)品配送的模型綜合考慮了車輛的裝載量、容量、速度，客戶的時間窗、需求量等限制條件。建立以客戶的滿意度最大和冷鏈車輛運(yùn)輸成本、貨損成本、能耗成本、固定成本、懲罰成本等總成本最小為目標(biāo)的模型。

1.客戶滿意度的處理

本文采用客戶對時間的要求來處理客戶的滿意度問題。把客戶i滿意度用客戶等待的時間來量化，建立客戶滿意度U（ti）和服務(wù)開始的時間的隸屬函數(shù)。

U（ti）=（ti-EiEi′-Ei）×β1;ti∈[E′i，Ei]

（L′i-tiLi-L′i）×β2;ti∈[L′i，Li]

1;ti∈[E′i，L′i]

0;ti[Ei，Li]

（1）

[Ei，Li]：客戶i所能接受到達(dá)的時間段，Li是客戶時間窗的上限;Ei是客戶時間窗的下限。其中β1、β2為客戶對時間的敏感系數(shù)，如果送達(dá)時間在客戶期望的時間段[E′i，L′i]， 則客戶點(diǎn)i的滿意度為100%。如果在其他的時間段送到貨，隨著與期望的時間偏離，客戶滿意度水平也會有一定的下降。

對客戶的滿意度處理有多種方法，主要是考慮每個客戶的滿意度情況，如果有一個客戶的滿意度低的話，會導(dǎo)致整體的滿意度大幅度下降，如果達(dá)到整體客戶滿意度的最優(yōu)，則每一個客戶的滿意度都達(dá)到最優(yōu)水平。本文對客戶對時間的滿意度的平均值進(jìn)行處理，其中還考慮了客戶的重要程度，其重要程度以購買貨物的價值來體現(xiàn)，本文整體客戶的滿意度水平函數(shù)為：

S=∑ni=1U（ti）×Qi/∑ni=1Qi

（2）

2.成本分析

（1）車輛的運(yùn)輸成本

隨著行駛里程的增加，車輛的油耗費(fèi)用也會增加。配送車輛的運(yùn)輸成本還包括車輛的維修和保養(yǎng)等費(fèi)用，運(yùn)輸成本主要由車輛與客戶的位置距離決定。用Zy表示車輛的運(yùn)輸成本，則配送車輛的運(yùn)輸成本的數(shù)學(xué)表達(dá)式為：

Zy=∑Kk=1∑ni=0∑nj=0ctkijxkij

（3）

（2）車輛的固定成本

配送車輛的固定成本不隨車輛運(yùn)動的里程增加而改變，本文認(rèn)為車輛的固定成本主要包括車輛人員的人工費(fèi)用、車輛啟動一次的租金以及車輛的損耗等成本。用Zg表示車輛的固定成本，則配送車輛的固定成本的數(shù)學(xué)表達(dá)式為：

Zg=∑Kk=1cgk

（4）

（3）車輛的能耗成本

為了保證生鮮農(nóng)產(chǎn)品在運(yùn)輸過程中沒有腐壞，生鮮農(nóng)產(chǎn)品需要冷鏈進(jìn)行配送，冷鏈車輛外部的溫度和車內(nèi)的溫度有一定溫差，那么就會進(jìn)行熱傳導(dǎo)，冷鏈設(shè)施就會產(chǎn)生能耗，用Zh1表示行駛中這段的能耗成本。另外，每到達(dá)一個客戶點(diǎn)需要裝卸貨物，車內(nèi)外的熱交換是通過車門進(jìn)行的，那么車外的暖空氣和車內(nèi)的冷氣進(jìn)行交換需要消耗車內(nèi)的制冷設(shè)施，需計(jì)算從車門進(jìn)行熱交換所消耗的制冷設(shè)施的成本。裝卸時車輛的能耗成本用Zh2表示。

a.車輛行駛中的能耗成本

Zg=∑Kk=1cgk

（5）

其中P表示單位時間的制冷成本，ΔT=TW-TN為冷鏈車輛外部和內(nèi)部的溫差，t為車輛K的行駛時間，Gt為車輛的熱負(fù)荷，與車輛的表面積、車輛的材料等有關(guān)。

b.裝卸時的能耗成本

Zh2=∑Kk=1Gk×ΔT×ti×P

（6）

其中P表示單位時間的制冷成本，ti為車輛K在客戶i的停留時間，ΔT=TW-TN為冷鏈車輛外部和內(nèi)部的溫差，GK為車輛開門消耗的熱負(fù)荷。

c.車輛的能耗成本

既包括行駛中的能耗成本，也包含裝卸時所消耗的能耗成本，車輛的能耗總成本用Zh表示，則能耗成本為：

Zh=Zh1+Zh2

（7）

d.貨損成本

車輛在運(yùn)輸過程中，雖然是保持冷鏈運(yùn)輸，但由于生鮮農(nóng)產(chǎn)品具有一些生命特質(zhì)，可能會產(chǎn)生腐爛，這也是生鮮農(nóng)產(chǎn)品在配送過程中與其他物品配送的區(qū)別，這就需要考慮生鮮農(nóng)產(chǎn)品配送中有一定的貨損成本。在裝卸過程中由于車輛的內(nèi)外溫差較大，會產(chǎn)生熱交換，對生鮮農(nóng)產(chǎn)品的腐爛有一定的影響。用Zs表示生鮮農(nóng)產(chǎn)品的貨損成本，則生鮮農(nóng)產(chǎn)品貨損成本的數(shù)學(xué)表達(dá)式為：

Zs=P∑Kk=1∑nj=1xjk（θ1tij+θ2qj）

（8）

e.違反時間窗的懲罰成本

在生鮮農(nóng)產(chǎn)品的配送過程中，經(jīng)常會遇到生鮮農(nóng)產(chǎn)品配送商沒有在指定的時間內(nèi)將貨物送到客戶的手中，有時也會在客戶指定的時間之前送達(dá)。這樣就會產(chǎn)生一定的懲罰成本，假設(shè)客戶的期望送達(dá)時間是[E′i，L′i]，那么將會出現(xiàn)圖1的幾種情況。

一是早于客戶需求[E′i，L′i]的時間到達(dá)，如果在[Ei，E′i]之間到達(dá)，這表明在這段時間內(nèi)，客戶是可以接受，但會給客戶帶來一定的不便，需要支付客戶一定的懲罰成本。違反這段時間窗的懲罰成本用Zc1表示，則懲罰成本表達(dá)式為：

Zc1=β1∑ni=1Qi×max{（E′i-ti），0}

（9）

二是如果早于Ei這個時間點(diǎn)或晚于Li時間點(diǎn)到達(dá)，那么客戶將不會接收貨物，此時用一個無窮大的懲罰值M表示，在模型求解中也是無可行解。

三是在客戶需求[E′i，L′i]的時間內(nèi)到達(dá)，則不會產(chǎn)生任何懲罰成本，此時客戶的滿意度為100%。

四是晚于客戶需求[E′i，L′i]的時間到達(dá)，如果配送是在[L′i，Li]這個時間段內(nèi)送達(dá)，則表示客戶可以接受，但會讓客戶等待，這時需要更大的懲罰成本來補(bǔ)償客戶的等待時間，此時客戶的滿意度也會降低，這段違反時間窗的懲罰成本的表達(dá)式為：

Zc2=β2∑ni=1Qi×max{（ti-L′i），0}

（10）

根據(jù)以上分析，違反時間窗的懲罰總成本的表達(dá)式為：

Zc=β1∑ni=1Qi×max{（E′i-ti），0}+β2∑ni=1Qi×max{（ti-L′i），0}

（11）

其中ti表示客戶到達(dá)的時間;β1表示早于客戶期望時間的懲罰系數(shù);β2是晚于客戶期望時間的懲罰系數(shù);M是一個無窮大數(shù)。[E′i，L′i]表示客戶期望的時間窗;[Ei，Li]為能夠服務(wù)客戶i的時間窗，Ei為能夠服務(wù)客戶時間窗的上界，Li為能夠服務(wù)客戶時間窗的下界。

3.模型的建立

本文的目標(biāo)是在滿足客戶需求量、時間窗等條件下，求總成本最小的配送方案，其中成本包括生鮮農(nóng)產(chǎn)品的易腐性所造成的配送貨損成本、車輛固定成本、隨里程而遞增的運(yùn)輸成本、配送時冷凍設(shè)備消耗的能耗成本和懲罰成本。以總成本最小為原則來構(gòu)建VRPTW模型：

S=∑ni=1U（ti）×Qi/∑ni=1Qi

minZ=Zy+Zg+Zh+Zs+Zc

（12）

約束條件：

∑kk=1yki=1 i=1，2，…，n

K i=0

（13）

∑ni=0ykij=ykj，j=0，1，2，…，K

（14）

∑nj=0xkij=ykj，i=0，1，2，…，n，k=1，2，…，K

（15）

Ei≤ti≤Li

（16）

∑ni=1ykiQi≤Mk，k=1，2，…，K

（17）

U（ti）=（ti-EiE′i-Ei）×β1;ti∈[E′i，Ei]

（L′i-tiLi-L′i）×β2;ti∈[L′i，Li]

1;ti∈[E′i，L′i]

0;ti[Ei，Li]

（18）

∑ni=1（yik·∑Hh=1qih·vh）≤Vk;k

（19）

U（ti）≥θi

（20）

xij=0 或1;i，j=1，2，L，n

（21）

yik=0或1;i=1，2，L，n;k

（22）

以上約束條件中，式（12）表示目標(biāo)函數(shù);式（13）表示每個客戶只有一個車輛服務(wù)，每個車輛都是從配送中心出發(fā)，最終再回到配送中心;式（14）、式（15）為每個點(diǎn)的有且僅有一次經(jīng)過約束;式（16）貨物送達(dá)的時間在時間窗的范圍內(nèi);式（17）貨物的重量不能超過車輛的載重量;式（18）表示車輛的容積約束限制;式（19）表示客戶時間窗的處理過程;式（20）表示客戶的滿意度不低于一定的值;式（21）、式（22）是決策變量的0-1約束。

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

（一）K-means聚類分析的設(shè)計(jì)

K-means聚類主要是根據(jù)客戶點(diǎn)之間的位置進(jìn)行分類，將客戶點(diǎn)進(jìn)行編號，根據(jù)客戶點(diǎn)的位置將其分為K類，根據(jù)譚波（2014）采用的公式確定K的數(shù)量[21]。

K=[∑ni=1Qi/αQmax]+1

（23）

其中Qi是客戶i的訂購量;Qmax表示車的最大載重量;α跟約束條件的復(fù)雜度有關(guān)，約束的條件越多α越小，本文設(shè)置α為0.8;[ ]表示取整。K-means聚類分析設(shè)計(jì)的具體步驟如下：

（1）K-means算法首先將客戶點(diǎn)分為K個點(diǎn)作為聚類中心。

（2）分別計(jì)算每個客戶點(diǎn)到聚類中心的距離，通過分配每個客戶點(diǎn)到與凝聚點(diǎn)最近的類來形成分類，直到所有的客戶點(diǎn)都進(jìn)行分類。

（3）檢查每類里客戶的總需求量是否大于車的載重量和目標(biāo)的約束條件，若是，則執(zhí)行（4）;若不是，則執(zhí)行（7）。

（4）將不符合約束條件的客戶點(diǎn)放在臨近的區(qū)域內(nèi)，檢查其他類是否滿足約束條件，是否有多余的車容量，若是，則執(zhí)行（5）;若不是，則執(zhí)行（6）。

（5）將不滿足條件的客戶點(diǎn)加入臨近且符合約束條件的區(qū)域內(nèi)，并執(zhí)行（7）。

（6）增加一輛車來進(jìn)行配送（K=K+1），返回（3）。

（7）分類完成，得到一組編碼，將其作為遺傳算法的初始解。

K-means聚類是一個反復(fù)迭代的分類過程，在聚類過程中，觀測樣本所屬的類會不斷地進(jìn)行調(diào)整，直到達(dá)到穩(wěn)定為止。

（二）遺傳算法設(shè)計(jì)

混合遺傳算法主要是融合聚類算法和遺傳算法，主要對K-means算法進(jìn)行分析，并對遺傳算法的編碼、初始化種群、適應(yīng)度函數(shù)值的確認(rèn)、交叉算子和變異率的選擇等。

1.染色體編碼方案設(shè)置

本文綜合地考慮了客戶的滿意度以及車輛路徑多目標(biāo)的優(yōu)化情況，把客戶總數(shù)n進(jìn)行編號，每個特征就是一個基因，一個解就相當(dāng)于一條染色體。本文采用了最常用的二進(jìn)制進(jìn)行編碼。二進(jìn)制具有簡單易行、便于用模式定理進(jìn)行分析等特點(diǎn)。

2.初始化染色體種群

本文不僅考慮客戶時間窗的限制，還要考慮末端大規(guī)?？蛻酎c(diǎn)問題以及每個客戶點(diǎn)的滿意度問題，需要在滿足每個客戶點(diǎn)滿意度的條件下進(jìn)行。一般情況下初始化種群都是隨機(jī)的，隨機(jī)產(chǎn)生初始化種群可以避免種群的單調(diào)性，但會增加迭代的次數(shù)，增加運(yùn)行的時間，可以避免局部最優(yōu)。本文假設(shè)群體規(guī)模N為100，利用initializega代碼產(chǎn)生100個個體，不斷地產(chǎn)生初始個體，指導(dǎo)初始群體的個體為N為止，形成初始種群，初始群體的表達(dá)式如下：

R0=（r1，r2，…，rn）

（24）

其中R0為初始群體，N為群體規(guī)模，r1，r2，…，rn為染色體。

通過運(yùn)行initializega代碼，隨機(jī)產(chǎn)生100條車輛的可行配送路線，構(gòu)成配送路線優(yōu)化問題解的初始種群，完成了該問題解集的初始化過程。initializega函數(shù)的部分代碼：

Function（t）=initializega（popsize，citynum）

for i=1：popsize

t（i，：）=randperm（citynum）;

3.適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是評價遺傳算法中染色體性能的唯一指標(biāo)，評價每條染色體的優(yōu)劣以及每條配送路線優(yōu)化的好壞。適應(yīng)度函數(shù)值越大，說明配送路線優(yōu)化效果越好，帶時間窗生鮮農(nóng)產(chǎn)品末端配送路徑優(yōu)化的客戶滿意度越高和配送總成本優(yōu)化得越好?？蛻舻臐M意度一定時，適應(yīng)度函數(shù)值最大的對應(yīng)配送路徑也是最優(yōu)化的。帶時間窗的生鮮農(nóng)產(chǎn)品末端配送路徑的適應(yīng)度函數(shù)如下：

fi=Z′Z

Pi=fi∑Nn=1fi

（25）

minZ=Zy+Zg+Zh+Zs+Zc

（26）

其中fi表示第i條染色體的適應(yīng)度函數(shù);Pi表示個體選擇概率的分布;Z′表示當(dāng)前染色體配送的總成本。適應(yīng)度fitness的部分代碼：

function rawcost=fitness（tspdist，gt）

（m，n）=size（gt）;

for k=l：m

for i=l：n-1

distan（k，i）=tspdist（gt（k，i），gt（k，i+1））;

end

distan（k，n）=tspdist（gt（k，n），gt（k，1））;

rawcost（k）=sum（distan（k，：））;

end

4.遺傳算子設(shè)計(jì)

（1）選擇算子

以優(yōu)勝劣汰的方式從群體中選擇優(yōu)勝的個體，選擇的目的是把優(yōu)勝的個體的基因直接遺傳或者通過交叉配對產(chǎn)生新個體的方式再遺傳到下一代。在適應(yīng)度評估的基礎(chǔ)上進(jìn)行選擇交叉、變異操作，目前常見的選擇算子的方法有：適應(yīng)度比例法、局部選擇法、隨機(jī)抽樣法及輪盤賭選擇法。針對本文帶時間窗生鮮農(nóng)產(chǎn)品末端大規(guī)模配送路徑的模型選擇輪盤賭選擇法。

輪盤賭選擇法是較為常用的一種方法，各個個體的選擇概率和其適應(yīng)度成比例。群體的大小為n;個體的i的適應(yīng)度為fi，則i被選擇的概率為：

Pi=fi∑nj=1fj

（27）

概率是反映個體i的適應(yīng)度在整個群體的個體適應(yīng)度總和中所占的比例。個體的適應(yīng)度越高，被選擇的概率越大，個體被選擇后，可隨機(jī)地組成交配對，供后面的交叉操作。選擇操作的部分代碼如下：

Function ret =Select（individual，sizepop）

% 本函數(shù)對每一代種群中的染色體進(jìn)行選擇，以進(jìn)行后面的交叉和變異

% individuals ?input ;種群信息

% sizepop ? input;種群規(guī)模

% ret ? ? output;經(jīng)過選擇后的種群

fitness1=1/individuals.fitness;

sumfitness =sum（fitness1）;

sumf=fitness1/sumfitness;

index=[];

for i=1：sizepop ?%轉(zhuǎn)sizepop次輪盤

pick=rand;

while pick=0

pick=rand;

end

for j=1：zizepop

pick=pick-sumf（j）

if pick <0

index=[index（j）]

break;%尋找落入的區(qū)間

end

end

end

individuals.chrom= individuals.chrom（index，：）

individuals.fitness= individuals.fitness（index）

ret = individuals;

（2）交叉算子

交叉算子在遺傳算法中起到核心的作用，是把兩個父代個體的部分結(jié)構(gòu)進(jìn)行交叉重組，然后形成新的個體，通過交叉可以使遺傳算法的搜索能力得以提高。交叉算子根據(jù)交叉率可以使兩個個體隨機(jī)地交換部分基因，產(chǎn)生新的基因組，和需要的基因組進(jìn)行組合。根據(jù)編碼表達(dá)方法的不同可以分為實(shí)值重組和二進(jìn)制交叉兩類[22]。本文交叉規(guī)則采用的是實(shí)數(shù)編碼的形式，在交叉時產(chǎn)生新的個體，本文通過反復(fù)的實(shí)驗(yàn)，設(shè)置交叉率為0.8。如圖2所示，實(shí)數(shù)編碼的PMX（部分交叉編碼）的具體操作如下：

第一，父代的染色體r1和r2隨機(jī)地選擇一段交叉的區(qū)域。

第二，r1和r2的交叉區(qū)域進(jìn)行互換，并形成一定的映射關(guān)系。

第三，將交叉區(qū)域外并且不存在映射關(guān)系的區(qū)域的數(shù)值直接復(fù)制到子代中。

第四，將交叉區(qū)域外的數(shù)值且存在映射關(guān)系的進(jìn)行交叉替換，并得到子代的染色體r1′和r2′。

（3）變異算子

變異算子是對群體中的個體串的某些基因值進(jìn)行改動：首先，對群體中的所有個體以事先設(shè)定的變異概率0.1判斷是否進(jìn)行變異，然后進(jìn)行變異的個體隨機(jī)選擇變異位進(jìn)行變異。

5.終止條件

混合遺傳算法是一個較為復(fù)雜的算法，對于終止條件主要有兩種情況：第一種是給定一個最大的遺傳迭代次數(shù)，算法迭代到最大次數(shù)為止;第二種是要求進(jìn)化的偏差小于所規(guī)定的下限。經(jīng)過幾次試驗(yàn)后，本文采用算法迭代到最大次數(shù)為止，發(fā)現(xiàn)當(dāng)?shù)螖?shù)達(dá)到200時，目標(biāo)函數(shù)值不再發(fā)生變化，達(dá)到穩(wěn)定。

四、算例分析

由于生鮮農(nóng)產(chǎn)品的易腐性等特點(diǎn)，在配送的過程中，配送路徑是否合理決定了是否能夠及時地將貨物送達(dá)客戶的手中，對配送的成本、收益等都會有較大的影響。本文對某生鮮農(nóng)產(chǎn)品公司進(jìn)行了調(diào)研，了解了該企業(yè)的基本情況，并對下面計(jì)算需要用到的相關(guān)業(yè)務(wù)數(shù)據(jù)進(jìn)行了收集和整理。本章算例的對比分析主要是驗(yàn)證帶時間窗生鮮農(nóng)產(chǎn)品末端配送路徑模型的應(yīng)用價值與混合遺傳算法的可行性和有效性。

（一）算例分析數(shù)據(jù)準(zhǔn)備

根據(jù)某生鮮農(nóng)產(chǎn)品公司的配送中心和客戶點(diǎn)的位置，本文在對客戶點(diǎn)與配送點(diǎn)之間的距離上采用歐式距離進(jìn)行測度。

（1）根據(jù)客戶下單的順序依次對客戶進(jìn)行編號，統(tǒng)計(jì)客戶的需求量、客服期望的時間窗以及能夠服務(wù)客戶的時間，根據(jù)客戶的需求量判斷服務(wù)該客戶的時間。本文將日常的時鐘時間轉(zhuǎn)化成數(shù)字，比如8：30用8.5進(jìn)行簡化處理。

（2）配送車輛屬性及貨物相關(guān)的參數(shù)。本文建立的帶時間窗的生鮮農(nóng)產(chǎn)品末端大規(guī)模客戶點(diǎn)配送模型，綜合考慮了生鮮農(nóng)產(chǎn)品的易腐等特性、車輛的載重量、車輛的速度、冷鏈設(shè)備內(nèi)外的溫度差以及客戶的滿意度等因素。表1是配送車輛屬性以及生鮮農(nóng)產(chǎn)品等相關(guān)的參數(shù)。

（二）模型的求解

當(dāng)客戶滿意度為80%時，在不同變異率和交叉率情況下進(jìn)行試驗(yàn)和記錄，如圖3所示。在變異率為0.1、交叉率為0.8時，迭代1000次，運(yùn)用混合遺傳算法對模型進(jìn)行求解，車輛路徑輸出情況如圖4所示。

在客戶滿意度為80%的條件下，計(jì)算結(jié)果表明完成配送任務(wù)需要車輛的數(shù)量為4輛，運(yùn)輸總成本為546.5元，貨損成本為160.6為元，能耗成本為304.9元，車輛固定成本為600元，以及懲罰成本為91.0元，最后得出末端配送總成本為1703.0元。各項(xiàng)成本函數(shù)值的末端配送情況以及客戶滿意度下輸出的結(jié)果匯總?cè)绫?、表3所示。

（三）優(yōu)化的效果分析

某生鮮農(nóng)產(chǎn)品公司的物流配送方案如表4所示，可以看出為給20個客戶服務(wù)，某生鮮農(nóng)產(chǎn)品公司的冷鏈配送中心安排了5輛車來運(yùn)輸，但總體看來車輛的容積利用率和載重利用率都不高，并且會造成運(yùn)力的浪費(fèi)，按照此配送方案，根據(jù)客戶滿意度的隸屬函數(shù)求得客戶的滿意度為80%。

從表5可以明顯看出優(yōu)化后的優(yōu)越性，在相同的客戶滿意度下，安排車輛數(shù)比原來少了20%，車輛行駛總距離比優(yōu)化前減少12.3%，平均的配送成本減少了447元，比優(yōu)化前節(jié)省了20.8%的費(fèi)用。公司現(xiàn)有的末端配送車輛平均裝載率為75.1%，優(yōu)化后的車輛的平均裝載率為91.3%，同比提高了21.5%。通過對比分析，證明了本文構(gòu)建的生鮮農(nóng)產(chǎn)品末端配送模型及混合遺傳算法的有效性和可行性。

（四）客戶滿意度和末端配送成本優(yōu)化

根據(jù)以上討論，確定混合遺傳算法的交叉率為0.8和變異率為0.1，迭代次數(shù)為1000次。在客戶的滿意度為80%、85%、90%、95%、100%的情況下，分析目標(biāo)函數(shù)值的變化、得出優(yōu)化結(jié)果所用的時間，在這五組客戶滿意度的條件下分別進(jìn)行5次的運(yùn)行，最后進(jìn)行分析比較，確定最終的客戶整體的滿意度水平。

當(dāng)客戶滿意度為95%時，對混合遺傳算法進(jìn)行運(yùn)算，以下是車輛路徑輸出圖和優(yōu)化迭代圖，如圖5所示。

在客戶滿意度為95%的條件下，輸出的路徑圖、得出優(yōu)化結(jié)果的迭代次數(shù)、運(yùn)行的時間和目標(biāo)的函數(shù)值如表6所示。

分別將客戶的滿意度從80%至100%進(jìn)行統(tǒng)計(jì)，按照成本目標(biāo)函數(shù)值和程序算法所運(yùn)行的時間分項(xiàng)進(jìn)行統(tǒng)計(jì)分析，在不同客戶滿意度下的配送成本的目標(biāo)函數(shù)值和得到滿意解程序運(yùn)行的時間運(yùn)行5次運(yùn)營的結(jié)果如表7所示。通過Excel進(jìn)行分析，如圖6所示，能夠直觀地反映情況。

在交叉率為0.8、變異率為0.1以及迭代次數(shù)為200的情況下，客戶的滿意度每次增加5%，從80%增加到100%，通過圖6發(fā)現(xiàn)從客戶滿意80%增加到95%這個區(qū)間，目標(biāo)函數(shù)值也在緩緩地增加，變化不是很明顯，配送成本的增長率增加得較少，也就是說物流成本上升得不是很快，但客戶的滿意度從95%提高到100%時，目標(biāo)函數(shù)值陡然上升，說明物流成本突然增加，那么可以認(rèn)為帶時間窗生鮮農(nóng)產(chǎn)品末端配送中，客戶滿意度為95%這個關(guān)鍵點(diǎn)具有重要的作用，其總物流成本為1928元，車輛1的配送路線：P0-P6-P13-P3-P11-P0;車輛2的配送路線：P0-P15-P5-P1-P16-P20-P0;車輛3的配送路線：P0-P4-P9-P10-P7-P17-P0;車輛4的配送路線P0-P2-P14-P12-P18-P19-P8-P0;其配送方案是合理的。

五、總結(jié)

帶時間窗的生鮮農(nóng)產(chǎn)品末端車輛配送中，客戶的滿意度和車輛路徑函數(shù)是兩個相互影響、相互制約的問題，本文綜合考慮了客戶滿意度和車輛路徑成本函數(shù)這兩方面的內(nèi)容，構(gòu)建了帶時間窗的生鮮農(nóng)產(chǎn)品末端配送車輛路徑的多目標(biāo)模型，采用了混合遺傳算法對模型進(jìn)行求解，使用Matlab軟件實(shí)現(xiàn)算法的設(shè)計(jì)和運(yùn)行，最后采用算例進(jìn)行分析，并求得滿意的可行解，驗(yàn)證了模型的有效性和算法的可行性。本文還針對該模型討論了在不同客戶滿意度下成本目標(biāo)函數(shù)值的變化，發(fā)現(xiàn)當(dāng)客戶滿意度為80%～95%時，客戶的滿意度越高，配送成本目標(biāo)函數(shù)值越大，但配送成本增加的幅度不高。當(dāng)客戶滿意度突破95%時，配送成本的目標(biāo)函數(shù)值會陡然上升。那么在實(shí)際的應(yīng)用中，這個關(guān)鍵的客戶滿意度值具有重要的參考價值。

參考文獻(xiàn)：

[1]OSVALD A，STIRN L Z.A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food[J].Journal of food engineering，2008，85（2）：285-295.

[2]ZHANG Y，CHEN X D .An optimization model for the vehicle routing problem in multi-product frozen food delivery[J].Journal of applied research and technology，2014，12（2）：239-250.

[3]GONG J，PU L，ZHANG H.Numerical study of cold store in cold storage supply chain and logistics[C]//2010 International Conference on E-Product E-Service and E-Entertainment.Henan：IEEE，2010.

[4]SONG B D，KO Y D .A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery[J].Journal of food engineering，2016，169：61-71.

[5]李昌兵，汪爾晶，袁嘉彬.物聯(lián)網(wǎng)環(huán)境下生鮮農(nóng)產(chǎn)品物流配送路徑優(yōu)化研究[J].商業(yè)研究，2017（4）：1-9.

[6]李曉.基于大數(shù)據(jù)的生鮮農(nóng)產(chǎn)品電商配送優(yōu)化研究[J].農(nóng)村經(jīng)濟(jì)，2018（6）：106-109.

[7]徐廣姝，宋子龍.生鮮電商與物流服務(wù)商的契約協(xié)調(diào)——基于生鮮宅配模式的分析[J].商業(yè)研究，2017（2）：151-159.

[8]吳靜旦.基于O2O模式的生鮮農(nóng)產(chǎn)品冷鏈物流配送網(wǎng)絡(luò)創(chuàng)新研究[J].農(nóng)業(yè)經(jīng)濟(jì)，2019（7）：133-134.

[9]汪旭暉，張其林.電子商務(wù)破解生鮮農(nóng)產(chǎn)品流通困局的內(nèi)在機(jī)理——基于天貓生鮮與沱沱工社的雙案例比較研究[J].中國軟科學(xué)，2016（2）：39-55.

[10]楊磊，肖小翠，張智勇.需求依賴努力水平的生鮮農(nóng)產(chǎn)品供應(yīng)鏈最優(yōu)定價策略[J].系統(tǒng)管理學(xué)報，2017（1）：142-153.

[11]王淑云，姜櫻梅，王憲杰.基于配送中心的三級冷鏈一體化庫存模型[J].系統(tǒng)管理學(xué)報，2017（2）：390-398.

[12]AZI N，GENDREAU M，POTVIN J Y .An excat algorithm for a single-vehicle routing problem with time windows and multiple routes[J].European journal of operational research，2007，178（3）：755-766.

[13]BEHNAM V.Vehicle routing scheduling using an enhanced hybrid optimization approach[J].Journal of intelligent manufacturing，2012（23）：759-774.

[14]張群，顏瑞.基于改進(jìn)模糊遺傳算法的混合車輛路徑問題[J].中國管理科學(xué)，2012，20（2）：121-128.

[15]HIASSAT A，DIABAT A，RAHWAN I.Agenetic algorithm approach for location-inventory-routing problem with perishable products[J].Journal of manufacturing systems，2017，42：93-103.

[16]WOENSEL T V.Vehicle routing problem with stochastic travel times：balancing service and transportation costs[J].Computers and operations research，2017，40（1）：214-224.

[17]ALINAGHIAN M，SHOKOUH N.Multi-Depot multi-Compartment vehicle routing problem，solved by a hybrid adaptive large neighborhood search[J].Omega，2018，76：85-99.

[18]GOVINDAN K，JAFARIAN A，KHODAVERDI R，et al.Two-echelon multiple-vehicle location-routing problem with time windows for optimization of sustainable supply chain network of perishable food [J].Production economics，2014（152）：9-28.

[19]侯玉梅，賈震環(huán).帶軟時間窗整車物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學(xué)報，2015，30（2）：24-28.

[20]劉炎寶，王珂，楊智勇，等.考慮碳排放與新鮮度的冷鏈物流配送路徑優(yōu)化[J].江西師范大學(xué)學(xué)報，2019，43（2）：188-195.

[21]譚波.農(nóng)產(chǎn)品配送路徑最優(yōu)化問題研究[J].技術(shù)與方法，2014，33（3）：173-175.

[22]李雅萍.鮮活農(nóng)產(chǎn)品冷鏈物流配送路徑優(yōu)化研究[J].價值工程，2013（31）：25-28.

Research on the Vehicle Routing Problem in the Distribution of?Fresh Agricultural Products Based on Customer Satisfaction

DU Zhiping，HU Yongbiao，CHEN Yongli

（School of Logistics，Beijing Wuzi University，Beijing 101149）

Abstract：In this paper，considering the factors of customer satisfaction，numerous customer terminals，time window restrictions and characteristics of fresh agricultural products，the vehicle routing problem（VRP） model in the terminal delivery of fresh agricultural products is built with the goal of minimum terminal logistics cost.Modified hybrid genetic algorithm is adopted for model solution and practical cases are used to verify the reasonableness of model and feasibility of algorithm.The results show that when the customer satisfaction falls in the range of 80% to 95%，the higher the customer satisfaction is，the greater the value of distribution cost objective function is，but the increase in the distribution cost is not big.If the customer satisfaction exceeds 95%，the value of distribution cost objective function will rise sharply.The paper provides a new perspective on the delivery of fresh agricultural products based on customer satisfaction.

Keywords：fresh agricultural products;terminal distribution path;hybrid genetic algorithm