基于改进遗传算法的连锁便利店配送路径优化研究

魏子秋，熊英翔 WEI Ziqiu,XIONG Yingxiang

（河北科技大学 经济管理学院，河北 石家庄 050000）

0 引 言

随着社会经济的不断发展和社会分工的不断细化，使得物流业快速发展，但是物流成本没有得到显著降低，物流业中的高消耗、高成本一直是有待解决的问题。其中运输费用在物流费用中的占比接近半成，是物流活动中的最主要费用。所以想要推动物流业的持续发展，务必要降低物流活动中的成本费用，降低物流成本费用应首先从降低运输费用开始。

配送路径的选择直接决定着运输成本和效率，对配送路径及其算法进行优化研究具有重要的意义和价值。李作山等学者结合遗传算法，针对企业车辆调度优化进行研究，基于减少汽车运行耗费为目的提出了相关策略。刘建仁等为了解决城市物流配送路径规划过程中存在的一些难题，以获得更优的城市物流配送路径规划结果，在已有的算法基础上，引入交通拥堵条件，提出考虑交通拥堵的城市物流配送路径规划算法，建立更优的城市物流配送路径规划数学模型；张瑾等为了解决带有容量和软时间窗约束的双目标生鲜农产品冷链物流车辆路径问题，建立了以客户满意度最大化、总成本最小化为目标的双目标优化模型，在求解过程中，以蚁群算法为基础，运用ε约束法来处理双目标模型，并且加入交叉与变异算子，设计了遗传蚁群算法。季琳琳等提出以成本与满意度为双目标的冷链水果运输模型。为了准确描述顾客满意度水平，提高冷链水果运输服务的响应能力，提出改进的满意度模型；引入灰度白化权函数构造顾客满意度不同等级阶段，设置不同等级分数将影响满意度感知的因素划分成不同等级，利用调研数据支撑顾客真实满意度感知；提出改进的遗传算法（IGA）求解该冷链水果运输模型。张肖琳等充分考虑耗油成本、绿色环保成本，将绿色物流与配送的路径优化结合起来，基于绿色环保视角，通过在物流配送中引入油耗、污染物排放等因素，构建出配送路径优化模型。李丹莲等为解决单车场多车型带密集半软时间窗问题，讨论解决方案预防其陷入局部最优解，提出多染色体改进遗传算法在减少车辆运输成本、惩罚成本的目标下进行最优路径求解；彭勇等为解决带有时刻表和时间窗的双重约束多式联运的路径优化问题，将运输总成本分解为运输成本和中转成本，建立以总成本最小化为目标的数学模型，使用蚁群算法对模型进行求解，并在多式联运网络节点编码方式和状态转移概率公式两个方面进行了针对性改进；沈丽等综合考虑货损成本、固定成本、燃油成本以及碳排放成本和时间惩罚成本，以其和最小为目标，细化货损和碳排放来源，构建生鲜产品配送路径优化模型；潘世凌等使用节约里程法对成都苏宁小店的配送路径进行优化，求解出最优的配送路线，降低物流成本。

目前各位学者对遗传算法解决物流配送路径方面的研究已取得一定的成果，但是针对有较强的送货时间窗限制的零售小店的配送路径优化相对较少，本文针对此问题进行研究。

1 构建数学模型

1.1 模型描述

本文所研究的连锁超市配送路径问题可描述为：有一个配送中心（=0）为个小店进行配送（=1,2,…,），需要辆配送车才能完成配送任务。为方便建立数学模型，做出以下假设：（1）配送活动以配送中心为起点，且最终要返回配送中心；（2）配送车辆额定载重量需大于或等于车辆配送路线上的客户需求总量；（3）一位需求客户只能被一辆配送车服务一次；（4）配送所用的运输车装载吨位相同。

再假设表示总的配送费用；C表示运输车每次运输的单位固定运输费用；C表示单位变动运输费用；d表示小店到小店的距离；x表示小店到小店使用配送车进行配送；P、P表示配送车早到等待成本和晚到惩罚成本；P表示配送车辆超重惩罚系数；ET、LT表示小店的最早和最晚到达时间；S表示配送车辆到达小店的时间；T表示配送车到达小店处的服务时间；T表示配送车从第个小店到第个小店的行驶时间；D表示第个小店的需求量；表示每辆配送车最多装载货物的数量。配送的限制条件如下：

配送车辆不能超载，要小于或等于车辆的最大装载量：

配送车的行驶方向和配送开始起点和到达服务地点需要具有唯一性：

小店的需求，只能由配送车辆为其配送：

配送车到达小店的时间窗限制：

配送车到达小店的时间与到达前一个小店处的时间关系：

决策变量取整数变量0或1：

在考虑以上假设和限制条件后下，以总的配送费用最小为目标建立带时间窗的物流配送路径化模型：

1.2 染色体编码

由于配送中心要通过配送车辆来向多个小店配送，因此选择使用自然数来进行编码，以求提高求解过程中的计算效率。将配送中心编码为0，配送的个小店随机编码为1,2,…,，配送车完成配送任务后要回到配送中心，完成一条配送路线即可编码的染色体长度是＋＋1。

1.3 初始群体设定

为了避免可能过早的陷入局部最优解而出现早熟现象，初始群体中设计的染色体数量要足够的多，而且初始群体应该要具有广泛代表性的特点。因此，配送路径问题的初始种群考虑以配送车的额定装载数量及需求商的需求量表示一组编码长度的限制条件，依次表示每辆配送车配送的需求商编码，不同配送车配送的需求商编码之间用0相连，形成初始染色体。

1.4 适应度函数构造

在遗传算法求解过程中，为了选择优秀的染色体，需构造适应度函数，用来作为评判个体好坏的标准。通过适应度函数值观察，适应度函数值越大，说明染色体适应度越好，也就代表该染色体越优秀，所以该配送方案在实际需要解决的问题中被选择的概率较大。由于建立的目标函数是求配送费用最小，在此采用界限构造法来构造适应度函数，适应度函数表示如下，其中是当前所有代目标函数（）的最大值。

1.5 遗传算子设计

遗传算子分别包括选择、变异和交叉几种形式，设计操作算子可以让遗传算法具有强大的搜索功能。在遗传算法中，通过计算过适应度，得出适应度函数值，并选择其中适应度值第一的和第二的个体进入下一代，之后通过轮盘赌的方式将适应度值排在后面的染色体复制个体进入下一代，进行选择。这样可以通过选择算子来筛选出更好的染色体进入到下一代中，避免过早收敛。在选择操作中将染色体根据交叉概率进行交叉配对，而适应度值排在第一和第二的染色体则不需要。其中的交叉操作考虑采用双切点交叉方法进行。另外，变异操作可以通过变异令染色体中的基因发生改变，增加种群的多样性，是遗传算法的辅助性操作，可以采用在染色体上随机选取两个非零的基因进行交换位置来实现变异。

2 算法实例

在石家庄范围内的苏宁小店如今已有100多家门店，在此只考虑店面规模较大，每日营业额较高的八家小店。藁城物流配送中心负责向石家庄的八家苏宁小店配送商品。为方便区分记录，表示藁城物流配送中心，P表示配送中心周围需要配送的门店。需求量见表1，车辆配载量为2t。

表1 石家庄8家苏宁小店每日需求量及服务信息

2.1 配送线路管理现状

苏宁云商集团股份有限公司采用扫描分析法为门店商品制定配送路线。

根据表1，假设直线从开始顺时针旋转，计算如下所示：第一条线路包含的门店有、、、，车辆配送量=0.34+0.67+0.52+0.32=1.85t；总运输距离=23.5+3.6+3.3+5.4+27.8=63.6km。第二条线路包含的门店有、、，车辆配送量=0.41+0.56+0.71=1.67t；总运输距离=31.5+6+5.1+21.6=64.2km。第三条路线包含的门店表示，车辆配送量=0.46t；总运输距离=22.6+22.6=45.2km。

2.2 配送优化分析

通过对苏宁小店物流配送现状的案例分析，得出相关参数，如表2所示。

表2 基础参数

遗传算法的相关参数表示初始种群规模为50，时间窗惩罚系数P为200，P为200，超重惩罚系数为15 000，进化代数为600。用MATLAB编程，通过20次迭代之后，得到最优配送路径，如图1所示。

图1 优化后配送路线图

2.3 优化前后对比

本文主要以苏宁藁城物流配送中心表示研究对象，实际情况调查发现：满配载为2t的微型货车使用时的维修资金为15元/d，闲置时的维修资金为10元/d，其中油耗为1.3L/km，油价为5.78元/L，每个送货司机的固定工资表示150元/d，配送费30元/趟，根据本文假设藁城基地负责此次配送的微型货车有3辆，送货司机3名。

涉及成本计算公式：运输成本=总运输距离×油耗×油价；

人工成本=司机固定成本×人数+配送费×路线；

运输车维修成本=货车使用的维修资金×使用的车辆数+货车闲置时的维修资金×未使用的车辆数（单位：元）。

对苏宁小店物流配送路径基于遗传算法进行优化，将优化后的结果与之前的路径进行对比分析，结果如表3所示：

表3 优化前后对比

通过装载对比分析，发现原先苏宁小店使用的扫描法消耗作业偏多，不能充分利用车辆装载能力，浪费较多的人力与物力，最终影响公司的市场竞争优势；通过运输距离的对比分析，发现优化前的总运输距离比优化后的总运输距离远了50.1km，优化前配送路线的运距过长，也会对城市的交通增加压力；通过优化前后的成本分析，发现优化后比优化前使用的配送费少414.35元作业成本，且因优化后只有两条配送路线，需要使用的车辆2辆，司机2人，剩下一辆微型货车和司机一名，可以作为其他作业备选资源，也可以进行人员裁员与货车出租，减少不必要资源占用。

优化后发现在车辆配载、运输距离和配送成本等方面都有显著成效，虽然单单考虑遗传算法在整个物流配送线路的问题上是不全面的，计算也不是最优的路线，但却是一个比较合理的路线，能够在极快的时间内求出一个比较优秀的方案，显然使用遗传算法在物流配送路线规划上比较经济，所以建议苏宁云商集团股份有限公司在以后的苏宁小店物流配送线路规划上使用遗传算法代替目前使用的扫描分析法。

3 总 结

物流配送路径优化问题一直是连锁超市较为关注的问题，配送路径是否合理对连锁超市物流费用及物流服务质量均有很大的影响。本文针对连锁超市的特点，建立了带时间窗的配送路径优化模型，运用改进遗传算法进行了配送路径优化求解。实例应用结果表明，本文所建立的模型和设计的求解方法能较好的优化配送路径，为物流决策者提供合理的优化方案。