求解多旅行商問題的改進(jìn)分組遺傳算法

王勇臻; 陳燕; 于瑩瑩

doi:10.11999/JEIT160211

求解多旅行商問題的改進(jìn)分組遺傳算法

doi: 10.11999/JEIT160211 cstr: 32379.14.JEIT160211

基金項(xiàng)目:

國(guó)家科技支撐計(jì)劃(2014BAH24F04)，國(guó)家自然科學(xué)基金(71271034)

計(jì)量
- 文章訪問數(shù): 2756
- HTML全文瀏覽量: 415
- PDF下載量: 606
- 被引次數(shù): 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)

摘要

摘要: 該文針對(duì)總路徑長(zhǎng)度最小的多旅行商問題，提出一種改進(jìn)分組遺傳算法。在該算法中，設(shè)計(jì)了一種有序分組編碼，采用新編碼方式的個(gè)體與多旅行商問題有效解之間具有一一對(duì)應(yīng)的關(guān)系。為了減少算法的運(yùn)行時(shí)間，根據(jù)編碼的特點(diǎn)構(gòu)造了一種快速交叉算子。同時(shí)，結(jié)合貪婪算法和2-opt算法設(shè)計(jì)了一種新的局部搜索算子，以提高算法的收斂精度。實(shí)驗(yàn)結(jié)果分析表明，所提算法能夠有效地解決多旅行商問題，具有可靠的全局收斂性，較高的計(jì)算效率。
- 分組遺傳算法 /
- 多旅行商問題 /
- 編碼 /
- 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全文

參考文獻(xiàn)(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.

謝秉磊, 李穎, 劉敏. 帶臨時(shí)補(bǔ)充點(diǎn)的融雪劑撒布車輛路徑問題[J]. 系統(tǒng)工程理論與實(shí)踐, 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.

劉明, 張培勇. 求解多旅行商問題的新混合遺傳算法: 以應(yīng)急物資配送為例[J]. 系統(tǒng)管理學(xué)報(bào), 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]. 電子學(xué)報(bào), 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.

王軍強(qiáng), 郭銀洲, 崔福東, 等. 基于多樣性增強(qiáng)的自適應(yīng)遺傳算法的開放式車間調(diào)度優(yōu)化[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)