Indexed by:
Abstract:
The capacitated minimum spanning tree (CMST) problem is a fundamental problem in telecommunication network design. Given a central node and a set of remote terminal nodes with specified demands for traffic, the goal of CMST is to find a minimum cost spanning tree (network) such that the traffic on any arc of the network satisfies the capacity constraint. To tackle this NP-hard problem, we propose an effective hybrid evolutionary algorithm that integrates a backbone-based crossover operator, a destroy-and-repair mutation operator to generate meaningful offspring solutions, and an intensification-driven adaptive tabu search procedure that considers both feasible and infeasible solutions in search of high-quality local optima. Extensive computational results on a set of 126 well-known CMST benchmark instances from the literature indicate that the proposed algorithm competes favorably with the state-of-the-art heuristics. For a selection of 25 most challenging CMST instances with unknown optimal solutions, the proposed algorithm reports new upper bounds (improved best-known solutions) in 9 cases, while reaching the best-known result for 12 instances. Furthermore, we provide experimental analyses to identify the key algorithmic features of the proposed approach.
Keyword:
Reprint 's Address:
Version:
Source :
COMPUTERS & OPERATIONS RESEARCH
ISSN: 0305-0548
Year: 2022
Volume: 144
4 . 6
JCR@2022
4 . 1 0 0
JCR@2023
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:61
JCR Journal Grade:2
CAS Journal Grade:2
Affiliated Colleges: