近年来,人们对生鲜蔬菜、瓜果、肉蛋奶等易腐品需求日益增多,同时对其品质要求也日趋苛刻。易腐品具有容易腐败变质,不易保鲜,较难运输与储存的特点,其新鲜度在存储和运输过程中随时间流逝而降低,导致消费者可接受度降低。 发展冷链配送是易腐品物流的重要战略举措,在保障易腐品品质要求的前提下,合理控制配送成本对于冷链物流发展具有重要的现实意义。

配送中心选址和车辆配送路径是影响易腐品冷链物流的两个重要因素,车辆路径问题( 由Dantzig和Ramser[1]于1959年首次提出,1964年Clarke和Wright[2]提出了对Dantzig Ramse方法改进的一种启发式算法,以上两篇论文的发表使VRP成为运筹学的研究热点问题。Tarantilies[3]等研究了雅典市区新鲜肉类配送路径优化问题,叶勇[4]等运用改进遗传算法对畜禽冷链进行了相关的优化研究,何静[5]等对连锁超市生鲜食品冷链物流网络的构建与优化进行了研究,杨建华[6]等对碳税约束下的城市冷链物流配送网络进行了设计, 黄华芳[7]等对果蔬运输车辆路径进行了再规划,陈迎欣[8]基于改进蚁群算法对车辆路径优化问题进行了研究,龚树生,梁怀兰[9]等对生鲜食品的冷链物流网络进行了研究,徐优香[10]基于云计算对冷链物流配送车辆路径优化方法进行了相关研究。易腐品冷链物流具有时变特性,基于此本文建立了将车辆运输成本,冷藏成本、货损成本以及配送中心运营成本考虑在内的总成本最小的优化模型,以郑州市某肉类连锁公司配送进行实证计算,运用改进遗传算法确定其配送中心的选址及配送路径。

1易腐品冷链配送中心选址及配送路径优化模型

1. 1问题描述

1. 1. 1配送中心选址

经典的配送中心选址优化假定配送中心备选位置已知, 对车辆配送路径进行优化。由于实配送中心的选址对整个配送路径优化具有决定性的作用,而配送中心的位置关系到整个物流网络的规模与结构,并且对用户点的配送路径产生至关重要的影响,从而使整个成本发生重大变化。本文假设配送中心数目一定,位置不确定,配送中心建设属于固定资产投资,投入成本较大,假定不同位置配送中心建设成本相同。根据配送中心坐落位置不同,对配送路线进行多次优化,以寻求一条总成本最低的路线。

1. 1. 2配送路径优化

随着冷链物流运输网络日趋复杂,并伴随交通条件等的变化其地理分布也在扩大,使得冷链物流的配送网络优化与经典TSP问题不同,配送产品的易腐性使得在配送过程中不仅要考虑运输成本,还要考虑其因冷藏保温而产生的冷藏成本以及在路途上易腐品腐烂变质而产生的货损成本等。

1运输成本。

行驶车辆的运输成本由燃油消耗而产生,而燃油消耗量取决于车辆在途中行驶的时间。行驶的时间由车辆行驶的速度、距离、以及路况等因素决定。由于路况信息过于复杂,本文假定车辆在整个运行过程中匀速行驶。

2冷藏成本。

冷藏成本受两个因素影响。一是车辆在途中运行时产生的成本,二是当车辆到达某一具体用户时,进行装卸货产生的成本。由于车辆的载重量一定,且车辆的载重量与所有用户的需求量是相同的,因此装卸货产生的成本为定值,故只考虑运送过程中时间的影响。

3货损成本。

对于易腐品,根据其类型的不同,其腐败变质的程度、特点均有所不同。但从整体上看,影响其腐败程度的因素有: 微生物( 细菌,霉菌,酵母) 、易腐品特性( 营养组成,PH值, 酶,水分含量,渗透压,完整性) 以及环境因素( 温度,湿度, 氧气,光线) 。但由于易腐品种类繁多,很难找到统一的货损比例对其进行描述。本文假设在货物运输过程中其腐败变质具有阈值特点,即阈值点以前货物损坏缓慢,但超过阈值后货物就会迅速损坏,其产品的货损比例与车辆的配送时间成正比。

1. 2模型建立

假设配送中心向多个用户配送,配送的货物类型单一,单次配送只需一辆货车,车辆配送完所有用户返回配送中心,每个用户的位置与需求量已知。

1. 2. 1符号说明

Cy———车辆的运输成本;

C0———车辆单位里程的运输费用;

V0———车辆匀速行驶的速度;

Tij———车辆从用户i到用户j的行驶时间;

cs ——— 产品货损成本;

p———产品单价;

θ———单位时间货损系数;

Cz———运输过程中的冷藏成本;

L——— 单位时间制冷成本;

C———运输总成本;

qi———用户i的需求量;

Q——— 车辆的载重量;

Xij= { 1表示用户i,j存在直接路线; 0表示车辆在用户i,j之间不存在直接路线}

1. 2. 2构建模型

式( 1) 中的三项分别表示配送中心向各个用户点的运输成本,货损成本和冷藏成本;

式( 2 ) 表示配送中心到用户点的运输成本;

式( 3 ) 表示配送中心到用户点的货损成本;

式( 4 ) 表示配送中心到用户点的冷藏成本;

式( 5) 表示所有用户对产品的需求量不大于车辆的载重量。

1. 3遗传算法求解

1. 3. 1遗传算法描述

配送路径优化求解方法可以分为精确算法和启发式算法两类。精确算法主要有动态规划法,分枝定界法,切平面法等,启发式算法主要有节约算法,邻接算法,插入算法,扫除算法,禁忌搜索算法,蚁群算法,粒子群算法等。本文采用遗传算法进行求解,相对于其他的启发式算法,遗传算法求解的结果是相对稳定的,且应用范围广泛。

遗传算法是模拟达尔文生物进化论的自然选择和遗传机制的一种启发式算法,从初始解出发,通过模拟自然进化过程寻找最优解,其算法流程如图1所示:

图 1 遗传算法流程图   

1. 3. 2遗传算法改进

1进化逆转操作。

本文中采用的交叉操作为部分映射杂交,对两父本进行中间数据交叉后,将重复编号消除。这种变异算子可以使种群内部维持多样性,即可避免陷入局部最优解; 但其对子代继承父代优良信息具有较大影响,尤其在进化后期,对父代优秀基因破坏很大。因此不仅进行选择,交叉,变异三大操作,还加上进化逆转操作。进化逆转可以使子代继承较多的父代基因,从而保持父代优秀基因的传承。

2采用精英策略。

子代群体中的最优个体永远比父代种群中的最优个体强,这样父代中的 优秀个体 不会因为 变异交叉 等操作而 消失。

1. 4实证计算

郑州市某肉制品连锁企业通过冷链配送中心向其覆盖的所有用户点进行配送,假设配送货物类型单一,单次配送采用单辆货车,车辆配送完所有用户后返回配送中心,每个用户的位置与需求量已知。其中各用户点的坐标见表1,相关参数见表2,安排合适的配送路线使总配送成本最优。

表 1 各点位置表

表 2 相关参数  

按照改进遗传算法,通过对郑州市某肉制品连锁企业这一实际问题的参数进行编码,生成初始种群,采用相应的适应度函数对这一问题进行个体评价。当未达到进化代数时,对其依次进行选择,交叉,变异,进化逆转操作,然后产生新种群后重复个体评价之后操作,直到满足终止条件,退出输出结果。程序设置参数为: 种群大小为100,循环次数200,交叉概率0. 9,变异概率0. 05,代沟为0. 9。在Matlab R2012b环境下进行计算,其结果如图2 ~ 图5所示:

图 2 用户坐标   

图 3 初始配送路径   

图 4 遗传算法优化过程  

图 5 最优配送路径   

图2显示的是郑州市某肉制品连锁企业所需配送的各个用户点的坐标位置,图3是程序自动产生的初始种群中的一个随机值,其路线描述如下所示:

7 - > 9 - > 3 - > 16 - > 6 - > 2 - > 20 - > 18 - > 8 - > 15 - > 4 - > 12 - > 11 - > 13 - > 19 - > 10 - > 21 - > 5 - > 22 - > 1 - > 17 - > 14 - > 7

在此行驶路线下,配送车辆需要行驶的总距离为: 81 9281。通过近200次的优化过程,可找到一条最优的路线,其最优路线如下所示:

7 - > 1 - > 8 - > 2 - > 9 - > 18 - > 10 - > 19 - > 20 > 4 - > 3 - > 15 - > 12 - > 16 - > 6 - > 14 - > 21 - > 5 - > 13 - > 22 - > 11 - > 17 - > 7

在此最优路径下其行驶距离为: 33. 24

从计算结果中我们可以看出,最初随机产生的路线距离有81. 9281。而经过了200次的优化,将最终的路线减少到33. 24。并且选择7号点作为配送中心。配送总成本为318 6608元。

2结论

本研究构建了基于成本最优的易腐品冷链网络优化模型。在目标函数中,除了引入传统路径优化中的运输成本,也考虑了因为低温冷藏而产生的冷藏成本和时变因素产生的货损成本。最后通过遗传算法和MATLAB对算例进行分析与计算,结果表明考虑冷藏成本与货损成本的易腐品冷链网络优化模型更适合冷链物流的配送,对易腐品冷链配送路径优化具有重要的意义。