冷链食品运输路线优化.doc

1、冷链食品运输路线优化物流 072 班组员：粱利英（ 200700709075）、苏凤美（ 200700709071）、周冬梅（ 200700709063）、梁小杰（ 200700709078）、蓝冬菊（ 200700709060）、张欣欣（ 200700709080）、周群 (200700709058 ）、钟玲 (200700709047)1摘要食品工业要发展， 速冻食品是一条必经之路。 冷链食品一般定义为适应于 0-4 保存的食品， 冷链食品具有易腐， 易变质的特性。 与一般食品相比较， 冷藏食品运输的特点是运输装备的特殊性， 即用冷藏设备进行运输： 运输时效性， 即在冷藏食品保质期内送达，

2、 时效性对于冷藏食品运输更为重要。 如何在规定时间内， 以最低成本运达冷藏食品，是冷藏食品运输中要考虑的关键问题。 运输成本主要取决于运输路线，因此确定冷藏食品运输的最优路线是冷藏食品运输决策要考虑的主要问题之一。近年来，物流配送车辆路径问题的研究已经引起了人们的广泛关注，但对于冷藏食品的运输路线优化的研究还不多见。 本文根据冷藏食品运输特性， 以物流运营商运成本最低为目标， 考虑超出客户时间窗的惩罚成本， 建立了冷藏食品运输路线优化模型。 在路线优化方面，通过建立节约里程模型找出运输的最佳路径， 从而节约运输里程、运达时间，最终降低运输成本。关键词：冷藏食品运输路线优化模型2目录摘要 .2目

3、录 .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确定第二条最优运输

4、路线 .124.4确定第三条最优运输路线 .134.5确定第四条最优运输路线 .14五、结论 .14【参考文献】.153一、背景介绍1.1 中国食品冷链发展状况中国食品冷链的发展历程：冷链起源于19 世纪上半叶冷冻机的发明，到了电冰箱的出现，各种保鲜和冷冻食品开始进入市场和消费者家庭。到 20 世纪 30 年代，欧洲和美国的食品冷链体系已经初步建立。40 年代，欧洲的冷链在二战中被摧毁，但战后又很快重建。现在欧美发达国家已形成了完整的食品冷链体系。新中国的冷链最早产生于50 年代的肉食品外贸出口，并改装了一部分保温车辆。1982年，中国颁布 “食品卫生法 ”，从而推动了食品冷链的发展起步。近2

5、0 年来，中国的食品冷链不断发展，以一些食品加工行业的龙头企业为先导， 已经不同程度地建立了以自身产品为核心的食品冷链体系，包括速冻食品行业，肉食品加工企业， 冰淇淋和奶制品企业和大型快餐连锁企业，还有一些食品类外贸出口企业。1.2 我国冷链物流运输现状评价随着城乡居民生活水平的提高和人们消费习惯的改变，以水产品、 畜产品、 果蔬及花卉为代表的冷链物流日渐趋热，成为人们关注的焦点。所谓冷链物流泛指冷藏冷冻类食品在生产、贮藏运输、 销售， 到消费前的各个环节中始终处于规定的低温环境下，以保证食品质量，减少食品损耗的一项系统工程。它是随着科学技术的进步、 制冷技术的发展而建立起来的，是以冷冻工艺学

6、为基础、以制冷技术为手段的低温物流过程。冷链物流的适用范围包括初级农产品：蔬菜、水果；肉、禽、蛋；水产品、花卉产品。加工食品：速冻食品、禽、肉、水产等包装熟食、冰淇淋和奶制品；快餐原料。特殊商品：药品。由于食品冷链是以保证易腐食品品质为目的，以保持低温环境为核心要求的供应链系统，所以它比一般常温物流系统的要求更高、更复杂，建设投资也要大很多，是一个庞大的系统工程。业内人士指出，目前，我国的冷藏物流业尚处于初级阶段，市场规模不大，区域性特征比较强， 缺乏有影响力的、全国性的第三方冷藏物流行业领袖。从全国范围来看，原有冷藏链设施一般自成系统、时有断裂、不能连网、 效率低下， 距离构建现代化低温物流

7、体系差距甚大。1.3我国冷冻冷藏食品市场和冷藏链物流发展我国冻制食品自20 世纪六十年代开始出现，主要是冻肉、冻禽和冻水产品，为保障市场供应， 调节淡旺季与全国计划调运，国内主要产地与大城市兴建了一批大型冷库，并由铁路冷藏车和水运冷藏船相联，形成了冻制品产地冷藏货车冷库市场之间的网络。这种以食品原料冷冻、贮存和运输为目的的初级冻制品冷藏链，在较长时间内，对保障国内副食品供应及出口贸易起了重要作用。随着我国加入WTO ，如何运用现代科学技术，成功开发各种冷冻冷藏温度带食品，建设完善可靠、 规范管理的食品冷藏链并提高社会公用化程度，全面提升我国食品安全与品质，充分利用食品资源， 减少易腐食品损失，

8、 加快农产品深加工， 适应国内外市场需求，是冷冻食品产业与冷藏链设备制造业及相关产业共同面临的新课题。4二、冷藏食品运输路线优化模型的建立2.1模型建立的基本思路定义路网G=（ V,A ） ,其中， V= v0 ， v1 ， ， vn 为点的集合， A= vi ， v j ： vi ，v j V,i j为路段集合， v0代表冷藏食品运输中心，vi （ i=1,2, ， n）代表所服务的第 i 个客户，客户 i 的需求量为wi 。运输中心的运送车辆路线用l 表示，共有 m 部运送车辆，故 l=1 ， 2， ， m）。而 Cijl为第 l 部车辆在路段（vi ， v j）上的运输成本，且 Cijl

9、= C jil 。显然， i=j 时， Cijl=0.将超出客户时间窗的惩罚成本及随里程递增的运输成本作为冷藏食品运输商的运输总成本， 以运输成本最小为目标， 求解模型，以获得最佳的运输路线l 0 。（忽略冷藏食品易腐性造成的货损成本）2.2目标函数的建立构建模型时，将运输的综合成本作为目标函数。 冷藏食品的运输综合成本包括：车辆运输成本，以及超出客户时间窗的惩罚成本。2.2.1运输成本运输成本包括固定成本和变动成本， 其中固定成本为常数， 与运输里程及客户数量没有直接关系，这里只考虑运输车辆的变动成本，可表示为：mnnCtr =i 1Cijl xijl（ 1）l 1j 0其中， C l=c

10、w 为第 l 部车辆在路段（vi ， vj ）上的运输成本，cij 为从第 i 点到ijij ij第 j 点运送单位冷藏食品的运费，wij 为从第 i 点向第 j 点运送冷藏食品的数量；xijl为 0、1 变量，若第 l 车辆行经（ vi ， v j ）路段，则xijl=1，否则 xijl=0。52.2.2惩罚成本。时间过长，冷藏食品易腐烂，故在其运输中对时间有严格的限制，即属于有时间窗限制的运输问题。 在实际运输中， 运输中心派出的运输车辆到达客户的时间，有三种情况，即：（1）在要求时间窗内运达；（2）在要求时间窗之外，客户可以接受范围内运达；（3）延迟并超出客户可以接受的范围内运达。第一种

11、情况下运达，可以进行货物交换，没有惩罚成本。第二种情况运达，货物可以交接， 但需要支付相应的惩罚成本。第三种情况下运达， 无法完成运输任务，在模型中不考虑。设客户 j 的时间窗上线为 t h ，下限为 tl ，可接受的范围时间上限Th , Tl 。则惩罚成本表示为：t jT e , t jT hC pj (t j )0T et jt e , t et jt h（ 3） Pwj ( t jt e )t ht jT h式（ 3）中 t j 为冷藏食品运达客户的时间，w j 为客户 j 的货物数量；为惩罚系数。则总的惩罚成本为：nC pj (t j )C p =（ 4）j12.2.3冷藏食品运输线路

12、优化模型以运输总成本最小为目标， 受约束条件限制， 确定出冷藏食品最优的运输路线。线路优化模型为：Min FCtr C p(5)6三、模型算法上述建立的运输线路优化模型为非线性规划问题，求解比较复杂。采用启发性算法，简化该问题的求解。3.1 算法计算的基本思路采用寻找最邻客户法，确定线路中第一位被服务的客户。最临近的客户是指满足时间窗的和车辆容量限制，并且尚未被排入任一线路的客户。该客户加入线路，除了满足上述两条件之外， 还应该满足加入成本最低原则，即新加入的客户能使新增成本最低，从而保证运输成本最低。采用节约法求解：节约算法的核心思想是将运输问题中存在的两个回路（ 0 i,0）和（ 0 j,

13、0 ）合并成一个回路（ 0 i,j, 0），合并后整个运输回路的运输距离将发生变化， 一般优化结果会使运输距离下降， 下降值称为路线节约值。节约里程法基本原理是几何学中三角形一边之长必定小于另外两边之和。节约法的目标是使所有车辆的行驶总里程最短， 并且为所有站点提供服务的卡车数量最少。 该方法先假设每一个站点都有一辆虚拟的车辆提供服务， 随后返回仓库，如图 1-1 所示，这时的路线里程最长。下一步，将两个站点合并到同一条行车路线上， 减少一辆运输车， 相应地缩短路线里程， 选择节约距离最多的一对站点合并在一起，修订后的路线如图 1-2。继续以上过程， 除了将单个站点合并在一起外， 还可以将某站

14、点并入已经包含多个站点的路线上。 每次合并都要计算所节约的距离， 节约距离最多的站点就应该纳入现有路线。 假如由于某些约束条件 （如路线太长， 无法满足时间窗口的要求，或超过车辆的承载能力） ，节约距离最多的站点不能并入该路线，就要考虑节约距离次多的站点。重复该过程直到所的站点的路线设计完成。图 1 节约法示意图如图 1 所示，假定冷藏食品运输中心为P0 ，P0 到客户 Pi 和 Pj 的距离分别为 d oi 和doj ，用 Sij 表示路线节约值，则合并后节约距离为：7Sij =doi +d oj l ij（ ）7式中 l ij为客户 Pi 到客户 Pj 的距离。运送车辆的运输成本与运输里程

15、成正比，故节约值Sij 越大，其成本越小。运输里程和客户的货物量两个因素决定了冷藏食品在运输途中腐烂的所造成的货损成本。 线路优化不改变客户的货物量。 因此冷藏食品的货损成本优化主要由运输里程决定。货损成本与运输里程成正比。惩罚成本只与运达时间有关，由式（ 3）计算。由此，冷藏食品运输线路优化模型的目标函数又可转化为：nnMaxCsiji1 j1nnn=(CijQij1 PQij )SijC pj（ 8）i 1j 1j1式（ 8）中 Csij 为从客户 i 到客户 j 运输中的节约成本， Cij 为单位货物从 i运输到 j客户的运输成本。由上，可得搜索新客户的顺序：1、时间窗先后顺序。超出可接

16、受的时间窗，意味着无法完成订单，因此必须按照时间窗为第一顺序原则， 加入新客，保证所有客户都可接受的范围内被服务。2、运输里程顺序。运输里程直接影响运输成本和货损成本，对运输总成本很大，作为第二顺序。3.2求解步骤根据上述算法，具体求解步骤如下：（1）初始化，输入已知的参数；（2）由配送中心开始寻找“最邻客户” ，加入成为第一条路线上的第一位被服务的客户；（3）令 i 为某一线路上最后一位加入的客户。 重复步骤（ 2），得到下一个邻近客户 j 。依次加入当前线路中。若所有尚未被排入任一路线的客户均无法满足时间窗限制或车辆容量限制，则重新建立一条新的路线，直到所有客户全部排入线路为止。8四、算例

17、分析一配送中心，向10 个客户 Pj（ j=1 ，2，10）配送酸奶。酸奶保存期限为24 小时，配送温度为 0。客户的需求量和时间窗见表1. 配送 P0 及客户间的距离（Km）见表 2.运输任务由配送中心利用q=3t的冷藏车来完成，其他参数见表3。确定最佳运输路线。表 1 客户货物需求量和时间窗客户P1P2P3P4P5P6P7P8P9P10需求量0.71.50.80.41.41.50.60.82.50.620:321:320:521:5021:0022:021:2022:423:120:00000000时间窗22:2021:3021:4021:022:021:222:423:123:420:3

18、000000020:021:020:221:2020:3021:420:4022:122:419:30000000接受时间窗22:0022:2021:0021:322:321:522:5023:123:40:2000000表 2配送中心及客户之间的距离客户P0P1P2P3P4P5P6P7P8P9P10P00109788834107P1100491418181314114P294051014171213158P37950591510111713P481410906710121815P581814960710121815P681817151370681715P7313121011106021110

19、P841413111212820911P91011171518181711908P1074813151515101180表 3其他参数表序号名称符号单位数值1酸奶价格P元吨40003惩罚系数%0.24单位运输成本C元吨公里0.85运输速度V公里小时306装卸时间H分钟客户2094.1 确定第一条最优运输路线将客户按时间的先后顺序排列，得表4。计算每一客户之间连接的距离节约值，见表5。表 4 各客户按时间先后排序的时间窗户客户P10P1P3P5P7P2P4P6P8P9时 间20:0020:3020:5021:0021:2021:3021:5022:0022:4023:10窗20:3021:002

20、1:2021:3021:4022:0022:0022:4023:1023:40接 受19:3020:0020:2020:3020:4021:0021:2021:4022:1022:40时 间窗21:0021:3021:5022:0022:2022:3022:5023:1023:4000:20表 5客户之间连接的距离节约值客户P1P2P3P4P5P6P7P8P9P10P115840000913P215117300048P381110600001P447101030000P50361091000P6000395410P7000015520P8000004550P9940001259P1013810

21、00009按时间窗先后顺序，客户P10 要求的时间最早，因此客户P10 为第一客户。接下来客户选择见表6和表 7。表 6客户选择表 1客户节约运节约运惩罚节约选择输里程输成本成本总成本p1137.2807.28是p289.2否p310.64否p400否p50000否p600否p7002.4-2.4否p800否p9918否10表 7客户选择表 2客户节约运节约运惩罚节约选择输里程输成本成本总成本p12833.63.630.00是p32113.442.1111.33否p4175.440.964.48否p51314.561.8712.69否p61315.6411.6否p7136.2406.24否p8

22、117.04否p92244否4.2 具体计算过程：按时间窗先后顺序，客户P 要求的时间最早，因此客户P 为第一客户。接1010下来应先算出 P10 到各个客户之间节约运输里程、节约运输成本、惩罚成本。4.2.1节约运输成本的求法步骤：1、 通过节约法原理，求出每一客户之间连接的距离节约值。2、 节约运输成本 =节约运输里程运费某一客户的需求量表 5 中客户之间连接的距离节约值是由表2 配送中心及客户之间的距离计算可得。例如 : 表 5 中 P1 与 P2 的距离节约值=P1 到 P0 的距离 + P2 到 P0 的距离- P1 与 P2 的距离 =10+9-4=15。同理可得其它客户之间连接的

23、距离节约值。由表 5 可知， P 与 P 的距离节约值为13 公里，由表 1 可知 P 客户货物需求1011量为 0.7吨，由表 3 其他参数表可知，单位运输成本为0.8 元吨公里，所以 P10与 P1 节约运输成本为 =130.7 0.8=7.28 同理可得：与 p2 节约运输成本 =9.2 与 p3 节约运输成本 =0.64与 p4 节约运输成本 =0与 p5节约运输成本 =0与 p6 节约运输成本 =0与 p7节约运输成本 =0与 p8 节约运输成本 =0与 p9节约运输成本 =18114.2.2惩罚成本的求法：假设冷藏车送到客户 时，刚好是客户 的时间下线，即送到客户 的时间是 20:

24、10 ，由于装卸时间为 20 分钟，所以冷藏车从 20:30 从 出发；若选择客户 P1 ， P1 和 P10 之间的距离为7 公里，运送速度是 30 公里小时，可算出运送时间 t=7/30=0.24h 15 分，即冷藏车到达 P1 时是 20:45 ，在 P1 的时间窗范围内，所以惩罚成本为 0。若选择客户 P2， P2和 P10之间的距离为 8 公里，可算出运送时间 t=8/30=0.27h 17 分，即冷藏车到达 P2 时是 20:47 ，不在客户 P2 接受的时间范围内，即超出了客户 P2 可接受的时间 范围，因此惩罚成本是。同理算得 P3 、P4、 P5、 P6、 P8、 P9。若选

25、择客户P7，和 10 之间的距离是10公里，可算出运送时间t=10/30=20P7P分，冷藏车到达 P7时是 20:50 ，在客户 P7 的要求时间窗之外，在客户P7 可接受的时间范围内送达， 超出了要求时间 30 分钟，此时，需要支付相应的惩罚成本。惩罚成本 = Pw j t =0.2% 4000 0.6 (30/60)=2.4.4.2.3节约总成本节约总成本 =节约运输成本惩罚成本选出节约总成本最大的客户加入路线。根据表6、表 7 分析，第一条线路上的客户为 P 、 P 、 P ，此时运输车辆的载重量为Q=0.6+0.7+1.5=2.8t ，剩余的1012载重量无法满足剩余的其他任何客户，

26、所以第一条最优运输路线是：P0- P10- P1- P2 - P0 。同样的道理，可算得冷藏车的其他几条最优运输路线： P0 - P3 - P5 P4 - P0 、P0 - P7 - P6- P8- P0、 P0- P9 - P0 。具体内容如下：4.3 确定第二条最优运输路线在剩余的客户中客户P3 要求时间最早， 作为第一个客户。 接下来客户选择见12表 8、表 9。表 8客户选择表 3客户节约运节约运惩罚节约选择输里程输成本成本总成本p4103.21.61.60否p566.7206.72是p6004-4.00否p70000.00否p800否p900否表 9客户选择表 4客户节约运节约运惩罚

27、节约选择输里程输成本成本总成本p4165.1205.12是p773.360.962.40否p863.8430.84否从表 8 中可见，选择客户 P5 ，表 9 中可见，选择客户 P4 ，此时第二条最优运输路线为 P0 - P3- P5 - P4 - P0 。4.4 确定第三条最优运输路线在剩余的客户中， 客户 P7 要求的时间最早， 客户 P7 作为第一个客户。 接下来客户的选择见表 10 和表 11。表 10客户选择表 5客户节约运节约运惩罚节约选择输里程输成本成本总成本p6561.564.44是p852.402.40否p921.28否表 11客户选择表 6客户节约运节约运惩罚节约总选择输里程输成本成本成本P895.7605.76是P96120.6711.33否13根据表 10 和表 11，第三条线路选择的客户