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

王勇臻; 陈燕; 于莹莹

doi:10.11999/JEIT160211

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

doi: 10.11999/JEIT160211

基金项目:

国家科技支撑计划(2014BAH24F04)，国家自然科学基金(71271034)

计量
- 文章访问数: 2613
- HTML全文浏览量: 384
- PDF下载量: 601
- 被引次数: 0
出版历程
- 收稿日期: 2016-03-07
- 修回日期: 2016-07-22
- 刊出日期: 2017-01-19

Improved Grouping Genetic Algorithm for Solving Multiple Traveling Salesman Problem

Funds:

The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2014BAH24F04), The National Natural Science Foundation of China (71271034)

摘要

摘要: 该文针对总路径长度最小的多旅行商问题，提出一种改进分组遗传算法。在该算法中，设计了一种有序分组编码，采用新编码方式的个体与多旅行商问题有效解之间具有一一对应的关系。为了减少算法的运行时间，根据编码的特点构造了一种快速交叉算子。同时，结合贪婪算法和2-opt算法设计了一种新的局部搜索算子，以提高算法的收敛精度。实验结果分析表明，所提算法能够有效地解决多旅行商问题，具有可靠的全局收敛性，较高的计算效率。
- 分组遗传算法 /
- 多旅行商问题 /
- 编码 /
- 2-opt算法
Abstract: In order to solve the total-path-shortest Multiple Traveling Salesman Problem (MTSP), an improved grouping genetic algorithm is proposed. This algorithm employs a new encoding scheme called ordered grouping encoding, which makes the adjusted individuals corresponding one by one to valid solutions of MTSP. According to the features of the encoding scheme, a fast crossover operator is constructed for the sake of reducing the running time of the algorithm. For enhancing its local search ability, the algorithm combines the greedy algorithm and the 2-opt algorithm to design a new local search operator. The comparison of results shows that the proposed algorithm can solve MTSP effectively and has an excellent search performance no matter in computing efficiency or convergence precision.
- Grouping Genetic Algorithm (GGA) /
- Multiple Traveling Salesman Problem (MTSP) /
- Encoding /
- 2-opt algorithm

HTML全文

参考文献(23)

SOYLU B. A general variable neighborhood search heuristic for multiple traveling salesmen problem[J]. Computers Industrial Engineering, 2015, 90(11): 390-401. doi: 10.1016/j.cie.2015.10.010.

KOTA L and JARMAI K. Mathematical modeling of multiple tour multiple traveling salesman problem using evolutionary programming[J]. Applied Mathematical Modelling, 2015, 39(12): 3410-3433. doi: 10.1016/j.apm. 2014.11.043.

谢秉磊, 李颖, 刘敏. 带临时补充点的融雪剂撒布车辆路径问题[J]. 系统工程理论与实践, 2014, 34(6): 1593-1598. doi: 10.12011/1000-6788(2014)6-1593.

XIE Binglei, LI Ying, and LIU Min. Vehicle routing problem with temporary supplementary points for spreading deicing salt[J]. Systems Engineering-Theory Pratice, 2014, 34(6): 1593-1598. doi: 10.12011/1000-6788(2014)6-1593.

刘明, 张培勇. 求解多旅行商问题的新混合遗传算法: 以应急物资配送为例[J]. 系统管理学报, 2014, 23(2): 247-254.

LIU Ming and ZHANG Peiyong. New hybrid genetic algorithm for solving the multiple traveling salesman problem: An example of distribution of emergence materials[J]. Journal of System Management, 2014, 23(2): 247-254.

ANN S, KIM Y, and AHN J. Area allocation algorithm for multiple UAVs area coverage based on clustering and graph method[J]. IFAC-PapersOnLine, 2015, 48(9): 204-209. doi: 10.1016/j.ifacol.2015.08.084.

KIRALY A, CHRISTIDOU M, CHOVAN T, et al. Minimization of off-grade production in multi-site multi-product plants by solving multiple traveling salesman problem[J]. Journal of Cleaner Production, 2016, 111: 253-261. doi: 10.1016/j.jclepro.2015.05.036.

KASHAN A H, AKBARI A A, and OSTADI B. Grouping evolution strategies: an effective approach for grouping problems[J]. Applied Mathematical Modelling, 2015, 39(9): 2703-2720. doi: 10.1016/j.apm.2014.11.001.

BEKTAS T. The multiple traveling salesman problem: An overview of formulations and solution procedures[J]. Omega, 2006, 34(3): 209-219. doi: 10.1016/j.omega.2004.10.004.

SINGH A and BAGHEL A S. A new grouping genetic algorithm approach to the multiple traveling salesperson problem[J]. Soft Computing, 2009, 13(1): 95-101. doi: 10.1007/s00500-008-0312-1.

YUAN S, SKINNER B, HUANG S, et al. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms[J]. European Journal of Operational Research, 2013, 228(1): 72-82. doi: 10.1016/j.ejor.2013.01.043.

LIU W, LI S, ZHAO F, et al. An ant colony optimization algorithm for the multiple traveling salesmen problem[C]. Proceedings of IEEE Conference on Industrial Electronics and Applications, ICIEA, Xian, China, 2009: 1533-1537. doi: 10.1109/ ICIEA.2009.5138451.

NECULA R, BREABAN M, and RASCHIP M. Performance Evaluation of Ant Colony Systems for the Single-depot Multiple Traveling Salesman Problem[M]. Springer International Publishing, 2015: 257-268. doi: 10.1007/ 978-3-319-19644-2_22.

XUE M, WANG T, and MAO S. Double evolutsional artificial bee colony algorithm for multiple traveling salesman problem[C]. Preoeedings of MATEC Web of Conferences, EDP Sciences, 2016: 44. doi: 10.1051/ matecconf/20164402025.

VENKATESH P and SINGH A. Two metaheuristic approaches for the multiple traveling salesperson problem[J]. Applied Soft Computing, 2015, 26: 74-89. doi: 10.1016/ j.asoc.2014.09.029.

韩丽霞, 王宇平, 兰绍江. 基于有序划分编码的图着色算法[J]. 电子学报, 2010, 38(1): 146-150.

HAN Lixia, WANG Yuping, and LAN Shaojiang. Graph coloring algorithm based on ordered partition encoding[J]. Acta Electronica Sinica, 2010, 38(1): 146-150.

HELSGAUN K. General k-opt submoves for the LinKernighan TSP heuristic[J]. Mathematical Programming Computation, 2009, 1(2/3): 119-163. doi: 10.1007/s12532- 009-0004-6.

ALIJLA B O, WONG L P, LIM C P, et al. A modified intelligent water drops algorithm and its application to optimization problems[J]. Expert Systems with Applications, 2014, 41: 6555-6569. doi: 10.1016/j.eswa.2014.05.010.

WANG S, WANG L, LIU M, et al. An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem[J]. International Journal of Production Economics, 2013, 145(1): 387-396. doi: 10.1016/j.ijpe.2013.05.004.

王军强, 郭银洲, 崔福东, 等. 基于多样性增强的自适应遗传算法的开放式车间调度优化[J]. 计算机集成制造系统, 2014, 20(10): 2479-2493. doi: 10.13196/j.cims201410016.

WANG Junqiang, GUO Yinzhou, CUI Fudong, et al. Diversity enhancement-based adaptive genetic algorithm for open-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2014, 20(10): 2479-2493. doi: 10.13196/j.cims201410016.

施引文献

资源附件(0)

访问统计