{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T13:14:15Z","timestamp":1775740455495,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"name":"Beijing Natural Science Foundation","award":["Z230002"],"award-info":[{"award-number":["Z230002"]}]},{"name":"CIE-Smartchip research fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>\n                    Ordered escape routing (OER), which seeks the routing paths from some signal pins to the boundary of a pin array in a given order, is an important research topic for PCB design. Although reinforcement learning based methods for OER have been proposed, the routing capacity between two adjacent pins is assumed to be just one. In this work, we propose MCMC-Escape, a Monte-Carlo tree search (MCTS) based multi-capacity ordered escape router, which includes, in turn, the initial solving approach, the improved Monte-Carlo tree search (improved MCTS) process, and the last routing attempt approach based on wires removing and re-routing. In the improved MCTS, the prior knowledge based pruning strategies and the fine-tuning strategy are proposed to enhance the efficiency of solving multi-capacity OER (MC-OER) problems, while the weight adjusting strategy is proposed to address the path occupancy issues arising from multiple capacity. Experimental results demonstrate that MCMC-Escape can effectively solve large-scale MC-OER problems and outperform existing methods in terms of routing success rate, runtime and wire length. For a set of problems with 50\u00d750 pin array, MCMC-Escape achieves 4X higher success rate of routing with 50% less solving time than MCMCF-Router [\n                    <jats:xref ref-type=\"bibr\">1<\/jats:xref>\n                    ], while reducing the average total wire length.\n                  <\/jats:p>","DOI":"10.1145\/3795522","type":"journal-article","created":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T20:37:37Z","timestamp":1769891857000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["MCMC-Escape: Multi-Capacity Ordered Escape Routing Based on Monte-Carlo Tree Search"],"prefix":"10.1145","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-9497-6852","authenticated-orcid":false,"given":"Jianxuan","family":"Yu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Technology, BNRist, Tsinghua University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-7569-7025","authenticated-orcid":false,"given":"Zhenyi","family":"Gao","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, BNRist, Tsinghua University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-8786-3313","authenticated-orcid":false,"given":"Sheqin","family":"Dong","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, BNRist, Tsinghua University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-5855-6728","authenticated-orcid":false,"given":"Zuochang","family":"Ye","sequence":"additional","affiliation":[{"name":"School of Integrated Circuits, BNRist, Tsinghua University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4897-7251","authenticated-orcid":false,"given":"Wenjian","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, BNRist, Tsinghua University","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,9]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3695253"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3569052.3578917"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394885.3431568"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2020.2985312"},{"key":"e_1_3_1_6_2","first-page":"6\u2013pp","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC)","author":"Tomioka Yoichi","year":"2006","unstructured":"Yoichi Tomioka and Atsushi Takahashi. 2006. Monotonic parallel and orthogonal routing for single-layer ball grid array packages. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). 6\u2013pp."},{"key":"e_1_3_1_7_2","first-page":"606","volume-title":"Proceedings of the Design Automation Conference (DAC)","author":"Fang Jia-Wei","year":"2007","unstructured":"Jia-Wei Fang, Chin-Hsiung Hsu, and Yao-Wen Chang. 2007. An integer linear programming based routing algorithm for flip-chip design. In Proceedings of the Design Automation Conference (DAC). 606\u2013611."},{"key":"e_1_3_1_8_2","first-page":"244","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC)","author":"Luo Lijuan","year":"2008","unstructured":"Lijuan Luo and Martin DF Wong. 2008. Ordered escape routing based on Boolean satisfiability. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). 244\u2013249."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2009.4796545"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1785481.1785579"},{"key":"e_1_3_1_11_2","first-page":"384","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC)","author":"Jiao Fengxian","year":"2016","unstructured":"Fengxian Jiao and Sheqin Dong. 2016. Ordered escape routing for grid pin array based on min-cost multi-commodity flow. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC). 384\u2013389."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3386263.3406942"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD57390.2023.10323718"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISQED57927.2023.10129354"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature16961"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature24270"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"e_1_3_1_18_2","unstructured":"Gurobi Optimization LLC. 2024. Gurobi Optimizer Reference Manual. (2024). Retrieved from https:\/\/www.gurobi.com"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3566097.3567901"},{"key":"e_1_3_1_20_2","unstructured":"2024. MCMCF-Router (V1.0). (2024). Retrieved from https:\/\/numbda.cs.tsinghua.edu.cn\/download_en.html"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3795522","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T11:56:46Z","timestamp":1775735806000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3795522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,9]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1145\/3795522"],"URL":"https:\/\/doi.org\/10.1145\/3795522","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,9]]},"assertion":[{"value":"2025-03-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}