Heuristic ranking and selection procedures for network design problems

Two heuristic approaches to solving discrete non‐linear network design problems and other subset selection problems are described and tested. These heuristics operate similarly to other add, delete and interchange heuristics that have been applied to network design problems. However, the selection criterion adopted here is the ratio of objective function change per unit of resource cost, which other authors have described as an effective gradient measure for zero‐one integer programming problems. Optimal branch‐and‐bound algorithms previously developed and tested are reviewed, and those results serve as benchmarks with which to compare these heuristics described in this paper. The first heuristic ranks and deletes alternative network modifications from an entire set of candidate projects, such as new links or link improvements, until the subset of remaining projects fits within the constraint space. This method was found to achieve optimal or near‐optimal solutions to each of the test cases, even when the number of candidate projects deleted in each iteration was increased from one to many. The quality of those results led us to investigate a constrained random sampling procedure in which candidate projects are ranked with regard to randomly generated networks, and a solution is then chosen on the basis of these rankings. This second approach was found to achieve solutions that were almost as good as those obtained with the rank and delete heuristic.