Survey of Metaheuristics for Steiner Trees, Wire-LengthDriven Routing, and Constrained Spanning TreeProblems in VLSI*

Routing in Very Large-Scale Integration (VLSI) is a challenging task that involves managing interconnect length, congestion, power consumption, and timing. With the rapid growth of semiconductor technology, traditional algorithms like Integer Linear Programming (ILP) and dynamic programming often become too slow and impractical for large-scale circuits. Overcome this, metaheuristic algorithms such as Genetic Algorithms (GA), Simulated Annealing (SA), Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO) offer effective solutions. These algorithms are particularly useful for NP-hard problems like Steiner tree construction and wire-length optimization, striking a balance between accuracy and computational effort. This paper provides a comprehensive overview of metaheuristic applications in VLSI routing, analyzing their strengths, limitations, and real-world performance. It also highlights emerging trends like AI-powered optimization and hybrid algorithms. By offering valuable insights, this survey serves as a helpful resource for researchers and engineers navigating the complexities of modern VLSI design.