求解多旅行商问题的改进分组遗传算法

被引：37

作者：

王勇臻

陈燕

于莹莹

机构：

[1] 大连海事大学交通运输管理学院

来源：

电子与信息学报 | 2017年 / 39卷 / 01期

关键词：

分组遗传算法; 多旅行商问题; 编码; 2-opt算法;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

该文针对总路径长度最小的多旅行商问题,提出一种改进分组遗传算法。在该算法中,设计了一种有序分组编码,采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间,根据编码的特点构造了一种快速交叉算子。同时,结合贪婪算法和2-opt算法设计了一种新的局部搜索算子,以提高算法的收敛精度。实验结果分析表明,所提算法能够有效地解决多旅行商问题,具有可靠的全局收敛性,较高的计算效率。

引用

页码：198 / 205

页数：8

共 14 条

[1]

A general variable neighborhood search heuristic for multiple traveling salesmen problem.[J].Banu Soylu.Computers & Industrial Engineering.2015,

[2]

Area Allocation Algorithm for Multiple UAVs Area Coverage Based on Clustering and Graph Method.[J].Sungjun Ann;Youdan Kim;Jaemyung Ahn.IFAC PapersOnLine.2015, 9

[3]

Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem.[J].András Király;Maria Christidou;Tibor Chován;Evangelos Karlopoulos;János Abonyi.Journal of Cleaner Production.2016,

[4] Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming [J].

Kota, L. ;

Jarmai, K. .

APPLIED MATHEMATICAL MODELLING, 2015, 39 (12) :3410-3433

[5] Grouping evolution strategies: An effective approach for grouping problems [J].

Kashan, Ali Husseinzadeh ;

Akbari, Ali Akbar ;

Ostadi, Bakhtiar .

APPLIED MATHEMATICAL MODELLING, 2015, 39 (09) :2703-2720

[6] A modified Intelligent Water Drops algorithm and its application to optimization problems [J].

Alijla, Basem O. ;

Wong, Li-Pei ;

Lim, Chee Peng ;

Khader, Ahmed Tajudin ;

Al-Betar, Mohammed Azmi .

EXPERT SYSTEMS WITH APPLICATIONS, 2014, 41 (15) :6555-6569

[7] An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem [J].

Wang, Sheng-yao ;

Wang, Ling ;

Liu, Min ;

Xu, Ye .

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2013, 145 (01) :387-396

[8] A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms [J].

Yuan, Shuai ;

Skinner, Bradley ;

Huang, Shoudong ;

Liu, Dikai .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 228 (01) :72-82

[9] A new grouping genetic algorithm approach to the multiple traveling salesperson problem [J].

Singh, Alok ;

Baghel, Anurag Singh .

SOFT COMPUTING, 2009, 13 (01) :95-101

[10]

The multiple traveling salesman problem: an overview of formulations and solution procedures.[J].Tolga Bektas.Omega.2004, 3

← 1 2 →