Home>Results

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

[期刊论文]

A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem

Share
Edit Delete 报错

author:

Lu, Yongliang (Lu, Yongliang.) [1] (Scholars:陆永亮) | Benlic, Una (Benlic, Una.) [2] | Wu, Qinghua (Wu, Qinghua.) [3]

Indexed by:

EI Scopus SCIE

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:

Capacitated minimum spanning tree Heuristics Hybrid evolutionary algorithm Tabu search

Community:

  • [ 1 ] [Lu, Yongliang]Fuzhou Univ, Sch Econ & Management, Fuzhou 350116, Peoples R China
  • [ 2 ] [Benlic, Una]Tesco PLC, Lever Bldg,85 Clerkenwell Rd, London EC1R 5AR, England
  • [ 3 ] [Wu, Qinghua]Huazhong Univ Sci & Technol, Sch Management, 1037 Luoyu Rd, Wuhan, Peoples R China

Reprint 's Address:

Show more details

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

Cited Count:

WoS CC Cited Count:

30 Days PV: 2

Online/Total:77/10717989
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