（交通运输）冷链食品运输
路线优化
（交通运输）冷链食品运输
路线优化
冷链食品运输路线优化
物流 072班
组员：
粱利英（200700709075）、苏凤美（200700709071）、
周冬梅（200700709063）、梁小杰（200700709078）、
蓝冬菊（200700709060）、张欣欣（200700709080）、
周群(200700709058）、钟玲(200700709047)
摘要
食品工业要发展，速冻食品是壹条必经之路。冷链食品壹般定
义为适应于 0-4保存的食品，冷链食品具有易腐，易变质的特性。和
壹般食品相比较，冷藏食品运输的特点是运输装备的特殊性，即用冷
藏设备进行运输：运输时效性，即在冷藏食品保质期内送达，时效性
对于冷藏食品运输更为重要。如何在规定时间内，以最低成本运达冷
藏食品，是冷藏食品运输中要考虑的关键问题。运输成本主要取决于
运输路线，因此确定冷藏食品运输的最优路线是冷藏食品运输决策要
考虑的主要问题之壹。
近年来，物流配送车辆路径问题的研究已经引起了人们的广泛关
注，但对于冷藏食品的运输路线优化的研究仍不多见。本文根据冷藏
食品运输特性，以物流运营商运成本最低为目标，考虑超出客户时间
窗的惩罚成本，建立了冷藏食品运输路线优化模型。在路线优化方面，
通过建立节约里程模型找出运输的最佳路径，从而节约运输里程、运
达时间，最终降低运输成本。
关键词：冷藏食品运输路线优化模型
目录
摘要 2
目录 3
壹、背景介绍 4
中国食品冷链发展状况 4
我国冷链物流运输现状评价 4
我国冷冻冷藏食品市场和冷藏链物流发展 4
二、冷藏食品运输路线优化模型的建立 5
模型建立的基本思路 5
目标函数的建立 5
运输成本 5
惩罚成本。6
冷藏食品运输线路优化模型 6
三、模型算法 7
算法计算的基本思路 7
求解步骤 8
四、算例分析 9
确定第壹条最优运输路线 10
具体计算过程：11
节约运输成本的求法步骤：11
惩罚成本的求法：12
节约总成本 12
确定第二条最优运输路线 12
确定第三条最优运输路线 13
确定第四条最优运输路线 14
五、结论 14
【参考文献】15
壹、背景介绍
中国食品冷链发展状况
中国食品冷链的发展历程：冷链起源于 19世纪上半叶冷冻机的发明，到了电冰箱的出
现，各种保鲜和冷冻食品开始进入市场和消费者家庭。到 20世纪 30年代，欧洲和美国的食
品冷链体系已经初步建立。40年代，欧洲的冷链在二战中被摧毁，但战后又很快重建。当下
欧美发达国家已形成了完整的食品冷链体系。新中国的冷链最早产生于 50年代的肉食品外
贸出口，且改装了壹部分保温车辆。1982年，中国颁布“食品卫生法”，从而推动了食品冷
链的发展起步。近 20年来，中国的食品冷链不断发展，以壹些食品加工行业的龙头企业为
先导，已经不同程度地建立了以自身产品为核心的食品冷链体系，包括速冻食品行业，肉食
品加工企业，冰淇淋和奶制品企业和大型快餐连锁企业，仍有壹些食品类外贸出口企业。
我国冷链物流运输现状评价
随着城乡居民生活水平的提高和人们消费习惯的改变，以水产品、畜产品、果蔬及花卉
为代表的冷链物流日渐趋热，成为人们关注的焦点。
所谓冷链物流泛指冷藏冷冻类食品在生产、贮藏运输、销售，到消费前的各个环节中始终处
于规定的低温环境下，以保证食品质量，减少食品损耗的壹项系统工程。它是随着科学技术
的进步、制冷技术的发展而建立起来的，是以冷冻工艺学为基础、以制冷技术为手段的低温
物流过程。
冷链物流的适用范围包括初级农产品：蔬菜、水果；肉、禽、蛋；水产品、花卉产品。
加工食品：速冻食品、禽、肉、水产等包装熟食、冰淇淋和奶制品；快餐原料。特殊商品：
药品。由于食品冷链是以保证易腐食品品质为目的，以保持低温环境为核心要求的供应链系
统，所以它比壹般常温物流系统的要求更高、更复杂，建设投资也要大很多，是壹个庞大的
系统工程。业内人士指出，目前，我国的冷藏物流业尚处于初级阶段，市场规模不大，区域
性特征比较强，缺乏有影响力的、全国性的第三方冷藏物流行业领袖。从全国范围来见，原
有冷藏链设施壹般自成系统、时有断裂、不能连网、效率低下，距离构建现代化低温物流体
系差距甚大。
我国冷冻冷藏食品市场和冷藏链物流发展
我国冻制食品自 20世纪六十年代开始出现，主要是冻肉、冻禽和冻水产品，为保障市
场供应，调节淡旺季和全国计划调运，国内主要产地和大城市兴建了壹批大型冷库，且由铁
路冷藏车和水运冷藏船相联，形成了冻制品产地——冷藏货车——冷库——市场之间的网
络。这种以食品原料冷冻、贮存和运输为目的的初级冻制品冷藏链，在较长时间内，对保障
国内副食品供应及出口贸易起了重要作用。
随着我国加入 WTO，如何运用现代科学技术，成功开发各种冷冻冷藏温度带食品，建设
完善可靠、规范管理的食品冷藏链且提高社会公用化程度，全面提升我国食品安全和品质，
充分利用食品资源，减少易腐食品损失，加快农产品深加工，适应国内外市场需求，是冷冻
食品产业和冷藏链设备制造业及相关产业共同面临的新课题。
二、冷藏食品运输路线优化模型的建立
模型建立的基本思路
定义路网 G=（V,A）,其中，V={，，···，}为点的集合，A={，}：，∈V,i≠j为路段集
合，代表冷藏食品运输中心，（i=1,2,···，n）代表所服务的第 i个客户，客户 i的需求量
为。运输中心的运送车辆路线用 l表示，共有 m部运送车辆，故 l=1，2，···，m）。而为第 l
部车辆在路段（，）上的运输成本，且=。显然，i=j时，=0.
将超出客户时间窗的惩罚成本及随里程递增的运输成本作为冷藏食品运输商
的运输总成本，以运输成本最小为目标，求解模型，以获得最佳的运输路线。（忽
略冷藏食品易腐性造成的货损成本）
目标函数的建立
构建模型时，将运输的综合成本作为目标函数。冷藏食品的运输综合成本包
括：车辆运输成本，以及超出客户时间窗的惩罚成本。
运输成本
运输成本包括固定成本和变动成本，其中固定成本为常数，和运输里程及客
户数量没有直接关系，这里只考虑运输车辆的变动成本，可表示为：
=（1）
其中，=为第 l部车辆在路段（，）上的运输成本，为从第 i点到第 j点运送单位冷藏食
品的运费，为从第 i点向第 j点运送冷藏食品的数量；为 0、1变量，若第 l车辆行经（，）
路段，则=1，否则=0。
惩罚成本。
时间过长，冷藏食品易腐烂，故在其运输中对时间有严格的限制，即属于有
时间窗限制的运输问题。在实际运输中，运输中心派出的运输车辆到达客户的时
间，有三种情况，即：
（1）在要求时间窗内运达；
（2）在要求时间窗之外，客户能够接受范围内运达；
（3）延迟且超出客户能够接受的范围内运达。
第壹种情况下运达，能够进行货物交换，没有惩罚成本。第二种情况运达，
货物能够交接，但需要支付相应的惩罚成本。第三种情况下运达，无法完成运输
任务，在模型中不考虑。
设客户 j的时间窗上线为，下限为，可接受的范围时间上限,。则惩罚成本表
示为：
（3）
式（3）中为冷藏食品运达客户的时间，为客户 j的货物数量；λ为惩罚系数。
则总的惩罚成本为：
=（4）
冷藏食品运输线路优化模型
以运输总成本最小为目标，受约束条件限制，确定出冷藏食品最优的运输路
线。
线路优化模型为：
Min(5)
三、模型算法
上述建立的运输线路优化模型为非线性规划问题，求解比较复杂。采用启发
性算法，简化该问题的求解。
算法计算的基本思路
采用寻找最邻客户法，确定线路中第壹位被服务的客户。最临近的客户是指
满足时间窗的和车辆容量限制，且且尚未被排入任壹线路的客户。该客户加入线
路，除了满足上述俩条件之外，仍应该满足加入成本最低原则，即新加入的客户
能使新增成本最低，从而保证运输成本最低。
采用节约法求解：节约算法的核心思想是将运输问题中存在的俩个回路（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、运输里程顺序。运输里程直接影响运输成本和货损成本，对运输总成本
很大，作为第二顺序。
求解步骤
根据上述算法，具体求解步骤如下：
（1）初始化，输入已知的参数；
（2）由配送中心开始寻找“最邻客户”，加入成为第壹条路线上的第壹位被
服务的客户；
（3）令 i为某壹线路上最后壹位加入的客户。重复步骤（2），得到下壹个邻
近客户 j。依次加入当前线路中。若所有尚未被排入任壹路线的客户均无法
满足时间窗限制或车辆容量限制，则重新建立壹条新的路线，直到所有客户
全部排入线路为止。
四、算例分析
壹配送中心，向 10个客户（j=1，2，···，10）配送酸奶。酸奶保存期限为 24小时，
配送温度为 0℃。客户的需求量和时间窗见表 1.配送及客户间的距离（Km）见表 2.运输任务
由配送中心利用 q=3t的冷藏车来完成，其他参数见表 3。确定最佳运输路线。
表 1客户货物需求量和时间窗
客户 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
需求量
20:3
0
21:3
0
20:5
0
21:50 21:00
22:0
0
21:20
22:4
0
23:1
0
20:00
— — —
—22:2
0
—21:3
0
—
—21:4
0
— — —时间窗
21:0
0
22:0
0
21:2
0
22:4
0
23:1
0
23:4
0
20:30
接受时间
窗
20:0
0
21:0
0
20:2
0
21:20 20:30
21:4
0
20:40
22:1
0
22:4
0
19:30
— — — —
—22:0
0
—
—22:2
0
— —
—21:0
0
21:3
0
22:3
0
21:5
0
22:50
23:1
0
23:4
0
0:20
表 2配送中心及客户之间的距离
客户 P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
P0 0 10 9 7 8 8 8 3 4 10 7
P1 10 0 4 9 14 18 18 13 14 11 4
P2 9 4 0 5 10 14 17 12 13 15 8
P3 7 9 5 0 5 9 15 10 11 17 13
P4 8 14 10 9 0 6 7 10 12 18 15
P5 8 18 14 9 6 0 7 10 12 18 15
P6 8 18 17 15 13 7 0 6 8 17 15
P7 3 13 12 10 11 10 6 0 2 11 10
P8 4 14 13 11 12 12 8 2 0 9 11
P9 10 11 17 15 18 18 17 11 9 0 8
P10 7 4 8 13 15 15 15 10 11 8 0
表 3其他参数表
序号 名称 符号 单位 数值
1 酸奶价格 P 元∕吨 4000
3 惩罚系数 λ %
4 单位运输成本 C 元∕吨公里
5 运输速度 V 公里∕小时 30
6 装卸时间 H 分钟∕客户 20
确定第壹条最优运输路线
①将客户按时间的先后顺序排列，得表 4。
②计算每壹客户之间连接的距离节约值，见表 5。
表 4各客户按时间先后排序的时间窗户
客户 P10 P1 P3 P5 P7 P2 P4 P6 P8 P9
时 间
窗
20:00
—
20:30
20:30
—
21:00
20:50
—
21:20
21:00
—
21:30
21:20
—
21:40
21:30
—
22:00
21:50
—
22:00
22:00
—
22:40
22:40
—
23:10
23:10
—
23:40
接 受
时 间
窗
19:30
—
21:00
20:00
—
21:30
20:20
—
21:50
20:30
—
22:00
20:40
—
22:20
21:00
—
22:30
21:20
—
22:50
21:40
—
23:10
22:10
—
23:40
22:40
—
00:20
表 5客户之间连接的距离节约值
客户 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
P1 — 15 8 4 0 0 0 0 9 13
P2 15 — 11 7 3 0 0 0 4 8
P3 8 11 — 10 6 0 0 0 0 1
P4 4 7 10 — 10 3 0 0 0 0
P5 0 3 6 10 — 9 1 0 0 0
P6 0 0 0 3 9 — 5 4 1 0
P7 0 0 0 0 1 5 — 5 2 0
P8 0 0 0 0 0 4 5 — 5 0
P9 9 4 0 0 0 1 2 5 — 9
P10 13 8 1 0 0 0 0 0 9 —
③按时间窗先后顺序，客户要求的时间最早，因此客户为第壹客户。接下来客户
选择见表 6和表 7。
表 6客户选择表 1
客户
节约运
输里程
节约运
输成本
惩罚
成本
节约
总成本
选择
p1 13 0 是
p2 8 ∞ －∞ 否
p3 1 ∞ －∞ 否
p4 0 0 ∞ －∞ 否
p5 0 0 0 0 否
p6 0 0 ∞ －∞ 否
p7 0 0 否
p8 0 0 ∞ －∞ 否
p9 9 18 ∞ －∞ 否
表 7客户选择表 2
客户
节约运
输里程
节约运
输成本
惩罚
成本
节约
总成本
选择
p1 28 是
p3 21 否
p4 17 否
p5 13 否
p6 13 4 否
p7 13 0 否
p8 11 ∞ －∞ 否
p9 22 44 ∞ －∞ 否
具体计算过程：
按时间窗先后顺序，客户要求的时间最早，因此客户为第壹客户。接下来应
先算出到各个客户之间节约运输里程、节约运输成本、惩罚成本。
节约运输成本的求法步骤：
1、通过节约法原理，求出每壹客户之间连接的距离节约值。
2、节约运输成本=节约运输里程×运费×某壹客户的需求量
表 5中客户之间连接的距离节约值是由表 2配送中心及客户之间的距离计算
可得。例如:表 5中和的距离节约值=到的距离+到的距离-和的距离=10+9-4=15。
同理可得其它客户之间连接的距离节约值。
由表 5可知，和的距离节约值为 13公里，由表 1可知客户货物需求量为
吨，由表 3其他参数表可知，单位运输成本为 元∕吨公里，所以和节约运输
成本为=13××=同理可得：
和 p2节约运输成本=和 p3节约运输成本=
和 p4节约运输成本=0和 p5节约运输成本=0
和 p6节约运输成本=0和 p7节约运输成本=0
和 p8节约运输成本=0和 p9节约运输成本=18
惩罚成本的求法：
假设冷藏车送到客户时，刚好是客户的时间下线，即送到客户的时间是20:10，
由于装卸时间为 20分钟，所以冷藏车从 20:30从出发；
若选择客户，和之间的距离为 7公里，运送速度是 30公里∕小时，可算出
运送时间 t=7/30=≈15分，即冷藏车到达时是 20:45，在的时间窗范围内，
所以惩罚成本为 0。
若选择客户，和之间的距离为 8公里，可算出运送时间 t=8/30=≈17
分，即冷藏车到达时是 20:47，不在客户接受的时间范围内，即超出了客户可接
受的时间范围，因此惩罚成本是∞。同理算得、、、、、。
若选择客户，和之间的距离是 10公里，可算出运送时间 t=10/30=20分，冷
藏车到达时是 20:50，在客户的要求时间窗之外，在客户可接受的时间范围内送
达，超出了要求时间 30分钟，此时，需要支付相应的惩罚成本。惩罚成本==%
×4000××(30/60)=.
节约总成本
节约总成本=节约运输成本－惩罚成本
选出节约总成本最大的客户加入路线。根据表 6、表 7分析，第壹条线路上
的客户为、、，此时运输车辆的载重量为 Q=++=，剩余的载重量无法
满足剩余的其他任何客户，所以第壹条最优运输路线是：----。同样的道理，可
算得冷藏车的其他几条最优运输路线：---、----、--。具体内容如下：
确定第二条最优运输路线
在剩余的客户中客户要求时间最早，作为第壹个客户。接下来客户选择见表
8、表 9。
表 8客户选择表 3
客户
节约运
输里程
节约运
输成本
惩罚
成本
节约
总成本
选择
p4 10 否
p5 6 0 是
p6 0 0 4 否
p7 0 0 0 否
p8 0 0 ∞ －∞ 否
p9 0 0 ∞ －∞ 否
表 9客户选择表 4
客户
节约运
输里程
节约运
输成本
惩罚
成本
节约
总成本
选择
p4 16 0 是
p7 7 否
p8 6 3 否
从表 8中可见，选择客户，表 9中可见，选择客户，此时第二条最优运输路
线为----。
确定第三条最优运输路线
在剩余的客户中，客户要求的时间最早，客户作为第壹个客户。接下来客户
的选择见表 10和表 11。
表 10客户选择表 5
客户
节约运
输里程
节约运
输成本
惩罚
成本
节约
总成本
选择
p6 5 6 是
p8 5 0 否
p9 2 ∞ －∞ 否
表 11客户选择表 6
客户 节约运
输里程
节约运
输成本
惩罚
成本
节约总
成本
选择
P8 9 0 是
P9 6 12 否
根据表 10和表 11，第三条线路选择的客户为、、，因为虽然此时节约的总成
本比大，若选择，运输车辆的载重量为 Q=++=，超过了冷藏车的载
重量，因此第三条最优运输路线为：----。
确定第四条最优运输路线
只剩余客户，单独作为第四条运输路线，即--。
综上分析，冷藏车的最优运输路线是：----、---、----、--。
五、结论
（1）冷链食品具有易腐性，所以必须要在客户接受的时间窗内送到客户手中，
本研究考虑了超出客户时间窗的惩罚成本等多个因素，通过运输路线的优化使节
约运输成本和惩罚成本的总成本之和最小。
（2）运用启发式算法，寻找“最临客户”，“最临客户”包括时间窗最临和运输
里程最临俩个方面。以时间窗为第壹顺序原则，然后再通过运输里程顺序，以成
本最低为原则，找出冷链食品运输路线模型的求解算法。
（3）把启发式算法运用到我们的实际例子，通过求解得出所需的最优配送路线，
从而提高客户服务水平和降低配送成本。
（4）研究展望：通过提供完整的配送服务使冷链食品的配送服务最大限度的适
应企业的发展能力，从而为各零售企业、食品企业提供更全面的服务。满足客户
的需要的情况下尽量降低总成本。
【参考文献】
[1]杨晓楼,许増茂，我国冷藏食品物流市场现状及发展趋势[j].重庆交通学院学
报（社科版），2005。
[2]刘兴，基于协作的车辆路径问题的研究[D]，天津，天津大学，2006。
[3]刘贵英，随机车辆路径问题模型及算法研究，西安;长安大学，2006。
[4]谢秉磊，随机车辆路径问题研究[D]，西安，西安交通大学，2003。
[5]刘荣华，孙浩，赵娟，基于供应链的运输决策[J]，中国海洋大学学报，
2007。[6]俞明南，刘申，李阳，物流管理中运输决策[J]，辽宁师范大学学报（自
然科学版），2005。
[7]张得志，凌春雨，多种运输方式组合优化模型及求解算法[J]，长沙铁道学院
学报，2002。
