You are here

An adaptive large neighbourhood search algorithm for diameter bounded network design problems

Authors: 

Michele Garraffa, Deepak Mehta, Barry O’Sullivan, Cemalettin Ozturk, Luis Quesada

Publication Type: 
Refereed Original Article
Abstract: 
This paper focuses on designing a diameter - constrained network where the maximum distance between any pair of nodes is bounded. The objective considered is to minimise a weighted sum of the total length of the links followed by the total length of the paths between the pairs of nodes. First, the problem is formulated in terms of Mixed Integer Linear Programming and Constraint Programming to provide two alternative exact approaches. Then, an adaptive large neighbourhood search (LNS) to overcome memory and runtime limitations of the exact methods in large size instances is proposed. Such approach is based on computing an initial solution and repeatedly improve it by solving relatively small subproblems. We investigate various alternatives for finding an initial solution and propose two different heuristics for selecting subproblems. We have introduced a tighter lower bound, which demonstrates the quality of the solution obtained by the proposed approach. The performance of the proposed approach is assessed using three real-world network topologies from Ireland, UK and Italy, which are taken from national telecommunication operators and are used to design a transparent optical core network. Our results demonstrate that the LNS approach is scalable to large networks and it can compute very high quality solutions that are close to being optimal.
Digital Object Identifer (DOI): 
10.1007/s10732-021-09481-1
Publication Status: 
Published
Publication Date: 
23/06/2021
Journal: 
Journal of Heuristics volume
Volume: 
27
Pages: 
887–922
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No