The　obstacle-avoiding　rectilinear　Steiner　minimal　tree　(OARSMT)　problem　is　a　fundamental　problem　in　very　large-scale　integrated　circuit　physical　design　and　can　be　reduced　to　the　Steiner　tree　problem　in　graphs　(GSTP),　which　can　be　solved　by　using　three　types　of　common　methods:　classic　heuristics,　local　search　algorithms,　or　computational　intelligence　algorithms.　However,　classic　heuristics　have　poor　solution　qualities;　local　search　algorithms　easily　fall　into　the　problem　of　the　local　optimum;　and　the　searching　effects　of　the　existing　computational　intelligence　algorithms　are　poor　for　this　problem.　In　order　to　improve　the　solution　quality,　we　propose　a　novel　discrete　artificial　bee　colony　algorithm　for　constructing　an　obstacle-avoiding　rectilinear　Steiner　tree.　We　first　generate　the　escape　graph　for　the　OARSMT　problem.　Then,　we　search　for　a　near-optimal　solution　consisting　of　some　edges　of　escape　graph　by　using　the　discrete　ABC　algorithm.　We　apply　a　key-node　neighborhood　configuration　for　the　local　search　strategy　and　introduce　two　local　search　operators.　We　then　naturally　use　a　key-node-based　encoding　scheme　for　representing　the　feasible　solution　and　obtain　a　tight　searching　scope.　We　employ　a　modified　classic　heuristic　as　the　encoder　that　can　produce　a　feasible　solution.　Experiments　conducted　on　both　general　GSTP　and　very　large-scale　integrated　circuit　instances　reveal　the　superior　performance　of　the　proposed　method　in　terms　of　the　solution　quality　among　the　state-of-the-art　algorithms.　©　2014,　The　Natural　Computing　Applications　Forum.