基于随机需求的冷链物流路径优化问题研究

邓红星,刘 敏,王 猛

(东北林业大学 交通学院，黑龙江 哈尔滨 150040)

我国生鲜市场的规模日益扩大，但冷链物流从质量和数量两方面的配送都不能完全满足消费者需求，发展滞后，同时配送企业间竞争的关键因素是高效保质的配送环节，为提高企业的经济效益与市场竞争力需要同时兼顾低配送成本和高配送效率，因此，路径优化问题一直是国内外学者的研究热点。冷链物流路径问题研究分为配送路径模型和算法两方面。冷链物流路径优化算法方面：张晓娜、廖吉林[1]通过蚁群算法进行路径优化求解；Ai T J和Kachitvichyanukul V[2]设计了两种不同的解编码方法(SR-1和SR-2)来生成初始解,改进粒子群算法求解CVRP问题；Mingyao Q I，Ding G等人[3]提出了一种基于时空度量的顾客分组方法和禁忌搜索算法来求解带时间窗的车辆路径问题；王进成、高岳林[4]提出一种改进的鸟群优化算法，以较好的收敛速度和寻优精度构建求解模型；蔡浩源[5]等人通过人工蜂群算法求解带有时间窗的农产品冷链物流路径优化模型；罗耀[6]在标准粒子群算法基础上引入微生物行为机制中的趋化、繁殖、迁移算子，提高搜索精度和收敛速度。在冷链物流路径优化模型方面：刘建仁[7]建立双层规划模型，通过上下层规划模型的相互作用达到冷链物流配送开放式车辆路径优化目的；梁承姬、邹倩倩[8]建立将温度作为决策变量之一的以运输成本、货损成本和制冷成本为总配送成本的模型；杨沈记[9]针对城市复杂路况从同城冷链配送的角度研究配送路径的优化问题；刘路[10]考虑配送企业使用不同制冷能力的冷藏车辆混合进行配送的情况和卸货时间等因素寻找控制成本和保证客户满意度之间的平衡。

目前大多数研究跨省市的冷链物流配送运输，因此，本文针对某市内的生鲜肉类企业进行路径优化研究。为更符合实际配送情况，本文将顾客需求转化为服从分布的随机需求，并设定配送过程中满足顾客需求量的满足率；将顾客对时间的需求转化为软时间窗[11]函数模型，并同步建立惩罚成本机制；将行驶时间的长短作为车辆通达程度和道路顺畅程度衡量的标准。提高模型的精准度和实际价值。

1 影响因素分析

1.1 需求分析

在生鲜农产品配送过程中，顾客满意度是衡量企业配送水平的重要标准之一[7]，因此需要满足顾客对配送时间要求以及提升不确定情况下的柔性处理能力。

1)需求量分析。顾客的需求量是配送成本中需要重点考虑的因素。实际配送中顾客需求量在不断变化，本文把顾客需求转化为服从分布的随机需求，并设定配送过程中满足顾客需求量的满足率。

2)需求时间分析。交通堵塞、车辆调度等实际交通状况使得硬时间窗的要求失效。为协调性地解决顾客对配送时间的需求，本文建立软时间窗[8]函数模型，并同步建立惩罚成本机制。

1.2 三级货损

相应的冷链物流产品生命周期变质率分布情况如图1所示。

t∈[0,A]属于第一阶段，此时生鲜品的品质完好，暂无变质的可能性，货物变质率为0；

t∈[A,B]属于第二阶段，由于搬运包装装卸等一系列操作，生鲜品开始发生腐坏，货物变质率可用θt=(t-A)∕(C-A)表示；

t∈[B,C]属于第三阶段，此时的生鲜品已经严重腐坏，无法满足顾客正常需求。

图1 冷链物流产品生命周期变质率分布

1.3 制冷时长

考虑到整个配送流程，本文将制冷分为两部分，一是运输配送制冷，二是装卸搬运制冷。

1)运输配送。从供应点到配送中心再到需求点的运输途中，企业为保证生鲜品的品质需要使用冷藏车、保温箱等特殊运输工具，因此需要一定的制冷。

2)装卸搬运。当冷藏车到达库存进行周转和顾客节点时，需要将生鲜农产品进行卸载，开启车口的时间越久，需要的制冷成本也就越高[8]。

2 问题描述及模型建立

2.1 问题描述

城市冷链物流路径优化要兼顾低成本和高效率，建立随机客户需求且带时间窗的多目标组合最小配送成本函数模型，除了考虑基本的固定成本、运输成本、制冷成本，还要考虑在运输和搬运过程中，货物即使在冷藏环境下也会发生一定的变质或腐坏，存在货损成本，未能在规定时间内送达产生的惩罚成本以及允许缺货产生的缺货成本。研究的重点在于考虑包含以上六项成本的复合函数最小化的同时缩短配送里程数，保质保量地高效送达需求节点。

本文考虑单个配送中心为多个库存点及顾客需求点提供配送服务的问题，节点的地理位置、时间窗要求己知；需求量服从己知的随机分布F；冷藏车按一定路线行驶，从一个配送中心出发，依次经过需要配送的节点，最后回到配送中心；不存在中途指派，即车辆一旦从某一点出发，其下一个配送点即为确定的；选择单一的冷藏车种，载重量一致且容量有限。

2.2 数学模型建立

1)固定成本

固定成本C1包括购买或租用车量的费用、司机的薪资费用、冷藏车的维修保养费用等，记节点集合为X={0,1,…,n}，配送中心为0，第k辆车的固定成本都同为h(k=1,2…,m)。

2)运输成本

3)货损成本

C3=C31+C32=

假设pi为需求节点xi的卸货时间，μ为生鲜品常数，则卸货过程产生的货损成本为

4)制冷成本

C4=C41=C42=

与货损成本同理，分别考虑运输过程制冷成本和装卸搬运过程制冷成本

假定顾客节点xi的时间窗为[ei,li]，顾客节点xi可接受的时间窗为[ei,Li]。

5)惩罚成本

6)缺货成本

式中：τ为每单位生鲜品的缺货成本，zk为k车的实际载货量，dk为k车所服务的配送节点实际总需求量。

由于冷藏车载重能力有限，可能出现无法满足需求节点数量要求的情况，造成利润损失，甚至顾客流失的风险。

考虑以上完整配送流程涉及的六个成本，可得以下配送成本模型，即

其约束条件如下

(1)

(2)

(3)

(4)

(5)

(6)

(7)

zk≤Qz,k=1,2,…,n.

(8)

(9)

式(1)为服务次数，即一辆冷藏车每次服务一个需求点；式(2)为路径与车辆关系，即车辆数大于等于路径数；式(3)为配送中心是冷藏车的起始点；式(4)为每辆车卸货后便离开；式(5)为送货频率为一次；式(6)为冷藏车离开时间约束；式(7)为确保冷藏车必须满足顾客时间窗；式(8)为车辆载重限制；式(9)为确保达到顾客需求量满足率。

3 模型算法和实例分析

以某生鲜肉类企业为例，获取该企业各配送节点的地理位置、需求量及运输时间等基础数据，为接近实际运营状态，拟定顾客需求服从独立正态分布，且存在客户软时间窗要求。利用MATLAB软件进行仿真模拟，得出随机需求下的配送总成本以及配送路径，最后以最优配送路径优化其余配送成本，验证模型的可行性。

3.1 模型算法设计

车辆路径问题(VRP)是典型的组合优化问题，求解时间随优化问题范围的扩大呈指数增长。鉴于粒子群算法寻优速度慢，模拟退火算法全局搜索能力较差，蚁群算法运算过程过于复杂，而遗传算法与专业领域关联小、运算简便而使其广泛应用于VRP问题中。单算法解决问题会暴露一定的问题，因此，本文改进遗传算法的适应度函数、选择方式和交叉变异概率，提高算法摆脱超常个体的束缚能力，并保持种群多样性的特点。

1)编码设计。二进制编码虽简单易行但会产生大量无效解，为突出需求点和位置顺序的贴合，本文选择整数直接编码。在编码过程中配送中心与需求节点分开，染色体中只有按顺序排列的需求点，且整数1,2，…，n表示n个需求节点，每种排列方式都是一个解。如染色体(9,5,3,1,6,8,7,2,4)表示配送车辆依次到达9-5-3-1-6-8-7-2-4节点，最后可生成N条配送路径，N列车辆配送N行×N列矩阵。

2)初始种群产生。种群数量较小可限定搜索空间但会导致染色体片段丢失从而降低群体的多样性，数量较大会增加种群多样性，使结果真实可靠，但部分高适应值的个体可能被淘汰，影响交叉。因此本文将种群规模规定为100。

5)交叉算子。为保证染色体多样性和全局最优，选择部分匹配交叉法。在交叉过程中将所选择交叉段插入到对方染色体前端，并依次去掉个体与交叉段基因的相同部分，从而得到交叉后的新个体。

6)变异算子。在某条染色体上选取两个基因交换，改变其个体，随机选取一个数值，若大于变异概率则发生变异，否则不发生变化，变异算子使得遗传算法具备兼顾全局和局部的均衡搜索能力。

3.2 遗传算法步骤

本文应用的遗传算法基本流程如图2所示。

图2 遗传算法基本流程

3.3 案例分析

该企业配送中心主要服务于齐齐哈尔市20家大中生鲜超市，拥有冷藏车10台。冷藏车从配送中心出发，按照既定的路线对沿途的需求节点进行配送，最后返回配送中心。基础数据如表1所示，其他参数值如表2所示。

表1 企业配送节点基础数据

表2 其他参数值

拟定顾客需求满足率为95%，且服从X～N(μ，σ2)独立正态分布，当x=μ+zα×σ，zα=z0.05=1.65，令超市的需求方差分别为1、2、3、4、5、6，将参数分别代入到函数模型中，取其中配送路径最优结果，顾客需求量满足正态分布下的配送路径，如表3所示。

以下是当σ分别为1,2,3,4,5,6时，经过75次、62次、71次、73次、76次和66次迭代后，目标函数值即总配送成本的变化趋势，如图3所示。

表3 顾客需求量满足正态分布下的配送路径

图3 随机需求下的目标函数值变化趋势

通过对比六种随机需求情况下得到的最优路径结果，发现σ=1情况下得到的配送路径最优，即在其余五种情况下选择σ=1的配送路径也会使配送总成本降低。将σ=1的路径分别代入进行优化，得到优化前后的总成本对比表，如表4所示。

表4 配送总成本对比表 元

4 结束语

以生鲜肉类企业为例，构建基于随机需求且带有时间窗的、以最小配送成本为目标函数的模型，考虑固定、运输、货损、制冷、惩罚和缺货六种成本。通过Matlab软件仿真优化后进行路径选择，之后进行路径优化，在满足客户需求的前提下降低企业配送成本，提高经济效益。优化后每条线路的总成本都有所下降，证明该模型及算法具有科学性和有效性。