推荐星级:
  • 1
  • 2
  • 3
  • 4
  • 5

带时间窗的车辆路径问题的离散蝙蝠算法

更新时间:2019-12-24 03:51:14 大小:687K 上传用户:守着阳光1985查看TA发布的资源 标签:离散蝙蝠算法 下载积分:1分 评价赚积分 (如何评价?) 打赏 收藏 评论(0) 举报

资料介绍

本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题(vehicle routing problem with time window).该算法提出了蝙蝠位置的定义、速度的定义、位置更新操作、速度更新操作、频率更新操作,并采用惩罚机制与向量比较机制相结合的方法处理相关约束条件.该算法引入了随机插入策略、最少客户车辆插入搜索、普通插入搜索、交换搜索、带时间窗的2-Opt搜索等策略来扩大搜索空间、加强算法的收敛效率.实验结果表明:所提出算法具有较强的寻优能力、较高的鲁棒性、较少的时间耗费;本文所采用的关键参数值和策略能提高所提出算法的性能;通过假设检验证明了所提出算法与对比算法之间的算法性能均有显著性差异.


部分文件列表

文件名 大小
带时间窗的车辆路径问题的离散蝙蝠算法.pdf 687K

部分页面预览

(完整内容请下载后查看)
3
Vol. 46 No. 3  
Mar. 2018  
2018  
3
ACTA ELECTRONICA SINICA  
带时间窗的车辆路径问题的离散蝙蝠算法  
1
1
2
1
戚远航 蔡延光 蔡 颢 黄何列  
( 1.  
510006; 2.  
9220)  
广东工业大学自动化学院 广东广州  
奥尔堡大学健康科学与工程系 丹麦奥尔堡  
:
( vehicle routing problem with time win-  
本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题  
dow) .  
该算法提出了蝙蝠位置的定义 速度的定义 位置更新操作 速度更新操作 频率更新操作 并采用惩罚机制与  
向量比较机制相结合的方法处理相关约束条件 该算法引入了随机插入策略 最少客户车辆插入搜索 普通插入搜索  
交换搜索 带时间窗的  
2-Opt  
搜索等策略来扩大搜索空间 加强算法的收敛效率 实验结果表明 所提出算法具有较强  
:
;
的寻优能力 较高的鲁棒性 较少的时间耗费 本文所采用的关键参数值和策略能提高所提出算法的性能 通过假设检  
;
验证明了所提出算法与对比算法之间的算法性能均有显著性差异  
:
;
;
; 2-Opt  
关键词  
中图分类号  
URL: http: / /www. ejournal. org. cn  
离散蝙蝠算法 车辆路径问题 时间窗  
:
TP301  
:
A
:
0372-2112 ( 2018) 03-0672-08  
DOI: 10. 3969 /j. issn. 0372-2112. 2018. 03. 024  
文献标识码  
文章编号  
电子学报  
Discrete Bat Algorithm for Vehicle Routing Problem with Time Window  
1
1
2
1
QI Yuan-hang CAI Yan-guang CAI Hao HUANG He-lie  
( 1. School of AutomationGuangdong University of TechnologyGuangzhouGuangdong 510006China;  
2. Department of Health Science and TechnologyAalborg UniversityAalborg 9220Denmark)  
Abstract: This paper presents a discrete bat algorithm to solve the vehicle routing problem with time window  
( VRPTW) . The proposed algorithm defines positionvelocityupdated operation of the positionupdated operation of the ve-  
locity and updated operation of the frequencyand uses a method which combines the penal function with vectorial compari-  
son to deal with constrained conditions. The proposed algorithm adopts random inserted strategyinserted research strategy  
for the vehicle with minimum customersordinary inserted research strategyexchanged research strategy and 2-Opt strategy  
with time window to expand the search space and enhance the convergent rate. Experimental results show thatthe proposed  
algorithm has a stronger optimization capabilityhigher robustness and less time consumptionkey parameter values and strat-  
egies used in this paper can improve performances of the proposed algorithmand according to the hypotheses testingthere  
exsits a significant difference between the proposed algorithm and comparative algorithms.  
Key words: discrete bat algorithm; vehicle routing problem; time window; 2-Opt  
VRPTW,  
该算法使用混沌算法初始化和扰动粒子群算  
1
引言  
;
4]  
法 以提高粒子群的局部搜索能力 文献 提出一种  
( Vehicle Routing Problem  
带时间窗的车辆路径问题  
VRPTW.  
但是 以上诸  
基于智能体的合作学习算法求解  
with Time WindowVRPTW)  
Routing ProblemVRP) 1]  
( Vehicle  
是车辆路径问题  
VRPTW  
算例中求解能力参差不齐  
算法在不同类型的  
的经典问题之一 经过多年的  
时间耗费较多 收敛效率也较低  
VRPTW  
研究 学者们应用启发式算法求解  
2VRPTW  
取得一定的  
的离散粒子群算  
( Bat AlgorithmBA)  
Yang X S  
2010  
蝙蝠算法  
效果 文献  
提出一种求解  
年提出的一种元启发式算5近年来 学者们把蝙蝠  
;
法 文 献  
3]  
提 出 一 种 混 合 混 沌 粒 子 群 算 法 解 决  
算法应用到物流运输调度领域并取得了一定的研究成  
: 2016-09-30;  
: 2016-12-21;  
:
收稿日期  
修回日期  
责任编辑 覃怀银  
广 东 省 自 然 科 学 基 金  
( No. 2012B050600028No. 2014B010118004No. 2016A050502060) ;  
:
( No. 61074147 ) ;  
( No. S2011010005059 ) ;  
( No.  
广 东 省 教 育 部 产 学 研 结 合 项 目  
基金项目 国 家 自 然 科 学 基 金  
2012B091000171No. 2011B090400460) ;  
广东省科技计划项目  
( No. 201604016055)  
广州市科技计划项目  
广州市花  
( No. HD14ZD001) ;  
都区科技计划项目  
673  
3
:
戚远航 带时间窗的车辆路径问题的离散蝙蝠算法  
6]  
;
送中心 式  
( 6)  
; ( 7)  
表示每个客户只能由一辆车服务 式  
果 文献 提出了改进的离散蝙蝠算法求解对称和非  
;
7]  
对称旅行商问题 文献 提出了基于路径重连的混合  
;
表示避免服务过程中产生子回路 式  
( 8)  
表示硬时间窗  
蝙蝠算法求解带容量约束的车辆路径问题等 但是 目  
;
( 9) ( 10)  
约束 式  
为对决策变量的约束  
VRPTW  
前还没有学者把蝙蝠算法应用到  
这些离散蝙蝠算法也不能直接运用到  
( Discrete Bat Algo-  
中 而现有的  
3
离散蝙蝠算法  
VRPTW  
上 因  
3. 1  
3. 1. 1  
参数定义与操作设计  
此 本文提出了一种离散蝙蝠算法  
rithmDBA) VRPTW,  
蝙蝠位置  
+
求解  
拓展了蝙蝠算法在物流运输  
Q
N
n,  
为蝙蝠种群规模 顶点数为 车辆数为  
调度领域的应用 具有一定的创新性 实际意义和较好  
的推广价值 实验结果表明  
: DBA  
m,  
维数  
w = n + m - 2.  
i
定义第 个蝙蝠的位置为  
x =  
i
具有较强的寻优能  
;
( x x x ) i = 12Q,  
其中  
x
( 12w)  
力 较高的鲁棒性 较少的时间耗费 所采用的关键参数  
i1  
i2  
iw  
i
DBA  
;
值和策略能提高  
DBA  
的性能 通过假设检验证明了  
的一个置换  
蝙蝠位置按照规则与  
: x = 1 x n  
与对比算法之间的算法性能均有显著性差异  
VRPTW  
路径形成一一对应  
1;  
关系  
均认为是配送中心  
蝙蝠位置  
; 2  
ij  
ij  
2
数学模型  
1VRPTW  
的前后分别加上 构成一条完整的  
路径  
K = { 12m}  
N =  
为配送中心车辆的集合  
1”  
之间经过的客户点构成一台车辆的访问路径 例  
{ 2n}  
V = { 1N}  
为配送中  
为配送中心的客户集合  
: n = 6m = 3w = 7x = ( 2354716) ,  
其对应的  
i
(
心 定义为  
1)  
. V  
k
为车辆 访问的  
和所有客户的集合  
k
( 123541161) .  
3  
因此 辆车的访问路径  
路径为  
分别为  
c ( c > 0c = 0ij V)  
包含客户集合  
为各客户顶点  
ij  
ij  
ii  
( 123541) ( 11) ( 161) ,  
车辆  
2
D  
间的距离 为车辆最大载重  
k
q ( i( V)  
为各客户的需求  
i
空车  
x  
k
i
j
载重量 表示车辆 服务完客户 以后是否服务客户  
ij  
3. 1. 2  
蝙蝠速度  
k
k
k
( x = 1  
x = 0  
k
) y  
k
i
表示客户 是否被  
为服务  
为不服务  
为被服务  
ij  
ij  
i
i
定义第 个蝙蝠的速度为  
v = ( v v v ) .  
i
i1  
i2  
iw  
k
车辆 务  
( y = 1  
y = 0  
) ,  
为不被服务  
1  
v
≤ ≤  
ij  
ni = 12Qj = 12w.  
i
i
a ,]  
i
a  
i
为客户 的允许开始  
为客户 的时间窗限制  
i
b i  
i
3. 1. 3  
蝙蝠位置 速度和频率的更新操作  
b  
i
s  
i
服务时刻  
为客户 的终止服务时刻 为客户 的开  
i
i
t  
i
在连续域中 时刻第 个蝙蝠的位置和速度分别  
8]  
t
t
t + 1  
t + 1  
VRPTW  
始服务时刻 则  
:
的数学模型 如下  
k
x v t + 1  
x
v
:
时刻蝙蝠的位置  
和速度  
5]  
i
i
i
i
k
{
}
min  
= min  
{
}
f = f  
i
+
(
(
f
f  
)
× f  
( 11)  
( 12)  
( 13)  
F F  
x ,  
c x  
∑∑ 0j ∑∑ ∑ ij ij  
β
min  
max  
min  
1
2
j
V
k
K
k
K
i
V j  
k
V \{ i}  
k
k
t + 1  
t
t
v
= v +  
i
x x  
i
)
i
*
i
( 1)  
t + 1  
t
t + 1  
x
= x + v  
i
i
i
其中  
f f f  
i
其中  
分别表示第 只蝙蝠当前的频率 频率  
i
max  
min  
k
k
x
= y ,  
i
 ∈  
V,  
V,  
k
k
 ∈  
K
( 2)  
( 3)  
( 4)  
( 5)  
( 6)  
( 7)  
ij  
i
;
0
的最大值 频率的最小值 β 是一个随机变量且 β≤  
j
V \{ i}  
k
k
k
1; x  
表示全局最优蝙蝠的位置  
x
= y ,  
j
 ∈  
k
 ∈  
K
*
ij  
j
i
V \{ j}  
k
( 11) ( 13) ,  
离散域中蝙蝠位置 速度和频  
根据式  
率的更新操作  
( 1) x x = v :  
k
q y  
i
D,  
K
 ∈  
i
:
i
V
k
1
k
k
i
设第 个蝙蝠的位置为  
x = ( x ,  
i
*
i
i
i1  
x
=
x
i0  
= 1,  
k
 ∈  
K
0j  
j
N
i
N
x x ) ,  
全局最优的蝙蝠的位置为  
x
= ( x x ,  
1
i2  
iw  
*
* 1  
* 2  
k
y
= 1,  
i
 ∈  
N
1
1
1
1
i
x ) v = ( v v v ) .  
1
x = x v = 0;  
如果  
*
w
i
i1  
i2  
iw  
ij  
*
j
ij  
k
K
k
x
x v = x .  
则 其中  
2
j = 12w.  
如果  
x
1,  
k
 ∈  
K
V
ij  
*
j
ij  
* j  
ij  
k
ij  
V
k
1
( 2) v × f = v :  
i
f ,  
设第 个蝙蝠的频率为 随机生成  
i
i
i
i
a
s
≤ ≤  
i
b ,  
i
 ∈  
N
( 8)  
( 9)  
i
i
2
2
2
2
2
f v = ( v v v ) .  
f f v = 0;  
f
f ,  
如果  
如果  
i
k
r
i
i1  
i2  
iw  
new  
r
i
ij  
r
x
{
01  
},  
ij V,  
k
 ∈  
K
ij  
2
1
f = f + ( f f ) / f = f v = v .  
θ
f f f  
k
其中  
i
i
r
i
i
i
ij  
ij  
min  
i
max  
y
{
01  
},  
i
N,  
k K  
( 10)  
F  
为车辆数 为所有车辆  
 ∈  
 ∈  
i
> 1j = 12w.  
频率因子 θ  
( 3) v + v = v  
( 1)  
F  
表示优化目标函数  
( 2)  
1
2
2
new  
new  
new  
new  
new  
:
v
= ( v v v ) .  
new  
i
i
i
i1  
i1  
i2  
iw  
;
的总行驶距离 式  
i
表示车辆服务完客户 后直接服  
new  
rand( ) < 0. 5v = v ;  
rand( ) 0. 5v  
则  
如果  
ij  
ij  
ij  
j; ( 3)  
j
务客户  
客户  
表示车辆在服务客户 之前只服务一个  
; ( 5)  
表示每辆车不得超过最大载重量 式  
2
= v .  
ij  
j = 12w.  
其中  
i; ( 4)  
new  
new  
new  
new  
new  
new  
( 4) x + v = x  
:
x
= ( x x x ) .  
表示车辆从配送中心出发后服务完客户后必须回到配  
i
i
i
i1  
i1  
i2  
iw  

全部评论(0)

暂无评论

上传资源 上传优质资源有赏金

  • 打赏
  • 30日榜单

推荐下载