基于混合NSGA-Ⅱ的有硬时间窗的多目标车辆路径问题

被引：7

作者：

吴天羿 ^{[1
]}

刘建永 ^{[1
]}

许继恒 ^{[1
]}

翁杰 ^{[2
]}

昝良 ^{[1
]}

机构：

[1] 解放军理工大学

[2] 南京军区工程环境质量监督站

来源：

交通运输系统工程与信息 | 2014年 / 14卷 / 02期

关键词：

物流工程; NSGA-Ⅱ; 多目标; 车辆路径问题; 硬时间窗; 时差插入法;

D O I：

10.16097/j.cnki.1009-6744.2014.02.030

中图分类号：

U116.2 [运输线路优选];

学科分类号：

摘要：

针对有硬时间窗的多目标车辆路径问题,本文采取交叉、变异和精英保留相结合的选择策略,分别以配送总时间、调用车辆数和配送总费用为决策目标,设计了混合NSGA-Ⅱ.首先,为提高初始种群的优越性,引入了时差插入法;其次,以继承父代的优秀基因、加快种群的寻优速度为目的,提出了新颖交叉算子并设计了新颖交叉运算;再次,通过子路径变异运算以增加种群的多样性;最后,构造了基于密度的Pareto排序以保证种群分布的均匀性.本文不仅描述了算法的详细步骤,而且通过实验就收敛代数、目标函数和仿真结果进行了比较与分析.结果表明,混合NSGA-Ⅱ较之基本算法有着更快的收敛速度和更好的收敛效果.

引用

页码：176 / 183

页数：8

共 13 条

[1] 求解带时间窗取送货问题的遗传算法 [J].

潘立军 ;

符卓 .

系统工程理论与实践, 2012, 32 (01) :120-126

[2] NSGA-II中一种改进的分布性保持策略 [J].

文诗华 ;

郑金华 .

计算机工程与应用 , 2010, (33) :49-53

[3] 带时间窗的车辆路径混合遗传算法 [J].

宋厚冰 ;

蔡远利 .

交通运输工程学报, 2003, (04) :112-115

[4] 有时间窗车辆路径问题的改进遗传算法 [J].

张丽萍 ;

柴跃廷 ;

曹瑞 .

计算机集成制造系统-CIMS, 2002, (06) :451-454

[5] 有时间窗的非满载车辆调度问题的遗传算法 [J].

谢秉磊 ;

李军 ;

郭耀煌 .

系统工程学报, 2000, (03) :290-294

[6] A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows [J].

Vidal, Thibaut ;

Crainic, Teodor Gabriel ;

Gendreau, Michel ;

Prins, Christian .

COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (01) :475-489

[7]

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows.[J].G.B. Alvarenga;G.R. Mateus;G. de Tomi.Computers and Operations Research.2005, 6

[8] Evolutionary algorithms for the vehicle routing problem with time windows [J].

Bräysy, O ;

Dullaert, W ;

Gendreau, M .

JOURNAL OF HEURISTICS, 2004, 10 (06) :587-611

[9]

A parallel hybrid genetic algorithm for the vehicle routing problem with time windows.[J].Jean Berger;Mohamed Barkaoui.Computers and Operations Research.2003, 12

[10]

Artificial intelligence heuristics in solving vehicle routing problems with time window constraints.[J].K.C. Tan;L.H. Lee;K. Ou.Engineering Applications of Artificial Intelligence.2002, 6

← 1 2 →