积分商城

最新搜索： 可靠性设计 pl5501 stm32cube 万用表 DP3001 基于单片机的太阳能热水器控制器(附相关论文）
您现在的位置是：首页 > 技术资料 > 带时间窗的车辆路径问题的离散蝙蝠算法
推荐星级：
  • 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

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
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 Automation，Guangdong University of Technology，Guangzhou，Guangdong 510006，China;  
2. Department of Health Science and Technology，Aalborg University，Aalborg 9220，Denmark)  
Abstract: This paper presents a discrete bat algorithm to solve the vehicle routing problem with time window  
( VRPTW) ． The proposed algorithm defines position，velocity，updated operation of the position，updated operation of the ve-  
locity and updated operation of the frequency，and uses a method which combines the penal function with vectorial compari-  
son to deal with constrained conditions． The proposed algorithm adopts random inserted strategy，inserted research strategy  
for the vehicle with minimum customers，ordinary inserted research strategy，exchanged research strategy and 2-Opt strategy  
with time window to expand the search space and enhance the convergent rate． Experimental results show that，the proposed  
algorithm has a stronger optimization capability，higher robustness and less time consumption，key parameter values and strat-  
egies used in this paper can improve performances of the proposed algorithm，and according to the hypotheses testing，there  
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 Window，VRPTW)  
Routing Problem，VRP) ［1］  
( Vehicle  
是车辆路径问题  
VRPTW  
，
算例中求解能力参差不齐  
算法在不同类型的  
．
的经典问题之一 经过多年的  
，
时间耗费较多 收敛效率也较低  
．
，
VRPTW  
研究 学者们应用启发式算法求解  
［2］ VRPTW  
取得一定的  
的离散粒子群算  
( Bat Algorithm，BA)  
Yang X S  
2010  
蝙蝠算法  
是
在
．
效果 文献  
提出一种求解  
年提出的一种元启发式算法［5］ 近年来 学者们把蝙蝠  
．
，
;
法 文 献  
［3］  
提 出 一 种 混 合 混 沌 粒 子 群 算 法 解 决  
算法应用到物流运输调度领域并取得了一定的研究成  
: 2016-09-30;  
: 2016-12-21;  
:
收稿日期  
修回日期  
责任编辑 覃怀银  
广 东 省 自 然 科 学 基 金  
( No． 2012B050600028，No． 2014B010118004，No． 2016A050502060) ;  
:
( No． 61074147 ) ;  
( No． S2011010005059 ) ;  
( No．  
广 东 省 教 育 部 产 学 研 结 合 项 目  
基金项目 国 家 自 然 科 学 基 金  
2012B091000171，No． 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  
参数定义与操作设计  
，
此 本文提出了一种离散蝙蝠算法  
rithm，DBA) VRPTW，  
蝙蝠位置  
+
求解  
拓展了蝙蝠算法在物流运输  
Q
N
， n，  
为蝙蝠种群规模 顶点数为 车辆数为  
，
、
设
∈
调度领域的应用 具有一定的创新性 实际意义和较好  
．
的推广价值 实验结果表明  
: DBA  
m，  
维数  
w = n + m － 2.  
i
定义第 个蝙蝠的位置为  
x =  
i
具有较强的寻优能  
、
、
;
( x ，x ，…，x ) ，i = 1，2，…，Q，  
其中  
x
( 1，2，…，w)  
力 较高的鲁棒性 较少的时间耗费 所采用的关键参数  
是
i1  
i2  
iw  
i
DBA  
;
值和策略能提高  
DBA  
的性能 通过假设检验证明了  
．
的一个置换  
蝙蝠位置按照规则与  
: x = 1 x ＞ n  
．
与对比算法之间的算法性能均有显著性差异  
VRPTW  
路径形成一一对应  
“1”;  
关系  
和
均认为是配送中心  
蝙蝠位置  
; 2  
ij  
ij  
2
数学模型  
“1”， VRPTW  
的前后分别加上 构成一条完整的  
路径  
K = { 1，2，…，m}  
，N =  
为配送中心车辆的集合  
令
“1”  
．
之间经过的客户点构成一台车辆的访问路径 例  
个
{ 2，…，n}  
，V = { 1，N}  
为配送中  
为配送中心的客户集合  
: n = 6，m = 3，w = 7，x = ( 2，3，5，4，7，1，6) ，  
如
其对应的  
i
(
心 定义为  
“1”)  
． V  
k
为车辆 访问的  
和所有客户的集合  
k
( 1，2，3，5，4，1，1，6，1) ．  
，3  
因此 辆车的访问路径  
路径为  
分别为  
，c ( c ＞ 0，c = 0，i，j V)  
∈
包含客户集合  
为各客户顶点  
ij  
ij  
ii  
( 1，2，3，5，4，1) 、( 1，1) 、( 1，6，1) ，  
车辆  
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  
n，i = 1，2，…，Q，j = 1，2，…，w．  
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 = 1，2，…，w．  
如果  
≠
x
－ 1，  
k
 ∈  
K
≤
V
ij  
*
j
ij  
* j  
∑
ij  
k
i，j  
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
{
0，1  
}，  
i，j 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
{
0，1  
}，  
i
N，  
k K  
( 10)  
，F  
为车辆数 为所有车辆  
∈
 ∈  
 ∈  
i
＞ 1，j = 1，2，…，w．  
频率因子 θ  
( 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. 5， v = v ;  
rand( ) 0. 5， v  
≥ 则  
果
则
如果  
ij  
ij  
ij  
j; ( 3)  
j
务客户  
客户  
式
表示车辆在服务客户 之前只服务一个  
; ( 5)  
表示每辆车不得超过最大载重量 式  
2
= v ．  
ij  
，j = 1，2，…，w．  
其中  
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日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号