李暢 陳淮莉

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

關(guān)鍵詞：易腐食品; 新鮮度; 成本; 配送路徑; 差分進(jìn)化（DE）算法

中圖分類號： ?U492.31

文獻(xiàn)標(biāo)志碼： ?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 引 言

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

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

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

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

1 模型構(gòu)建

1.1 問題描述

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

1.2 模型假設(shè)

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

1.3 符號定義

2 模型求解

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

2.2.5 交叉操作

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

2.2.6 合法化處理操作

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

2.2.7 選擇操作

采用“貪婪策略”根據(jù)適應(yīng)值的大小在試驗(yàn)個(gè)體Ui，g和父代個(gè)體Xi，g中進(jìn)行篩選，適應(yīng)值較優(yōu)者保存到下一代。

2.2.8 參數(shù)的自適應(yīng)策略

3 算例分析

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

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

4 靈敏度分析

分別對高度易腐食品的保質(zhì)期、時(shí)間窗寬度和車輛裝載量進(jìn)行靈敏度分析，以第3節(jié)所構(gòu)造的算例為例，研究不同情況下交付產(chǎn)品的平均新鮮度與配送總成本之間的關(guān)系。

4.1 食品保質(zhì)期的影響

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

5 結(jié) 論

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

參考文獻(xiàn)：

[1]吳瑤， 馬祖軍. 時(shí)變路網(wǎng)下帶時(shí)間窗的易腐食品生產(chǎn)–配送問題[J]. 系統(tǒng)工程理論與實(shí)踐， 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]邵舉平， 曹倩， 沈敏燕， 等. 生鮮農(nóng)產(chǎn)品配送中帶時(shí)間窗的VRP模型與算法[J]. 工業(yè)工程與管理， 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]楊曉芳， 姚宇， 付強(qiáng). 基于新鮮度的冷鏈物流配送多目標(biāo)優(yōu)化模型[J]. 計(jì)算機(jī)應(yīng)用研究， 2016， 33（4）： 1050-1053. DOI： 10.3969./j.issn.1001-3695.2016.04.019.

[10]吳忠和， 陳宏， 趙千， 等. 時(shí)間約束下鮮活農(nóng)產(chǎn)品供應(yīng)鏈應(yīng)急協(xié)調(diào)契約[J]. 系統(tǒng)管理學(xué)報(bào)， 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]陳玉光， 陳志祥. 基于準(zhǔn)時(shí)送貨和最小耗油的配送車輛路徑問題研究[J]. 中國管理科學(xué)， 2015， 23（s1）： 156-164.

[14]周輝仁， 唐萬生， 王海龍. 基于差分進(jìn)化算法的多旅行商問題優(yōu)化[J]. 系統(tǒng)工程理論與實(shí)踐， 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.

（編輯 賈裙平）