Ordered escape routing combining heuristic algorithm and improved integer linear programming
Escape routing is an important part in printed circuit board routing.As the number of pins increases and the scale of pin array expands,the ordered escape routing becomes more and more complex.To solve the problem that the time and quality of ordered escape routing cannot be balanced simultaneously,an ordered escape routing scheme combining heuristic algorithm and improved integer linear programming was proposed.The scheme consisted of two stages:initial solution construction,rip-up and reroute.In the first stage,the longest common subsequence was used to determine the initial wiring sequence of escape pins.Then,the heuristic algorithm of piece-wise cost prediction function is used to pre-route most pins in a short time,and finally to optimize and adjust the circuit.In the second stage,the subgraph range was determined first,then the improved integer linear programming expression was given,and the rip-up and rerouting was carried out based on the initial routing,to improve the routing rate and achieve local optimization.Finally,the shortest path algorithm was used to rip-up and reroute to further enhance the overall routing rate.Experimental results showed that the proposed routing scheme could obtain the optimal or ap-proximate optimal results in a short time,and the CPU time was reduced by 35.57％on average compared with the previous integer linear programming.
heuristic algorithmsinteger linear programmingordered escape routingrip-up and rerouteshortest path
万方数据
维普
