多级规约算法在PCB钻孔路径优化中的应用

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (16): 212-215.

多级规约算法在PCB钻孔路径优化中的应用

程森林，曾伟

重庆大学自动化学院，重庆 400044

出版日期:2012-06-01 发布日期:2012-06-01

Application of multilevel reduction algorithm to PCB path optimization

CHENG Senlin, ZENG Wei

College of Automation, Chongqing University, Chongqing 400044, China

Online:2012-06-01 Published:2012-06-01

摘要/Abstract

摘要： 以求解PCB（Printed Circuit Board）钻孔路径优化这一大规模复杂的TSP（Traveling Salesman Problem）问题为背景，研究了一种改进的多级规约算法（EMR）。该算法依据工程应用中实用性、通用性的特点重新设计了多级规约算法（MR）的规约和细化算子并增加了控制参数以提高算法的灵活性；针对算法中会产生大量部分解集且难以储存这一问题，设计了一种类似人类族谱的数据结构。实验结果以及与循环LK算法和蚁群算法的对比分析表明，EMR算法兼顾了实用性和通用性，且有较高的优化质量和优化效率。

关键词: 旅行商问题TSP, 印制线路板PCB, 多级归约算法, 路径优化

Abstract: The PCB（Printed Circuit Board） path optimization is a large-scale TSP（Traveling Salesman Problem） problem. An Enhanced Multilevel Reduction algorithm（EMR） is proposed to solve this problem. The proposed algorithm redesigns the reduction operator and brings a control parameter to improve its flexibility. Meanwhile, in view of the difficulties of saving the results produced by reduction operator, a new data structure like human family tree is presented. Experimental results, compared with the other method, demonstrate that EMR outperforms in practicability and generality with higher quality and efficiency of optimization.

Key words: Traveling Salesman Problem（TSP）, Printed Circuit Board（PCB）, multilevel reduction algorithm, path optimization

程森林，曾伟. 多级规约算法在PCB钻孔路径优化中的应用[J]. 计算机工程与应用, 2012, 48(16): 212-215.

CHENG Senlin, ZENG Wei. Application of multilevel reduction algorithm to PCB path optimization[J]. Computer Engineering and Applications, 2012, 48(16): 212-215.

[1]	王嘉月，史立. 考虑电池损耗的电动冷藏车路径及充电策略[J]. 计算机工程与应用, 2021, 57(24): 283-289.
[2]	胡小兵，陈树念，张盈斐，谷升豪. 求解多目标路径优化问题的涟漪扩散算法[J]. 计算机工程与应用, 2021, 57(23): 81-90.
[3]	熊兴隆，刘佳，李猛，马愈昭. 基于无人机-配送车联合配送的优化算法研究[J]. 计算机工程与应用, 2021, 57(19): 259-266.
[4]	魏念巍，姜媛媛，刘延彬，辛元芳，洪炎. 关键节点和平滑处理的PRM路径优化方法[J]. 计算机工程与应用, 2020, 56(16): 118-123.
[5]	彭露，陈淮莉. 改进遗传算法下的无水港集货路径优化研究[J]. 计算机工程与应用, 2020, 56(14): 250-256.
[6]	蒋丽，王静，梁昌勇，赵树平. 基于改进蚁群算法的众包配送路径研究[J]. 计算机工程与应用, 2019, 55(8): 244-249.
[7]	姚坤，杨斌，朱小林. 考虑时变交通状况的低碳车辆路径优化[J]. 计算机工程与应用, 2019, 55(3): 231-237.
[8]	姚书婷，胡志华，魏晨. 多禁止时间窗约束的路径恢复问题研究[J]. 计算机工程与应用, 2019, 55(12): 265-270.
[9]	邓烨，朱万红，王凤山，刘华丽. 应急物流车辆调度多目标鲁棒优化研究[J]. 计算机工程与应用, 2019, 55(1): 248-255.
[10]	王转，裴泽平. 启发式路径下节约里程的订单分批算法[J]. 计算机工程与应用, 2018, 54(23): 203-209.
[11]	汤旻安1，2，谷宝慧1. 改进PSO在AGV系统路径优化调度中的应用研究[J]. 计算机工程与应用, 2016, 52(3): 261-265.
[12]	姜海洋，周宽久，林林，郝佳亮，郭铖. 战时运输风险评估模型及其路径优化研究[J]. 计算机工程与应用, 2016, 52(17): 235-242.
[13]	陈海松，贺伟雄，楼增龙，彭永飞. 应急条件下边防地区路径优化算法研究[J]. 计算机工程与应用, 2016, 52(1): 33-36.
[14]	蒋国清1，潘勇2，胡飞跃1. 两阶段式的物流配送路径优化方法[J]. 计算机工程与应用, 2015, 51(2): 255-258.
[15]	李雪竹. 基于免疫萤火虫算法的RFID仓储车辆动态调度[J]. 计算机工程与应用, 2014, 50(6): 235-239.