基于客戶滿意度的生鮮農產品末端配送的VRP研究

杜志平 胡永彪 陳永立

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

關 鍵 詞：生鮮農產品;末端配送路徑;混合遺傳算法

中圖分類號：F326 文獻標識碼：A 文章編號：2096-7934（2020）01-0113-16

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

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

一、文獻綜述

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

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

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

二、問題的描述和數學模型的建立

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

（一）模型的基本假設

依據對某企業的現實情況進行分析，將現實問題抽象為數學模型，對模型設置了如下假設：

（1）本文研究的是單一的冷鏈配送中心與末端大規模客戶的問題;

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

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

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

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

（6）車輛如果出發，所服務的客戶的先后順序確定，不會有新的客戶進入規劃的路線中;

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

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

（9）生鮮農產品在配送的過程中一直保持恒溫狀態，損耗只與配送的時間有關，所配送產品為同一類產品，產品之間不相互影響。

（二）模型參數的描述

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

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

（3）n表示客戶的數量;

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

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

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

（7）dij是客戶點i到客戶點j的行駛距離;

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

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

（10）a1為貨物在運輸過程中的損耗系數;

（11）[E′i，L′i]表示客戶i預期到達的時間段;

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

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

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

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

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

0;否則

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

0;否則

（三）帶時間窗生鮮農產品末端配送模型的建立

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

1.客戶滿意度的處理

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

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所能接受到達的時間段，Li是客戶時間窗的上限;Ei是客戶時間窗的下限。其中β1、β2為客戶對時間的敏感系數，如果送達時間在客戶期望的時間段[E′i，L′i]， 則客戶點i的滿意度為100%。如果在其他的時間段送到貨，隨著與期望的時間偏離，客戶滿意度水平也會有一定的下降。

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

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

（2）

2.成本分析

（1）車輛的運輸成本

隨著行駛里程的增加，車輛的油耗費用也會增加。配送車輛的運輸成本還包括車輛的維修和保養等費用，運輸成本主要由車輛與客戶的位置距離決定。用Zy表示車輛的運輸成本，則配送車輛的運輸成本的數學表達式為：

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

（3）

（2）車輛的固定成本

配送車輛的固定成本不隨車輛運動的里程增加而改變，本文認為車輛的固定成本主要包括車輛人員的人工費用、車輛啟動一次的租金以及車輛的損耗等成本。用Zg表示車輛的固定成本，則配送車輛的固定成本的數學表達式為：

Zg=∑Kk=1cgk

（4）

（3）車輛的能耗成本

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

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

Zg=∑Kk=1cgk

（5）

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

b.裝卸時的能耗成本

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

（6）

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

c.車輛的能耗成本

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

Zh=Zh1+Zh2

（7）

d.貨損成本

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

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

（8）

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

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

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

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

（9）

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

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

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

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

（10）

根據以上分析，違反時間窗的懲罰總成本的表達式為：

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

（11）

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

3.模型的建立

本文的目標是在滿足客戶需求量、時間窗等條件下，求總成本最小的配送方案，其中成本包括生鮮農產品的易腐性所造成的配送貨損成本、車輛固定成本、隨里程而遞增的運輸成本、配送時冷凍設備消耗的能耗成本和懲罰成本。以總成本最小為原則來構建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）表示目標函數;式（13）表示每個客戶只有一個車輛服務，每個車輛都是從配送中心出發，最終再回到配送中心;式（14）、式（15）為每個點的有且僅有一次經過約束;式（16）貨物送達的時間在時間窗的范圍內;式（17）貨物的重量不能超過車輛的載重量;式（18）表示車輛的容積約束限制;式（19）表示客戶時間窗的處理過程;式（20）表示客戶的滿意度不低于一定的值;式（21）、式（22）是決策變量的0-1約束。

三、算法設計

（一）K-means聚類分析的設計

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

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

（23）

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

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

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

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

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

（5）將不滿足條件的客戶點加入臨近且符合約束條件的區域內，并執行（7）。

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

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

K-means聚類是一個反復迭代的分類過程，在聚類過程中，觀測樣本所屬的類會不斷地進行調整，直到達到穩定為止。

（二）遺傳算法設計

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

1.染色體編碼方案設置

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

2.初始化染色體種群

本文不僅考慮客戶時間窗的限制，還要考慮末端大規模客戶點問題以及每個客戶點的滿意度問題，需要在滿足每個客戶點滿意度的條件下進行。一般情況下初始化種群都是隨機的，隨機產生初始化種群可以避免種群的單調性，但會增加迭代的次數，增加運行的時間，可以避免局部最優。本文假設群體規模N為100，利用initializega代碼產生100個個體，不斷地產生初始個體，指導初始群體的個體為N為止，形成初始種群，初始群體的表達式如下：

R0=（r1，r2，…，rn）

（24）

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

通過運行initializega代碼，隨機產生100條車輛的可行配送路線，構成配送路線優化問題解的初始種群，完成了該問題解集的初始化過程。initializega函數的部分代碼：

Function（t）=initializega（popsize，citynum）

for i=1：popsize

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

3.適應度函數設計

適應度函數是評價遺傳算法中染色體性能的唯一指標，評價每條染色體的優劣以及每條配送路線優化的好壞。適應度函數值越大，說明配送路線優化效果越好，帶時間窗生鮮農產品末端配送路徑優化的客戶滿意度越高和配送總成本優化得越好。客戶的滿意度一定時，適應度函數值最大的對應配送路徑也是最優化的。帶時間窗的生鮮農產品末端配送路徑的適應度函數如下：

fi=Z′Z

Pi=fi∑Nn=1fi

（25）

minZ=Zy+Zg+Zh+Zs+Zc

（26）

其中fi表示第i條染色體的適應度函數;Pi表示個體選擇概率的分布;Z′表示當前染色體配送的總成本。適應度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.遺傳算子設計

（1）選擇算子

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

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

Pi=fi∑nj=1fj

（27）

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

Function ret =Select（individual，sizepop）

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

% individuals ?input ;種群信息

% sizepop ? input;種群規模

% ret ? ? output;經過選擇后的種群

fitness1=1/individuals.fitness;

sumfitness =sum（fitness1）;

sumf=fitness1/sumfitness;

index=[];

for i=1：sizepop ?%轉sizepop次輪盤

pick=rand;

while pick=0

pick=rand;

end

for j=1：zizepop

pick=pick-sumf（j）

if pick <0

index=[index（j）]

break;%尋找落入的區間

end

end

end

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

individuals.fitness= individuals.fitness（index）

ret = individuals;

（2）交叉算子

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

第一，父代的染色體r1和r2隨機地選擇一段交叉的區域。

第二，r1和r2的交叉區域進行互換，并形成一定的映射關系。

第三，將交叉區域外并且不存在映射關系的區域的數值直接復制到子代中。

第四，將交叉區域外的數值且存在映射關系的進行交叉替換，并得到子代的染色體r1′和r2′。

（3）變異算子

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

5.終止條件

混合遺傳算法是一個較為復雜的算法，對于終止條件主要有兩種情況：第一種是給定一個最大的遺傳迭代次數，算法迭代到最大次數為止;第二種是要求進化的偏差小于所規定的下限。經過幾次試驗后，本文采用算法迭代到最大次數為止，發現當迭代次數達到200時，目標函數值不再發生變化，達到穩定。

四、算例分析

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

（一）算例分析數據準備

根據某生鮮農產品公司的配送中心和客戶點的位置，本文在對客戶點與配送點之間的距離上采用歐式距離進行測度。

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

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

（二）模型的求解

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

在客戶滿意度為80%的條件下，計算結果表明完成配送任務需要車輛的數量為4輛，運輸總成本為546.5元，貨損成本為160.6為元，能耗成本為304.9元，車輛固定成本為600元，以及懲罰成本為91.0元，最后得出末端配送總成本為1703.0元。各項成本函數值的末端配送情況以及客戶滿意度下輸出的結果匯總如表2、表3所示。

（三）優化的效果分析

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

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

（四）客戶滿意度和末端配送成本優化

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

當客戶滿意度為95%時，對混合遺傳算法進行運算，以下是車輛路徑輸出圖和優化迭代圖，如圖5所示。

在客戶滿意度為95%的條件下，輸出的路徑圖、得出優化結果的迭代次數、運行的時間和目標的函數值如表6所示。

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

在交叉率為0.8、變異率為0.1以及迭代次數為200的情況下，客戶的滿意度每次增加5%，從80%增加到100%，通過圖6發現從客戶滿意80%增加到95%這個區間，目標函數值也在緩緩地增加，變化不是很明顯，配送成本的增長率增加得較少，也就是說物流成本上升得不是很快，但客戶的滿意度從95%提高到100%時，目標函數值陡然上升，說明物流成本突然增加，那么可以認為帶時間窗生鮮農產品末端配送中，客戶滿意度為95%這個關鍵點具有重要的作用，其總物流成本為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;其配送方案是合理的。

五、總結

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

參考文獻：

[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]李昌兵，汪爾晶，袁嘉彬.物聯網環境下生鮮農產品物流配送路徑優化研究[J].商業研究，2017（4）：1-9.

[6]李曉.基于大數據的生鮮農產品電商配送優化研究[J].農村經濟，2018（6）：106-109.

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

[8]吳靜旦.基于O2O模式的生鮮農產品冷鏈物流配送網絡創新研究[J].農業經濟，2019（7）：133-134.

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

[10]楊磊，肖小翠，張智勇.需求依賴努力水平的生鮮農產品供應鏈最優定價策略[J].系統管理學報，2017（1）：142-153.

[11]王淑云，姜櫻梅，王憲杰.基于配送中心的三級冷鏈一體化庫存模型[J].系統管理學報，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].中國管理科學，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]侯玉梅，賈震環.帶軟時間窗整車物流配送路徑優化研究[J].系統工程學報，2015，30（2）：24-28.

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

[21]譚波.農產品配送路徑最優化問題研究[J].技術與方法，2014，33（3）：173-175.

[22]李雅萍.鮮活農產品冷鏈物流配送路徑優化研究[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