魏志刚 毛   东 张家铭（中国建筑西北设计研究院有限公司，西安市 710018）

Application of TSP Problem Solving in Electrical Design Process

WEI Zhigang MAO Dong ZHANG Jiaming

(China Northwest Architectual Design and Research Institute Co.,Ltd.,Xi’an 710018，China)

Abstract：By introducing the characteristics of solving the traveling salesman problem(TSP)as well as the principles and calculation methods of using heuristic algorithms such as the nearest neighbor algorithm,crossover algorithm,roundabout algorithm and optimization algorithm,high‑quality TSP problem solving thinking is proposed and the computer function of automatic optimal routing generation on the AutoCAD platform based on AutoLISP programming technology is realized,which improves the design efficiency of engineering and technical personnel.

Key words：TSP problem;optimal path;AuotCAD;Autolisp programming;nearest‑neighbor algorithm;automatic wiring;cross paths;roundabout path

摘　要：通过介绍求解旅行商问题(TSP)的特点,论述采用启发式算法中的最近邻点算法、交叉迂回优化算法的原理和计算方法，提出TSP问题高质量求解的思路，并实现基于AutoLISP编程开发技术在AutoCAD平台上计算机自动生成最优布线功能，可提高工程技术人员的设计效率。

关键词：TSP问题；最优路径；AuotCAD；AutoLISP编程；最近邻点算法；自动布线；交叉路径；迂回路径

中图分类号：TU201.4             　  文献标识码：A

doi：10.3969 / j. issn.1003 － 8493.2024.06.008