<p>The obstacle-avoiding rectilinear Steiner minimum tree problem is a computationally fundamental and challenging problem 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 motivate 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 Delaunay 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal {L}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">L</mi> </math></EquationSource> </InlineEquation>, which is the longest length restriction of the connected component inside an obstacle. The algorithm’s capability to efficiently optimize routing for circuits involving thousands of terminals and obstacles aligns it with the performance and scalability objectives central to high-performance computing applications.</p>