蚁群算法求解带有时间约束旅行商问题

李安颖,陈 群,宋 荷

(西北工业大学计算机学院,陕西 西安 710072)

0 引言

随着线上线下(online to offline，O2O)商业模式发展迅速，对物流配送的要求越来越高。物流配送已成为O2O服务中的一个重要环节[1]，其服务质量对提高O2O企业的竞争力具有重要意义。当前，物流企业一般提供的是由客户下单时预先设定的货物送达时间，进而在该设定的时间段内实现配送服务。为了实现快速、有效的配送，可以将问题转化为含时间约束的旅行商问题(traveling salesman problem,TSP)[2-3]。TSP其实是一个多项式复杂程度的非确定性问题(non-deterministic polynomial,NP)，常用粒子群算法、遗传算法、蚁群算法等智能算法来解决。但是使用这些传统的智能算法，存在运行时间较长、求解效率低的问题。本文采用以MapReduce为基础的蚁群算法，从而更为高效地解决物流配送顺序的带时间约束TSP。

Hadoop框架是由Apache开源组织开发的、具有高可靠性、高可扩展性的存储与分布式并行计算平台[4]。MapReduce是Hadoop框架的核心模型之一，已经广泛应用于大数据处理、分布式计算等[5]。本文使用MapReduce实现蚁群算法以及高效求解带时间约束的TSP，从而快速地给出对含时间约束的物流配送问题的有效解决方案[6-8]。目前，对于基于MapReduce的蚁群算法进行求解传统的TSP已经有比较好的阐述，但是对于含时间约束的TSP，尚未有相关文献对其进行详细分析。

1 问题描述及构建模型

传统TSP是假设一个货郎需要走访N个城市，每个城市必须且仅经过一次，最终回到起点城市，形成闭环。因此，必须找到一条最短的旅行路径。

假设物流配送的客户集为U={u1,u2,…,ui,…,un}，1≤i≤n。当前时间为T0,配送员配送过程中的速度为v,到达客户ui的时间为Ti；客户ui预定的配送时间在Ti1到之间，记为[Ti1-Ti2]，对于未约定配送时间的客户，其配送时间设置为(-∞,+∞)。为了提高客户满意度，如果Ti∉[Ti1-Ti2]，即未能在客户约定的时间内到达城市i，则设置惩罚值wi。不考虑配送员在每个节点上提留的时间，惩罚值可定义如下：

(1)

式中：εv为惩罚因子。该值为经验值。在计算过程中，通过将该惩罚值wi增加到路径开销中，可以将客户ui的时间约束转化为路径约束Li。

假设物流配送人员访问的节点顺序为X={x1,x2，…,.xi,…,xn}，0≤xi≤N。xi表示物流配送人员到达的第i个节点。则该路径对应总路径长度为：

(2)

式中：d(xi,xi+1)为总路径中第i个、第(i+1)个节点之间的距离。

整个路径上的惩罚值为：

(3)

式中：w(xi)为总路径上第i个节点所对应的客户节点的惩罚值wi。

可构建目标函数为路径值与惩罚值的总和：

C=L+W

(4)

本文求解的最终目标是寻找目标函数的最小值，实现路径最优化与惩罚值最小。

2 改进的蚁群算法

蚁群算法 (ant system或ant colony system)由意大利学者Dorigo、Maniezzo等人于20世纪90年代提出。使用该算法解决优化配送路径问题的基本思路为：用蚂蚁的行走路径表示待优化路径问题的可能解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素(模拟蚂蚁会在其经过的路径上释放的物质，能使得蚂蚁根据感知到的信息素浓度行走)量较多。随着时间的演化，较短路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也将约来越多。最终，每个蚂蚁会在这种正反馈的作用下集中到最佳的路径上。此时对应的路径便是待优化问题的最优解。

本文在传统的蚁群算法基础上进行改进。因此，求解含时间约束的TSP算法详述如下。

2.1 参数说明

设m为本算法中的蚂蚁数目，di,j(i,j=1,2,…,n)表示从ui用户到用户uj之间的距离，τi,j(t)表示时刻t在用户i、j之间的路径上保留的信息素。将每条路径上初始时刻的信息素设为τi,j(0)=c。在运动过程中，蚂蚁k(k=1,2,…，m)根据各个路径上的信息素确定下一步待转移的目标用户；S表示在t时刻，蚂蚁k转移到用户uj的概率。

(5)

2.2 蚁群算法信息素改良机制

将信息素强度的值进行限定在范围[τmin,τmax]内，不在这个范围内的最小值与最大值分别设为τmin或τmax。限制最大值的目的是防止算法陷入局部最优解；限制最小值的目的是防止搜索向错误的方向收敛。

当τij>τmax时，按式(6)计算信息素强度：

τij(t+1)=(1-α1)1+s(m)τij(t)+Δτij

(6)

当τij﹤τmin时，按式(7)计算信息素强度：

τij(t+1)=(1-α1)1-s(m)τij(t)+Δτij

(7)

当τmin≤τij≤τmax时，按式(8)计算信息素强度：

τij(t+1)=(1-α1)τij(t)+Δτij

(8)

式中：α1为挥发因子，表示信息素的保留率；Δτij为示信息素的增加量；s(m)为与迭代过程中被改进的解的个数m成正比的函数。

2.3 局部信息素更新机制

在采用局部信息素更新规则来修正信息素值时，蚂蚁k对其走过的每条路径，参照式(6)～式(8)来更新边上保留的局部信息素值。

当0<α1<1时，信息素挥发参数：

Δτij=(ngLnn)-1

(9)

式中：Lnn为由最近邻域启发算法计算出的路径长度。

2.4 全局信息素更新机制

对于应用全局信息素更新规则来修正信息素值时，考虑在一次迭代的过程中，m个蚂蚁生成m个解后，计算该求解过程中的最短路径，作为本次迭代的最优解。将这条路径上所有保留的信息素按照式(10)更新：

τ(t+1)=(1-α)τ(t)+αΔτ(t)

(10)

当0<α<1时，信息素挥发系数为：

(11)

式中：Lgb为当前得到的全局最优解的路线长度。

随着信息素的挥发，全局最短路线上各边上的信息素值得到增加。

3 基于MapReduce的蚁群算法的实现

使用MapReduce方法求解本问题的思路如下：在Map函数中初始化，设置蚁群，利用多个Map函数并行计算蚂蚁的求解过程，获得多个可行解，并在Map函数中设置局部信息素矩阵，对局部信息素进行更新。

首先，读入待处理文件中记录的数据，并设置m个Map，每个Map中设置n个蚂蚁，并以键值对的形式输出，key代表蚁群编号，value的形式为{X={x1,x2,…,xi,…xn}}，该Map计算得到的最优解的路径长度}。在Reduce函数中设置全局信息素矩阵为：

Pn×n=|pij|

(12)

式中：pij为用户ui到用户uj之间的全局信息素，1≤i,j≤n。

利用Reduce函数，求得全局最优解和调整全局信息素。然后，利用云计算的管道能力，将Reduce函数的计算结果，即信息素的改变、全局最优解、全局最优解路径，传递到Map函数，作为下一个Map函数的输入，执行迭代计算。使用的蚁群算法最终改进如下。

①初始化。

{1-1：构造Map函数、Reduce函数，设置Map函数的个数NUM_MAP、Reduce函数的个数NUM_REDUCE，初始化局部信息素矩阵、全局信息素矩阵；

1-2：设置每个Map函数中的蚂蚁数，蚂蚁算法运行代数为no_iteration}

②对每个Map函数中的每只蚂蚁随机产生一个初始解：

{X={x1,…xi,…xn}}

③更新信息素。

{3-1：每个Map节点分别根据式(1)～式(4)计算本节点下各个蚂蚁的解;

3-2：根据式(9)更新每个蚂蚁的局部信息素以及局部最优解。}

④调整信息素。

{4-1：将Map获得的各个蚂蚁分配到各个Reduce节点中;

4-2：通过Reduce函数计算全局最优解;

4-3：根据式(10)调整全局解向量的信息素。}

⑤本次迭代结束。

{if 迭代次数 => no_ iteration

算法结束；

Else 将全局最优解信息更新到所有的Map节点中}

4 试验

为了对以上理论进行验证，试验环境搭建如下。采用4台普通的服务器进行搭建的Hadoop集群系统试验，每台服务器内存2 GB，存储空间250 GB。Hadoop的版本是hadoop.0.20.2。操作系统的版本是Red Hat Linux 9.0。测试方法是在Hadoop的框架下进行计算。以TSP标准测试集中的数据gr431为例，设置物流配送人员的配送时间段为[9：00-21：00]，在该时间段内以两个小时为一个预约时间段，随机设置预约配送时间，求解了运算结果。另外，还比较了TSP节点数分别为48、120、229、431时，基于MapReduce的蚁群算法(记为并行)与串行的蚁群算法(即未使用分布式算法的蚁群算法)的运行时间。蚁群算法与串行蚁群算法的运行时间对比如表1所示。

表1 并行蚁群算法与串行蚁群算法的运行时间对比

经过多次反复试验，程序中用到的参数设置为ρ=0.1、α=0.7、β=0.1、θ=0.4比较合理，能够得到较好的试验结果。设置Map数m=4，每个Map上的蚂蚁数n=200，车速为60 km/h。又以TSP标准测试集中的数据gr431为例，比较了蚂蚁数不同时对运算时间的影响。

运行时间1 800 s，运行的解路径长度为221 827.78。

如图1所示，当 TSP 节点数为 48 和 120 时，并行算法的运行时间大于串行算法；当TSP节点数为229和431时，并行算法运行的时间小于串行算法所需的时间。随着TSP节点数增多，并行算法运行时间比串行算法更短时间的趋势。不同蚂蚁数的运算时间对比如图1所示。

图1 不同蚂蚁数的运算时间对比图

从图1中的结果可以看出，随着蚂蚁数量的增加，运行时间有缩短的趋势。

5 结束语

本文采用基于MapReduce的蚁群算法求解包含时间约束的TSP，用蚂蚁的行走路径表示待优化路径问题的可能解，整个蚂蚁群体的所有路径构成待优化问题的解空间；利用MapReduce的并行机制，对蚁群算法进行并行处理，使其运行在分布式环境中，增强了求解大规模问题的能力，提高了运行速度。试验结果表明，该算法有效。后续的工作将探索结合多种智能算法解决带有复杂约束的NP问题。