冷链食品运输路线优化

冷链食品运输路线优化物流072班组员：粱利英（200700709075）、苏凤美（200700709071）、周冬梅（200700709063）、梁小杰（200700709078）、蓝冬菊（200700709060）、张欣欣（200700709080）、周群(200700709058）、钟玲(200700709047)摘要食品工业要发展，速冻食品是一条必经之路。冷链食品一般定义为适应于0-4保存的食品，冷链食品具有易腐，易变质的特性。与一般食品相比较，冷藏食品运输的特点是运输装备的特殊性，即用冷藏设备进行运输：运输时效性，即在冷藏食品保质期内送达，时效性对于冷藏食品运输更为重要。如何在规定时间内，以最低成本运达冷藏食品，是冷藏食品运输中要考虑的关键问题。运输成本主要取决于运输路线，因此确定冷藏食品运输的最优路线是冷藏食品运输决策要考虑的主要问题之一。近年来，物流配送车辆路径问题的研究已经引起了人们的广泛关注，但对于冷藏食品的运输路线优化的研究还不多见。本文根据冷藏食品运输特性，以物流运营商运成本最低为目标，考虑超出客户时间窗的惩罚成本，建立了冷藏食品运输路线优化模型。在路线优化方面，通过建立节约里程模型找出运输的最佳路径，从而节约运输里程、运达时间，最终降低运输成本。关键词：冷藏食品运输路线优化模型目录摘要2目录3一、背景介绍41.1中国食品冷链发展状况41.2我国冷链物流运输现状评价41.3我国冷冻冷藏食品市场和冷藏链物流发展4二、冷藏食品运输路线优化模型的建立52.1模型建立的基本思路52.2目标函数的建立52.2.1运输成本52.2.2惩罚成本。62.2.3冷藏食品运输线路优化模型6三、模型算法73.1算法计算的基本思路73.2求解步骤8四、算例分析94.1确定第一条最优运输路线104.2具体计算过程：114.2.1节约运输成本的求法步骤：114.2.2惩罚成本的求法：124.2.3节约总成本124.3确定第二条最优运输路线124.4确定第三条最优运输路线134.5确定第四条最优运输路线14五、结论14【参考文献】15一、背景介绍1.1中国食品冷链发展状况中国食品冷链的发展历程：冷链起源于19世纪上半叶冷冻机的发明，到了电冰箱的出现，各种保鲜和冷冻食品开始进入市场和消费者家庭。到20世纪30年代，欧洲和美国的食品冷链体系已经初步建立。40年代，欧洲的冷链在二战中被摧毁，但战后又很快重建。现在欧美发达国家已形成了完整的食品冷链体系。　　新中国的冷链最早产生于50年代的肉食品外贸出口，并改装了一部分保温车辆。1982年，中国颁布“食品卫生法”，从而推动了食品冷链的发展起步。近20年来，中国的食品冷链不断发展，以一些食品加工行业的龙头企业为先导，已经不同程度地建立了以自身产品为核心的食品冷链体系，包括速冻食品行业，肉食品加工企业，冰淇淋和奶制品企业和大型快餐连锁企业，还有一些食品类外贸出口企业。1.2我国冷链物流运输现状评价随着城乡居民生活水平的提高和人们消费习惯的改变，以水产品、畜产品、果蔬及花卉为代表的冷链物流日渐趋热，成为人们关注的焦点。所谓冷链物流泛指冷藏冷冻类食品在生产、贮藏运输、销售，到消费前的各个环节中始终处于规定的低温环境下，以保证食品质量，减少食品损耗的一项系统工程。它是随着科学技术的进步、制冷技术的发展而建立起来的，是以冷冻工艺学为基础、以制冷技术为手段的低温物流过程。冷链物流的适用范围包括初级农产品：蔬菜、水果；肉、禽、蛋；水产品、花卉产品。加工食品：速冻食品、禽、肉、水产等包装熟食、冰淇淋和奶制品；快餐原料。特殊商品：药品。由于食品冷链是以保证易腐食品品质为目的，以保持低温环境为核心要求的供应链系统，所以它比一般常温物流系统的要求更高、更复杂，建设投资也要大很多，是一个庞大的系统工程。业内人士指出，目前，我国的冷藏物流业尚处于初级阶段，市场规模不大，区域性特征比较强，缺乏有影响力的、全国性的第三方冷藏物流行业领袖。从全国范围来看，原有冷藏链设施一般自成系统、时有断裂、不能连网、效率低下，距离构建现代化低温物流体系差距甚大。1.3我国冷冻冷藏食品市场和冷藏链物流发展我国冻制食品自20世纪六十年代开始出现，主要是冻肉、冻禽和冻水产品，为保障市场供应，调节淡旺季与全国计划调运，国内主要产地与大城市兴建了一批大型冷库，并由铁路冷藏车和水运冷藏船相联，形成了冻制品产地——冷藏货车——冷库——市场之间的网络。这种以食品原料冷冻、贮存和运输为目的的初级冻制品冷藏链，在较长时间内，对保障国内副食品供应及出口贸易起了重要作用。随着我国加入WTO，如何运用现代科学技术，成功开发各种冷冻冷藏温度带食品，建设完善可靠、管理的食品冷藏链并提高社会公用化程度，全面提升我国食品安全与品质，充分利用食品资源，减少易腐食品损失，加快农产品深加工，适应国内外市场需求，是冷冻食品产业与冷藏链设备制造业及相关产业共同面临的新课题。二、冷藏食品运输路线优化模型的建立2.1模型建立的基本思路定义路网G=（V,A）,其中，V={，，···，}为点的集合，A={，}：，∈V,i≠j为路段集合，代表冷藏食品运输中心，（i=1,2,···，n）代表所服务的第i个客户，客户i的需求量为。运输中心的运送车辆路线用l表示，共有m部运送车辆，故l=1，2，···，m）。而为第l部车辆在路段（，）上的运输成本，且=。显然，i=j时，=0.将超出客户时间窗的惩罚成本及随里程递增的运输成本作为冷藏食品运输商的运输总成本，以运输成本最小为目标，求解模型，以获得最佳的运输路线。（忽略冷藏食品易腐性造成的货损成本）2.2目标函数的建立构建模型时，将运输的综合成本作为目标函数。冷藏食品的运输综合成本包括：车辆运输成本，以及超出客户时间窗的惩罚成本。2.2.1运输成本运输成本包括固定成本和变动成本，其中固定成本为常数，与运输里程及客户数量没有直接关系，这里只考虑运输车辆的变动成本，可表示为：=（1）其中，=为第l部车辆在路段（，）上的运输成本，为从第i点到第j点运送单位冷藏食品的运费，为从第i点向第j点运送冷藏食品的数量；为0、1变量，若第l车辆行经（，）路段，则=1，否则=0。2.2.2惩罚成本。时间过长，冷藏食品易腐烂，故在其运输中对时间有严格的限制，即属于有时间窗限制的运输问题。在实际运输中，运输中心派出的运输车辆到达客户的时间，有三种情况，即：（1）在要求时间窗内运达；（2）在要求时间窗之外，客户可以接受范围内运达；（3）延迟并超出客户可以接受的范围内运达。第一种情况下运达，可以进行货物交换，没有惩罚成本。第二种情况运达，货物可以交接，但需要支付相应的惩罚成本。第三种情况下运达，无法完成运输任务，在模型中不考虑。设客户j的时间窗上线为，下限为，可接受的范围时间上限,。则惩罚成本表示为：（3）式（3）中为冷藏食品运达客户的时间，为客户j的货物数量；λ为惩罚系数。则总的惩罚成本为：=（4）2.2.3冷藏食品运输线路优化模型以运输总成本最小为目标，受约束条件限制，确定出冷藏食品最优的运输路线。线路优化模型为：Min(5)三、模型算法上述建立的运输线路优化模型为非线性规划问题，求解比较复杂。采用启发性算法，简化该问题的求解。3.1算法计算的基本思路采用寻找最邻客户法，确定线路中第一位被服务的客户。最临近的客户是指满足时间窗的和车辆容量限制，并且尚未被排入任一线路的客户。该客户加入线路，除了满足上述两条件之外，还应该满足加入成本最低原则，即新加入的客户能使新增成本最低，从而保证运输成本最低。采用节约法求解：节约算法的核心思想是将运输问题中存在的两个回路（0……i,0）和（0……j,0）合并成一个回路（0…i,j,…0），合并后整个运输回路的运输距离将发生变化，一般优化结果会使运输距离下降，下降值称为路线节约值。节约里程法基本原理是几何学中三角形一边之长必定小于另外两边之和。节约法的目标是使所有车辆的行驶总里程最短，并且为所有站点提供服务的卡车数量最少。该方法先假设每一个站点都有一辆虚拟的车辆提供服务，随后返回仓库，如图1-1所示，这时的路线里程最长。下一步，将两个站点合并到同一条行车路线上，减少一辆运输车，相应地缩短路线里程，选择节约距离最多的一对站点合并在一起，修订后的路线如图1-2。继续以上过程，除了将单个站点合并在一起外，还可以将某站点并入已经包含多个站点的路线上。每次合并都要计算所节约的距离，节约距离最多的站点就应该纳入现有路线。假如由于某些约束条件（如路线太长，无法满足时间窗口的要求，或超过车辆的承载能力），节约距离最多的站点不能并入该路线，就要考虑节约距离次多的站点。重复该过程直到所的站点的路线设计完成。图1节约法示意图如图1所示，假定冷藏食品运输中心为，到客户和的距离分别为和，用表示路线节约值，则合并后节约距离为：=+－（7）式中为客户到客户的距离。运送车辆的运输成本与运输里程成正比，故节约值越大，其成本越小。运输里程和客户的货物量两个因素决定了冷藏食品在运输途中腐烂的所造成的货损成本。线路优化不改变客户的货物量。因此冷藏食品的货损成本优化主要由运输里程决定。货损成本与运输里程成正比。惩罚成本只与运达时间有关，由式（3）计算。由此，冷藏食品运输线路优化模型的目标函数又可转化为：=（8）式（8）中为从客户i到客户j运输中的节约成本，为单位货物从i运输到j客户的运输成本。由上，可得搜索新客户的顺序：1、时间窗先后顺序。超出可接受的时间窗，意味着无法完成订单，因此必须按照时间窗为第一顺序原则，加入新客，保证所有客户都可接受的范围内被服务。2、运输里程顺序。运输里程直接影响运输成本和货损成本，对运输总成本很大，作为第二顺序。3.2求解步骤根据上述算法，具体求解步骤如下：（1）初始化，输入已知的参数；（2）由配送中心开始寻找“最邻客户”，加入成为第一条路线上的第一位被服务的客户；（3）令i为某一线路上最后一位加入的客户。重复步骤（2），得到下一个邻近客户j。依次加入当前线路中。若所有尚未被排入任一路线的客户均无法满足时间窗限制或车辆容量限制，则重新建立一条新的路线，直到所有客户全部排入线路为止。四、算例分析一配送中心，向10个客户（j=1，2，···，10）配送酸奶。酸奶保存期限为24小时，配送温度为0℃。客户的需求量和时间窗见表1.配送及客户间的距离（Km）见表2.运输任务由配送中心利用q=3t的冷藏车来完成，其他参数见表3。确定最佳运输路线。表1客户货物需求量和时间窗客户P1P2P3P4P5P6P7P8P9P10需求量0.71.50.80.41.41.50.60.82.50.6时间窗20:3021:3020:5021:5021:0022:0021:2022:4023:1020:00————22:20—21:30——21:40———21:0022:0021:20　　22:40　23:1023:4020:30接受时间窗20:0021:0020:2021:2020:3021:4020:4022:1022:4019:30—————22:00——22:20———21:0021:3022:3021:5022:50　23:10　23:400:20　表2配送中心及客户之间的距离客户P0P1P2P3P4P5P6P7P8P9P10P00109788834107P1100491418181314114P294051014171213158P37950591510111713P481410906710121815P581814960710121815P681817151370681715P7313121011106021110P841413111212820911P91011171518181711908P1074813151515101180表3其他参数表序号名称符号单位数值1酸奶价格P元∕吨40003惩罚系数λ%0.24单位运输成本C元∕吨公里0.85运输速度V公里∕小时306装卸时间H分钟∕客户204.1确定第一条最优运输路线①将客户按时间的先后顺序排列，得表4。②计算每一客户之间连接的距离节约值，见表5。表4各客户按时间先后排序的时间窗户客户P10P1P3P5P7P2P4P6P8P9时间窗20:00—20:3020:30—21:0020:50—21:2021:00—21:3021:20—21:4021:30—22:0021:50—22:0022:00—22:4022:40—23:1023:10—23:40接受时间窗19:30—21:0020:00—21:3020:20—21:5020:30—22:0020:40—22:2021:00—22:3021:20—22:5021:40—23:1022:10—23:4022:40—00:20表5客户之间连接的距离节约值客户P1P2P3P4P5P6P7P8P9P10P1—15840000913P215—117300048P3811—10600001P44710—1030000P503610—91000P600039—5410P7000015—520P80000045—50P994000125—9P101381000009—③按时间窗先后顺序，客户要求的时间最早，因此客户为第一客户。接下来客户选择见表6和表7。表6客户选择表1客户节约运输里程节约运输成本惩罚成本节约总成本选择p1137.2807.28是p289.2∞－∞否p310.64∞－∞否p400∞－∞否p50000否p600∞－∞否p7002.4-2.4否p800∞－∞否p9918∞－∞否表7客户选择表2客户节约运输里程节约运输成本惩罚成本节约总成本选择p12833.63.630.00是p32113.442.1111.33否p4175.440.964.48否p51314.561.8712.69否p61315.6411.6否p7136.2406.24否p8117.04∞－∞否p92244∞－∞否4.2具体计算过程：按时间窗先后顺序，客户要求的时间最早，因此客户为第一客户。接下来应先算出到各个客户之间节约运输里程、节约运输成本、惩罚成本。4.2.1节约运输成本的求法步骤：1、通过节约法原理，求出每一客户之间连接的距离节约值。2、节约运输成本=节约运输里程×运费×某一客户的需求量表5中客户之间连接的距离节约值是由表2配送中心及客户之间的距离计算可得。例如:表5中与的距离节约值=到的距离+到的距离-与的距离=10+9-4=15。同理可得其它客户之间连接的距离节约值。由表5可知，与的距离节约值为13公里，由表1可知客户货物需求量为0.7吨，由表3其他参数表可知，单位运输成本为0.8元∕吨公里，所以与节约运输成本为=13×0.7×0.8=7.28同理可得：与p2节约运输成本=9.2与p3节约运输成本=0.64与p4节约运输成本=0与p5节约运输成本=0与p6节约运输成本=0与p7节约运输成本=0与p8节约运输成本=0与p9节约运输成本=184.2.2惩罚成本的求法：假设冷藏车送到客户时，刚好是客户的时间下线，即送到客户的时间是20:10，由于装卸时间为20分钟，所以冷藏车从20:30从出发；若选择客户，和之间的距离为7公里，运送速度是30公里∕小时，可算出运送时间t=7/30=0.24h≈15分，即冷藏车到达时是20:45，在的时间窗范围内，所以惩罚成本为0。若选择客户，和之间的距离为8公里，可算出运送时间t=8/30=0.27h≈17分，即冷藏车到达时是20:47，不在客户接受的时间范围内，即超出了客户可接受的时间范围，因此惩罚成本是∞。同理算得、、、、、。若选择客户，和之间的距离是10公里，可算出运送时间t=10/30=20分，冷藏车到达时是20:50，在客户的要求时间窗之外，在客户可接受的时间范围内送达，超出了要求时间30分钟，此时，需要支付相应的惩罚成本。惩罚成本==0.2%×4000×0.6×(30/60)=2.4.4.2.3节约总成本节约总成本=节约运输成本－惩罚成本选出节约总成本最大的客户加入路线。根据表6、表7分析，第一条线路上的客户为、、，此时运输车辆的载重量为Q=0.6+0.7+1.5=2.8t，剩余的载重量无法满足剩余的其他任何客户，所以第一条最优运输路线是：----。同样的道理，可算得冷藏车的其他几条最优运输路线：---、----、--。具体内容如下：4.3确定第二条最优运输路线在剩余的客户中客户要求时间最早，作为第一个客户。接下来客户选择见表8、表9。表8客户选择表3客户节约运输里程节约运输成本惩罚成本节约总成本选择p4103.21.61.60否p566.7206.72是p6004-4.00否p70000.00否p800∞－∞否p900∞－∞否表9客户选择表4客户节约运输里程节约运输成本惩罚成本节约总成本选择p4165.1205.12是p773.360.962.40否p863.8430.84否从表8中可见，选择客户，表9中可见，选择客户，此时第二条最优运输路线为----。4.4确定第三条最优运输路线在剩余的客户中，客户要求的时间最早，客户作为第一个客户。接下来客户的选择见表10和表11。表10客户选择表5客户节约运输里程节约运输成本惩罚成本节约总成本选择p6561.564.44是p852.402.40否p921.28∞－∞否表11客户选择表6客户节约运输里程节约运输成本惩罚成本节约总成本选择P895.7605.76是P96120.6711.33否根据表10和表11，第三条线路选择的客户为、、，因为虽然此时节约的总成本比大，若选择，运输车辆的载重量为Q=0.6+2.5+1.5=4.6t，超过了冷藏车的载重量，因此第三条最优运输路线为：----。4.5确定第四条最优运输路线只剩余客户，单独作为第四条运输路线，即--。综上分析，冷藏车的最优运输路线是：----、---、----、--。五、结论（1）冷链食品具有易腐性，所以必须要在客户接受的时间窗内送到客户手中，本研究考虑了超出客户时间窗的惩罚成本等多个因素，通过运输路线的优化使节约运输成本和惩罚成本的总成本之和最小。（2）运用启发式算法，寻找“最临客户”，“最临客户”包括时间窗最临和运输里程最临两个方面。以时间窗为第一顺序原则，然后再通过运输里程顺序，以成本最低为原则，找出冷链食品运输路线模型的求解算法。（3）把启发式算法运用到我们的实际例子，通过求解得出所需的最优配送路线，从而提高客户服务水平与降低配送成本。（4）研究展望：通过提供完整的配送服务使冷链食品的配送服务最大限度的适应企业的发展能力，从而为各零售企业、食品企业提供更全面的服务。满足客户的需要的情况下尽量降低总成本。【参考文献】[1]杨晓楼,许増茂，我国冷藏食品物流市场现状及发展趋势[j].重庆交通学院学报（社科版），2005。[2]刘兴，基于协作的车辆路径问题的研究[D]，天津，天津大学，2006。[3]刘贵英，随机车辆路径问题模型及算法研究，西安;长安大学，2006。[4]谢秉磊，随机车辆路径问题研究[D]，西安，西安交通大学，2003。[5]刘荣华，孙浩，赵娟，基于供应链的运输决策[J]，中国海洋大学学报，2007。[6]俞明南，刘申，李阳，物流管理中运输决策[J]，辽宁师范大学学报（自然科学版），2005。[7]张得志，凌春雨，多种运输方式组合优化模型及求解算法[J]，长沙铁道学院学报，2002。