A survey on network design problems: main variants and resolution approaches

Abstract

Over the last decades, network design problems (NDPs) have been one of the most investigated combinatorial optimisation problems that are still catching the interest of both practitioners and researchers. In fact, NDPs pose significant algorithmic challenges, as they are notoriously NP-hard, and arise in several applications, mainly in logistics, telecommunication, and production systems. Based on the literature published mainly between 1962 and 2021, this paper provides a comprehensive taxonomy of NDPs and also identifies the most investigated variants as well as their main fields of application. This taxonomy highlights the diversity as well as the assets of this core class of operations research problems. Moreover, the main mathematical formulations and solution methods are reported. Finally, directions for future research on NDPs are derived. [Submitted: 14 March 2021; Accepted: 23 January 2022]