1引言

我国冷链物流模式落后、损耗大、成本高,无法满足当前社会对冷链物流的巨大需求。有关数据显示在我国冷链物流的配送过程中,水果损耗为25% ,蔬菜损耗为30% ,肉类和水产品损耗为12% 和15% ,损耗量居世界首位,其损耗能够满足2亿人口的基本需求,每年由此造成经济损失达上亿元。配送是冷链物流中重要的环节,但其研究的滞后己成为制约冷链物流业发展的瓶颈[1]。

冷链物流配送路径优化问题的理论基础是车辆路径问题 ( VRP) ,其早已被证明是一个NP - hard问题,精确算法很难得到全局最优解[2],只能依靠一些启发式算法[3,4,5]。随着冷链物流的发展,研究学者将VRP问题带入到特定的领域,取得了一些成果。如刘镇等[6]构建了冷链物流配送路径优化模型,并在云计算环境下利用遗传算法进行求解; 杨玮等[7]利用粒子群算法求解冷链物流配送模型,为农产品配送提供了借鉴。然而,对于冷链物流配送路径的研究目前还处于初级阶段,大部分研究只停留在定性阶段,许多研究并没有深入考虑到冷链物流的特性。

“良中行”是国内首家专注于提供冷藏冷冻食品供应链服务的专业公司,为了提高冷链班车的装载率、降低单位配送成本,良中行公司会在配送过程中对冷链食品进行中转。这种状况会延长冷链食品的在途时间,丧失冷链食品的时效性和企业的美誉度。基于此,本文拟对良中行公司的食品冷链配送路径优化问题进行研究,通过合理安排冷藏车辆的配送路径和车辆的装载率,有效减少中转环节,缩短中转时间,提高食品冷链配送的及时性、降低食品冷链的运输成本。

2基于时间窗的冷链物流运输路径优化模型

2. 1模型建立

2. 1. 1模型及问题描述

假设冷链配送中心f为多个客户( N,N = { 1,2,…,n} ) 服务,配送的产品类型单一,客户i对某种食品的需求量为gi。车辆送货方向单一; 配送中心每天派出k辆载重量为G0的车,每辆车从配送中心出发为一个或者多个客户服务完后返回配送中心,车k配送路径即为一条路径k,其中k = 1,2,…, K; 车辆以均匀速度v行驶; 每个客户的需求量与地点已知,而且只能被一辆车辆完成配送需求,所有客户得到服务;

2. 1. 2构建模型

考虑到冷链配送过程中的制冷成本和惩罚成本,本文提出一种全新的冷链物流的配送路径优化模型。模型以物流系统总成本最小为目标,总成本包括: 运输成本、制冷成本以及超出客户需求时间所造成的惩罚成本。

1配送车辆的运输成本。运输成本可分为固定成本和变动成本。固定成本为常数,如车辆折旧等费用,与运输里程和客户需求量没有直接联系。为计算方便,在本模型中不予考虑。而变动成本则与车辆行驶里程成正比,配送车辆运输成本采用公式( 2 - 1) 计算。

其中:

式( 2) 为车辆的载重约束; 式( 3)为需求点i由车辆k完成的唯一性约束; 式( 4) 和式( 5)为每个需求点只路径一次的唯一性约束; 式( 6)为时间窗约束。

2配送过程中的货损成本。冷冻冷藏产品在配送过程中由于温度等多种不可控因素会导致产品受损,因此产生货损成本。货损成本主要由以下两种情况产生:一种情况是运送时间累积使得产品受损; 另一种情况是装卸货打开冷藏车门导致产品毁坏,因而产生货损成本。计算公式如下( 7)

其中: η冷藏冷冻食品单价; η1配送过程中冷藏冷冻食品货损比例; η2装卸过程中冷藏冷冻食品货损比例; dij客户i到客户j的距离;

3超出客户配送时间的惩罚成本。超出客户要求的服务时间会造成惩罚成本。本模型中采用软时间窗方法计算惩罚成本。当配送到达时间为[t2,t3]时,无惩罚成本; 当配送到达时间为[t1,t2]或者[t3,t4]时,产生固定的惩罚成本为α; 当配送到达时间为[∞ ,t1]或者[t4,∞]时,惩罚成本无限大为M。从而可得惩罚成本计算公式如( 8)

4配送过程中的制冷成本。冷链物流配送产品要求配送过程中始终处于低温冷藏状态,从而产生制冷成本。制冷成本包括运输中的制冷成本及装卸时的制冷成本。其中,运输过程中的制冷成本与行驶时间成正比。装卸所产生的制冷成本主要是车门打开时热交换所产生的,所以只需计算通过车门的热交换所产生的制冷成本。计算公式如( 9)

其中,Gt为车辆热负荷; θ为常数,表示车辆车厢的劣化程度; R为热传导率,单位为( W/( m2·K)); S为车体的平均表面积,S =槡Sw Sn,Sw为外表面积,Sn为内表面积,单位均为m2; ΔT = Tw- Tn,为车内外温差,单位为K; t为车辆配送过程中总的行驶时间; p为单位制冷成本; Gs为车辆开门消耗的热负荷; V为车厢体积; β为开门程度系数;

5建立目标函数。根据上述不同成本的分析,建立目标函数如下:

2. 2算法设计

2. 2. 1编码方式

本文采用自然数编码方法构造问题解向量的染色体结构。每个染色体长度为n + m + 1,即: G = ( 1,i11,i12,∧,i1t,1, i21,i22,∧,i2t,1,iml,im2,∧,imt,1) ,表示一条可行配送路线。该式的含义是: 第m辆配送车从“0”出发,完成对“im1,im2,…∧,int”的配送后,又回到“0”,形成了子路径,m以此反复,直到完成对所有需求点的配送。

2. 2. 2遗传算子设计

1选择算子。选择操作通过选择优质个体、抛弃劣质个体,使得种群中的适应度值不断接近最优解。选择操作中选择概率函数为:

2交叉算子和变异算子。变异操作模拟生物突变生成新物种的状态,使得种群局部收敛时可以保持种群的多样性。交叉概率函数和变异概率函数分别为

其中: fmax为群体中最大的适应度值; favg为群体的平均适应度值; f'为需要交叉的个体中较大的适应度值; f将变异个体的适应度值。分别用式( 16) ( 17) 得出的两个适应度计算Pc、Pm,选取其中较大的作为最终的Pc、Pm。

2. 3算例分析

2. 3. 1数据来源

以良中行公司给市区内10个客户点进行冷链物流配送的服务过程为实例。为保证海产品的新鲜度,保存时限为72h,冷藏车内温度控制在规定范围内。配送中心编号为“0”, 各配送点的需求量、坐标值、时间窗约束和服务时间见表1所示。

表 1 各配送点的货物需求量 - 坐标值 - 时间窗 - 服务时间 

2. 3. 2算法实现

为了提高一次运载量,降低单位配送成本,路况较好的情况下应尽量选择大型车辆完成配送任务,因此本文选取载重量11t的冷藏车作为配送车辆。图1为运行CEGA算法得到的收敛曲线。

图 1 算法的收敛情况   

由图1可知,算法在110次迭代时逼近最优解,对最优解进行解码得到最优配送方案,见表2和图2。

表 2 优化的配送方案

图 2 最优解配送路线  

对最优解配送路径下的最优成本进行计算可得:

3分析与结论

考虑到冷链物流配送过程中产生的货损成本、冷冻设备消耗的制冷成本、违反客户时间约束的惩罚成本以及车辆的固定成本和运输成本,本文建立了以总成本最小为目标的带软时间窗的冷链物流配送优化模型。通过算例验证可知,该模型不仅能够为冷链物流配送企业选择最优的路径,而且可以大幅降低配送的系统成本。该优化模型可行、有效,值得推广和借鉴。