Some embodiments of the invention provide a method of routing several nets in a region of a design layout. Each net includes a set of pins in the region. In some embodiments, the method partitions the region into several sub-regions that have a number of edges between them. The method (1) for each particular edge, identifies an edge-intersect cost based on a set of potential routes for the nets that intersect the particular edge, and (2) selects routes for the nets based on the computed edge-intersect costs. A potential route for a particular net traverses the set of sub-regions that contain the particular net's set of pins. Also, different embodiments identify different edge-intersect costs. For instance, the edge-intersect cost of a particular edge (1) can be the number of routes that intersect the particular edge, (2) can be a edge-intersect probability that equals the number of routes that intersect the particular edge divided by the total number of routes, or (3) can be a cost derived from the edge-intersect probability. Other embodiments might define other edge-intersect costs. In other embodiments, the method partitions the region into several sub-regions that have a number of paths between them. The method next (1) for each particular path, identifies a path-use cost based on a set of potential routes for the nets that use the particular path, and (2) selects a route for each net based on the computed path-use costs. Different embodiments identify different path-use costs. For instance, the path-use cost of a particular path (1) can be the number of routes that use the particular path, (2) can be a path-use probability that equals the number of routes that use the particular path divided by the total number of routes, or (3) can be a cost derived from the path-use probability. Other embodiments might define other path-use costs.