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

author:

Lu, Y. (Lu, Y..) [1] | Benlic, U. (Benlic, U..) [2] | Wu, Q. (Wu, Q..) [3]

Indexed by:

Scopus

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:

Capacitated minimum spanning tree; Heuristics; Hybrid evolutionary algorithm; Tabu search

Community:

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

Reprint 's Address:

  • [Wu, Q.]School of Management, No. 1037, Luoyu Road, China

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:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Affiliated Colleges:

Online/Total:152/10718915
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