基于新鮮度和配送成本的易腐食品配送路徑

李暢 陳淮莉

摘要：為解決企業在制定易腐食品配送計劃時難以權衡配送總成本與交付產品的新鮮度的問題，建立以配送總成本最低和交付產品平均新鮮度最大為目標，帶時間窗的易腐食品配送路徑規劃模型。采用自適應差分進化（differential evolution， DE）算法求解模型，通過數值算例驗證模型和算法的有效性。與基本DE算法和基本蟻群算法的求解結果進行對比，自適應DE算法的求解結果更優，收斂速度更快。求得的帕累托解集表明配送總成本與交付產品平均新鮮度相悖，增加少量的配送成本可以使交付產品的平均新鮮度得到大幅提升。對易腐食品保質期、時間窗寬度和車輛裝載量進行靈敏度分析，為企業在不同配送情景下在配送總成本與交付產品的平均新鮮度之間的權衡提供參考。

關鍵詞：易腐食品; 新鮮度; 成本; 配送路徑; 差分進化（DE）算法

中圖分類號： ?U492.31

文獻標志碼： ?A

Abstract：In order to solve the problem enterprises faced with when making the highly perishable food distribution planning that it is difficult to balance between the total cost of distribution and the freshness of delivery products， a distribution route planning model of perishable food with time window is established with the objectives of the minimum total cost of distribution and the maximum average freshness of pro-ducts. The adaptive differential evolution （DE） algorithm is used to solve the model. A numerical example is used to verify the validity of the model and the algorithm. Compared with the results of the basic DE algorithm and the basic ant colony algorithm， the adaptive DE algorithm has better results and faster convergence speed. The obtained Pareto solution set shows that the relationship between the total cost of delivery and the average freshness of delivery products are contrary. By increasing a small amount of distribution cost， the average freshness of delivery products can be greatly improved. Sensitivity analysis on perishable food shelf-life， time window width and vehicle loading provides reference for enterprises to balance between the total cost of delivery and the average freshness of delivered products under different distribution scenarios.

Key words：perishable food; freshness; cost; distribution route; differential evolution （DE） algorithm

0 引 言

隨著人民群眾生活水平的提高，食品安全也越來越受關注。消費者在購買易腐食品（如鮮奶、鮮肉、快餐和烘培食品等）時不僅會考慮價格，而且會關注食品的新鮮度[1]。該類食品的新鮮度在生產加工結束后便開始衰減，在配送過程中繼續不斷下降。因此，為提高消費者的滿意度，易腐食品企業不能僅關注生產配送成本，還需要考慮交付給消費者的食品的新鮮度。本文研究同時考慮配送總成本和交付產品新鮮度的易腐食品配送路徑模型，以適應企業需要。

近年來，易腐食品的配送路徑問題已引起國內外學者的廣泛關注：SHUKLA等[2]研究了以總成本最低為目標，帶時間窗的易腐食品配送路徑問題，并采用免疫算法求解;AMORIM等[3]研究了有多個時間窗、異質車輛的易腐食品配送路徑優化問題，并采用自適應大規模鄰域搜索算法求解該問題;CHEN等[4]建立了以供應商預期利潤最大為目標的易腐食品生產配送調度模型;MA等[5]針對易腐食品終端配送問題，提出了時變路網下基于訂單選擇、帶時間窗的易腐食品配送路徑優化模型;OSVALD等[6]對新鮮蔬菜的配送路徑問題進行了研究，考慮了配送過程中車輛速度的時變性和蔬菜的易腐性對配送路徑的影響;邵舉平等[7]建立了以配送成本最低和客戶滿意度最大為目標，帶時間窗的易腐食品車輛路徑模型，并通過配送的準時性反映客戶的滿意度。上述文獻大部分以配送總成本最低或預期利潤最高作為優化目標，采用貨損成本表示易腐食品的易腐性帶來的損失，從經濟層面優化易腐食品的配送路徑，但沒有考慮交付產品的新鮮度水平。

在以往的針對易腐食品配送路徑的研究中，考慮交付產品新鮮度的文獻較少：SONG等[8]研究了以客戶滿意度最大為目標，采用異質車輛的易腐食品配送路徑優化問題，以交付產品的新鮮度衡量客戶滿意度，但是沒有考慮配送成本問題;楊曉芳等[9]建立了考慮新鮮度的易腐食品配送網絡模型，采用途中的貨損成本表示配送產品新鮮度的降低，并證明采用該模型能夠比采用不考慮貨損的傳統模型節約更多物流成本，但是該模型也只是從經濟角度優化易腐食品的配送網絡。

綜上，易腐食品配送路徑在經濟層面的優化已取得豐碩的研究成果，但是至今還沒有將交付產品新鮮度最大與配送總成本最低兩個目標相結合的研究。為此，本文在前人研究的基礎上，以交付產品的平均新鮮度最大和配送總成本最低為目標對高度易腐食品配送路徑進行規劃建模，采用自適應差分進化（differential evolution， DE）算法進行求解，通過數值算例驗證模型和算法的有效性，并通過對相應參數進行靈敏度分析，為企業在不同配送情景下在配送總成本與交付產品的平均新鮮度之間的權衡提供參考。

1 模型構建

1.1 問題描述

一食品加工配送中心每天早上根據前一天的客戶訂單進行配送服務，雖然各客戶需求量和配送時間窗不同，但是客戶訂單均能得到滿足。產品新鮮度在裝車時最大，在配送過程中不斷下降，但是交付給消費者的產品不會超過其保質期。以交付產品的平均新鮮度最大和配送總成本最低為目標進行配送路徑的求解。

1.2 模型假設

加工配送中心用同一類型的車輛進行配送，車輛運能充足;不考慮配送車輛裝載時間，車輛從加工配送中心出發完成配送任務后需要返回;不允許分批配送，每位客戶至多由一輛車進行配送;各客戶和加工配送中心的地理坐標已知;車輛勻速行駛。

1.3 符號定義

2 模型求解

車輛路徑問題（vehicle routing problem， VRP）問題是NP難題，目前求解該問題的算法主要有遺傳算法[11]、蟻群算法[12]、粒子群算法[13]等。DE算法最早由STORN和PRICE提出，是一種基于群體差異的啟發式隨機搜索算法。與現有算法相比，DE算法的優點是決定其性能的參數較少，解決復雜的全局優化問題的能力更強，魯棒性更強[14-15]。然而，基本DE算法存在收斂速度緩慢、計算量大、易早熟等問題，因此本文采用自適應DE算法對模型進行求解。DE算法不能直接求解多目標問題，本文用ε-約束法（Epsilon constraint method， ECM）對雙目標模型進行求解[13]，求解流程見圖1。

2.2.5 交叉操作

將變異個體Vi，g與父代個體Xi，g進行交叉操作，產生試驗個體Ui，g（i=1，2，…，H;g=1，2，…，G）。為保證Ui，g中至少有一個基因位的基因來自變異個體Vi，g，以免與父代個體Xi，g相同，首先通過隨機選擇使Ui，g的基因中至少有一位由變異個體Vi，g的等位基因貢獻，Ui，g的其他基因位的基因利用交叉概率Bi（Bi∈[0，1]）決定是由Vi，g的等位基因貢獻還是由Xi，g的等位基因貢獻（若Ui，g的其他基因位上在[0，1]區間內的隨機生成數大于Bi，則該基因位由Xi，g的等位基因貢獻，否則由Vi，g的等位基因貢獻）。

2.2.6 合法化處理操作

由于VRP的編碼有一定的取值范圍，交叉處理后得到的試驗個體Ui，g的某些基因位的基因值可能超出其取值范圍;若超出則表明這些試驗個體對應的運輸方案不能滿足車輛最大運輸容量的約束條件，這類個體統稱為“不合法個體”。為提高算法的優化效率，本文采用第2.2.2節所述的初始化方式重新生成新的個體，用于取代“不合法個體”。

2.2.7 選擇操作

采用“貪婪策略”根據適應值的大小在試驗個體Ui，g和父代個體Xi，g中進行篩選，適應值較優者保存到下一代。

2.2.8 參數的自適應策略

3 算例分析

某食品加工配送中心每天早上根據前一天的客戶訂單為本市30家便利店提供蔬菜沙拉的配送服務，各便利店的地理位置坐標、接受服務的時間窗、需要的服務時間和當天的需求量見表1。表1中，節點0表示加工配送中心，節點1～30分別表示30 ?家便利店。加工配送中心所使用的冷藏車最大裝載量為2 000盒，起動的固定成本為100元，行駛單位路程的運輸成本為1.8 元/km，行駛速度為40 km/h;車輛晚到的懲罰系數為50元/h;蔬菜沙拉的保質期為12 h。在本文算法中，種群規模H為150，最大迭代次數為600次，uF和uB初始值均為0.5。采用MATLAB R2016a編程實現本文算法。

首先通過自適應DE算法對f2進行求解，求得最大新鮮度值為90.1%，然后將其作為約束條件，并逐步放寬約束，得到帕累托解集。為驗證算法的有效性，將本文算法的求解結果與基本DE算法和基本蟻群算法的求解結果進行對比，表2為在交付產品的平均新鮮度f2≥75.1%和f2≥85.1%的約束下以配送總成本最低為目標進行尋優時各算法的求解結果，圖2為在f2≥75.1%的約束下以配送總成本最低為目標進行尋優時各算法的進化曲線。

4 靈敏度分析

分別對高度易腐食品的保質期、時間窗寬度和車輛裝載量進行靈敏度分析，以第3節所構造的算例為例，研究不同情況下交付產品的平均新鮮度與配送總成本之間的關系。

4.1 食品保質期的影響

將高度易腐食品的保質期分別設置為8 h、12 h和16 h，其他參數不變，求得的帕累托解集見圖4。

5 結 論

本文建立了同時考慮交付產品的平均新鮮度和配送總成本的雙目標并帶時間窗的高度易腐食品配送路徑模型;根據該模型的特點采用自適應差分進化（DE）算法進行求解;通過數值算例驗證了模型和算法的有效性，并與基本DE算法和基本蟻群算法的求解結果進行對比，證明了自適應DE算法更適合該問題的求解。求解結果表明，本文提出的雙目標明顯相悖。通過靈敏度分析可知，高度易腐食品的保質期越長、時間窗寬度越大對配送服務越有利，車輛裝載量控制在一定范圍內可以節約成本。后續研究可以考慮引入異質車輛，并考慮配送過程中交通擁堵狀況及突發狀況對高度易腐食品配送路徑的影響，也可以對高度易腐食品的生產排程和配送路徑進行協同優化研究。

參考文獻：

[1]吳瑤， 馬祖軍. 時變路網下帶時間窗的易腐食品生產–配送問題[J]. 系統工程理論與實踐， 2017， 37（1）： 172-181. DOI： 10. 12011/1000-6788（2017）01-0172-10.

[2]SHUKLA M， JHARKHARIA S. Artificial immune system-based algorithm for vehicle routing problem with time window constraint for the delivery of agri-fresh produce[J]. Journal of Decision Systems， 2013， 22（3）： 224-247. DOI： 10. 1080/12460125. 2013. 810859.

[3]AMORIM P， PARRAGH S N， SPERANDIO F， et al. A rich vehicle routing problem dealing with perishable food： a case study[J]. TOP， 2014， 22（2）： 489-508. DOI： 10.1007/s11750-012-0266-4.

[4]CHEN H K， HSUEH C F， CHANG M S. Production scheduling and vehicle routing with time windows for perishable food products[J]. Computers & Operations Research， 2009， 36（7）： 2311-2319. DOI： 10.1016/j.cor.2008.09.010.

[5]MA Zujun， WU Yao， DAI Ying. A combined order selection and time-dependent vehicle routing problem with time windows for perishable product delivery[J]. Computers & Industrial Engineering， 2017， 114： 101-113. DOI： 10. 1016/j.cie.2017.10.010.

[6]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. DOI： 10.1016/j.jfoodeng.2007.07.008.

[7]邵舉平， 曹倩， 沈敏燕， 等. 生鮮農產品配送中帶時間窗的VRP模型與算法[J]. 工業工程與管理， 2015（1）： 122-127.

[8]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. DOI： 10.1016/j.jfoodeng.2015.08.027.

[9]楊曉芳， 姚宇， 付強. 基于新鮮度的冷鏈物流配送多目標優化模型[J]. 計算機應用研究， 2016， 33（4）： 1050-1053. DOI： 10.3969./j.issn.1001-3695.2016.04.019.

[10]吳忠和， 陳宏， 趙千， 等. 時間約束下鮮活農產品供應鏈應急協調契約[J]. 系統管理學報， 2014， 23（1）： 49-56.

[11]BARKAOUI M， BERGER J， BOUKHTOUTA A. Customer satisfaction in dynamic vehicle routing problem with time windows[J]. Applied Soft Computing， 2015， 35： 423-432. DOI： 10.1016/j.asoc.2015.06.035.

[12]SCHYNS M. An ant colony system for responsive dynamic vehicle routing[J]. European Journal of Operational Research， 2015， 245（3）： 704-718. DOI： 10.1016/j.ejor.2015.04.009.

[13]陳玉光， 陳志祥. 基于準時送貨和最小耗油的配送車輛路徑問題研究[J]. 中國管理科學， 2015， 23（s1）： 156-164.

[14]周輝仁， 唐萬生， 王海龍. 基于差分進化算法的多旅行商問題優化[J]. 系統工程理論與實踐， 2010， 30（8）： 1471-1476.

[15]ZHANG Jingqiao， SANDERSON A C. JADE： adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Computation， 2009， 13（5）： 945-958.

（編輯 賈裙平）