An Edge Replacement Heuristic Algorithm for Length-Restricted Steiner Minimum Tree Problem

The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has attracted considerable research attention due to its significance in physical design of very large scale integrated (VLSI) circuits. In practical VLSI design, the obstacles often occupy some of the layers, and wires may pass through some obstacles by routing on higher layers. Therefore, the new demands bring about the length-restricted Steiner minimum tree (LRSMT) problem. The original rectilinear Steiner minimum tree (RSMT) problem does not involve obstacles and has been proven to be NP-complete. The LRSMT extends RSMT by incorporating obstacle constraints, which dramatically increases its computational complexity. This paper proposes an edge replacement heuristic algorithm (ERH) for the LRSMT problem. First, we generate initial solutions based on FLUTE or Delauney triangulation, and apply a fast greedy obstacle-avoiding method to connect vertices. Then, a refinement procedure is performed on the initial solutions to detect and eliminate the local detour structures and redundant Steiner points quickly. Finally, an edge replacement procedure is proposed to optimize the structure at the macro level by replacing circuitous routes with shorter ones. Experimental results show that ERH algorithm shows a significant advantage over the existing algorithms by obtaining superior results in all values of \((\mathcal{L})\), which is the longest length restriction of the connected component inside an obstacle. Besides, the ERH without edge replacement can generate initial solutions with competitive quality compared with the existing algorithms in a short time.