超拼科技关于车辆路径系统、app的蚁群算法调优

超拼科技关于车辆路径系统、app的蚁群算法调优

超拼科技在App系统设计研发中经常遇到客户有路径规划相关业务需求，然而现有地图API接口的方案普遍不能深度满足用户的定制需求，于是如何通过算法解决车辆路径问题（vehicleroutingproblem）变得尤为重要。

算法如何有序安排配送，寻找最优车辆调度方案，这就是一个需要深度思考的问题，一段时间内，超拼科技技术团队采用精确式算法进行功设计，在一定情况下，精确式算法确实独居优势，但是当数据规模数量无限变大时，我们遇到了由于计算量过大导致算力不足的情况，很难有效解决问题，只适用于并发和用户量较小的系统。于是我们试图通过元启发式算法(Meta-heuristic)来解决大规模的问题，显而易见的是在超拼科技的部分项目中我们使用元启发式算法，算法更适合解决大规模搜索的问题，通过蚁群算法的深度调优最终很好的解决了这个问题。

算法模型构建

VRP可以描述为配送中心按照不同配送点的要求，从配送中心出发，对所有配送点进行配送。每条配送路径的总载货量不可以超过车的最大承载能力，以确保每个配送点都能得到服务，一个配送点只能由一辆配送车提供服务。服务完配送路径最后一个配送点后，配送车要返回配送中心。为了找到满足约束的最小配送成本配送方案，做以下假设：(1)无缺货假设；(2)配送货物包装规则，无异型包装，配送货物按质量计算；(3)配送点需求量不会超过配送车的最大载重量。符号定义如表1所示。

符号定义

模型构建

式（１）表示目标函数，目标为总配送距离最短；式（２）表示配送车辆不可以超载；式（３）表示配送车辆出发

后需要返回出发点；式（４）和式（５）表示每个配送点只能由一辆配送车配送。

对蚁群算法的构建改进

蚁群算法步骤如下。

１）初始化参数。

２）迭代次数ＮＣ＝ＮＣ＋１。

３）ｍ只蚂蚁从起点出发。

４）选择下一个配送点。根据选择概率公式（６）和轮盘赌法选择下一个要到达的点：

式中：τ(t)为时刻，j两点间的信息素浓度，信息素浓度越高，蚂蚁选择该路径的概率越大；η为启发函数，＝1／d，为和两点距离的倒数，两点距离越短，蚂蚁选择该路径的概率越大；allowed表示未访问点的集合。

5)判断是否历遍所有点，没有历遍返回步骤4)，反之转到步骤6)。

6)更新信息素。每只蚂蚁历遍所有配送点后需要更新信息素，按τij(＋1)＝()＊(1－ρ)＋Δ进m行更新，其中Δ为新增信息素含量，Δ＝∑Δijk。这里采用的是蚁周模型，即历遍后蚂蚁才会释放信息素，即Δijk＝人Lk其中，为蚂蚁k所经路径之和。

7)判断当前迭代是否达到最大迭代次数，若没达到返回步骤2)，反之转到步骤8)。8)输出结果。

改进蚁群算法

对于基础蚁群算法而言，一开始蚂蚁的搜索具有盲目性，实际操作中容易出现陷入局部最优解、收敛速度

慢等情况。为此引入节约矩阵引导蚂蚁搜索，采用改进的挥发因子调整收敛速度，运用２－ｏｐｔ法改善算法效果。

２．２．１构建路径

如图１所示，１点想要给ｉ点和ｊ点运送货物，原路线是从１点出发分别向ｉ点和ｊ点运送并原路返回，

具体路线由实线线段标出。总距离

，需要２台车辆完成配送任务。

节约矩阵原理图

采用节约矩阵思想优化后，把原路线合并成一个路线，即从１点出发向ｉ点运送，服务完ｉ点后再向ｊ点运送，服务完ｊ点后返回１点，具体路线由虚线线段标出。总距离Ｄ１＝ｄ１ｉ＋ｄｉｊ＋ｄｊ１，且只需要１台车辆就可以完成配送任务。这样一来节约的里程数Ａ＝Ｄ０－Ｄ１＝ｄｉ１＋ｄｊ１－ｄｉｊ。Ａ越大，表明越应该把ｉ点和ｊ点合并到一条配送路径上来。在基本蚁群算法运算后期，蚂蚁搜索主要依赖信息素，对能见度的依赖变少，可能会出现陷入局部最优解的情况。为了解决该问题，需要引入节约矩阵Ｕ，增强先验信息对蚂蚁的吸引力：Ｕ（ｉ，ｊ）＝Ｄ（ｉ，１）＋Ｄ（ｊ，１）－Ｄ（ｉ，ｊ）。引入节约矩阵后，概率公式更新如式（７）所示，其中θ是可以调节节约矩阵的权重系数。

设置挥发因子

挥发因子ρ反映信息素的消失水平，（１－ρ）反映信息素的保留水平，ρ取值范围为０～１。挥发因子设置过大，信息素挥发较快，每条路径上的信息素含量差别较大，加大了蚂蚁搜索范围，虽会加快算法的收敛速度，但也增加了陷入局部最优解的可能性；挥发因子设置过小，信息素挥发较慢，每条路径上的信息素含量差别较小，有利于找到全局最优解，但会使算法的收敛速度减缓。

为了控制算法的收敛速度且避免算法陷入局部最优解，应合理设置挥发因子值，在不同迭代时段设置不同的值。迭代初期，为了能扩大蚂蚁的搜索范围，让蚂蚁历遍全局找到全局最优解，挥发因子应该定一个比较大的值；迭代一定程度后，为了不让算法陷入局部最优解，应适当调小挥发因子值，提高算法局部搜索能力，让蚂蚁在当前情况下找到最优解，避免算法急剧收敛而陷入局部最优解；迭代后期，需要提高算法收敛速度，把挥发因子降到最低，让当前较优路径中的信息素含量较大，加快收敛速度找到最优解。挥发因子的设置改进如式（８）所示。

运用２－ｏｐｔ法

2－opt就是两元素优化，亦可称作2－exchange，核心在于随机选择路径上一个区间段进行优化，这个优化只是对当前一个状态的优化，并不是对全局的优化，所以是局部搜索算法。蚁群算法在迭代后期，有些路径上会因为距离短留下大量信息素，引导蚂蚁继续选择该路径，容易陷入局部最优解。

2－opt法基本思想如下。首先，通过迭代当前产生一条最短路径，如图2a)中的a－b－c－－e－f－g－h－，图中箭头只表示方向，与距离无关。然后，随

机选择2个不同的配送点，反转这2个配送点在内的中间路线，比如随机选择配送点和配送点，此时原路径被分割成3段：(－)－(－－－)－(－－)，反转后，新路径为(－)－(－－－)－(－－)，新路径如图2b)所示。最后，如果新路径的总距离小于原路径的总距离，那么最短路径变为新路径，此时NC要归零，继续迭代；如果新路径的总距离大于原路径总距离，那么原路径还是当前的最短路径，此时＝＋1；如果≥max，算法结束，当前的路径就是最短路径(局部最优的最短路径)。运用2－opt法调整配送点的顺序增强局部搜索能力，再对局部进行优化，有助于找到全局最优解。

物流中心

表2数据集特点

Tab．2Datasetcharacteristics

表3α和β不同组合下的算法结果Tab．3Resultsunderdifferentcombinationsofand

服务的客户距离都较近，车辆路径鲜少出现交叉与迂回等现象，因此改进蚁群算法给车辆路径规划提供了更大的组合优化空间，能有效避免出现交叉配送与迂回运输不合理等现象，缩短车辆行驶距离，减少车辆使用数量，降低物流成本。

与基础蚁群算法的比较

运用基础蚁群算法和改进蚁群算法分别进行计算，基础蚁群算法中＝0．2[21]，改进蚁群算法中θ＝2。其他参数设置如下：＝节点数×1．5[22]，Q＝1000，max＝200。使用MATLABR2018a软件进行仿真，小规模问题、中规模问题和大规模问题的迭代曲线如图5—图7所示，不同案例最优路径总长度和比较如表4所示。