2. 电子科技大学 经济与管理学院,成都 611731
2. School of Economics and Management, University of Electronic Science and Technology of China, Chengdu~611731, China
生鲜商品物流在配送过程中极易出现商品腐烂、变质等问题, 且在服务时效性和商品鲜活性等方面具有更高的要求.研究带时间窗和温控特征的生鲜商品物流配送问题, 有助于完善冷链可追溯体系以及促进国民经济持续增长和保证社会和谐安定.国内外学者在生鲜商品物流配送问题方面的研究主要集中在考虑温控特征的生鲜商品配送问题和易腐商品配送问题研究两个方面.
基于温度控制的物流配送相关问题已引起学者的广泛关注, Hsiao等[1]应用遗传算法研究了多种类多温度的食品贮藏车辆配送优化问题. Hsu等[2]基于蓄冷箱式的多温共配系统建立了0-1整数规划模型, 对多温共配系统的最佳配送周期、车队规模和配送路线进行了优化研究. Rai等[3]研究了考虑碳排放的货车配送在两种不同温度控制下运营成本和耗能方面的异同. Hsu等[4]考虑动态需求和多温控技术, 对多品种食品配送的问题进行了建模研究. Aung等[5]研究了基于多温度冷藏的商品聚类区域划分问题, 得到了多种商品存储的最佳温度控制.综上研究文献可以发现, 生鲜商品的多温控特性为物流配送过程中的客户点聚类问题和配送调度模型构建提供了研究切入.
在易腐商品配送研究方面, 吴瑶等[6]研究了时变路网环境下带时间窗的易腐食品集成生产-配送优化问题. Amorim等[7]提出一种多目标优化模型, 并应用混合MOEA方法研究了带时间窗的易腐商品车辆路径问题. Wang等[8]提出一种基于帕累托变量邻域搜索的两阶段启发式算法, 研究了易腐品的多目标车辆路径问题. Accorsi等[9]考虑外界环境温度提出一种混合整数线性规划模型, 研究了易腐商品配送过程中的能耗变化, 研究结果表明合理的温度控制能有效降低易腐产品配送过程中的能耗和成本. Devapriya等[10]提出一种基于进化的启发式算法, 研究了易腐商品生产和配送的集成问题.在易腐商品运输优化问题研究中, 冷藏运输车辆比通用型车辆在物流成本、顾客满意度、交付商品的新鲜度等方面具有更高的要求.由上述相关文献可知, 当前对于生鲜商品物流配送的研究主要集中在考虑温度控制、时间窗特征的配送优化问题[11-13], 而基于温度控制并结合生鲜价值损失进行生鲜配送相关问题的研究还有待进一步深入.
本文研究在生鲜商品物流配送过程中, 结合不同温度控制下生鲜商品价值损失的变化特点, 构建包含生鲜商品配送的物流成本和生鲜商品价值损失的双目标优化函数模型.设计了一种基于K-means聚类的遗传-禁忌搜索混合算法(GA-TS), 进而研究了带时间窗和温度控制的生鲜商品物流配送车辆路径问题, 并通过温度参数变化(-2℃~5℃)和不同聚类结果(3类~7类)的敏感性分析研究确定了不同生鲜商品在配送过程中的最佳配送温度和最佳聚类数.
1 问题描述生鲜商品在配送过程中会随着配送时间的增长、配送环境温度的升高产生过多成本消耗, 为了有效控制生鲜商品价值衰减和降低生鲜商品配送的物流成本, 需要综合考虑生鲜商品的温控条件和生鲜配送的物流成本进行合理运输调度.
图 1为基于时间窗和温度控制的生鲜商品物流配送优化前后对比图, 图 1(a)表示生鲜商品物流配送优化前, 由于客户(零售商)需求的各类生鲜商品存在不同的温度控制和服务时间窗要求, 生鲜物流配送中心往往根据客户需求的商品类型和时间窗单独安排冷藏车进行配送服务, 但考虑到冷藏车数量的有限性, 现有的配送方式往往无法满足部分客户的需求且物流配送成本较高.图 1(b)表示生鲜商品物流配送优化后, 基于生鲜商品需求、服务时间窗和温控特性等进行客户聚类, 形成若干具有相似属性的客户点聚集配送单元, 进行生鲜商品的物流配送服务, 并对每条配送线路进行合理的温度控制, 进而降低生鲜商品在配送过程中的价值损失和物流配送成本.
本模型假定生鲜企业将多种生鲜商品储存于配送中心, 接收到一定数量的客户订单后, 优化配送路线并快速向各需求客户进行配送服务[14-15].
本模型假设如下:
1) 配送中心拥有有限数量的同型冷藏配送车辆, 装载容量为定值, 且车辆从配送中心出发完成配送任务后返回配送中心;
2) 每位客户可订购一定种类和数量的生鲜商品;
3) 配送中心的最大配送量可以满足所有客户的总需求, 每位客户仅由一辆冷藏配送车访问;
4) 冷藏车配送生鲜商品到客户后的卸货服务时间忽略不计.
2.2 符号定义本文涉及到的变量和符号如表 1所示.
本文以配送企业的物流成本Z1和生鲜商品的价值损失Z2最小为优化目标, 建立生鲜商品的物流配送优化模型如下:
(1) |
(2) |
约束条件为
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |
(10) |
(11) |
(12) |
(13) |
其中: TC为运输成本, 即配送车辆将生鲜商品送达客户的运输成本, 且有
(14) |
TCC为温控成本, 即配送车辆在配送过程中为保持低温配送环境所消耗的成本, 且有
(15) |
PC为惩罚成本, 即配送车辆交付商品时间未满足客户指定时间窗需要支付的成本, 有
(16) |
式(1)表示配送中心为客户提供配送服务的物流成本; 式(2)表示生鲜商品在配送过程中的价值损失; 式(3)表示客户的生鲜商品需求总量不超过配送中心最大配送量; 式(4)和(5)表示所有客户的需求得到满足; 式(6)表示车辆k配送生鲜商品的数量不超过车辆容量; 式(7)表示消除配送路径上的子回路; 式(8)和(9)表示对于任一客户点, 仅能有一辆车访问并离开; 式(10)表示生鲜配送车辆将商品送达客户后必须离开; 式(11)表示配送过程的连续性; 式(12)和(13)表示变量约束.
3 基于K-means聚类的GA-TS混合算法 3.1 算法过程描述本文构建的带时间窗和温度控制的生鲜商品配送优化模型含有较多变量和约束条件, 求解规模较大且为双目标函数, 鉴于此, 提出一种基于K-means聚类的GA-TS混合算法用于求解该模型.
GA-TS混合算法集成了GA较好的全局搜索能力和TS的局部搜索能力[16], 可以在一定程度上避免局部最优解, 进而提高算法的全局收敛性能.混合算法操作流程见图 2.
在遗传算法中根据目标函数设计带时间窗和温控约束的适应度函数能有效衡量种群中个体优化过程的替代性.本文的适应度函数如下所示:
(17) |
其中: Zmin为目标函数中物流成本和价值损失组合优化的最小取值, 本文采用比较f(x)的方法得到适应度值, 然后将每次得到的适应度值进行遗传操作.
3.3 基于K-means聚类的GA-TS混合算法步骤根据上文的改进方法, 基于K-means聚类的GA-TS混合算法具体实现过程如下.
step 1:基于客户空间位置、客户需求商品的温度控制和时间窗约束, 应用改进的K-means算法完成客户点聚类操作, 确定q个聚类单元[17].
如图 3所示, 将配送时间Y(即时间轴)分成3个时间段t1、t2、t3, 将地理位置和温控范围分别表示成X轴、Y轴和温度轴.建立一个包含客户时间窗的禁忌集合A, 当客户不满足禁忌集合A时, 考虑进行客户聚类操作.在每个椭圆的空间区域内, 若客户要求的时间窗在同一个时间段内, 则考虑客户聚类到一个配送单元.改进的K-means算法过程如下:
1) 建立一个禁忌集合A, 当客户属性不满足集合A时, 客户间能够参与聚类;
2) 导入客户的相应数据;
3) 将数据矩阵转换为数据向量;
4) 基于K-means聚类算法确定初始聚类单元数为q, 并选择q个初始聚类中心;
5) 判断待聚类客户与已聚类客户间是否满足禁忌集合A, 若不满足或部分满足, 则将每个客户分配到其聚类中心最接近该客户的聚类单元, 否则转至7);
6) 更新每个聚类单元的中心;
7) 增加聚类单元数为q=q+1, 并生成新的聚类单元和中心;
8) 重复6)和7), 直到每个客户的集群关系不再更改.
step 2:聚类得到初始个体染色编码生成初始种群, 给定参数包括种群规模inn、最大迭代次数maxgen、交叉概率Pc、变异概率Pm.
step 3:计算种群中个体的适应度值, 本文将配送车辆的运输成本、温控成本、违反时间窗的惩罚成本之和及生鲜商品的价值损失设定为目标函数, 根据建立的目标函数确定适应度函数f(x).
step 4:考虑客户点的时间窗约束, 从种群中选择出优秀的个体作为下一代的父体, 并采用轮盘赌方法进行选择操作.
step 5:根据交叉概率和变异概率对种群进行交叉操作、变异操作形成新的种群, 对于违反时间窗的子代以惩罚成本的形式产生新的适应度值f(x).
step 6:将遗传算法操作得到的染色体进行禁忌搜索, 生成初始邻域解并确定候选解, 运用藐视准则更新禁忌表, 进行禁忌迭代寻优.
step 7:重复step 3和step 6进行循环操作, 算法迭代至最大迭代次数maxgen后, 结束并输出最优结果.
3.4 算法检验为了验证基于K-means聚类的GA-TS混合算法的有效性, 将GA-TS混合算法与混合遗传算法(HGA)[18]、多目标粒子群算法(MO-PSO)[19]和改进的蚁群优化算法(IACO)[20]进行比较.分别给定80、100、120个客户点实验数据的各项参数, 如表 2所示.应用不同算法计算不同求解规模下的物流成本及价值损失, 4种算法计算结果如表 3所示.
由表 3可见, 本文提出的基于K-means聚类的GA-TS算法求解得到不同规模的物流成本平均值比HGA算法减少7.3 %, 比MO-PSO算法减少5.5 %, 比IACO算法减少5.6 %, GA-TS计算出的价值损失平均值比HGA算法减少26.5 %, 比MO-PSO算法减少17.6 %, 比IACO算法减少10.9 %.此外, 由t检验和p值统计分析可得出, 基于K-means聚类的GA-TS算法求解得到的24组实例数据结果相对于其他3种算法的计算结果更稳定且具有明显优势.因此, 本文所提出的基于K-means聚类的GA-TS混合算法充分集成了遗传算法全局优化能力和禁忌搜索算法的局部搜索能力, 结果表明该混合算法具有更好的优化结果.
4 算例分析 4.1 实例相关数据以重庆市某配送中心(DC)及其服务的105个生鲜客户需求点(D1~D105)为例进行研究, 相应的地理位置分布如图 4所示.首先应用改进的K-means算法对客户进行聚类形成不同的配送单元, 得到的客户点配送聚类如表 4所示.
参数设置如下: inn=150, Pc= 0.9, Pm= 0.08, maxgen= 300, popsize=50, tsin = 10, Qk = 220, μ = 0.8, ν=50, σ= 6.2, θ1 =1.27, θ2 = 2.03, θ3 = 1.56, α1 = 0.15, α2=0.09, α3= 0.22, p1 =12, p2 = 15, p3= 9, fkw=0.129, 并将生鲜商品划分为3类进行研究.
4.2 结果及分析 4.2.1 温控成本的计算由于不同种类商品对温控要求不同, 冷藏车会根据商品特性设置合适的冷藏温度.结合热量变化的特征, 用COP表示能量与热量之间的转化比率, 有
(18) |
其中: TH为外界环境的温度, TL为温度控制调节的目标温度.绝对温度对应的物理量是热力学温度, 表示为T(K), 其对应的单位是开尔文, 符号为K.热力学温度T(K)与摄氏温度t的关系为
(19) |
若外界环境温度TH为25℃ (298 K), 温控目标温度TL为5℃ (278 K), 则应用式(18)可计算出不同温度下的COP值, 如表 5所示.假设外部环境温度为25℃, 5℃时的冷却成本为单位1, 那么4℃时的冷却成本系数为13.9/13.19=1.05, 同样方法可计算得到其他温度条件下的冷却成本系数.此外, 采用下式可计算得到不同温度下的单位温控成本gmw:
(20) |
在各配送单元内应用GA-TS混合算法计算求解生鲜商品配送的物流成本和价值损失的双目标组合优化配送方案, 进而获取各配送单元的配送线路, 并得到各配送单元的物流成本和价值损失值.计算得到各聚类单元内的优化方案如表 6所示.
本文的敏感度分析包括温度的敏感度分析和聚类方案的敏感度分析两个方面.温度的敏感度分析是假设客户时间窗、地理位置等属性不发生变化的条件下, 如果冷藏车的温度在一定区间内变化, 则在运输途中温控成本和价值损失均会发生改变, 从而影响物流成本和产生价值损失.由于不同种类的生鲜商品对不同温度下敏感系数不同, 导致商品的价值损失值有所差异.以配送单元1为例, 控制生鲜商品配送车辆温度在-2℃~5℃区间变化, 物流成本和价值损失变化如图 5所示.图 5中, 空白框为价值损失, 阴影框为物流成本.
由图 5可见, 当温度在-2℃~5℃区间变化时, 配送单元1的成本和价值损失都会随着温度的变化而发生改变.当温度为5℃时, 生鲜商品在配送过程中的物流成本最小、价值损失最大; 反之, 当温度为-2℃时, 生鲜商品由于处于低温环境价值损失最小, 但温控成本会增加导致物流成本增加.当温度设为-1℃, 物流成本较小, 生鲜商品价值损失也不高, 且能够满足消费者对生鲜商品的新鲜度要求.
当温度分别设为-2℃、-1℃、5℃时, 其物流成本与价值损失的关系如图 6所示.由图 6可见, 生鲜商品配送的物流成本和价值损失成悖反关系, B点相对于A点和C点明显具有更优性, 即-1℃是最佳冷藏温度, 此时调节温度上升或降低都不能使物流成本和价值损失综合方案更优.
聚类方案的敏感度分析主要是研究不同的聚类结果下应用本文构建的模型和所提出的GA-TS混合算法计算得到的车辆使用数、违反客户服务时间窗累积值、物流成本和价值损失.不同聚类方案的敏感度分析如表 7所示.由表 7可见, 随着聚类数的递增, 违反客户服务时间窗的累积值逐渐减少, 当聚类方案为4和5时, 对应的车辆使用数相同, 聚类方案为5时(38.7)对应的违反客户服务时间窗累积值优于聚类方案为4时(51.3).如果同时考虑不同聚类方案对应的物流成本和价值损失, 聚类方案为4、5和6时具有一定的可比性, 但结合帕累托优化理论[21], 可以选择出聚类结果为5时对应的配送方案最佳.
本文研究了温度控制下带时间窗的生鲜商品物流配送优化问题, 考虑到生鲜商品存在易腐性特征, 构建了以生鲜商品配送的物流成本最小和交付商品时的价值损失最小为目标的双目标优化模型.将影响生鲜商品质量衰减的温度因素与生鲜商品配送路线结合进行研究, 根据模型特征设计了一种GA-TS混合算法进行优化求解.
本研究通过模型求解对各类生鲜商品的运输配送路线、运输环境温度进行了优化设计, 验证了模型的可行性.将GA-TS混合算法与HGA算法、MO-PSO算法和IACO算法的求解结果对比分析, 验证了该算法的有效性和合理性.温度参数变化和不同聚类方案的敏感度分析结果可以作为模型对温度进行有效合理控制的依据.研究发现, 当温度在-2℃~5℃变化时, 配送单元1的物流成本和价值损失都会随之改变, 而考虑物流成本和价值损失的悖反关系, 结合帕累托优化理论, 选取-1℃为最佳的生鲜配送温度, 选取聚类结果5为最佳的聚类方案数.本文研究丰富了生鲜商品配送路径优化模型, 为生鲜商品配送研究提供了新的理论依据, 有较强的现实意义和应用价值.
[1] |
Hsiao Y H, Chen M C, Chin C L. Distribution planning for perishable foods in cold chains with quality concerns: Formulation and solution procedure[J]. Trends in Food Science & Technology, 2017, 61: 80-93. |
[2] |
Hsu C, Liu K. A model for facilities planning for multi-temperature joint distribution system[J]. Food Control, 2011, 22(12): 1873-1882. DOI:10.1016/j.foodcont.2011.04.029 |
[3] |
Rai A, Tassou S A. Environmental impacts of vapour compression and cryogenic transport refrigeration technologies for temperature controlled food distribution[J]. Energy Conversion and Management, 2017, 150: 914-923. DOI:10.1016/j.enconman.2017.05.024 |
[4] |
Hsu C I, Chen W T, Wu W J. Optimal delivery cycles for joint distribution of multi-temperature food[J]. Food Control, 2013, 34(1): 106-114. DOI:10.1016/j.foodcont.2013.04.003 |
[5] |
Aung M M, Chang Y S. Temperature management for the quality assurance of a perishable food supply chain[J]. Food Control, 2014, 40: 198-207. DOI:10.1016/j.foodcont.2013.11.016 |
[6] |
吴瑶, 马祖军. 时变路网下带时间窗的易腐食品生产-配送问题[J]. 系统工程理论与实践, 2017, 37(1): 172-181. (Wu Y, Ma Z J. Time-dependent production delivery problem with time windows for perishable food[J]. Systems Engineering - Theory & Practice, 2017, 37(1): 172-181.) |
[7] |
Amorim P, Almada-Lobo B. The impact of food perishability issues in the vehicle routing problem[J]. Computers & Industrial Engineering, 2014, 67: 223-233. |
[8] |
Wang X P, Wang M, Ruan J H, et al. The multi-objective optimization for perishable food distribution route considering temporal-spatial distance[J]. Procedia Computer Science, 2016, 96: 1211-1220. DOI:10.1016/j.procs.2016.08.165 |
[9] |
Accorsi R, Gallo A, Manzini R. A climate driven decision-support model for the distribution of perishable products[J]. Journal of Cleaner Production, 2017, 165: 917-929. DOI:10.1016/j.jclepro.2017.07.170 |
[10] |
Devapriya P, Ferrell W, Geismar N. Integrated production and distribution scheduling with a perishable product[J]. European Journal of Operational Research, 2017, 259(3): 906-916. DOI:10.1016/j.ejor.2016.09.019 |
[11] |
王万良, 黄海鹏, 赵燕伟. 基于车辆共享的软时间窗动态需求车辆路径问题[J]. 计算机集成制造系统, 2011, 17(5): 1056-1063. (Wang W L, Huang H P, Zhao Y W. Dynamic customer demand VRP with soft time windows based on vehicle sharing[J]. Computer Integrated Manufacturing Systems, 2011, 17(5): 1056-1063.) |
[12] |
严正峰, 梅发东, 葛茂根, 等. 基于模糊软时间窗的车间物料流路径优化方法[J]. 计算机集成制造系统, 2015, 21(10): 2760-2767. (Yan Z F, Mei F D, Ge M G, et al. Path optimization method of workshop logistics based on fuzzy soft time windows[J]. Computer Integrated Manufacturing Systems, 2015, 21(10): 2760-2767.) |
[13] |
Keizer M, Akkerman R, Grunow M, et al. Logistics network design for perishable products with heterogeneous quality decay[J]. European Journal of Operational Research, 2017, 262(2): 535-549. DOI:10.1016/j.ejor.2017.03.049 |
[14] |
李兵飞, 熊智勇, 张建业, 等. 不确定条件下速度时变VRPTW问题[J]. 控制与决策, 2017, 32(5): 804-810. (Li B F, Xiong Z Y, Zhang J Y, et al. Uncertain time-dependent vehicle routing problem with time window[J]. Control and Decision, 2017, 32(5): 804-810.) |
[15] |
刘明, 赵林度. 应急物资混合协同配送模式研究[J]. 控制与决策, 2011, 26(1): 96-100. (Liu M, Zhao L D. Mix-collaborative distribution mode of emergency materials[J]. Control and Decision, 2011, 26(1): 96-100.) |
[16] |
李妍峰, 李军, 高自友. 大规模领域搜索算法求解时变车辆调度问题[J]. 管理科学学报, 2012, 15(1): 22-32. (Li Y F, Li J, Gao Z Y. Large-scale neighborhood search algorithm for time - varying vehicle scheduling problem[J]. Journal of Management Sciences in China, 2012, 15(1): 22-32. DOI:10.3969/j.issn.1007-9807.2012.01.003) |
[17] |
Markova I, Varone S, Bierlaire M. Integrating a heterogeneous fixed fleet and a flexible assignment of destination depots in the waste collection VRP with intermediate facilities[J]. Transportation Research, Part B: Methodological, 2016, 84(5): 256-273. |
[18] |
Kaya T, Guler H. A hybrid genetic algorithm for analog active filter component selection[J]. AEU-International Journal of Electronics and Communications, 2018, 86: 1-7. DOI:10.1016/j.aeue.2018.01.015 |
[19] |
Zhang R, Chang P C, Song S, et al. Local search enhanced multi-objective PSO algorithm for scheduling textile production processes with environmental considerations[J]. Applied Soft Computing, 2017, 61: 447-467. DOI:10.1016/j.asoc.2017.08.013 |
[20] |
Ding Q L, Hu X P, Sun L J, et al. An improved ant colony optimization and its application to vehicle routing problem with time windows[J]. Neurocomputing, 2012, 98: 101-107. DOI:10.1016/j.neucom.2011.09.040 |
[21] |
Jaszkiewicz A. Many-objective pareto local search[J]. European Journal of Operational Research, 2018, 271(3): 1001-1013. DOI:10.1016/j.ejor.2018.06.009 |