﻿ 基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解
 计算机系统应用  2019, Vol. 28 Issue (7): 9-16 PDF

1. 中国科学院 计算机网络信息中心, 北京 100190;
2. 中国科学院大学, 北京 100049

Solving Vehicle Routing Problem with Time Window Based on Spark’s Improved Ant Colony Algorithm
LI Yi-Ying1,2, QIN Gang1
1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China
Abstract: In order to cope with the real-time solution requirements of the Vehicle Routing Problem with Time Window (VRPTW) in the era of big data, this study proposed an improved parallel ant colony algorithm based on Spark platform. At the algorithm level, the improved state transition rule and roulette selection mechanism are used to construct the initial solution, and the k-opt local search is used to optimize the path construction. In addition, the improved pheromone update strategy of max-min ant colony algorithm is applied. At the implement level, the ant colony is encapsulated into RDD, which is operated by Spark API to realize distributed construction solution. The experimental results of the Solomon benchmark and Gehring & Homberger benchmark show that the proposed algorithm can improve the accuracy and speed of large-scale problems.
Key words: vehicle routing problem with time window     Spark     ant colony algorithm     local search

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

1 传统蚁群算法求解VRPTW 1.1 VRPTW多目标0-1规划模型

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

 ${x_{ijk}} = \left\{ \begin{array}{l} 1,\;\;{\text{车辆}}{{k}}{\text{选择路径}}\;({{i}},{{j}})\\ 0,\;\;{\text{其它}} \end{array} \right.$ (1)

 $Z = \min \left({\rho _1}\sum\limits_{k = 1}^m {\sum\limits_{j = 1}^n {\sum\limits_{i = 1}^n {{l_{ij}}{x_{ijk}} + {\rho _2}\sum\limits_{k = 1}^m {\sum\limits_{j = 1}^n {{x_{0jk}}} } } } } \right)$ (2)

 $\sum\limits_{j = 1}^n {{x_{0jk}} = 1}\;\;{\text{且}}\;\; \sum\limits_{i = 1}^n {{x_{i0k}} = 1} ,\forall k$ (3)
 $\sum\limits_{k = 1}^m {\sum\limits_{j = 0}^n {{x_{ijk}}} } = 1,\forall i$ (4)
 $\sum\limits_{i = 0}^n {\sum\limits_{j = 0 \wedge j \ne i}^n {{D_i}{x_{ijk}}} } \leqslant Q,\forall k$ (5)
 $S{T_i} < {t_i} < E{T_i},\forall i$ (6)
 ${x_{ijk}} \in \{ 0,1\} ,\;\forall i,j,k$ (7)

1.2 传统蚁群算法求解VRPTW

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

 {p_{ij}} = \left\{ \begin{aligned} & \dfrac{{\tau _{ij}^\alpha \eta _{ij}^\beta }}{{\displaystyle\sum\limits_{j \in allowe{d_i}} {\tau _{ij}^\alpha \eta _{ij}^\beta } }},\;{\rm{if}}\;\;j \in allowe{d_i}\\ \;\; & \;\;\;\;\;\;\;\;\; 0,\;\;\;\;\;\;\;\;\;{\text{否则}} \end{aligned} \right. (8)

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

 $\left\{ \begin{gathered} {\tau _{ij}}(t + 1) = \rho {\tau _{ij}}(t) + \vartriangle {\tau _{ij}}(t,t + 1) \\ \vartriangle {\tau _{ij}}(t,t + 1) = \sum\limits_{k = 1}^m {\vartriangle \tau _{ij}^k(t,t + 1)} \\ \end{gathered} \right.$ (9)

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

2.2 路径构建优化

 {p_{ij}} = \left\{ \begin{aligned} & \dfrac{{\tau _{ij}^\alpha \eta _{ij}^\beta }}{{\sum\limits_{j \in allowe{d_i}} {\tau _{ij}^\alpha \eta _{ij}^\beta } }}*\dfrac{{1/(|{t_{ij}} - S{T_j}| + |{t_{ij}} - E{T_j}|)}}{{\sum\limits_{j \in allowe{d_i}} {1/(|{t_{ij}} - S{T_j}| + |{t_{ij}} - E{T_j}|)} }},\\ & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{if}}\;j \in allowe{d_i}\\ & \;0,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\text{其它}} \end{aligned} \right. (10)

${t_{ij}}$ 为到达节点 $j$ 的时间, 当 ${t_{ij}} \geqslant S{T_j}$ 时, 等待时间为 $0$ , $|{t_{ij}} - S{T_j}| + |{t_{ij}} - E{T_j}|$ 为时间窗大小, 否则当 ${t_{ij}} < S{T_j}$ 时, $|{t_{ij}} - S{T_j}| + |{t_{ij}} - E{T_j}|$ 为时间窗和等候时间的综合指标.

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

2.3 信息素更新优化

 $\rho = \left\{ {\begin{array}{*{20}{l}} {0.9,} & {{\rho _{\max }}}\\ {0.95 * \rho ,} & {{\text{停滞}}}\\ {0.5,} & {{\rho _{\min }}} \end{array}} \right.$ (11)

 \left\{ \begin{aligned} &{\tau _{\max }} = 1/(1 - \rho ){C^{\rm{best}}} \\ &{\tau _{\min }} = {\tau _{\max }}(1 - \sqrt[n]{{0.05}})/(n/2 - 1) \\ \end{aligned} \right. (12)

2.4 基于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等方法真正执行数据的计算部分.

 图 2 Spark核心计算过程

2.5 算法描述

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

(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()方法如下:

② 构造候选节点集, 满足负载、时间窗要求;

③ 从候选节点中依据状态转移规则(10)并采用轮盘赌选择下一个需要服务的节点next并加入当前路径中;

⑤ 判断是否还有未服务的点, 若存在则返回步骤(1), 否则结束

(6) 每轮迭代结束后通过Spark中的collect()方法收集蚁群计算结果, 对每只蚂蚁搜索得到的可行解进行排序, 根据图1对迭代最优解进行k-opt局部调整优化;

(7) 得到迭代最优解后通过ant.set_parameter方法统一更新参数, 各路径信息素浓度更新公式参考式(9)、(11)、(12), 采用TIbestTGbest轮流进行更新、自适应信息素蒸发策略且限制信息素范围为[τmin, τmax];

(8) 判断迭代是否终止, 迭代终止输出全局最优解, 否则返回步骤(4)继续并行化求解.

3 实验设计及结果分析

3.1 实验环境及算例说明

(1) 单机运行环境

Intel Core i7.

2 GB内存.

(2) Spark集群运行环境

Intel Core i7.

2 GB内存.

3.2 实验设计及结果分析 3.2.1 信息素矩阵可视化表达

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

3.2.2 收敛性比较实验

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

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

3.2.3 求解精度比较实验

3.2.4 求解速度比较实验

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

4 总结与展望

 [1] 郎茂祥. 配送车辆优化调度模型与算法. 北京: 电子工业出版社, 2009. [2] Solomon MM. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987, 35(2): 254-265. DOI:10.1287/opre.35.2.254 [3] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 1996, 26(1): 29-41. [4] Jin NB, Rahmat-Samii Y. Particle swarm optimization for antenna designs in engineering electromagnetics. Journal of Artificial Evolution and Applications, 2008, 9. [5] Goldberg DE. Genetic algorithms in search, optimization, and machine learning. Upper Saddle River, New Jersey: Addison-Wesley, 1989. [6] 陈迎欣. 基于改进蚁群算法的车辆路径优化问题研究. 计算机应用研究, 2012, 29(6): 2031-2034. DOI:10.3969/j.issn.1001-3695.2012.06.007 [7] 李琳, 刘士新, 唐加福. 改进的蚁群算法求解带时间窗的车辆路径问题. 控制与决策, 2010, 25(9): 1379-1383. [8] 董攀. 带时间窗车辆路径问题的蚁群算法改进[硕士学位论文]. 长沙: 长沙理工大学, 2014. [9] Helsgaun K. An effective implementation of the Lin–Kernighan traveling salesman heuristic. European Journal of Operational Research, 2000, 126(1): 106-130. DOI:10.1016/S0377-2217(99)00284-2 [10] 崔文. 大规模多配送中心车辆路径问题研究[硕士学位论文]. 济南: 山东大学, 2012. [11] 吴越钟. 改进的Lin-Kernighan局部搜索算法和杂交算法在旅行商问题中的应用[硕士学位论文]. 合肥: 中国科学技术大学, 2016. [12] 葛斌. 求解车辆路径问题的蚁群优化算法研究及应用[博士学位论文]. 合肥: 合肥工业大学, 2016. [13] 丁秋雷. 带有时间窗的车辆路径问题的混合蚁群算法研究[硕士学位论文]. 大连: 大连理工大学, 2006. [14] 王颖, 谢剑英. 一种自适应蚁群算法及其仿真研究. 系统仿真学报, 2002, 14(1): 31-33. DOI:10.3969/j.issn.1004-731X.2002.01.010 [15] Nalepa J, Czech ZJ. A parallel memetic algorithm to solve the vehicle routing problem with time windows. arXiv: 1402.6942, 2014. [16] 郭宝恩. 基于Spark的蚁群算法在物流配送路径优化问题中的应用研究. 信息与电脑(理论版), 2018(3): 50-52. [17] 王诏远, 王宏杰, 邢焕来, 等. 基于Spark的蚁群优化算法. 计算机应用, 2015, 35(10): 2777-2780, 2797. [18] 金淳, 张雨, 王聪. 带时间窗车辆路径问题的分布式多agent蚁群算法. 计算机应用研究, 2018, 35(3): 666-670.