Enhanced simulated annealing technique for the single-row routing problem
This paper presents ESSR (Enhanced Simulated annealing for Single-row Routing) model for solving the single-row routing problem. The main objective in this problem is to produce a realization that minimizes both the street congestion and the number of doglegs. Simulated annealing (SA) is a stochasti...
| المؤلفون الرئيسيون: | , , , , |
|---|---|
| التنسيق: | مقال |
| اللغة: | English |
| منشور في: |
Springer Netherlands
2002
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://eprints.utm.my/88/1/Langkah_Input_Sampel_ArtikelJurnal.pdf |
| _version_ | 1825908864995819520 |
|---|---|
| author | Salleh, Shaharuddin Sanugi, Bahrom Jamaluddin, Hishamuddin Olariu, Stephan Zomaya, Albert Y. |
| author_facet | Salleh, Shaharuddin Sanugi, Bahrom Jamaluddin, Hishamuddin Olariu, Stephan Zomaya, Albert Y. |
| author_sort | Salleh, Shaharuddin |
| collection | ePrints |
| description | This paper presents ESSR (Enhanced Simulated annealing for Single-row Routing) model for solving the single-row routing problem. The main objective in this problem is to produce a realization that minimizes both the street congestion and the number of doglegs. Simulated annealing (SA) is a stochastic, hill-climbing and gradient-descent technique based on the statistical properties of particles undergoing thermal annealing. By performing slow cooling, the nets in the single-row routing problem align themselves according to a configuration with the lowest energy. The model has been known to produce reasonably good solutions for many NP-complete optimization problems, such as the single-row
routing problem. In ESSR, our strategy is to minimize both the street congestion and the number of interstreet crossings (doglegs) by expressing a single energy function as their collective properties. This objective is achieved by representing the energy as the absolute sum of the heights of the net segments. To speed up convergence, we pivot the street congestion value while having the energy drops directly proportional to the number of doglegs. This action has the effect of minimizing the number of doglegs as the energy stabilizes. Our simulation work on ESSR produces optimal results in most cases for both the street congestion and the number of doglegs. Our experimental results compare well against results obtained from our earlier model (SRR-7) and two other methods reported in the literature.
|
| first_indexed | 2024-03-05T17:53:40Z |
| format | Article |
| id | utm.eprints-88 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2024-03-05T17:53:40Z |
| publishDate | 2002 |
| publisher | Springer Netherlands |
| record_format | dspace |
| spelling | utm.eprints-882010-06-01T02:40:09Z http://eprints.utm.my/88/ Enhanced simulated annealing technique for the single-row routing problem Salleh, Shaharuddin Sanugi, Bahrom Jamaluddin, Hishamuddin Olariu, Stephan Zomaya, Albert Y. QA75 Electronic computers. Computer science QA Mathematics This paper presents ESSR (Enhanced Simulated annealing for Single-row Routing) model for solving the single-row routing problem. The main objective in this problem is to produce a realization that minimizes both the street congestion and the number of doglegs. Simulated annealing (SA) is a stochastic, hill-climbing and gradient-descent technique based on the statistical properties of particles undergoing thermal annealing. By performing slow cooling, the nets in the single-row routing problem align themselves according to a configuration with the lowest energy. The model has been known to produce reasonably good solutions for many NP-complete optimization problems, such as the single-row routing problem. In ESSR, our strategy is to minimize both the street congestion and the number of interstreet crossings (doglegs) by expressing a single energy function as their collective properties. This objective is achieved by representing the energy as the absolute sum of the heights of the net segments. To speed up convergence, we pivot the street congestion value while having the energy drops directly proportional to the number of doglegs. This action has the effect of minimizing the number of doglegs as the energy stabilizes. Our simulation work on ESSR produces optimal results in most cases for both the street congestion and the number of doglegs. Our experimental results compare well against results obtained from our earlier model (SRR-7) and two other methods reported in the literature. Springer Netherlands 2002-03 Article PeerReviewed application/pdf en http://eprints.utm.my/88/1/Langkah_Input_Sampel_ArtikelJurnal.pdf Salleh, Shaharuddin and Sanugi, Bahrom and Jamaluddin, Hishamuddin and Olariu, Stephan and Zomaya, Albert Y. (2002) Enhanced simulated annealing technique for the single-row routing problem. Journal of Supercomputing, 21 (3). pp. 285-302. ISSN 1573-0484 http://dx.doi.org/10.1023/A:1014160411818 doi : 10.1023/A:1014160411818 |
| spellingShingle | QA75 Electronic computers. Computer science QA Mathematics Salleh, Shaharuddin Sanugi, Bahrom Jamaluddin, Hishamuddin Olariu, Stephan Zomaya, Albert Y. Enhanced simulated annealing technique for the single-row routing problem |
| title | Enhanced simulated annealing technique for the single-row routing problem |
| title_full | Enhanced simulated annealing technique for the single-row routing problem |
| title_fullStr | Enhanced simulated annealing technique for the single-row routing problem |
| title_full_unstemmed | Enhanced simulated annealing technique for the single-row routing problem |
| title_short | Enhanced simulated annealing technique for the single-row routing problem |
| title_sort | enhanced simulated annealing technique for the single row routing problem |
| topic | QA75 Electronic computers. Computer science QA Mathematics |
| url | http://eprints.utm.my/88/1/Langkah_Input_Sampel_ArtikelJurnal.pdf |
| work_keys_str_mv | AT sallehshaharuddin enhancedsimulatedannealingtechniqueforthesinglerowroutingproblem AT sanugibahrom enhancedsimulatedannealingtechniqueforthesinglerowroutingproblem AT jamaluddinhishamuddin enhancedsimulatedannealingtechniqueforthesinglerowroutingproblem AT olariustephan enhancedsimulatedannealingtechniqueforthesinglerowroutingproblem AT zomayaalberty enhancedsimulatedannealingtechniqueforthesinglerowroutingproblem |