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

Authors: Imen Mejri; Safa Bhar Layeb; Farah Zeghal

Addresses: LR-OASIS, National Engineering School of Tunis, University of Tunis El Manar, Tunisia ' LR-OASIS, National Engineering School of Tunis, University of Tunis El Manar, Tunisia ' LR-OASIS, National Engineering School of Tunis, University of Tunis El Manar, Tunisia

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]

Keywords: network design problems; NDPs; literature review; survey; combinatorial optimisation.

DOI: 10.1504/EJIE.2023.129443

European Journal of Industrial Engineering, 2023 Vol.17 No.2, pp.253 - 309

Received: 14 Mar 2021
Accepted: 23 Jan 2022
Published online: 09 Mar 2023 *