Simulated Annealing Technique for Routing in a Rectangular Mesh Network. (22nd December 2014)

• Record Type: Journal Article
• Authors: Adzhar, Noraziah; Salleh, Shaharuddin
• Other Names: Chiu Min-Chie Academic Editor.
• Is Part Of: Modelling and simulation in engineering. Volume 2014(2014)
• Publication Date: 2014-12-22
• Subjects: Engineering -- Simulation methods -- Periodicals; Engineering -- Mathematical models -- Periodicals; 620.004
• DOI: 10.1155/2014/127359
• Languages: English
• ISSNs: 1687-5591

Abstract

Abstract : In the process of automatic design for printed circuit boards (PCBs), the phase following cell placement is routing. On the other hand, routing process is a notoriously difficult problem, and even the simplest routing problem which consists of a set of two-pin nets is known to be NP-complete. In this research, our routing region is first tessellated into a uniformN x × N y array of square cells. The ultimate goal for a routing problem is to achieve complete automatic routing with minimal need for any manual intervention. Therefore, shortest path for all connections needs to be established. While classical Dijkstra's algorithm guarantees to find shortest path for a single net, each routed net will form obstacles for later paths. This will add complexities to route later nets and make its routing longer than the optimal path or sometimes impossible to complete. Today's sequential routing often applies heuristic method to further refine the solution. Through this process, all nets will be rerouted in different order to improve the quality of routing. Because of this, we are motivated to apply simulated annealing, one of the metaheuristic methods to our routing model to produce better candidates of sequence.