第
32
击得
!S
2
期
20J5
年
3
月
深圳大学学
1111)1
[1
J
版
\ 0
1.
32
刊门
2
JOURNAL
0
1<'
SHENZ
fH~N
UNIVEHSITY
SCTENCE
AND
ENGJNEEHJNG
Ma
r.
20J5
{电子与信息科学/
Electronics
and
Information
Science
1
车辆路径问题的快速多邻域迭代局部搜索算法
刘万峰
1
，
2
李霞
J
.2
1
)深圳大学信息!程学院，深圳
I
518060;
2)
深圳市现代通信与信息处理珉，点实验室，深圳
518060
摘
要:对于容量约束的车辆路径问题(
c.:
apacÜaled
vehi
e:
k
rouling
prohle
Jl
I ,
CVRP)
以及容量和最大行
驶距离约束的车辆问题
(capacitated
and
distance
c:
onstrained
vehi
c:l
e
routing
problem
,
CDVRP)
，邻域解的评
估包含了适应值计算及合法性评估.设计一种可变长编码的可行解表示，提出用于
CVRP/CDVRP
问题的邻
域解合法性快速评估策略.该策略针对交换、插入、
2-opt
和
2-opt
午四种常用的局部搜索算子，通过引入前
载重、后载重、前向距离和后向距离的概念，实现了邻域解合法性的快速坪估.将改进后的局部搜索算子
与迭代局部搜索
(iterated
lo
c:
al
sear
c:
h ,
ILS)
算法相结合，提出用于车辆路径问题的快速多邻域迭代局部搜
索
(fast
multi-neighborhood
ILS ,
FMNILS)
算法.该快速评估策略将评估一个邻域解的时间复杂度由。(
N)
降至
0
(1)
，
算法仿真结果表明，
FMNILS
算法运算能力的提高大致与配送路线所服务的客户数成正比;对
客户数介于
200
-
500
的容量/最大距离约束
VRP
问题，该算法能在短时间内获得较满意解，平均求解精度
1.
2%
以内，平均耗时约
96
s
，仅为对比算法的
6%
或更少.
关键词:人工智能;启发式算法;车辆路径问题;多邻域;迭代局部技索;可变长编码
中图分类号
TP
391
文献标志码
A
doi:
10.
3724/SP.
J.
1249.2015.02196
A fast multi-neighborhood iterated local search
algorithm for vehicle routing problem
Liu
Wanfeng
J
, 2
and
Li Xia
1
, 2.[
1 )
College
of
Information Engineering , Shenzhen University , Shenzhen 518060 ,
P.
R.
China
2)
Shenzhen
Key
Lab
of
Communication and Information Processing , Shenzhen 518060 ,
P.
R. China
Abstract:
For
c:
apa
c:
itated
vehi
c:l
e
routing
problems
withou
t/
with
maximum
traveling
distan
c:
e
c:
onstraint
(CVRP/
CDVRP)
,
the
evaluation
of
neighborhood
solutions
involves
fitness
c:
a
lc:
ulation
and
feasibility
assessmen
t.
This
paper
proposes
a fast feasibility
assessment
strategy
in
which
variable
length
c:
oding
is
used
to
represent
feasible
solutions
of
vehi
c:l
e
routing
problem.
We
introdu
c:
e
the
c:
on
c:
epts
of
pre-load
,
post-Ioad
,
pre-distan
c:
e
and
post-distan
c:
e to
obtain
fast
feasibility
assessments
for
neighborhood
solutions
achieved
by four
widely
used
lo
c:
al
sear
c:
h
operations
(insert
,
exchange
,
2-
opt
,
and
2-
opt
'"
).
By
c:
ombining
the
improved
local
sear
c:
h
operations
and
iterated
lo
c:
al
search
(ILS)
,
we
propose
a fast
multi-neighborhood
iterated
local
search
(FMNILS)
for
CVRP.
The
feasibility
assessment
strategy
can
reduce
c:
omputational
complexity
of
the
neighborhood
solution
assessment
from 0
(N)
to 0 ( 1
).
Experimental
results
show
that
the
improvement
in
speed
is
approximately
linearly
prop
Ol
tional
to
the
average
c:
ustomer
numher
in
a
?出
;z;2
也
2;
…乒二
1
飞
!t
立汇
UU::LμU;
二斗
:JJi
I
L
丘
m:1:??
阿陀
s
胆吃吧飞
et
含
LE:
(υJC
口
201
门
10
仍
51η70
侃
61
口
3A)
目哥旨
E
配宦罩
;l
E
[
Cωor
盯
r
臼呻
po
佣
nd
仙
i
讪
ng
口
au
毗
t
仙
ho
眨
r:
Pr
巾
S
旧
S
阳旧
Or
Li
Xia.
E-n
→
-ma
出
ail
让
1:
lixia@s
阳
zu.e
旺叫巾【
dL
巾
lu.cn
暨贾穹古暨圄责暨
R
暨量缸
C
口
i
阳
tion:
Liu
Wanfe
吨，
Li
Xia.
A
fast
ll1
ulii-neighhorhood
iterated
local
…h
algorilhlll
for
whiclc
1υ
l1
ling
prohl
C'11l
~
JJ.
Jou
l'
nal
~望国幅
of
Shcnzhen
Uni
飞
er"it)
Science
and
Engineeling
,
2015
咱
32(2):
196-204.
(il1
Ch
川附、)
阻
J!'~
后词回自
剩余8页未读，继续阅读
资源评论
weixin_38622467
- 粉丝: 4
最新资源
- 库文件libz.a
- 可编辑LIN数据库的免费软件-LDFtool软件
- 库文件libz.a
- 可编辑LIN数据库的免费软件-LDFtool软件
- 2018_5_30基于Python的美食聚集点的可视化分析研究.zip
- Python 基于 Selenium 爬取招聘岗位信息的基础程序
- Microsoft.CompactFramework.CSharp.targets 文件下载
- Microsoft.CompactFramework.CSharp.targets 文件下载
- A cdn detector with high speed! 基于Python 多线程+多协程实现高并发查询API接口进行多地Ping Host来确认IP的真实归属。.zip
- 一个经典贪吃蛇游戏，Python编写，基于树莓派b+和ssd1306 128x64 OLED屏幕
- 基于C++_Python的用于调整Windows系统分辨率的小程序
- A python nacos sdk client based on the official openapi(一个基于Nacos官方API的python客户端实现，支持同步和异步).zip
- PDR (Pedestrian Dead Reckoning)行人航位推算实现代码（matlab）
- A Eye基于python、open-cv、pywin32等类库 主要用于搭建eve手游预警机系统，支持多模拟器，支持监测多星系，支持发送游戏指定频道预警、微信预警.zip
- A rpc framework base on grpc for python,一个基于grpc的python快速开发框架.zip
- Analysis of Holland's Occupational Personality. （基于Python的霍兰德职业性格测试分析WebApp）.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
