推荐星级：
- 1
- 2
- 3
- 4
- 5
带时间窗的车辆路径问题的离散蝙蝠算法
资料介绍
本文提出了一种离散蝙蝠算法求解带时间窗的车辆路径问题(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 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
相关下载
- 华为模块电源管理设计指导-(V100R001_02 Chi...
- 华为LGA模块PCB设计指导_V2.0_20150126.pdf
- HUAWEI Module USB Interface Descriptor Gui...
- HUAWEI ME909s-821 LTE LGA模块硬件指南V100R...
- HUAWEI ME909s-821 LTE LGA Module Acceptanc...
- HUAWEI 30 mm x 30 mm LGA Module Hardware M...
- HUAWEI 30 mm x 30 mm LGA Module Developmen...
- Altium_Designer_规则设置三例.pdf
- STM32F407产品技术培训-DSP库及其例程
- STM32F407产品技术培训-2.浮点单元.pdf
全部评论(0)