混合伊藤算法求解多尺度着色旅行商问题

doi:10.11772/j.issn.1001-9081.2021040776

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (3): 695-700.DOI: 10.11772/j.issn.1001-9081.2021040776

• 2021年中国计算机学会人工智能会议(CCFAI 2021) • 上一篇

混合伊藤算法求解多尺度着色旅行商问题

韩舒宁¹, 徐敏², 董学士¹(), 林青¹, 沈凡凡³

^1.青岛大学计算机科学技术学院, 青岛 266071
^2.长江航道规划设计研究院, 武汉 430040
^3.南京审计大学信息工程学院, 南京 211815

收稿日期:2021-05-13 修回日期:2021-06-19 接受日期:2021-06-22 发布日期:2021-11-09 出版日期:2022-03-10
通讯作者: 董学士
作者简介:韩舒宁（1997—），女，山东青岛人，硕士研究生，主要研究方向：智能交通、智能计算
徐敏（1989—），女，浙江金华人，博士，主要研究方向：航道规划、数据分析
林青（1981—），男，山东泰安人，助理教授，博士，主要研究方向：智能交通、智能感知算法
沈凡凡（1987—），男，湖北荆门人，副教授，博士，主要研究方向：嵌入系统、计算机体系结构。
基金资助:
国家自然科学基金资助项目(61902189);山东省软件工程重点实验室（山东大学）开放基金资助项目(2020SPKLSE0612)

Hybrid ITÖ algorithm for multi-scale colored traveling salesman problem

Shuning HAN¹, Min XU², Xueshi DONG¹(), Qing LIN¹, Fanfan SHEN³

^1.College of Computer Science and Technology，Qingdao University，Qingdao Shandong 266071，China
^2.Changjiang Waterway Institute of Planning and Design，Wuhan Hubei 430040，China
^3.School of Information Engineering，Nanjing Audit University，Nanjing Jiangsu 211815，China

Received:2021-05-13 Revised:2021-06-19 Accepted:2021-06-22 Online:2021-11-09 Published:2022-03-10
Contact: Xueshi DONG
About author:HAN Shuning， born in 1997， M. S. candidate. Her research interests include intelligent transportation， intelligent computing.
XU Min， born in 1989， Ph. D. Her research interests include waterway planning， data analysis.
LIN Qing， born in 1981， Ph. D.， assistant professor. His research interests include intelligent transportation， intelligent perception algorithm.
SHEN Fanfan， born in 1987， Ph. D.， associate professor. His research interests include embedded system， computer architecture.
Supported by:
National Natural Science Foundation of China(61902189);Shandong Provincial Key Laboratory of Software Engineering(2020SPKLSE0612)

摘要/Abstract

摘要：

着色旅行商问题（CTSP）是多旅行商问题（MTSP）与旅行商问题（TSP）的一种扩展，主要应用于含重复区域的多机工程系统（MES）等工程问题。CTSP是NP完全问题，尽管相关研究尝试采用遗传算法（GA）、模拟退火（SA）等方法求解该问题，但它们求解的问题尺度有限，且速度和求解质量上不尽人意。基于此，尝试采用一种基于均匀设计（UD）融合蚁群（ACO）算法和伊藤算法（IT?）的混合伊藤算法（UDHIT?）来求解该问题。UDHIT?采用UD来选择合适的参数组合，借助ACO的概率图模型来产生可行解，并利用伊藤算法的漂移和波动算子进行优化。实验的结果表明，UDHIT?求解多尺度CTSP的最优解和平均解比传统GA、ACO和IT?有所改善。

关键词: 伊藤算法, 着色旅行商问题, 蚁群算法, 漂移算子, 波动算子

Abstract:

Colored Traveling Salesman Problem （CTSP） is a variant of Multiple Traveling Salesmen Problem （MTSP） and Traveling Salesman Problem （TSP）， which can be applied to the engineering problems such as Multi-machine Engineering System （MES） with overlapping workspace. CTSP is an NP complete problem， although related studies have attempted to solve the problem by Genetic Algorithm （SA）， Simulated Annealing （SA） algorithm and some other methods， but they solve the problem at a limited scale and with unsatisfactory speed and solution quality. Therefore， a hybrid IT? algorithm combined with Uniform Design （UD）， Ant Colony Optimization （ACO） and IT? algorithm was proposed to solve this problem， namely UDHIT?. UD was applied to choose the appropriate combination of parameters of the UDHIT? algorithm， the probabilistic graphic model of ACO was used to generate feasible solutions， and the drift operator and volatility operator of IT? were used to optimize the solutions. Experimental results show that the UDHIT? algorithm can demonstrate improvement over the traditional GA， ACO and IT? algorithm for the multi-scale CTSP problems in terms of best solution and average solution.

Key words: IT? algorithm, Colored Traveling Salesman Problem (CTSP), Ant Colony Optimization (ACO), drift operator, volatility operator

中图分类号:

TP18

韩舒宁, 徐敏, 董学士, 林青, 沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 计算机应用, 2022, 42(3): 695-700.

Shuning HAN, Min XU, Xueshi DONG, Qing LIN, Fanfan SHEN. Hybrid ITÖ algorithm for multi-scale colored traveling salesman problem[J]. Journal of Computer Applications, 2022, 42(3): 695-700.

图/表 6

参考文献 19

1	LI J， QIRU S， ZHOU M， et al. A new multiple traveling salesman problem and its genetic algorithm-based solution ［C］// Proceedings of the 2013 IEEE International Conference on Systems Man and Cybernetics. Piscataway： IEEE， 2013： 627-632. 10.1109/smc.2013.112
2	LI J， ZHOU M， SUN Q， et al. Colored traveling salesman problem ［J］. IEEE Transactions on Cybernetics， 2015， 45（11）： 2390-2401. 10.1109/tcyb.2014.2371918
3	MENG X. H， LI J， ZHOU M， et al. Population-based incremental learning algorithm for a serial colored traveling salesman problem ［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2018， 48（2）：277-288. 10.1109/tsmc.2016.2591267
4	DONG W Y， CAI Y L， WANG Y F， et al. Discrete ITÔ algorithm to the coloured travelling salesman problem ［J］. International Journal of Wireless and Mobile Computing， 2016， 11（2）： 157-165. 10.1504/ijwmc.2016.080175
5	董文永，张文生，于瑞国. 求解组合优化问题伊藤算法的收敛性和期望收敛速度分析［J］. 计算机学报， 2011， 34（4）： 636-646. 10.3724/SP.J.1016.2011.00636
	DONG W Y， ZHANG W S， YU R G. Convergence and runtime analysis of ITO algorithm for one class of combinatorial optimization［J］. Chinese Journal of Computers， 2011， 34（4）： 636-646. 10.3724/SP.J.1016.2011.00636
6	董学士，董文永，蔡永乐. 混合算法求解着色瓶颈旅行商问题［J］. 计算机研究与发展， 2018， 55（11）：2372-2385. 10.7544/issn1000-1239.2018.20180009
	DONG X S， DONG W Y， CAI Y L. Hybrid algorithm for colored bottleneck traveling salesman problem ［J］. Journal of Computer Research and Development， 2018， 55（11）：2372-2385. 10.7544/issn1000-1239.2018.20180009
7	董学士，董文永，王豫峰. 混合算法求解多目标平衡旅行商问题［J］. 计算机研究与发展， 2017， 54（8）： 1751-1762. 10.7544/issn1000-1239.2017.20170347
	DONG X S， DONG W Y， WANG Y F. Hybrid algorithms for multi-objective balanced traveling salesman problem［J］. Journal of Computer Research and Development， 2017， 54（8）： 1751-1762. 10.7544/issn1000-1239.2017.20170347
8	张可，凌海峰. 基于均匀设计和混沌理论的蚁群算法参数调整［J］. 计算机工程， 2012， 38（4）：141-143. 10.3969/j.issn.1000-3428.2012.14.042
	ZHANG K， LING H F. Parameter turning of ant colony algorithm based on uniform design and chaos theory［J］. Computer Engineering， 2012， 38（4）：141-143. 10.3969/j.issn.1000-3428.2012.14.042
9	DONG W Y， DONG X S. Parameters selection for genetic algorithms and ant colony algorithms by uniform design ［C］// ICIC 2014： Proceedings of the 10th International Conference on Intelligent Computing. Cham： Springer， 2014： 184-195. 10.1007/978-3-319-09333-8_20
10	DONG X S， DONG W Y， CAI Y L. Ant colony optimization for colored traveling salesman problem by multi-task learning ［J］. IET Intelligent Transport Systems， 2018， 12（8）：774-782. 10.1049/iet-its.2016.0282
11	DONG X S， LIN Q， XU M， et al. Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem ［J］. IET Intelligent Transport Systems， 2019， 13（10）：1483-1491. 10.1049/iet-its.2018.5359
12	DONH X S， CAI Y L. A novel genetic algorithm for large scale colored balanced traveling salesman problem ［J］. Future Generation Computer Systems， 2019， 95：727-742. 10.1016/j.future.2018.12.065
13	DONG X S， ZHONG H， XU M， et al. Hybrid genetic algorithm with variable neighborhood search for multi-scale multiple bottleneck traveling salesmen problem ［J］. Future Generation Computer Systems， 2021，114： 229-242. 10.1016/j.future.2020.07.008
14	MENG X H， LI J， ZHOU M C， et al. Population-based incremental learning algorithm for a serial colored traveling salesman Problem ［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2018， 48（2）：277-288. 10.1109/tsmc.2016.2591267
15	MENG X H， LI J， DAI X Z， et al. Variable neighborhood search for a colored traveling salesman problem ［J］. IEEE Transactions on Intelligent Transportation Systems， 2018， 19（4）：1018-1026. 10.1109/tits.2017.2706720
16	XU X P， LI J， ZHOU M C. Delaunay-triangulation-based variable neighborhood search to solve large-scale general colored traveling salesman problems ［J］. IEEE Transactions on Intelligent Transportation Systems， 2021， 22（3）： 1583-1593. 10.1109/tits.2020.2972389
17	LU F， LI J B， JIANG S，et al. Geographic information and node selfish-based routing algorithm for delay tolerant networks ［J］. Tsinghua Science and Technology， 2017， 22（3）： 243-253. 10.23919/tst.2017.7914197
18	XU D L， LI Y， CHEN X L， et al. A survey of opportunistic offloading ［J］. IEEE Communications Surveys & Tutorials， 2018， 20（3）： 2198-2236. 10.1109/comst.2018.2808242
19	XU D L， LI Y， XIA T， et al. Portfolio optimization in traffic offloading： concept， model， and algorithms ［J］. IEEE Transactions on Mobile Computing， 2021， 20（2）： 691-706. 10.1109/tmc.2019.2946811

组合	m	ρ	α	β	组合	m	ρ	α	β
1	1（30）	8（0.303）	6（2.45）	12（4.19）	9	9（30）	1（0.100）	4（1.87）	10（3.61）
2	2（30）	2（0.129）	12（4.19）	6（2.45）	10	10（30）	7（0.274）	10（3.61）	1（1.00）
3	3（30）	12（0.419）	3（1.58）	2（1.29）	11	11（30）	14（0.477）	5（2.16）	5（2.16）
4	4（30）	15（0.500）	9（3.32）	9（3.32）	12	12（30）	5（0.216）	14（4.77）	11（3.90）
5	5（30）	4（0.187）	8（3.03）	15（5.00）	13	13（30）	10（0.361）	2（1.29）	13（4.48）
6	6（30）	9（0.332）	15（5.00）	4（1.87）	14	14（30）	3（0.158）	7（2.74）	3（1.58）
7	7（30）	6（0.245）	1（1.00）	7（2.74）	15	15（30）	11（0.390）	11（3.90）	8（3.03）
8	8（30）	13（0.448）	13（4.48）	14（4.77）

组合	m	ρ	α	β	组合	m	ρ	α	β
1	1（30）	8（0.303）	6（2.45）	12（4.19）	9	9（30）	1（0.100）	4（1.87）	10（3.61）
2	2（30）	2（0.129）	12（4.19）	6（2.45）	10	10（30）	7（0.274）	10（3.61）	1（1.00）
3	3（30）	12（0.419）	3（1.58）	2（1.29）	11	11（30）	14（0.477）	5（2.16）	5（2.16）
4	4（30）	15（0.500）	9（3.32）	9（3.32）	12	12（30）	5（0.216）	14（4.77）	11（3.90）
5	5（30）	4（0.187）	8（3.03）	15（5.00）	13	13（30）	10（0.361）	2（1.29）	13（4.48）
6	6（30）	9（0.332）	15（5.00）	4（1.87）	14	14（30）	3（0.158）	7（2.74）	3（1.58）
7	7（30）	6（0.245）	1（1.00）	7（2.74）	15	15（30）	11（0.390）	11（3.90）	8（3.03）
8	8（30）	13（0.448）	13（4.48）	14（4.77）

组合	最优解	平均解	组合	最优解	平均解	组合	最优解	平均解	组合	最优解	平均解
1	904.36	957.03	5	897.57	927.28	9	985.53	1 007.59	13	952.10	976.63
2	973.52	1 024.44	6	1 003.77	1 044.64	10	1 214.53	1 282.15	14	1 159.61	1 204.06
3	1 301.53	1 344.14	7	1 078.94	1 108.60	11	1 122.68	1 160.66	15	956.22	981.02
4	973.99	1 003.10	8	851.42	885.18	12	874.25	904.12

组合	最优解	平均解	组合	最优解	平均解	组合	最优解	平均解	组合	最优解	平均解
1	904.36	957.03	5	897.57	927.28	9	985.53	1 007.59	13	952.10	976.63
2	973.52	1 024.44	6	1 003.77	1 044.64	10	1 214.53	1 282.15	14	1 159.61	1 204.06
3	1 301.53	1 344.14	7	1 078.94	1 108.60	11	1 122.68	1 160.66	15	956.22	981.02
4	973.99	1 003.10	8	851.42	885.18	12	874.25	904.12

序号	n	m	GA		GAG		ACO		HCGA
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
1	21	2	149.24	163.39	149.24	163.74	203.21	221.43	145.25	161.89
2	21	3	158.96	170.80	160.62	169.89	213.93	234.76	157.47	173.19
3	31	2	276.33	339.95	294.55	344.58	399.37	458.60	291.40	336.00
4	31	3	321.16	352.96	309.13	348.73	439.85	481.05	318.42	361.12
5	31	4	331.28	357.95	322.49	354.08	465.56	497.43	332.64	362.72
6	41	2	435.64	526.08	445.52	523.70	566.44	618.89	430.90	476.76
7	41	3	518.89	613.61	506.29	611.16	678.57	738.10	502.90	579.95
8	41	4	455.45	531.08	442.60	532.53	626.50	672.08	429.44	515.22
9	51	3	658.04	750.77	641.88	748.83	784.72	828.26	549.60	646.99
序号	n	m	SAGA		DITÖ		HITÖ		UDHITÖ
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
1	21	2	144.91	153.95	144.91	146.40	144.91	147.58	144.91	145.30
2	21	3	157.47	168.74	157.47	158.13	157.47	159.91	157.47	157.76
3	31	2	290.51	320.46	261.20	268.57	267.06	287.47	259.35	262.18
4	31	3	314.49	355.56	295.36	295.36	311.22	331.83	298.96	305.78
5	31	4	324.47	368.98	315.96	319.27	322.19	339.58	316.02	318.84
6	41	2	405.99	458.04	350.01	359.89	375.12	415.41	346.23	354.40
7	41	3	515.04	566.83	439.59	451.25	492.72	522.19	440.20	455.92
8	41	4	471.33	517.85	392.13	402.78	446.42	488.00	392.53	406.09
9	51	3	611.60	645.13	475.89	492.37	551.64	551.64	482.57	494.08

混合伊藤算法求解多尺度着色旅行商问题

Hybrid ITÖ algorithm for multi-scale colored traveling salesman problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 19

相关文章 15

编辑推荐

Metrics

实例尺度	实例序号	城市数量n	旅行者数m	共享城市数s	独享城市数e	实例尺度	实例序号	城市数量n	旅行者数m	共享城市数s	独享城市数e	实例尺度	实例序号	城市数量n	旅行者数m	共享城市数s	独享城市数e
小尺度	1	21	2	11	5	中尺度	10	51	5	21	6	大尺度	19	202	12	82	10
	2	21	3	9	4		11	76	3	31	15		20	202	25	77	5
	3	31	2	19	6		12	76	4	36	10		21	202	35	62	4
	4	31	3	16	5		13	76	5	26	10		22	431	12	191	20
	5	31	4	15	4		14	76	6	40	6		23	431	25	181	10
	6	41	2	21	10		15	101	4	21	20		24	431	40	231	5
	7	41	3	23	6		16	101	5	53	10		25	655	17	145	30
	8	41	4	21	5		17	101	6	41	10		26	655	25	155	20
	9	51	3	21	10		18	101	7	21	10		27	655	33	160	15

[1]	李二超, 齐款款. B样条曲线融合蚁群算法的机器人路径规划[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3558-3564.
[2]	段宇君, 王耀力, 常青, 刘鑫. 改进型蚁群算法融合混沌优化的pSPIEL算法的无线传感器布局优化[J]. 计算机应用, 2020, 40(3): 793-798.
[3]	屈立成, 吕娇, 赵明, 王海飞, 屈艺华. 基于三维时空地图和运动分解的多机器人路径规划算法[J]. 计算机应用, 2020, 40(12): 3499-3507.
[4]	刘育良, 陈淮莉. 负载影响下纯电动汽车配送路径规划及充电策略[J]. 计算机应用, 2020, 40(10): 2831-2837.
[5]	王东先, 孟学雷, 乔俊, 汤霖, 焦志臻. 基于改进蚁群算法的铁路乘务交路计划的编制[J]. 计算机应用, 2019, 39(9): 2749-2756.
[6]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[7]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[8]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[9]	杨继东, 孙兆琦, 王飞龙. 基于视觉抓取的并联桁架机器人最优路径控制[J]. 计算机应用, 2019, 39(3): 913-917.
[10]	王东先, 孟学雷, 何国强, 孙慧萍, 王喜栋. 基于改进蚁群算法的铁路乘务排班计划编制[J]. 计算机应用, 2019, 39(12): 3678-3684.
[11]	魏亚茹, 朱瑾. 自动化码头双场桥调度与集装箱存储选位建模[J]. 计算机应用, 2018, 38(4): 1189-1194.
[12]	王超, 朱明, 王敏. 基于管制员认知负荷和改进蚁群算法的扇区动态通行能力评估[J]. 计算机应用, 2018, 38(1): 277-283.
[13]	许凯波, 鲁海燕, 程毕芸, 黄洋. 求解TSP的改进信息素二次更新与局部优化蚁群算法[J]. 计算机应用, 2017, 37(6): 1686-1691.
[14]	鲍振华, 康宝生, 张雷, 张婧. 基于草图局部几何不变矩的图像检索方法[J]. 计算机应用, 2017, 37(6): 1753-1758.
[15]	梁本来, 杨忠明, 秦勇, 蔡昭权. 引入梯度下降的蚁群算法求解多约束服务质量路由[J]. 计算机应用, 2017, 37(3): 722-729.

序号	n	m	GA		GAG		ACO		HCGA
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
10	51	5	632.13	755.98	668.81	745.91	815.91	851.55	618.05	706.46
11	76	3	1 110.94	1 270.72	1 142.95	1 265.85	1 041.12	1 090.92	819.55	887.84
12	76	4	1 116.36	1 247.91	1 183.99	1 284.90	1 044.16	1 108.55	877.62	989.67
13	76	5	996.16	1 138.75	1 059.34	1 157.45	1 079.40	1 121.59	869.49	941.38
14	76	6	1 195.84	1 325.42	1 174.49	1 299.19	1 128.32	1 200.42	1 040.05	1 139.04
15	101	4	1 399.04	1 520.15	1 389.30	1 518.91	1 237.37	1 301.65	900.20	1 024.24
16	101	5	1 710.71	1 928.83	1 693.95	1 941.83	1 406.26	1 480.74	1 290.99	1 400.73
17	101	6	1 452.68	1 636.56	1 497.94	1 632.01	1 278.51	1 350.34	1 161.92	1 279.23
18	101	7	1 377.01	1 495.14	1 359.04	1 515.02	1 298.23	1 355.49	1 091.81	1 245.45
序号	n	m	SAGA		DITÖ		HITÖ		UDHITÖ
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
10	51	5	629.56	689.08	526.50	538.23	629.75	670.60	533.17	545.44
11	76	3	914.17	964.10	620.87	651.77	889.91	942.33	609.52	626.55
12	76	4	973.91	1 024.87	612.29	659.09	888.45	946.98	621.82	650.93
13	76	5	894.73	956.06	690.08	722.31	935.33	980.40	682.64	710.11
14	76	6	1 073.33	1 134.24	707.34	743.15	975.00	1 030.29	712.77	746.10
15	101	4	1 116.67	1 166.02	866.13	909.27	1 254.75	1 299.01	806.44	847.51
16	101	5	1 416.72	1 509.19	860.83	910.47	1 276.47	1 355.13	846.35	901.99
17	101	6	1 258.79	1 342.65	808.65	861.77	1 192.35	1 247.96	804.83	841.64
18	101	7	1 212.33	1 274.53	903.95	936.46	1 239.09	1 284.76	864.40	890.80

序号	n	m	GA		GAG		ACO		HCGA
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
10	51	5	632.13	755.98	668.81	745.91	815.91	851.55	618.05	706.46
11	76	3	1 110.94	1 270.72	1 142.95	1 265.85	1 041.12	1 090.92	819.55	887.84
12	76	4	1 116.36	1 247.91	1 183.99	1 284.90	1 044.16	1 108.55	877.62	989.67
13	76	5	996.16	1 138.75	1 059.34	1 157.45	1 079.40	1 121.59	869.49	941.38
14	76	6	1 195.84	1 325.42	1 174.49	1 299.19	1 128.32	1 200.42	1 040.05	1 139.04
15	101	4	1 399.04	1 520.15	1 389.30	1 518.91	1 237.37	1 301.65	900.20	1 024.24
16	101	5	1 710.71	1 928.83	1 693.95	1 941.83	1 406.26	1 480.74	1 290.99	1 400.73
17	101	6	1 452.68	1 636.56	1 497.94	1 632.01	1 278.51	1 350.34	1 161.92	1 279.23
18	101	7	1 377.01	1 495.14	1 359.04	1 515.02	1 298.23	1 355.49	1 091.81	1 245.45
序号	n	m	SAGA		DITÖ		HITÖ		UDHITÖ
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
10	51	5	629.56	689.08	526.50	538.23	629.75	670.60	533.17	545.44
11	76	3	914.17	964.10	620.87	651.77	889.91	942.33	609.52	626.55
12	76	4	973.91	1 024.87	612.29	659.09	888.45	946.98	621.82	650.93
13	76	5	894.73	956.06	690.08	722.31	935.33	980.40	682.64	710.11
14	76	6	1 073.33	1 134.24	707.34	743.15	975.00	1 030.29	712.77	746.10
15	101	4	1 116.67	1 166.02	866.13	909.27	1 254.75	1 299.01	806.44	847.51
16	101	5	1 416.72	1 509.19	860.83	910.47	1 276.47	1 355.13	846.35	901.99
17	101	6	1 258.79	1 342.65	808.65	861.77	1 192.35	1 247.96	804.83	841.64
18	101	7	1 212.33	1 274.53	903.95	936.46	1 239.09	1 284.76	864.40	890.80

序号	n	m	GA		GAG		ACO		HCGA
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
19	202	12	137 492.00	148 597.50	137 492.0	148 597.50	95 439.0	99 458.46	92 545.0	99 338.53
20	202	25	141 993.00	150 275.13	138 436.0	149 896.56	115 207.0	118 200.80	117 679.0	123 451.23
21	202	35	141 387.00	149 637.20	143 435.0	150 221.43	132 419.0	135 551.96	129 864.0	135 346.33
22	431	12	1 283 216.00	1 382 433.10	1 215 495.0	1 346 433.53	465 264.0	630 108.10	581 971.0	635 743.76
23	431	25	1 216 263.00	1 362 397.00	1 251 482.0	1 342 393.46	578 535.0	693 119.00	760 573.0	810 081.06
24	431	40	1 614 524.00	1 792 588.63	1 634 642.0	1 773 183.06	632 420.0	942 360.70	1 199 665.0	1 286 575.70
25	655	17	2 059 644.00	2 217 360.23	2 068 484.0	2 219 176.40	777 187.0	1 052 090.43	887 693.0	980 863.33
26	655	25	2 045 475.00	2 220 820.23	2 068 198.0	2 227 858.53	851 011.0	1 074 822.56	1 039 623.0	1 117 060.00
27	655	33	2 118 182.00	2 218 765.40	2 156 266.0	2 252 611.16	949 871.0	1 121 713.86	1 164 960.0	1 251 597.70
序号	n	m	SAGA		DITÖ		HITÖ		UDHITÖ
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
19	202	12	88 840.0	94 439.06	69 553.0	71 389.70	95 891.0	98 010.73	67 192.0	69 648.80
20	202	25	113 539.0	118 793.10	98 549.0	99 827.50	115 187.0	117 659.33	97 429.0	98 106.03
21	202	35	129 993.0	134 275.73	118 172.0	118 998.60	130 577.0	132 743.20	116 411.0	117 297.93
22	431	12	551 168.0	593 980.53	320 362.0	332 958.23	570 604.0	596 072.33	306 913.0	317 210.76
23	431	25	727 746.0	780 897.36	454 436.0	464 472.76	677 847.0	694 612.90	441 835.0	450 776.86
24	431	40	1 116 394.0	1 248 226.60	479 748.0	496 253.73	799 127.0	826 919.83	473 250.0	482 892.60
25	655	17	889 811.0	952 891.43	633 018.0	651 474.80	1 118 257.0	1 141 971.16	580 345.0	588 648.63
26	655	25	1 007 375.0	1 055 211.93	727 219.0	734 617.10	1 103 409.0	1 117 786.13	675 453.0	684 856.66
27	655	33	1 160 764.0	1 218 103.56	813 794.0	826 738.40	1 179 552.0	1 205 980.70	772 757.0	781 393.30

序号	n	m	GA		GAG		ACO		HCGA
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
19	202	12	137 492.00	148 597.50	137 492.0	148 597.50	95 439.0	99 458.46	92 545.0	99 338.53
20	202	25	141 993.00	150 275.13	138 436.0	149 896.56	115 207.0	118 200.80	117 679.0	123 451.23
21	202	35	141 387.00	149 637.20	143 435.0	150 221.43	132 419.0	135 551.96	129 864.0	135 346.33
22	431	12	1 283 216.00	1 382 433.10	1 215 495.0	1 346 433.53	465 264.0	630 108.10	581 971.0	635 743.76
23	431	25	1 216 263.00	1 362 397.00	1 251 482.0	1 342 393.46	578 535.0	693 119.00	760 573.0	810 081.06
24	431	40	1 614 524.00	1 792 588.63	1 634 642.0	1 773 183.06	632 420.0	942 360.70	1 199 665.0	1 286 575.70
25	655	17	2 059 644.00	2 217 360.23	2 068 484.0	2 219 176.40	777 187.0	1 052 090.43	887 693.0	980 863.33
26	655	25	2 045 475.00	2 220 820.23	2 068 198.0	2 227 858.53	851 011.0	1 074 822.56	1 039 623.0	1 117 060.00
27	655	33	2 118 182.00	2 218 765.40	2 156 266.0	2 252 611.16	949 871.0	1 121 713.86	1 164 960.0	1 251 597.70
序号	n	m	SAGA		DITÖ		HITÖ		UDHITÖ
序号	n	m	最优解	平均解	最优解	平均解	最优解	平均解	最优解	平均解
19	202	12	88 840.0	94 439.06	69 553.0	71 389.70	95 891.0	98 010.73	67 192.0	69 648.80
20	202	25	113 539.0	118 793.10	98 549.0	99 827.50	115 187.0	117 659.33	97 429.0	98 106.03
21	202	35	129 993.0	134 275.73	118 172.0	118 998.60	130 577.0	132 743.20	116 411.0	117 297.93
22	431	12	551 168.0	593 980.53	320 362.0	332 958.23	570 604.0	596 072.33	306 913.0	317 210.76
23	431	25	727 746.0	780 897.36	454 436.0	464 472.76	677 847.0	694 612.90	441 835.0	450 776.86
24	431	40	1 116 394.0	1 248 226.60	479 748.0	496 253.73	799 127.0	826 919.83	473 250.0	482 892.60
25	655	17	889 811.0	952 891.43	633 018.0	651 474.80	1 118 257.0	1 141 971.16	580 345.0	588 648.63
26	655	25	1 007 375.0	1 055 211.93	727 219.0	734 617.10	1 103 409.0	1 117 786.13	675 453.0	684 856.66
27	655	33	1 160 764.0	1 218 103.56	813 794.0	826 738.40	1 179 552.0	1 205 980.70	772 757.0	781 393.30