Premium
Exact and approximate algorithms for optimal network design
Author(s) -
Dionne R.,
Florian M.
Publication year - 1979
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230090104
Subject(s) - heuristics , mathematical optimization , heuristic , computer science , algorithm , constraint (computer aided design) , branch and bound , mathematics , geometry
ABSTRACT In this paper, we present exact and approximate algorithms for the problem of optimal network design, which was first studied by Ridley [15], Stairs [17] and Scott [16], among others. Given a network, the problem consists in selecting a subset of links that minimizes the sum of shortest routes between all nodes subject to a budget constraint. Congestion effects are not considered. First, we refine a branch‐and‐bound algorithm proposed by Hoang [7] and we compare the resuling algorithm to an algorithm developed by Boyce et al. [1]. Our conclusion is that these exact algorithms perform adequately on medium size problems; however, for larger problems, approximate methods based on heuristic approaches are necessary. We then introduce two new heuristic approaches and test their computational efficiency as well as that of two other already known heuristics. The new heuristics presented produce excellent results. Finally, we consider more general versions of the problem.