基于遗传算法的冷链物流配送路径优化研究

郑义彬， 邱兴宇， 孙源泽， 刘立博

(武汉理工大学 交通学院， 湖北 武汉 430063)

不少学者对冷链配送路径问题进行了研究。陈婧怡等针对多温共配模式下生鲜农产品冷链配送问题，采用多温区冷藏车，构建了考虑运输成本、货损成本、制冷成本的路径优化模型,利用遗传算法对算例进行求解,借助ArcGIS规划最短路径。张云川等在第三方冷链物流配送路径优化研究的基础上，考虑车辆行驶速度和载重量对运输能耗的影响，采用指数函数刻画食品的变质速率，运用模拟退火算法对模型进行优化。邵举平等引入生鲜度损耗系数反映产品质量随时间的变化，考虑配送总成本和顾客满意度两个目标,建立了生鲜农产品配送路径多目标优化模型，并对模型参数进行了敏感性分析。陶志文等采用粒子群算法求解多目标冷链配送优化模型，同时对碳税和冷藏车速度进行了灵敏度分析。Xuping Wang等根据交付时装置和车辆冷藏食品的特殊要求，以运输成本、配送中心建立成本、罚款成本和损坏成本等总成本最小为目标，建立了不同运输方式下考虑冷藏食品时间窗的食品配送优化模型。Y. Zhang等考虑与不同冷冻食品的单位体积相关的装载量的限制，建立了多品种速冻食品配送中车辆路径优化模型，采用遗传算法进行求解，通过实际案例计算验证了模型的可行性和合理性，并显示了遗传算法参数值的有效组合。但现有研究考虑的环境变量不够全面。该文建立较完善的综合成本生鲜冷链路径配送优化模型，研究满足客户时间窗条件下总配送成本最小的最优配送方案。

1 模型建立

1.1 模型假设

某配送中心对多个客户进行配送，配送产品单一，且满足以下条件：1) 配送车辆有限且最大载重量固定,每辆车的最大容量满足每条线路的需求量；2) 配送车辆都从配送中心出发，配送结束后返回配送中心；3) 每个客户的需求已知，且均能被一辆车服务；4) 客户有规定的时间窗，若配送到达时间不在客户要求的配送时间窗内，则产生相应的惩罚成本；5) 每条配送线路长度均小于车辆最大行驶里程；6) 车辆匀速行驶，考虑在途目标是使总配送费用最小且客户满意度较高；7) 每个客户的服务时间固定。

1.2 成本分析

根据假设的目标，构建以总成本最小为目标的函数。总成本包含运输费用、货损费用、惩罚成本。

参数描述：配送中心编号为0，各客户位置编号为1～n。

车辆编号为1～k，车辆最大载重为Qm。变量xijk表示车辆k是否经过线路i—j：当车辆k经过线路i—j时，xijk=1，否则xijk=0。若车辆k服务客户i，则yik=1,否则yik=0。

冷链配送过程中固定成本与行驶里程无关，故只考虑与运输里程相关的变动成本，如油耗、车辆保养和维修。配送车辆的变动成本与行驶里程成正比。运输的变动成本由式(1)计算：

(1)

式中：C1为单位运距的油耗成本(元/km)；dij为客户i与j之间的距离。

为保持生鲜产品的质量而产生的制冷费用，只考虑行驶过程中产生的制冷成本，不考虑装卸货过程中产生的制冷费用。计算公式如下：

(2)

式中：tk表示车辆的行驶时间；C2为单位制冷成本(元/kJ);G为制冷过程消耗的热量，G=αRSΔT；α为常数；R为热传导系数；S为车厢受热面积(m2)；ΔT为车辆内外温差(K)。

一般客户要求的时间窗为软时间窗，允许配送到达时间在客户满意时间之外的一定阶段，在这一阶段会产生相对应的惩罚成本。设客户n要求的时间窗为[En,Ln]，车辆k到达客户i的时刻记为tik，eik表示在时间窗之前到达，lik表示在时间窗之后到达，则惩罚成本由下式计算：

F3=a(En-eik)+b(lik-Ln)

(3)

式中：a为提前到达的惩罚系数；b为延迟到达的惩罚系数。

1.3 数学模型构建

冷链物流配送总费用以F表示，目标函数如下：

minF=F1+F2+F3

(4)

约束条件：

(5)

(6)

(7)

(8)

(9)

式(5)表示车辆的载重量不超过其满载；式(6)表示一个客户只被服务一次；式(7)表示每个客户只被一辆车服务；式(8)表示车辆从配送中心出发，完成配送后返回配送中心；式(9)表示所有门店都能接受到配送服务。

2 算法设计

采用遗传算法对冷链物流配送路径优化模型进行求解(见图1)。

(1) 变异。采用两点互易进行变异：1) 产生2个随机自然数r1、r2；2) 交换第r1、r2位的基因。

(2) 交叉。采用两点交叉：1) 随机选择2个染色体作为父本；2) 产生2个随机自然数r1和r2；3) 将r1至r2之间的基因片段进行交换,得到2个子代染色体,并进行修订处理,使其不发生冲突。

(3) 解码。根据载重约束和时间窗约束对一个编码S进行划分，步骤如下：1)i=1；2) 开始第i条路线Ri=[0]，0为配送中心；3) 尝试将编码S中的第1个点加入Ri，如果加入Ri后车辆载重满足，则进入下一步，否则i=i+1，转入步骤2；4) 删除S的第1位编码，如果S空，则进入下一步，否则转入步骤3；5) 输出各子路径。

(4) 选择。采用轮盘赌选择，个体被选中的概率与其适应度函数值成正比。

图1 遗传算法设计流程

3 算例分析

某配送中心以额定载重3 t的车辆给10个客户配送货物，各客户的位置及需求量qi见表1，相关参数见表2。下面运用上述优化模型，通过合理安排车辆及配送路线使总配送成本最小。

表1 各客户的位置及需求量

按照各节点坐标计算配送中心及每个客户之间的距离，两点间的距离近似看作直线。计算结果见表3。

表2 相关参数设置

表3 客户节点之间的距离 km

运行遗传算法进行计算。运行至50代时目标函数值为435.95 元，对应的最优方案为配送中心选用3辆冷藏车进行配送，配送线路分别为0—3—6—7—4—0、0—5—9—1—0、0—8—2—10—0。图2为遗传算法迭代曲线，图3为遗传算法求解的最优路径，图4为经验法得到的初始配送方案。

图2 遗传算法优化迭代曲线

从图2可看出：采用遗传算法求解冷链物流配送路径优化模型，迭代超过50次后，曲线基于平稳，逐渐收敛于最优值435.95 元，相较于初始方案的总成本543.65 元，优化模型的总成本降低较大。

图3 遗传算法优化得到的配送路径

图4 根据经验法得到的初始配送方案

4 结语

该文对冷链配送各部分成本进行分析，以运输成本、货损成本及针对客户满意度的惩罚成本最小为目标建立考虑客户时间窗的冷链配送路径优化模型，并设计遗传算法对模型进行求解。算例计算结果表明，该总费用最小模型及算法有效，可为冷链配送路径优化决策提供理论依据。但需在以下两方面进行完善：1) 针对不确定环境下冷链物流配送方案的选择；2) 配送车辆及配送种类不固定情形下的配送方案选择。