基于差分进化算法的卷烟配送路径优化研究

李致远 王璐 张磊 王晋冰 张杰 林辉轮

摘 要：本文提出了解决卷烟配送问题的差分进化算法。在继承了传统的遗传算法解决路径优化问题的诸多算法优点基础上，差分进化算法具有更强的鲁棒性，并且逼近效果更加显著。由于卷烟配送问题有时间、精确度需求，因此，运用差分进化算法解决该问题具有显著优势。

关键词：卷烟配送;路径优化;差分进化算法

中图分类号：TP18 文献标识码：A

0 引言

我国烟草公司客户数量众多、分布不均匀且客户订单大小有差异。因此烟草公司在进行卷烟配送时，如果事先没有合理的卷烟配送路径安排，就会导致运输频次过高以及资源浪费。因此，如何合理优化卷烟配送路径，具有很大的现实意义。本文以贵州省烟草公司贵阳市公司为例，对其卷烟配送路径选择系统进行了优化，建立了精度、效率更高的卷烟配送路径选择模型，并采用差分进化算法进行模型求解。

1 卷烟配送路径优化问题描述及数学模型

1.1 问题描述

VRP配送问题为大规模组合优化问题，而且随着问题求解规模扩大而呈指数式增长。一般情况下，卷烟配送问题涉及几千个配送节点，配送网络路径组合更是复杂，因此，采用经典VRP算法直接求解相当困难。考虑到卷烟配送问题的规律性和区域特点，对卷烟配送问题采用基于区域划分的差分进化算法，将复杂的卷烟配送问题转化为简单的VRP问题求解。

1.2 数学模型

1.2.1 模型转化

第一步：建立配送点区域单元集合，在同一区域单元，各配送点之间路径距离相近，一般以相邻多个街道作为一个区域单元，区域单元范围以区域范围内包含配送点的数量和统计配送量的多少来确定。区域单元集合的构建可以通过对现有配送方案进行聚类，构建初始区域单元集合，然后通过人工调整得到合理的区域单元集合。其中，采用正半矢公式进行两配送点之间距离计算。

式中，和表示两点的纬度，和表示两点的经度，r表示地球半径。

用该原则将贵阳市公司客户进行区域划分，结果如图1所示。

第二步：针对每个区域，采用聚类算法将距离相近的客户“打包”为一个配送域，并计算出每个配送域的中心位置及订单总量。

以已划分的花溪区为例，将该区域内相邻的顾客划分为不同的配送域，结果如图2所示。

将每个配送域看作一个订单，采用相关路径规划启发式算法确定配送车辆及配送路线。针对每个配送域再次进行路径规划，最终求得整个区域所有客户的具体配送方案。

1.2.2 传统VRP模型

该模型中，目标函数（2）表示最小化车辆行驶路程，公式（3）表示所有配送域必须被访问，且每个配送域只能访问一次;公式（4，5，6）表示所有车辆都从起始点出发并最终回到起始点;公式（7）表示每辆车访问的配送域订单货物总量不得超过车辆荷载量（若某个配送域的订单货物超出载荷量，可在第二阶段的路径规划中安排多辆车进行配送）;公式（7）定义所有车辆实际运送卷烟量不得超过其规定载重;公式（8）定义决策变量为0-1整数变量。

2 模型求解

由于构建的模型对应的决策变量很多，若用传统的遗传算法对该实例中构建的VRP模型进行求解，则需要花费大量时间，且求出的结果精度较低。因此，本文提出了使用差分进化算法进行模型求解。通过进化个体编码与解码、初始种群产生、变异和交叉得出最优路径。

3 实验结果与分析

3.1 实验结果

本文采用贵州省烟草公司贵阳分公司的数据，并结合提出的差分进化算法，对该公司卷烟配送路径选择模型进行求解，并将求解得出的配送路径与现有配送路径进行对比。

首先采用差分进化算法对各个配送域之间的配送路径进行求解，所得结果如图3所示。接着可采用同样的方法对每个配送域中的客户进行具体的路径规划，从而最终得到所有客户的具体配送线路，所得结果如图4所示。

最后用同样算法算出每个区域的具体卷烟配送路径（如图5），并与原有的卷烟配送路径进行比较（如图6）。

3.2 结果分析

模拟仿真实验结果表明，本研究所规划的配送路线远优于现有固定配送线路，并且更加灵活，节约了大量运输成本，具有一定的应用潜力。

本文研究不足在于：目前本研究中计算客户两两之间的距离是根据经纬度计算出两点之间的直线距离，与实际的路网行驶距离会存在一定偏差。同时所采用的聚类算法是根据客户位置进行自动划分，未考虑道路实际情况，如采用人工标注将会更加准确。

參考文献：

[1]齐佳婷.城市农产品冷链物流配送车辆路径问题研究[D].浙江理工大学，2016.

[2]周辉仁，唐万生，王海龙.基于差分进化算法的多旅行商问题优化[J].系统工程理论与实践，2010，30（08）：1471-1476.

[3]王小平，曹立明.遗传算法理论、应用软件实现[M].西安交通大学出版社，2002.

[4]邓欣.基于遗传算法的多车场车辆路径间题研究[D].重庆大学，2007.

[5]胡红春.烟草物流配送车辆线路优化研究与应用[J].物流技术，2012，31（21）：214-217.

[6]付依良，李萌，程强，等.烟草物流配送网络综合优化模型与方法[J]中外企家，2013，30（30）：205-215.