(交通运输)冷链食品运输路线优化精编.doc

（交通运输）冷链食品运输路线优化（交通运输）冷链食品运输路线优化冷链食品运输路线优化物流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,ij为路段集合，代表冷藏食品运输中心，（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算法计算的基本思路采用寻找最邻客户法，确定线路中第壹位被服务的客户。最临近的客户是指满足时间窗的和车辆容量限制，且且尚未被排入任壹线路的客户。该客户加入线路，除了满足上述俩条件之外，仍应该满足加入成本最低原则，即新加入的客户能使新增成本最低，从而保证运输成本最低。采用节约法求解：节约算法的核心思想是将运输问题中存在的俩个回路（0i,0）和（0j,0）合且成壹个回路（0i,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:0022:2021:3021:4021:0022:0021:2022:4023:1023:4020:30接受时间窗20:0021:0020:2021:2020:3021:4020:4022:1022:4019:3022:0022:2021:0021:3022:3021:5022:5023:1023:400:20表2配送中心及客户之间的距离客户P0P1P2P3P4P5P6P7P8P9P10P00109788834107P1100491418181314114P294051014171213158P37950591510111713P481410906710121815P581814960710121815P681817151370681715P7313121011106021110P841413111212820911P91011171518181711908P1074813151515101180表3其他参数表序号名称符号单位数值1酸奶价格P元吨40003惩罚系数%0.24单位运输成本C元吨公里0.85运输速度V公里小时306装卸时间H分钟客户204.1确定第壹条最优运输路线将客户按时间的先后顺序排列，得表4。计算每壹客户之间连接的距离节约值，见表5。表4各客户按时间先后排序的时间窗户客户P10P1P3P5P7P2P4P6P8P9时间窗20:0020:3020:3021:0020:5021:2021:0021:3021:2021:4021:3022:0021:5022:0022:0022:4022:4023:1023:1023:40接受时间窗19:3021:0020:0021:3020:2021:5020:3022:0020:4022:2021:0022:3021:2022:5021:4023:1022:1023:4022:4000:20表5客户之间连接的距离节约值客户P1P2P3P4P5P6P7P8P9P10P115840000913P215117300048P381110600001P447101030000P50361091000P6000395410P7000015520P8000004550P9940001259P101381000009按时间窗先后顺序，客户要求的时间最早，因此客户为第壹客户。接下来客户选择见表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.24h15分，即冷藏车到达时是20:45，在的时间窗范围内，所以惩罚成本为0。若选择客户，和之间的距离为8公里，可算出运送时间t=8/30=0.27h17分，即冷藏车到达时是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。