• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Lu, Yongliang (Lu, Yongliang.) [1] | Benlic, Una (Benlic, Una.) [2] | Wu, Qinghua (Wu, Qinghua.) [3]

Indexed by:

EI

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. © 2022 Elsevier Ltd

Keyword:

Benchmarking Computational complexity Genetic algorithms Tabu search Trees (mathematics)

Community:

  • [ 1 ] [Lu, Yongliang]School of Economics and Management, Fuzhou University, Fuzhou; 350116, China
  • [ 2 ] [Benlic, Una]Tesco PLC, Lever Building, 85 Clerkenwell Rd, London, Holborn; EC1R 5AR, United Kingdom
  • [ 3 ] [Wu, Qinghua]School of Management, Huazhong University of Science and Technology, No. 1037, Luoyu Road, Wuhan, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

Computers and Operations Research

ISSN: 0305-0548

Year: 2022

Volume: 144

4 . 6

JCR@2022

4 . 1 0 0

JCR@2023

ESI HC Threshold:61

JCR Journal Grade:2

CAS Journal Grade:2

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 5

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Affiliated Colleges:

Online/Total:136/10718895
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1