Global　routing　is　a　critical　step　in　VLSI　physical　design.　This　paper　proposes　a　novel　pathfinding　model　based　on　integer　linear　programming　for　VLSI　global　routing.　The　Lagrangian　relaxation　method　combined　with　a　direction-aware　weighted　A∗-algorithm　is　developed　to　quickly　solve　the　model　to　obtain　a　better　initial　routing　solution,　which　is　further　optimized　by　a　designed　multi-stage　rip-up　&　rerouting　algorithm.　In　each　stage　of　rip-up　&　rerouting,　different　routing　algorithms　and　cost　functions　are　used　to　optimize　the　overflow　and　wire　length.　SPRoute　and　CUGR　are　two　state-of-the-art　global　routers.　Our　proposed　global　routing　algorithm　outperforms　SPRoute　1.0　&　2.0　in　both　the　wire　length　and　the　number　of　vias　on　the　ISPD08　benchmarks.　On　the　ISPD18　benchmarks,　compared　to　CUGR,　our　algorithm　has　about　5.1%　reduction　in　the　number　of　vias,　and　the　average　runtime　is　4.89×　speedup;　compared　to　SPRoute　2.0,　our　algorithm　has　about　1.7%　reduction　on　the　average　wire　length,　and　the　number　of　vias　is　comparable.　©　2023　IEEE.