Applications of Combinatorial Optimization, 2nd Edition

Chapter 9

Network Design Problems: Fundamental Methods

9.1. Introduction

Network design problems have taken on particular importance in operations research over the last 20 years. The main reason for this is the evolution undergone by the world of telecommunications and, to a lesser degree, by those of transport and production systems. The tendency to open up to competition between the different operators (of infrastructure or services) has led operators to become more concerned about optimizing their decisions in terms of infrastructure and operations modes, and to seek tools that allow them to better identify their share of the market. The expansion and integration movement of tools and communication modes has created new requirements in terms of modeling, and has provoked the emergence of more and more complex decision models. The increasing power of tools for acquiring and storing information (sensors, mobile transmission devices, databases, distributed systems, etc.) at present enables the structuring of the information systems associated with the monitoring of distributed activities, which makes it possible to supply these models with relevant data (measures of demand, costs, quality of service, etc.).

It is not easy to define the exact outline of a network optimization or design problem: for design proposals, see for example [AHU 95] and [CHAN 93] (focusing on telecommunications), [CHR 81] (focusing on connectivity constraints), [DIO 79], [FER 94], [MAG 78], [STE 74] and ...