带时间窗的生鲜产品冷链配送优化模型的构建与应用研究

□ 耿秀娥 □ 刘文慧 □ 于庆安

1.西安工程大学 机电工程学院 西安 710048

2.西北工业大学 管理学院 西安 710072

目前，人们对生鲜产品的需求日益增加，而生鲜产品易腐、季节性强、地域性强、储运保鲜条件要求苛刻等特点使其面临高昂的配送成本，因此合理优化路径，尽可能地降低物流成本成为非常重要的问题。李泽华［1］以最小生鲜产品配送总成本为目标，建立了生鲜产品配送路径优化的模型，运用了自适应交叉遗传算法，进行了案例分析。祁文祥等［2］在传统路径问题的研究基础上，增加软时间窗约束，提出了最小的目标函数包括租车费用、运输费用和时间惩罚费用之和，运用启发节约算法求解该模型。曹倩等［3］运用改进的遗传算法进行生鲜农产品多目标配送路径优化研究，引用了配送成本最小和顾客满意度最大的多目标优化，成功运用改进遗传算法对模型进行分析。何静等［4］研究了连锁超市生鲜食品冷链物流网络构建与优化，提出了3种典型的冷链物流网络模式并进行模式优化，降低超市的运营成本。笔者以生鲜产品运输过程中的路径优化为研究对象，描述了配送成本构成，不仅考虑了由于时间窗的因素引起的惩罚成本，及在运输过程中生鲜产品存在损耗，加入了货损成本，而且在产品的运输中，要保持产品的新鲜度，必须保持运输车辆的温度，因此把制冷成本引入。另外，国家认识到环境保护的重要性，对于车辆排放也进行限制，对于排放尾气超标的车辆进行处罚，笔者还引入了尾气惩罚成本。在比较系统地考虑成本的基础上，建立成本函数，以总成本最小为目标构建了生鲜产品冷链配送路径优化模型，通过合理优化，提高配送效率，减少产品在运输过程中的损耗，从而降低成本，提高利润。

1 问题描述

笔者所建立的冷链物流配送优化模型是在一个配送中心与多个客户的基础上，并且作以下假设：运输车辆为相同容量、型号、使用年限和车况的冷冻（冷藏）车辆，运输的货物为单一品种（某种生鲜产品），每个客户的基本信息（客户距离配送中心的距离、客户两两之间的距离、客户对货物的需求量）为已知，并且顾客有送达时间的约束。在满足顾客需求量、时间窗、有害气体排放量的限制下，求总成本最小的配送方案，其中，成本包括：车辆固定成本、运输成本、运输距离补偿费用、生鲜产品的易腐性所造成的配送货损成本［5］（一部分是配送过程中由于时间的累积，产品腐败所产生的货损成本，另一部分是用于开启车门造成车厢内部和外界空气产生对流，使产品的品质下降所造成的货损）、制冷成本［6］（冷藏车行驶中的制冷成本和打开车门时的制冷成本）、惩罚成本（超出客户时间窗的惩罚成本和汽车尾气惩罚成本）。

2 配送成本构成因素分析

冷链物流配送模型目标函数的构成要素如下［7-8］。

2.1 车辆的固定成本

设配送车辆总数为K，每辆车的固定成本为P，则总固定成本为Cg：

2.2 车辆的运输成本

车辆运输总成本Cys：

2.3 运输距离补偿费用

运输距离补偿总费Csb：

式中：s为配送车辆超出常规最大行驶距离后行驶单位距离需支付的补偿费用；Ek为车辆k需要缴纳距离补偿费用的里程，；H为配送车辆的距离补偿费用计费点；Sk为车辆k行驶的距离。

2.4 生鲜产品的易腐性所造成的配送货损成本

货损成本［9］Ch：

式中：c为货物的单位成本；α为车辆行驶中，货物在单位时间内产生的货损比例；为车辆k到达客户j的时刻为第k辆车从配送中心出发的时刻；β1为装卸过程中，货物在单位时间内产生的货损比例；Qj为第j个客户对货物的需求量；为第k辆车在服务第j个客户时的装卸效率；为第k辆车到达第j个客户时，车上所剩的货物量（包括客户j的货物量）。

2.5 车辆制冷成本

车辆制冷成本包括车辆行驶中的制冷成本和打开车门时的制冷成本。

2.5.1 车辆行驶中的制冷成本

车辆k在配送过程中的制冷成本为［10］：

式中：α1为常数，表示车厢体的劣化程度；R为热传导率；S为车体的平均表面积；ΔT为车体内外温差；p2为单位制冷成本；为车辆k完成配送任务到达配送中心的时间。

2.5.2 车辆装卸时的制冷成本

车辆k在开车门时的制冷成本为：

式中：V为车厢体的体积；β为平均开门程度系数；ti为车辆在配送点i的停留时间。

本文研究的是单车型且配送单一产品问题，车内温度相同，βi是个经验值，它由该配送车辆所服务的客户点需求量的空间分布形态来决定，假设每部配送车辆的开门频率均等于服务该批顾客的整体开门频率期望值，对照表1以求得平均开门程序系数β，即β=Eβi，其中 i=A，B，C，D，E。

表1 系数与开门频率对照表

2.6 惩罚成本

惩罚成本由超出客户时间窗的惩罚成本和汽车尾气惩罚成本组成。

2.6.1 超出客户时间窗的惩罚成本Ctp

式中：Gi为超出顾客时间窗的惩罚成本；m为惩罚成本的最大限值；［ai，bi］为客户i期望的货物送达时间段；［ci，di］为客户i可接受的货物送达时间段；为车辆k到达客户i的时刻。

2.6.2 汽车尾气惩罚成本

汽车尾气排放的主要气体污染物为一氧化碳（CO）、碳氢化合物（CH）、氮氧化物（NOx）等，RCO为汽车尾气一氧化碳排放标准，RCH为汽车尾气碳氢化合物排放标准，RNOx为汽车尾气氮氧化物排放标准。汽车尾气有害物排放量计算公式为：

配送过程中总的尾气排放量Lall：

尾气排放超标惩罚成本Cwq：

式中：M为一个非常大的正数；Lmax为配送过程最大尾气排放量限制。

3 带时间窗的生鲜产品冷链配送优化模型的构建

3.1 约束条件

①车辆容量限制，一条线上的客户需求总量不能超过车辆的最大载重量，同时从配送中心发出的车辆不得超过K；②每个客户仅仅由一辆车服务且服务一次，每辆车辆从配送中心出发并最终返回配送中心；③每个客户必须在特定的时间范围进行服务；④配送过程中有害气体不得超过最大限制。

3.2 模型构建

根据决策目标,本模型以综合成本最低作为目标函数。

式中：wi、wj分别为车辆提前到达客户点 i、j时的等待时间）；tj、ti分别为车辆在配送点 j、i的停留时间）；tij为车辆从客户i行驶到客户j的所用时间。

式（10）表示目标函数，式（11）表示每条线路所运送货物总和不能超过车辆的载重量，式（12）表示从配送中心发出的车辆不得超过K，式（13）、式（14）表示每个客户仅由一辆车服务且服务一次，式（15）表示每辆车辆从配送中心出发并最终返回配送中心，式（16）、（17）表示每个客户必须在特定的时间范围进行服务；式（18）表示配送过程中有害气体不得超过最大限制。

4 实例分析

某配送企业在某区域内（区域边长为20 km），需要对15个用户提供货物配送服务。各个用户的货物需求量都在2 t以下（包括2 t），车辆的最大载重均为8 t，车辆一次配送的最大行驶距离均为50 km。其中，配送中心的坐标为（11.14 km，11.10 km），15 个用户的坐标、货物需求量及时间窗数据见表2。车辆在配送过程的平均行驶速度为20 km/h，车辆统一的出发时刻为0。

笔者运用禁忌搜索算法［11-13］，其中选择迭代步数为400，每次迭代搜索当前解的邻居个数为40个，禁忌长度取20。根据算法，计算出配送的最优解，其中，最优解包括使用车辆数、车辆总的等待时间、总的迟到时间以及最佳配送路径。

计算结果为：最优使用的车辆数为2，车辆总的等待时间为56.440 5 h，车辆总的迟到时间为0，车辆配送的最佳路径为0-5-13-15-8-14-7-4-2-0和0-6-11-9-10-12-1-3-0。由于配送中心发车时间一律为0，因此可能导致过多的等待时间、但迟到时间为0的情况。如果变动了发车时间，最终的结果肯定也不会一样。因此，最终结果和发车时间也有关系。

5 总结

笔者以传统带时间窗的车辆路径问题为基本参考模型，分析了配送成本的构成要素，在考虑时间惩罚成本的同时，考虑车辆固定成本、运输成本、运输补偿费用、制冷成本、货损成本和汽车尾气惩罚成本，建立了以总成本最小为目标的带软时间窗的冷链物流配送优化模型，通过实例验证，证明了模型的可行性和有效性，为物流企业的实际配送操作提供优化支持。

［1］ 李泽华.带时间窗约束的生鲜产品配送车辆路径优化问题研究［D］.大连：大连海事大学，2009.

［2］ 祁文祥,陆志强,孙小明.带软时间窗的集货与送货多车辆路径问题节约算法［J］.交通运输工程学报,2010（2）:99-103.

［3］ 曹倩,邵举平,孙延安.基于改进遗传算法的生鲜农产品多目标配送路径优化［J］.工业工程,2015（1）:71-76.

［4］ 何静,张歆祺,宗传宏.连锁超市生鲜食品冷链物流网络构建与优化研究［J］.广东农业科学,2011（22）:166-169.

［5］ Pureza V,Morabito R,Reimann M.Vehicle Routing with Multiple Delivery Men:Modeling and Heuristic Approaches for the VRPTW ［J］.European Journal of Operational Research,2012,218（3）:636-647.

［6］ 李进,张江华.基于碳排放与速度优化的带时间窗车辆路径问题［J］.系统工程理论与实践,2014（12）:3063-3072.

［7］ Chen ZI,Xu H.Dynamic Column Generation for Vehicle Routing with Time Windows ［J］.Transportation Science,2006,40（1）:74-88.

［8］ 贾振军,沙威.降低食品冷链中的物流成本分析［J］.重庆交通大学学报（社会科学版）,2008（4）:40-42.

［9］ 杨丹婷.冷链物流配送路径优化研究［D］.大连：大连海事大学,2014.

［10］李进,傅培华.基于能耗的带时间窗车辆路径问题建模与仿真［J］.系统仿真学报,2013（6）:1147-1154.

［11］张晓菲,张火明.基于连续函数优化的禁忌搜索算法［J］.中国计量学院学报,2010（3）:251-256.

［12］郑建辉.第三方配送带软时间窗车辆路径问题的模型与禁忌算法研究［D］.杭州:杭州科技大学,2013.

［13］邓松,林为民,张涛,等.基于禁忌GEP的分布式数据库查询优化算法［J］.计算机与数字工程,2013（10）:1552-1555.