基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题

被引：52

作者：

王超 ^{[1
,2
,3
]}

刘超 ^{[1
,3
]}

穆东 ^{[4
]}

高扬 ^{[1
,3
]}

机构：

[1] 北京工业大学经济与管理学院

[2] 波士顿大学物理系

[3] 北京现代制造业发展研究基地

[4] 北京交通大学经济与管理学院

来源：

计算机集成制造系统 | 2018年 / 24卷 / 03期

基金：

中国博士后科学基金;

关键词：

车辆路径问题; 同时取送货; 时间窗; 布谷鸟算法;

D O I：

10.13196/j.cims.2018.03.004

中图分类号：

F252 [物资流通]; TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

为求解带时间窗和同时取送货的车辆路径问题(VRPSPDTW),提出一种离散布谷鸟(DCS)算法,该算法在标准布谷鸟算法的基础上,在Lévy飞行位置更新过程中,使用路径内搜索2-opt法和路径间搜索swap/shift法改进当前巢穴;在寄生巢位置更新过程中,使用路径内搜索relocate/exchange法和路径间搜索GENE法,随机产生新巢穴。选取Wang和Chen测试数据集,对算法性能进行测试,并与遗传算法和并行模拟退火算法进行比较。测试结果显示,在9个中小型顾客规模算例中,DCS算法获取了所有的当前国际最优解,在56个大型顾客规模的算例中,DCS算法在5个算例中更新了当前国际最优解,在17个算例中获取了当前国际最优解。通过Rank值法对这3种算法进行Friedman检验和Wilcoxon秩检验,结果表明所提DCS算法的有效性。

引用

页码：570 / 582

页数：13

共 20 条

[1] 基于并行模拟退火算法求解时间依赖型车辆路径问题 [J].

穆东 ;

王超 ;

王胜春 ;

周圣川 .

计算机集成制造系统, 2015, 21 (06) :1626-1636

[2] 基于模拟退火算法求解VRPSPDTW问题 [J].

王超 ;

穆东 .

系统仿真学报, 2014, 26 (11) :2618-2623

[3] 基于CS算法的Markov模型及收敛性分析 [J].

王凡 ;

贺兴时 ;

王燕 ;

杨松铭 .

计算机工程, 2012, 38 (11) :180-182+185

[4]

易逝品逆向物流的库存控制及车辆路径问题的优化研究[D]. 孟丽君.浙江大学 2009

[5]

The vehicle routing problem: State of the art classification and review[J] . Kris Braekers,Katrien Ramaekers,Inneke Van Nieuwenhuyse.Computers ＆ Industrial Engineering . 2015

[6]

Enhanced Intelligent Water Drops and Cuckoo Search Algorithms for Solving the Capacitated Vehicle Routing Problem[J] . Ehsan Teymourian,Vahid Kayvanfar,GH.M. Komaki,M. Zandieh.Information Sciences . 2015

[7]

A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows[J] . Chao Wang,Dong Mu,Fu Zhao,John W. Sutherland.Computers ＆ Industrial Engineering . 2015

[8]

Nature-Inspired Optimization Algorithms[J] . Xin-She Yang.Nature-Inspired Optimization Algorithms . 2014

[9]

A cooperative population learning algorithm for vehicle routing problem with time windows[J] . Dariusz Barbucha.Neurocomputing . 2014

[10] Discrete cuckoo search algorithm for the travelling salesman problem [J].

Aziz Ouaarab ;

Belaïd Ahiod ;

Xin-She Yang .

Neural Computing and Applications, 2014, 24 :1659-1669

← 1 2 →