基于新鲜度和配送成本的易腐食品配送路径

李畅 陈淮莉

摘要：为解决企业在制定易腐食品配送计划时难以权衡配送总成本与交付产品的新鲜度的问题，建立以配送总成本最低和交付产品平均新鲜度最大为目标，带时间窗的易腐食品配送路径规划模型。采用自适应差分进化（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.

（编辑 贾裙平）