Spark的改进蚁群算法对带时间窗车辆路径问题的求解①

李奕颖,秦 刚

1(中国科学院 计算机网络信息中心,北京 100190)

2(中国科学院大学,北京 100049)

引言

车辆路径问题是指在一个存在供求关系的系统中,在一定的约束条件下,合理安排车辆的行车路线和出行时间,把客户需求的货物从配送中心送达客户,并使目标函数取得最优化[1].随着研究的深入和实际应用场景的需求,增加了对客户偏好服务时间的约束,即个性化地限定了客户被服务时间的范围,延伸出了带时间窗的车辆路径问题(VRPTW),在实际生产应用中有广泛应用,比如O2O 外卖配送、冷链物流、生产线上的工作调度、网络路由策略等.

VRPTW 是NP-hard 的组合优化问题[2],计算复杂度高,难以有效率地使用精确算法求得最优解,目前的研究大多集中在如何设计高质量的启发式算法,求取近似解以换取计算效率的提高,如蚁群算法[3]、粒子群算法[4]、遗传算法[5]、模拟退火等群体智能算法.目前算法研究主要集中于两方面,一是提升VRPTW 的求解精度,二是提升计算速度.

现阶段VRPTW 求解存在的问题是:(1)算法过早收敛,易陷入局部最优解；(2)相较于集中式节点分布,算法对随机分布的节点处理精度差；(3)算法能处理的节点数少,一般为100 节点之内；(4)面对大规模问题出现单机处理效率瓶颈,忽视使用分布式平台进行并行计算[6].针对上述问题,本文对蚁群算法进行改进,基于Spark平台进行编程求解VRPTW,在Solomon benchmark 和Gehring & Homberger benchmark 上进行实验,为快速有效地求解大规模VRPTW 提供了一种新思路.

1 传统蚁群算法求解VRPTW

1.1 VRPTW 多目标0-1 规划模型

VRPTW 可被定义为:某物流配送网络中,记0 为配送中心,{ 1,2,···,n}为n个待配送客户点,已知各客户点的位置坐标为 (xi,yi) 、货物需求为Di,允许的开始服务时间窗为[S Ti,ETi](i=1,2,···,n),安排装载能力为Q的m辆车从0 出发,共同完成对n个客户的配送后回到起点0,优化目标是最小化配送路径长度和车辆数目.

由上述定义可知,VRPTW 是一个离散组合优化问题,我们将其抽象为多目标0-1 规划问题[6],其数学模型具体如下:

决策变量:

目标函数:

约束条件:

式(2)中lij为 点i和点j间路径长度,ρ1和 ρ2分别为目标函数中路径长度和车辆数目的优化重要度,如ρ1∈[0,1]越大则表示以路径长度最短为第一目标.约束目标中式(3) 表示车辆从 0出发并回到0 形成闭环；式(4) 表示各客户点有且只有一辆车对其服务；式(5) 表示各车辆的载重约束；式(6) 表示时间窗约束；式(7)表示决策变量为0-1 变量.

1.2 传统蚁群算法求解VRPTW

蚁群算法启发于真实蚂蚁自组织的觅食行为[3],对VRPTW 这种难解的离散优化问题有优秀的求解能力,得益于正负反馈机制的协同作用和其并行性.核心思想是:单只蚂蚁在其走过的路径上释放信息素,根据信息素浓度和启发式信息决策转移路径；蚂蚁之间通过信息素进行通信,单次迭代后信息素进行挥发且增加优秀路径上的信息素浓度,使得大概率选择目前优秀解的同时扩展搜索范围,通过多只蚂蚁间相互协作多次迭代寻优.

蚁群算法是构建解和更新信息素的相互作用[7],具体如下:

(1)构建解:通过计算状态转移概率逐步构建完整解后,对解进行评估.状态转移概率公式见式(8):

其中,pij表示由节点i选 择转移到节点js 的概率；τij表示路径(i,j)上 的信息素浓度；ηij表示路径(i,j)的启发式因子,通常是路径长度的倒数；α和 β分别表示信息素和启发式因子的重要程度.

(2)更新信息素:一次迭代后,根据解评估结果更新信息素浓度,之后继续迭代寻优.信息素更新包括追溯增加和挥发减少两种,具体见式(9):

其中,蚂蚁t时刻位于节点i,t+1时 刻位于节点j,ρ表示残留因子,△τij(t,t+1)表示信息素增量,(t,t+1)表示第k辆车信息素增量,通常为1/Ck,Ck为第k辆车路径总长度.

传统蚁群求解VRPTW 仍存在引言中提到的4 个共性问题,为了避免陷入局部最优,提升各类点分布和大数据下的求解精度和速度,下面提出基于Spark 平台的改进蚁群算法求解VRPTW.

2 基于Spark 的改进蚁群算法求解VRPTW

2.1 算法思路

本文采用基于Spark 的改进蚁群算法求解带时间窗车辆路径问题,该算法从算法层和实现层进行改进,在算法层面,通过改进状态转移规则[8]、加入轮盘赌选择机制、结合k-opt 邻域搜索[9]进行路径构建优化,改进最大最小蚁群中的信息素更新策略,在实现层面,用Spark 计算平台对改进蚁群算法并行实现,采用Spark 提供的API 对蚁群弹性分布式数据集(Resilient Distributed Dataset,RDD)进行操作,实现蚁群并行构建解的过程.

2.2 路径构建优化

蚁群算法是从最初的空解开始,逐步添加解成分直到构建完整解,只能生成数量有限的解,邻域搜索最初依赖一个好的初始解,不断通过局部调整尝试改进当前解.本文采用蚁群算法和邻域搜索相结合的方式进行路径构建,通过状态转移规则和轮盘赌选择机制构建初始解后,使用邻域搜索进行局部优化获得高质量解.

针对VRPTW 问题,由于增加了时间窗约束,因此状态转移规则除了以信息素浓度高、路径长度小为优先选择原则外,还要在满足车载限制和时间窗的前提下,以等候时间短、时间窗紧为优先选择原则,则蚂蚁由节点i选择转移到节点j的概率见式(10):

记tij为 到达节点j的时间,当tij≥S Tj时 ,等待时间为0,|tij-S Tj|+|tij-ETj|为时间窗大小,否则当tij＜S Tj时,|tij-S Tj|+|tij-ETj|为时间窗和等候时间的综合指标.

在式(10)中参数α和β的作用如下:α 和β 分别表示信息素和启发式因子的相对重要程度,如果α=0,则算法未使用信息素,而大概率地选择距离最近的节点,属于随机贪心算法；如果β=0,则算法没有任何启发式信息带来的偏向性,特别是当 α＞1时,所有蚂蚁按照最初信息素浓度最大的同一条路径移动,算法很快停滞于一个精度很差的解.因此这里选择最大最小蚁群算法(MMAS)具有良好性能的参数设置:α取值1～2,β取值2～5.

若每次迭代均按照状态转移规则pij直接选择最大概率的节点作为下一个待配送客户,则信息素向局部最优路径聚集,使算法过早收敛停滞于次优解,为了增加算法随机性,本文使用轮盘赌选择机制对路径构建进行优化,具体做法是:随机选取一个实数T∈[0,1],分别减去各候选节点被选择的概率pij,若T-pij≤0,则选择城市j作为下一个配送节点,否则重复上述过程.

因此每只蚂蚁的搜索过程是从候选节点中依据改进的状态转移规则并采用轮盘赌选择机制选择下一个待服务的节点,逐步添加解成分直至构成完整初始解,相较于传统蚁群算法的初始解构建过程该方法可以得到更合理的初始解,状态转移规则改进后使得减少配送过程中车辆的等待时间并能根据顾客的具体时间需求调配配送方案,轮盘赌选择机制增强了初始解选择的随机性,使得各节点均有概率被选中且被选择的可能性与其状态转移概率成正比,能保持发现新路径的能力,避免算法陷入局部最优.

获得完整初始解后,通常用k-opt(k=2,3)局部搜索策略对当前解邻域进行局部调整优化,核心思想是任意选取k个点(a,b,···,k) ,删除当前解中的相应k条边[(a,a+1),(b,b+1),···,(k,k+1)],替换为相关节点重组的另外k条边以期获得更优解,若当前解满足k最优,则对k′＜k一定也满足最优[10],k-opt 的时间复杂度为O(nk),k越大时虽然效果越好但耗费的计算时间近似指数级增长[11],本文采用Lin 和Kernighan 提出的Lin-Kernighan(LK 算法)局部搜索策略处理大规模数据,在时间和求解效率间取得较好的平衡,LK 算法通过迭代、回溯不断寻找边yi代替初始路径的边xi,构成序列X=[x1,x2,···,xr]和Y=[y1,y2,···,yr],其中r不固定,是此序列的最大长度,具体的算法流程如图1所示.

图1 Lin-Kernighan 邻域搜索算法程序

2.3 信息素更新优化

通过上述路径构建方法,每只蚂蚁已经可以得到VRPTW 问题的一个较优可行解,但是要想获得精度高的解,还需要群体进行分布式学习的过程,蚂蚁之间通过每轮迭代后的信息素更新来交互协作,其中信息素初始化、蒸发策略、更新策略都会影响算法寻优能力[12].

本文选择最大最小蚁群算法(MMAS)中的信息素更新策略,强调对最优路径区域的搜索,每轮迭代后只选择一只构建出最优路径的蚂蚁释放信息素,最优路径分为迭代最优TIbest和全局最优TGbest,使用全局最优更新规则会使得搜索加速集中到TGbest附近,而使用迭代最优规则能相对减弱搜索导向性[13].针对节点数较多的情况,本文采用TIbest和TGbest轮流进行更新的策略.

信息素蒸发策略使得所有路径上的信息素均随时间而衰减,避免信息素在某些边上无限积累或者快速减少[14].传统蚁群算法中的信息素蒸发因子1-ρ为一个常数,当 ρ过大时,信息素留存持久度高,信息素在当前局部最优路径上聚集,正反馈作用增强,全局搜索能力差,当 ρ过小时,信息素衰减过快,留存时间少,信息素在路径选择过程中的作用降低,最终会导致算法收敛性降低,搜索时间过长且找不到最优路径.为了平衡全局搜索和正反馈寻优能力,解决在迭代中后期出现长期找不到新的全局最优解的问题,本文采用一种自适应信息素蒸发策略,见式(11),具体为在迭代初始采用较大的信息素残留因子 ρmax,加速收敛且增强寻优能力,随后当全局最优解的搜索停滞超过总迭代次数的1/10 时,自适应减少残留因子,扩大搜索范围,同时设置残留因子的最小值ρmin.这里取最大残留值ρmax=0.9,最小残留值 ρmin=0.5,由于搜索停滞超过总迭代次数的1/10 时残留因子自适应衰减,则至多衰减10 次,因此衰减系数为

通过信息素择优和衰减策略可以确定一轮迭代后每条路径上的信息素浓度 τij,t次迭代后 τij的值为各条路径上的信息素浓度差值过大会造成所有蚂蚁向局部最优路径聚集,为了避免算法陷入停滞,这里采用MMAS 中对信息素浓度大小的限制[τmin,τmax],见式(12).

信息素初值 τ0一般将其设为略高于每次迭代中蚂蚁释放的信息素大小的期望值,若 τ0太小,信息素更新会有较强的引导性作用,搜索会快速集中到最初产生的几条路径上,导致搜索陷入局部空间,若 τ0太大,迭代初始阶段收敛速度慢,直到信息素衰减后更新才开始发挥作用.本文取 τ0为 τmax,使得在循环初始阶段,具有很强的探索性.

2.4 基于Spark 平台并行化

目前VRPTW 问题的许多实际应用面对爆炸式的数据增长和实时性求解的要求,出现单机求解的效率瓶颈,而蚁群算法是一个分布式学习的过程[15],有内在的并行性,每次迭代中多只蚂蚁独立的根据规则同时同地的构建可行解,因此本文将基于Spark 分布式平台来实现该算法.

Spark 是一个快速且通用的集群计算平台,扩充了Map-Reduce 计算模型,与Hadoop 不同的是多个任务之间数据通信不需要借助硬盘而是通过内存,减少了IO 时间,提高了程序的执行效率[16].Spark 的核心概念是RDD,RDD 的一大特性是分布式存储,每个RDD可以在不同工作节点存储并计算,另一大特性是延迟计算,一个完整的RDD 运行任务被分为Transformation和Action 两部分[17],Transformation 创建RDD,同时提供map、filter、join 等大量操作方法生成新的RDD,Action 通过执行count、reduce、collect 等方法真正执行数据的计算部分.

本文将蚂蚁封装为Ant 类,可行路线的搜索过程实现在Ant 类的search()方法中,实例化n个Ant 对象生成蚁群,蚁群间通过ant.set_parameter 方法共享参数,利用Spark 的parallelize()方法将蚁群转换为分布式的RDD,在每轮迭代中通过Spark 中的map()方法实现n只蚂蚁的并行search()过程,一轮迭代结束后通过Spark 中的collect()方法收集蚁群计算结果,得到本轮最优结果后统一更新参数,核心计算过程如图2所示,从而实现蚁群分布式并行构建可行解,提升计算效率.

图2 Spark 核心计算过程

2.5 算法描述

基于Spark 的改进蚁群算法对VRPTW 的求解流程如图3所示.

图3 基于Spark 的改进蚁群算法求解VRPTW 流程图

具体算法步骤如算法1.

算法1.基于Spark 的改进蚁群算法(1) 读入算例文件,初始化车辆数m、车辆容量load,构造地图(横坐标x、纵坐标y、需求demand、最早开始时间ready、最晚结束时间due、服务时间service_time),并计算地图上各节点间距离；(2) 采用最近邻贪心算法获得初始可行解和初始路径长度 C 0；(3) 实例化参数类,设置α,β,ρ,τ0 等参数,基于初始路径长度设置信息素初值τ0τmax=1/C0,生成全局参数；(4) 将蚂蚁封装为Ant 类,根据蚂蚁数目实例化数个Ant 对象生成蚁群ants,通过ant.set_parameter方法设置每只蚂蚁的参数,利用Spark 的parallelize(ants)方法将蚁群转换为分布式的RDD；(5) 在每轮迭代中通过Spark 中的map()方法实现n 只蚂蚁的并行search()过程,每只蚂蚁search()方法如下:① 初始化当前路径road,加入原点,设置当前时间current_time=0车辆剩余负载remaind_load=load；② 构造候选节点集,满足负载、时间窗要求；③ 从候选节点中依据状态转移规则(10)并采用轮盘赌选择下一个需要服务的节点next 并加入当前路径中；④ 若next 节点为空,将路径加入路径集中,新派遣一辆车,置current_time=0,remaind_load=load；⑤ 判断是否还有未服务的点,若存在则返回步骤(1),否则结束,

搜索.(6) 每轮迭代结束后通过Spark 中的collect()方法收集蚁群计算结果,对每只蚂蚁搜索得到的可行解进行排序,根据图1对迭代最优解进行k-opt 局部调整优化；(7) 得到迭代最优解后通过ant.set_parameter 方法统一更新参数,各路径信息素浓度更新公式参考式(9)、(11)、(12),采用TIbest 和TGbest 轮流进行更新、自适应信息素蒸发策略且限制信息素范围为[τmin,τmax]；(8) 判断迭代是否终止,迭代终止输出全局最优解,否则返回步骤(4)继续并行化求解.

3 实验设计及结果分析

为测试基于Spark 的改进蚁群算法对VRPTW 的求解效果,本文在物理机上利用Virtual Box 构建3 台虚拟机搭建Spark 集群,并分别在单台虚拟机和Spark集群上进行实验.

3.1 实验环境及算例说明

实验环境如下:

(1) 单机运行环境

操作系统:Ubuntu 16.04.

硬件环境:Virtual Box 虚拟机.

Intel Core i7.

2GB 内存.

(2) Spark 集群运行环境

操作系统:Ubuntu 16.04.

硬件环境:Virtual Box 虚拟机.

Intel Core i7.

2GB 内存.

部署方式:Standalone 模式.

集群规模:1 台Master,2 台Slave.

实验采用Solomon benchmark 和Gehring &Homberger benchmark 两个国际通用基准算例库中的数据,数据集按照影响VRPTW 求解的地理数据分布、客户节点数、时间窗松紧程度、车辆载重上限4 个因素进行分类,Solomon 数据集规模包括25、50、100 节点数,标号为X1X2X3X4,X1取值R、C、RC,分别表示客户节点随机、聚集、混合分布,X2表示车辆载重,取值0 或1,X3X4取值一个两位十进制数,表示时间窗松紧程度,Gehring & Homberge 数据集是大规模数据集,包括200、400、600、800、1000 节点数.数据包含车辆数上限、载重上限、客户位置坐标、客户需求量、时间窗、服务时间[18].

3.2 实验设计及结果分析

3.2.1 信息素矩阵可视化表达

为直观表达蚁群算法求解VRPTW 的行为,选取Solomon-r101 的前25 节点进行求解并给出信息素矩阵的可视化表达,信息素含量被转化成灰度值,颜色越暗的方格所对应的信息素值越高,在第0、10、100 次迭代之后的实验效果如图4.

图4 信息素矩阵可视化表达

由图4可以看出,主对角线的单元格始终为白色,表示这些单元格的信息素被初始化为0 并且永不更新,其余单元格初始为黑色表示 τ0=τmax,随着迭代过程反复执行,单元格间的信息素含量差异越来越大,最后只有少数边含有较高信息素而被选择为全局最优解.

3.2.2 收敛性比较实验

为验证本算法的改进效果,分别将不同信息素更新策略、不同邻域搜索方法作为控制变量进行实验.选取Solomon-c101 和Gehring & Homberger-c121 作为实验数据,分别采用信息素全局更新和交替更新的求解收敛过程如图5,选取Gehring & Homberger-rc121作为实验数据,分别采用2-opt、3-opt、k-opt 这3 种邻域搜索的求解收敛过程如图6.

由图5可以看出,对100 节点数据,信息素更新方式对求解过程无明显影响,而对200 节点数据,采用全局信息素更新方式使得求解陷入局部最优解而过早收敛,采用信息素交替更新方式能在执行结束后得到更高质量的解.由图6可以看出,使用k-opt 进行局部搜索优化比2-opt 和3-opt 得到的解的精度高.综上,改进蚁群算法求解较大规模VRPTW 时在迭代初期收敛速度较快,在迭代中后期能保持全局搜索能力使求解持续收敛,最终在期望的时间内收敛于一个精度较好的近似解.

图5 不同信息素更新策略收敛过程

图6 不同邻域搜索收敛过程

3.2.3 求解精度比较实验

为验证本算法的求解精度,选取Solomon 节点数为100 的各类数据和Gehring & Homberger benchmark节点数为200 及400 的大规模各类数据进行测试,参数设置为:α =1,β =2 ,ρ =0.9,迭代400 轮计算与当前最优解的误差率见表1.

由表1可以看出,对100 以内小规模问题求解的精度基本可达最优解；对混合分布的RC 类问题求解精度有明显提升；对随机分布的R 类问题误差率仍较高,尤其是对车辆载重小且最大可服务时间短的R1 类问题精度更差,原因是该类问题节点的随机分布增大了路径构造的难度,各子路线可能包含的节点数差异大；对200、400 节点的大规模问题在计算速度提升的前提下精确度在可接受的误差范围内.

表1 100、200、400 数据量求解精确度实验结果

3.2.4 求解速度比较实验

为比较单机求解和基于Spark 平台并行求解的求解效率,选取客户数为25、50、100、200 以及400 的Solomon-r101、Gehring & Homberge-R1_2_1、Gehring& Homberge-R1_4_1 作为实验数据,基于相同参数和迭 代轮数进行实验,实验结果如图7.

图7 求解速度比较实验结果

从图7可以看出,当问题规模较小时,由于Spark 内部的通信消耗,基于Spark 的并行蚁群算法的求解效率较单机蚁群算法没有显著的提升,而当问题规模逐步增大时,基于Spark 的并行蚁群算法的求解时间要显著少于单机算法的求解时间,并行算法的加速比逐步增加,当客户数为400 时,并行算法的加速比为1.95.

4 总结与展望

本文设计了一种基于Spark 的改进蚁群算法求解带时间窗的车辆路径问题,根据改进的状态转移规则和轮盘赌选择机制构建初始解,结合k-opt 邻域搜索进行局部搜索优化,采用全局最优解和局部最优解交替更新策略、自适应信息素蒸发策略改进最大最小蚁群算法中的信息素更新策略,借助Spark 计算平台,将蚁群封装为弹性分布式数据集,实现蚂蚁的并行搜索.

实验结果表明本算法对100 以内小规模问题求解的精度基本可达最优解,对混合分布的RC 类问题求解精度有提升,对200、400 节点的大规模问题求解效率有明显提升.因此把蚁群算法这样的启发式算法和邻域搜索相结合是解决优化问题的有效途径,另外利用Spark 分布式平台处理蚁群算法中耗时的迭代过程可以有效降低计算时间.

本文试图对C、R、RC 类VRPTW 问题同时取得较好的优化效果,但对R 类分布的节点求解精度还不理想,今后可结合其它群体智能算法或者根据随机分布类问题的特点进行合适的参数调整对R 类VRPTW问题进行进一步优化求解.另外本文尚未对600、800、1000 等更大规模节点进行实验,今后可以通过改进算法、充分利用分布式平台、提升硬件环境来解决更复杂的大规模求解问题.