A taxonomy of multilayer network design and a survey of transportation and telecommunication applications
Teodor Gabriel Crainic, Bernard Gendron, Mohammad Rahim Akhavan Kazemzadeh
Abstract
Multilayer network design represents an important problem class when interwoven design decisions must be simultaneously considered. Examples of such cases are the selection of trains and blocks in freight rail transportation and the selection of physical and logical paths in telecommunications. Each set of those design variables are then defined on a particular network making up a layer with its own nodes, which can represent or not the same physical or conceptual locations, potential arcs, with fixed selection cost and with or without limited capacities, and, possibly, multicommodity demands, which need to be routed within the layer by selecting/opening the appropriate arcs. The particular characteristic and challenge of multilayer network design consists in the various design and flow-connectivity requirements linking the decisions on different layers. Thus, for example, to select a light path, all the links making up the supporting physical path must be installed. Similarly, to select a transportation service, all the supporting resources must be selected together with their feasible working paths in the corresponding layers. We propose the first classification and a state-of-the-art survey of multilayer network design problems. The survey focuses on applications in transportation and telecommunications, as well as on solution methods. We also propose a general modeling framework which encompasses the models in the literature.