Networks synthesis and optimum network design problems: Models, solution methods and applications

TLDR

Network synthesis and optimum network design, originating in telecommunication studies in the 1960s, have expanded to encompass transportation, computer, energy, and water distribution systems, yet most applications can be described by a limited set of core models. This survey aims to classify the field so readers can identify the fundamental structure of their problem and link it to existing literature. The paper is organized around three core models—minimum‑cost multicommodity flows, tree‑like networks, and non‑simultaneous single or multicommodity flows—surveying their variants, application contexts, and the most efficient computational methods.

Abstract

Abstract This paper is intended as a survey in the area of network synthesis and optimum network design, which, in view of the importance and variety of the underlying applications, has attraced, since the early 1960s, much interest in the Operations Research community. Indeed, if the first models were studied in connection with telecommunication networks, the range of applications kept on getting broader and broader, including transportation networks, computer and teleprocessing networks, energy transport systems, water distribution networks, etc. However, beyond the apparent diversity of practical situations involved, most of these applications can be accounted for (modulo possibly a few minor adaptations), by a rather limited number of basic models. One of the main purposes of this paper is to provide the reader with a relevant classification of the area which will help him identify the fundamental structure of the problem (if any) he has to cope with, and relate it to already published work. In order to obtain a fairly good coverage of the matter, we have thus been led to identify three basic models aroung which the whole paper is organized: a general model using minimum cost multicommodity flows (Section 2); models in terms of tree‐like networks (Section 3); models using nonsmultaneous single‐commodity or multicommodity flows (Section 4). In each bcase the most important variants of the basic models have been surveyed with the purpose of providing as much information as possible concerning (a) the various contexts of applications from which the problem arose; (b) the main computational methods proposed in the literature for solving it, with emphasis on those techniques which appear at present, to be most efficient or promising.