多约束条件车辆路径问题的二阶段遗传退火算法 (2005年)
需积分: 0 184 浏览量
2021-05-17
16:57:41
上传
评论
收藏 267KB PDF 举报
第
39
卷第
12
期
西安交通大学学报
Vo
l.
39
NQ12
2005
年
12
月
JOURNAL
OF
XI'
AN
JIAOTONG
UNIVERSITY
Oec. 2005
多约束条件车辆路径问题的二阶段遗传退火算法
17
o
军，冯博琴，李波
(西安交通大学电子与信息工程学院.
710049.
西安)
摘要:针对多约束条件的多配送中心有时间窗车辆路径问题，提出了一种二阶段遗传退火算法.在第
1
阶
段，使用遗传算法对客户按供应量和路径长度进行模糊分区;在第
2
阶段，采用二维变长染色体编码及相应
的遗传算子进行混合遗传算法的全局优化.在初始种群生成和交叉、变异算子中采用了随机贪心算法以避免
无效解，并利用退火选择未提高种群的多样性.实验结果表明，二阶段遗传退火算法可加速收敛，提高搜索效
率，在模糊分区上的搜索速度较之标准遗传算法提高了
3~10
倍.
关键词:车辆路径;遗传退火算法;贪心算法
中图分类号
TP18;
U
1l
6
文献标识码
A
文章编号:
0253-987X(2005)
12-1299-04
Tw
o-
Phase Genetic-Annealing Algorithm for Vehicle Routing
Problem with Multiple Constraints
Lü
]
un
,
Feng
Boq
巾
，
Li
Bo
CSchool
of
Electronics
and
Information
Engineering.
Xi'an
]iaotong
University.
Xi'an
710049.
China)
Abstract:
A novel
two-phase
geneti
c-
annealing
algorithm
is
proposed
to
solve
the
vehicle
routing
problem
with
time
window
CMOVRPTW)
and
multi-constraint
in
multiple
dispatching
centers.
In
the
first
phase
,
users
are
partitioned
into
fuzzy
regions
according
to
quantity
supplied
and
the
length
of
paths
using
genetic
algorithm;
in
the
second
phase
the
global
optimization
is
carried
out
by
the
hybrid
genetic
algorithm
with
20
variable-length
chromosomes
and
corresponding
genetic
operators.
The
random
greedy
algorithm
is
used
in
generating
of
initial
population
and
crossover
and
mutation
operator
to
avoid invalid
solution
,
then
the
simulated
annealing
algorithm
is
employed
to
enhance
the
diversity
of
population.
The
experimental
re-
sults
show
that
compared
with
the
traditional
genetic
algorithm
the
search
speed
of
the
proposed
algorithm
is
3~10
times
fastcr
,
the
convergence is
speed
up
,
and
search
efficiency is increased.
Keywords: vehicle
routing;
geneti
c-
annealing
algorithm;
greedyalgorithm
车辆路径问题
C
Vehicle
Routing
Problem
,
VRP)
是→类经典的
NP
难问题旧，目标函数通常为
车辆数和运输成本最小化.随着约束条件的不同，
VRP
演化出许多模型，如非对称
VRPCAVRP)
、带
时间窗的
VRPCVRPTW)
及多配送中心的
VRP
CMOVRP)
等，而现实环境中的问题往往是以上模
型的混合.
VRP
的求解算法主要有精确算法和启发式算
法对大规模的
VRP
问题，启发式算法能在较短的
时间内获得满意的近似最优解，这种算法主要指构
造型算法、改进型算法、导向邻域搜索算法
t
叫，也有
许多研究是这些算法的某种混合算法.
对于复杂约束
VRP
问题的遗传算法，其简单
的编码必然损失解的大量信息，所以需要设计合适
的编码方案.另外，由于约束的增加，会造成整个搜
索空间不连续，使邻域搜索更加困难.一般的遗传算
子易导致大量的解因违背约束条件而成为元效解，
必须针对问题的特殊性设计相关的交叉、变异算子.
收稿日期:
2005-04-08.
作者简介:吕
军Cl
968~)
.男，在职博士生，高工;冯博琴(联系人)
.男，教授，博士生导师.
基金项目:国家高技术研究发展计划资助项目
(2003AAOO
1 048).
资源评论
