混合最大最小蚁群算法在VRPTW中的应用
计算机技术与发展第20卷 第2期 ol. 20 No. 2 V F 2010年2月eb. 2010COM PUT ER TECHNOLOGY AND DEVELOPM ENT
混合最大最小蚁群算法在VRPTW 中的应用
苏红畏1, 刘希玉1, 王晓敏2
(11山东师范大学管理与经济学院, 山东济南250014; 21山东师范大学信息科学与工程学院, 山东济南250014)
摘 要:为解决有时间窗车辆路径问题, 采用两个最大最小蚁群系统, 一个蚁群最小化车辆数量, 另一个蚁群最小化旅行距离。通过分析有时间窗车辆路径问题和旅行商问题的区别, 改进了最大最小蚁群算法中状态转移策略, 并增加与可用车辆相同数量的虚拟仓库, 使这两个蚁群使用独立的信息素但通过分享全局最优解来协作, 算法还结合了2-opt 局部搜索, 从而减少了算法的计算时间并避免过早收敛。仿真实验结果表明, 该算法性能优良, 能有效地求解有时间窗车辆路径问题。
关键词:最大最小蚁群算法; 时间窗车辆路径问题; 2-opt 局部搜索
中图分类号:T P391 文献标识码:A 文章编号:1673-629X(2010) 02-0090-05
Hybrid Max-Min Ant System for Vehicle Routing
Problem with Time Windows
SU H ong -wei 1, LIU X-i yu 1, WANG Xiao -min 2
(1. School of M anag ement and Economics, Shandong N ormal U niv ersity, Jinan 250014, China; 2. Information Science and Engineer ing Institute, Shandong N ormal U niversity , Jinan 250014, China)
Abstract:Tw o ant colonies employing max-min ant colony system, one m i n i mizes the number of vehicles while the other mini m i z es the traveled distances, have been designed to tackle the VRPT W(vehicle routi ng problem w ith time w indow ) . By analyzing the difference be -tw een the vehicle routing problem w i th time w indow and traveling s alesman problem, the state transition strategy of the max-mi n ant colony sys tem is i m proved and the depot is duplicated a number of times equal to the num ber of available vehicles. These tw o col onies w ork by using i n dependent pheromone trails but col laborate by shari ng the global best feasible solution, and integrating 2-opt local search method in order to decrease computing time and overcome early convergence. S i mulation results show that the algorithm present is feasible and valid for VRPTW.
Key words:max-min ant system; vehicle routing problem w ith time w indow ; 2-opt local search
0 引 言
车辆路径问题(vehicle routing problem, VRP) 最早由Dant zig 和Ramser [1]于1959年提出。目前求解VRP 的方法可以分为精确算法和启发式算法两大类, 典型的启发式算法有禁忌搜索算法、模拟退火算法、遗传算法、神经网络算法、蚁群优化算法等。
蚁群算法由意大利学者M arco Dorigo 于1991年
[2]
在其博士论文中首次提出。为了克服基本蚁群算法搜索效率低和早熟停滞的不足, T homas St tzle 等人[3]提出的M MAS(M ax-M in Ant System) 在解决二次分配问题、大学课程时间表问题、装箱问题等组合优化问题[4]时取得了显著的效果。赵传信等[5]提出了将粒子群算法和禁忌搜索算法相结合的禁忌搜索粒子群算法, 来解决车辆路径问题; 刘志硕等[6]在分析车辆路径和中国邮递员问题的基础上构造了具有自适应功能的混合蚁群算法; 万旭等[7]提出了改进的最大最小蚁群算法在V RPT W 中的应用。但是这些算法都存在计算时间长和早熟停滞的缺点, 笔者受Gambardella [8]的启发在分析VRPT W 两个目标的基础上, 利用两阶段构造策略并结合2-opt 局部搜索提出了解决VRPT W 收稿日期:2009-05-31; 修回日期:2009-08-14
基金项目:国家自然科学基金项目(60873058) ; 山东省自然科学基金项目(Z2007G03) ; /泰山学者0建设工程专项经费资助项目(2005-2010)
作者简介:苏红畏(1982-) , 男, 山东阳信人, 硕士研究生, 研究方向为进化计算与智能算法; 刘希玉, /泰山学者0, 教授, 博士生导师, 研究方向为人工智能与数据挖掘。
第2期 苏红畏等:混合最大最小蚁群算法在V RPT W 中的应用#91#
1 VRPTW 问题描述及模型
1. 1 VRPT W 问题描述
VRPT W (vehicle rout ing problem with t ime win -dows) 即带有时间窗的车辆路径问题[9]是指:已知有一批客户, 每个客户的地理位置坐标和货物需求已知, 每辆车都从仓库出发完成若干客户点的货物分配任务后再回到仓库, 车辆的负载能力给定。假设每个客户只能被访问一次, 每辆车所访问客户的需求总和不能超过车辆的负载能力。每个客户i 带有一个时间窗[e i , l i ], e i 为客户i 允许服务的最早开始时间, l i 为客户i 允许的服务最迟开始时间, 车辆必须在这个时间范围内对客户进行服务。若车辆在时间e i 之前到达客户点i , 则要等到e i 才开始服务。问题的目标是用最少的车辆数和总路长来完成所有任务。1. 2 VRPT W 数学模型
记每辆车的最大载重量为D , 客户i 的需求为d i (i I V ) , V 为客户集合。se i 表示对客户i 服务的开始时刻, sl i 表示服务终止时间, s i 表示完成任务所需的服务时间, 即s i =sl i -se i , t ij 为车辆从客户i 到客户j 的旅行时间, w i 表示开始为客户i 服务所需的等待时间, 通常取t ij =c i j 。
设x ijk =
1, 若车辆k 经过路径(i , j )
0, 否则
:min Z =
i
2 混合最大最小蚁群算法
2. 1 改进的最大最小蚁群算法描述
在M M AS [3]基础上文中改进的最大最小蚁群算法如下。
Step 1:状态转移规则采用下式:if q [q 0
t hen j =arg else p ij =
B
S A G r w i j H k
if j I N i
i l i l r w k
S A
G i j
B
r w k
(1)
l I N i
0 otherwise
其中, q 0为区间[0, 1]中的任意实数, q 为[0, 1]中的随机数; p k i j 表示位于结点i 的车辆k 选择结点j 的概率; S i j 表示边(i , j ) 上信息素的值; G ij 表示由结点i 选择j 的期望值; r i j 为车辆从结点i 到结点j 的到达时间与时间窗上限的时间差; w ij 为车辆从结点i 到结点j 后, 在结点j 的等待时间; C 和H 分别为时间差和等待时间的相对重要性; N k i 表示位于结点i 的蚂蚁k 可以直接到达的相邻结点的集合。
ib gb
Step 2:只有迭代最优W 或全局最优W 的蚂蚁才
允许释放信息素, 即
S i j =(1-Q ) S i j +$S ij , 对于P (i , j ) I W
b s
ib
bs
b s
(2)
其中Q 为信息素的挥发系数, $S i j =1/f (W ) 或者$S i j =1/f (W ) 。
Step 3:为解决某些边上信息素增长过快以防止搜索停滞现象的出现, 把信息素的大小限制在S ma x =1/Q f (W ) 到S mi n =S ma x (1- (b )
n
bs gb
E E E c i j x i j k , E E x 0jk
i
j
k
j
k
E d i y ki [D , P k E y k i =
k
(a )
b s
n
0. 05) /((n/2-1) #
1, i I V
) 之间。
Step 4:信息素的初始值设定为其取值范围的上界
E x ijk =
i
y kj , j I V , P k (c ) y ki , i I V , P k
(d )
s. t.
E x ijk =
j i, j I S @S
S ma x , 并与一个小的信息素蒸发率Q 相结合, 目的是使得算法可以在最初的搜索步骤中探索更多可能的路径。
2. 2 混合最大最小蚁群算法在VRPTW 上的应用2. 2. 1 HM M AS-VRPTW 算法
在HM M AS-V RPT W 算法中采用两个蚁群, 第一个蚁群M MAS-V EI 最小化使用的车辆数目; 第二个蚁群M MAS-T IM E 最优化由M M AS-VEI 得到的可行解的距离。两个蚁群的信息素独立但两者通过
gb
分享由HM MAS-VRPT W 求出的变量W (全局最优
E E
x i jk [|S |-1, S A V (e )
sl i +t i j [se j , i , j I V , P k (f ) e i [se i [l i , i I V x ijk , y kj I {0, 1}, i , j I V , P k 其中,
约束(a) 为车辆负载限制;
约束(b) 保证每个车辆对每个客户只访问一次; 约束(c ) ~(e) 保证形成可行回路;
约束(f) 表示一条线路上两相邻任务存在的条件; 约束(g) 表示时间窗约束;
(g )
解) 来协作。HM MAS-VRPT W 算法的详细过程如下:
HM MAS-VRPT W()
gb 00
Step 1:W z W , 其中W 由最近邻启发式得到。
# 92 # 计算机技术与发展 第20卷
Repeat
gb
将W 中车辆数赋给变量v ;
Repeat
k
对每只蚂蚁分别构建一个解W , 即调用new -
然后依次调用M MAS -VEI (v -1) 和M MAS -T IM E (v ) ;
While M MA S-VEI 和M MAS -T IM E 没有结束如果M MAS-VEI 或M M AS-T IM E 可找到一个
gb
改进的解W c , 那么W z W c 。
gb
如果W 中车辆数
active -ant(k, local -searc h =T RUE, 0) , 如果存在一个
k k gb k
蚂蚁k , 使得W 是可行解并且W 比W 更优, 那么将W
存入HM M AS-VRPTW 。
然后对信息素据公式(2) 执行全局更新, 即S ij =(1-Q ) #S i j +Q /f (W ) P (i , j ) =W 。
如果信息素更新后的值S ij |[S min , S ma x ], 那么将
gb S i j 重新初始化到[S min , S ma x ] P (i , j ) =W 。
gb
gb
和M MAS-T IM E 。
end While
Unt il a stopping c rit erion is met 2. 2. 2 M M AS-VEI 算法
MM AS-VEI(s)
Step 1:将含s 个车辆的初始解赋给W 中, s =v -1, 变量W
Step 2:Repeat
对每只蚂蚁分别构建一个解W , 即调用new -active -ant(k, local -searc h =FALSE, IN ) 。若顾客j 未被蚂蚁k 访问, 则变量IN j ++。其中, IN j 表示顾客j 未被插入到解中的次数。
k
如果存在一个蚂蚁k , 使得W 中顾客数目>M MAS -VEI M MAS-VEI k W 中顾客数目, 那么W z W , 否则, 清
k
M MAS-VEI
M MAS -VEI
U nt il a stopping crit erion is met 2. 2. 4 解的构建过程
new -ac t ive -ant(k, local -search, IN)
Step 1:将蚂蚁k 放到随机选择的虚拟仓库i 上, 并
, 其
置当前时刻和蚂蚁k 的负载为0, 即current -t ime k z 0, load k z 0。
Step 2:Repeat
当蚂蚁k 位于结点i 时, 计算其可行结点的集合
k
N k i , 并对P j I N i 计算启发式信息G ij 如下:
保存本次迭代中含最高
访问数量顾客的解(此解常常是不可行解) 。
Delivery -time j z max(current -time k +t i j , b j ) Delta -time ij z Delivery -t ime j -current -time k dist ance ij z delta -time i j *(e j -current -t ime k ) dist ance ij z max(1. 0, (distance i j -IN j ) ) G ij z 1. 0/dist ance ij
然后, 据公式(1) 选择下一个可能的结点j , 并将j
k 加入蚂蚁k 的解W 中。如果j 是仓库, 那么current -
空向量IN 。如果W
MM AS-VEI
是可行解, 那么, 将其保存
到HM M AS-VRPT W 中。
然后据公式(2) 对信息素执行全局更新, 即S ij =(1-Q ) #S ij +
MM AS -VEI
$S ij
gb
P (i , j ) I W
gb
MM AS-VEI
t ime k z 0, load k z 0。
据公式(3) 执行信息素局部更新, 即S i j =(1-Q ) #S i j +Q #S 0
然后置j 为蚂蚁k 的当前结点。
U nt il N i =ª, 即若无可行结点可用, 则结束St ep 3。
Step 3:插入未访问的顾客来扩展路径W 。
k Step 4:如果参数local -searc h =TRU E 并且W 是
k
k
, S i j =
(1-Q ) #S i j +Q /f (W ) P (i, j ) I W 。
如果S i j |[S mi n , S max ], 那么将信息素的值S ij 重新
gb
初始化到[S mi n , S max ]P (i , j ) I W 。
(3)
Unt il a stopping c rit erion is met 2. 2. 3 M M AS-T IM E 算法
MM AS-T IME 的目标是使得由MM AS-VEI 求出的路径尽可能短。在MM AS-T IME 阶段让m 只
1人工蚂蚁调用new -active -ant() 来构造问题的解W ,
可行解, 那么使用局部搜索过程来优化可行解的路径,
k k
即W z 2-opt -local -searc h (W ) 。
, , W , 这类似于旅行商问题中路径的构建过程。然后将W , , , W 与W 比较, 一旦有一个比W 更好的解, 设为W , 就将W 加入HMM AS-VRPT W 中。最后, 根据公式(2) 和S mi n 、S max 执行信息素的全局更新。详细算法如下:
MM AS-T IM E (v )
Step 1:用v 来初始化信息素和数据结构。k
k
1
m
gb
gb
m
文中采用常用于旅行商问题中的2-opt 局部搜索[6]来改进可行解的质量, 详细过程如下。2. 2. 5 2-opt 局部搜索过程
k
设可行解W 由p 个子回路组成, 记为{L 1, L 2, , ,
L p }, 更新可行解的过程实际上就是对各个子回路分别应用2-opt 。设W k 是路径L k 经过结点的有序排列, W k ={v 0, v 1, v 2, , , v n , v 0}, v i , v j 是从W k 中随机选, L c k 为
第2期 苏红畏等:混合最大最小蚁群算法在V RPT W 中的应用#93#
没有任何改进的最大循环次数, 文中用到的2-opt 局
k
部搜索, 即2-opt -local -search (W ) 其步骤如下:
表1说明:BestSoFar 是当前已知最优解, MMAS -AVG 、M MAS -BEST 分别是文献[7]中平均值解和最优解, HMMAS -AVG 、HM MAS -BEST 分别是文中10次实验全局最优解的平均值和最优解。
Step 1:初始化循环次数变量t =1, 当前最优解
**W =W , 其长度为f (W ) 。
Step 2:在W k 中随机选择2个结点v i , v j , i
Step 3:求$C d =d(x i +1, x j ) +d(x i , x j+1) -d (x i +1, x i ) +d (x j , x j+1) , 若$C d >0, 则不交换, t ++, 转到Step 4, 否则交换, 更新W k , 更新后的解为W c , 则最优解W =W c , t =1, 转到Step 2。
*
在文中算法中, 实验开始将路径上的信息素初始化为上限值S max , 这样可使该系统有更好的全局搜索的能力。以实例r103为例, 图1描述了迭代次数和全局最优解之间的关系, 其中横轴表示迭代次数, 纵轴表示全局最优解的值。图例M M AS 和HMM AS 分别表示文献[7]、文中算法迭代次数和全局最优解之间的关系。由图1可知, 迭代次数位于1~170时, 算法HM MAS 所求的解的质量明显要比算法M MAS 解的质量低, 迭代次数位于171~380时, 算法HM M AS 与M M AS 所求解的质量相差不大, 而在381次迭代之后算法HM MAS 所求解的质量明显好。原因是迭代开始时文中算法将信息素的值设定为上限值S max , 这可使算法HM MAS 初始有更好的全局搜索的能力, 但是所求解的质量会相对差一些, 随着迭代次数的增加通过使用2-opt 局部搜索机制来提高解的质量, 算法HM MAS 显示了较好的性能。文中算法每次实验运行时间限制为60秒, 而文献[7]中的图1表明MM AS 在运行时间为350秒时, 总的运行距离的收敛才趋于平稳, 这说明算法HM M AS 在求解最优解时明显缩短了每次迭代的计算时间。
图2描述了算法运行时间和某路径上信息素的值之间的关系, 其中横轴表示算法运行时间, 纵轴表示信息素的值。由图2可知, 随着时间和迭代次数的变化信息素的值出现了震荡并且被限定在[S mi n , S ma x ]之间, 这有利于避免某条路径上信息素聚集太多, 而防止搜索过早陷入局部最优。
Step 4:若f (W ) 在最后C N 个循环中没有减少, 则本算法结束; 否则转到Step 2。
*
3 仿真实验及分析
将文中提出的HM M AS-V RPT W 算法应用于Solomon 在文献[10]中所述的基准实例。每个实例都含有100个客户和一个中心仓库, 并规定了车辆负载、服务时间和客户的地理位置坐标、货物需求量、时间窗等。实验是在AMD Athlon(tm) 64X2Dual, Core Pro -cessor 4000+2. 10GHz, 内存为1G 的硬件环境, 基于Redhat Linux 9. 0平台在GCC 3. 2. 2编译器下用C++语言实现。
3. 1 参数设定及试验结果分析
实验开始将每个虚拟仓库都放置一个蚂蚁, 蚂蚁个数与虚拟仓库的个数相同(各个实例蚂蚁个数n 取值不同) 。A =1. 00, B =2. 00, Q =0. 10, q 0=0. 95, C =0. 10, H =0. 10, S 0=1/Q C (C
nn
nn
由文献[11]获
得) 。对基准实例R1做10次实验, 每次实验的时间限制为60. 00秒, 然后取全局最优解的平均值和最优解, 见表1。由表1可知, 算法HM M AS-VRPT W 的整体计算结果比文献[7]中结果要好, 个别最优解如R103已经接近已知最优解。
表1 文中平均值解、最好解与已知最优解的比较
实例
BestSoFar
MMAS -AVG 1701. 58/181554. 91/171338. 57/131050. 72/91412. 14/131303. 61/121148. 15/101002. 17/91247. 32/111161. 25/101133. 94/10MMAS -BEST 1660. 71/181503. 47/171307. 74/131032. 29/91374. 03/131266. 74/121121. 94/10979. 64/91217. 09/111155. 43/101120. 57/10HMMAS -AVG
HMMAS -BEST
R1011650. 80/19R1021486. 12/17R1031292. 68/13R1041007. 31/9R1051377. 11/14R1061252. 03/12R1071104. 66/10R108
963. 99/9
R1091194. 73/11R1101124. 4/10R1111096. 72/101713. 71/181676. 23/181564. 98/171519. 45/171332. 64/131301. 28/131047. 19/9
1028. 75/9
1446. 14/131378. 91/131309. 48/121276. 64/121152. 37/101116. 74/101011. 17/9
984. 28/9
图1 迭代次数和全局最优解之间的关系
1238. 12/111230. 43/111179. 42/101136. 12/101132. 41/101117. 84/10
4 结束语
# 94 # 计算机技术与发展 第20卷
的旅行距离这两个目标, 结合该问题本身的特点, 受文献[8]的启发提出用信息素相互独立, 但又通过交换信息来协作的混合蚁群算法。当M M AS-VEI 算法找到可行解以后, 通过使用MM AS-T IM E 算法并结合2-opt 局部搜索来提高可行解的质量, 在算法运行过程中信息素被限定在[S min , S ma x ]之间, 有利于防止某条路径信息素聚集过高, 从而减少计算时间以避免过早收敛。通过使用含2-opt 和不含2-opt 局部搜索机制分别对Solomon 的测试数据进行实验, 并与文献[7]中实验做了对比,
结果表明了文中算法的有效性。
M anagement Science, 1959, 6(1) :80-91.
[2] Dorigo M. Optimization, Learning and Natural Algorithms
[D].M ilan, Italy:Diparti mento di Elettronica, Politecnio di M ilano, 1992.
[3] St tzle T, Hoos H H. MAX-M IN Ant System[J].Future
Generation Computer Systems, 2000, 16:889-914. [4] Dorigo M , St tzle T. 蚁群优化[M ].张 军, 胡晓敏, 译.
北京:清华大学出版社, 2007.
[5] 赵传信, 张雪东, 季一木. 改进的粒子群算法在VRP 中的
应用[J].计算机技术与发展, 2008, 18(6) :240-242. [6] 刘志硕, 申金关. 车辆路径问题的混合蚁群算法设计与实
现[J]. 管理科学学报, 2007, 10(3) :15-22.
[7] 万 旭, 林健良, 杨晓伟. 改进的最大-最小蚂蚁算法在有
时间窗车辆路径问题中的应用[J].计算机集成制造系, 2005, 11(4) :572-576.
[8] Gambardella L M, Taillard E, Agazzi G. MACS-VRPTW:
A Multi ple A nt Colony System for V ehicle Routing Problems with T ime Windows[M]. In:Corne D, Dorigo M, Glover F. N ew Ideas in Opti mizati on. U K:M cGraw -Hill, 1999:63-76.
[9] Flood M M. T he Traveling Salesman Problem[J].Operations
Research, 1956(4) :61-75.
[10]Solomon M. Algorithms for the Vehicle Routi ng and Schedu-l
图2 算法运行时间和信息素的值之间的关系
参考文献:
[1] Dantizig G, Ramser J. T he truck dispatching problem [J].
ing Problem with T ime Window Constraints[J]. Operations Research, 1987, 35:254-365.
[11]马 良, 朱 刚, 宁爱兵. 蚁群优化算法[M ].北京:科学出
版社, 2008.
(上接第89页) 参考文献:
[1] Hansen L K, Salamon P. Neural network ensembles[J].IEEE
T ransactions on Pattern Analysi s and Machine Intelligence, 1990, 12(10) :993-1001.
[2] Zhou Z-H, Wu J, Tang W. Ensembling neural networks:
many could be better than all[J].Artificial Intelligence, 2002, 137(1-2) :239-263.
[3] Dietter ich T G. Ensemble methods in machine learni ng[C]//
In:Proceedings of the First International Workshop on Mult-i ple Classifier Systems. Cagliari, Italy:[s. n. ], 2000:1-15. [4] 唐耀华, 高静怀. 一种新的选择性支持向量机集成学习算
法[J]. 西安交通大学学报, 2008(10) :1221-1225. [5] 蒋望东, 林士敏. 基于选择性集成遗传算法的BNC 结构学
习[J]. 计算机辅助工程, 2006(3) :46-50.
[6] 王正群, 陈世福. 一种主动学习神经网络集成方法[J].计
算机研究与发展, 2005(3) :375-380.
[7] 王建敏, 李铁军. 基于神经网络集成学习的智能决策支持
系统构建[J].电脑知识与技术, 2008(9) :2045-2050. [8] 李 凯, 崔丽娟. 集成学习算法的差异性及性能比较[J].
计算机工程, 2008(3) :35-37.
数据集上明显优于Adaboost 占75%, 1个数据集上持平占5%。可以分析出Ada -ens 在分类准确率、泛化性能、稳定性上都表现出较好的性能。
3 结束语
文中在选择性集成学习的集成上提出了多层次选择性集成算法Ada -ens, 针对决策树与神经网络模型在20个标准数据集对集成学习算法Ada -ens 进行了实验研究, 试验证明基于数据的集成学习算法的性能优于基于特征集的集成学习算法的性能, 有更好的分类准确率和泛化性能。
下一步工作中着重需要解决的问题:与目前集成学习相似试验的参数均是认为设定的希望通过理论推导或试验分析得出最佳的参数设置和理由; 用数学理论佐证为什么选择性集成会更有效对其进行改进和完善。
[8]
, 在什么情况下
更有效; 在真实的情况下测试Ada -ens 的效果, 并依次