期刊
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
卷 273, 期 2, 页码 464-487出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ejor.2018.08.043
关键词
Tabu search; Memetic algorithm; Infeasible local search; Capacitated clustering
资金
- National Natural Science Foundation of China [71401059, 71771099, 71810107003, 71620107002, 71531009]
- Huazhong University of Science and Technology [5001300001]
Given a weighted graph, the capacitated clustering problem (CCP) is to partition a set of nodes into a given number of distinct clusters (or groups) with restricted capacities, while maximizing the sum of edge weights corresponding to two nodes from the same cluster. CCP is an NP-hard problem with many relevant applications. This paper proposes two effective algorithms for CCP: a Tabu Search (denoted as FITS) that alternates between exploration in feasible and infeasible search space regions, and a Memetic Algorithm (MA) that combines FITS with a dedicated cluster-based crossover. Extensive computational results on five sets of 183 benchmark instances from the literature indicate that the proposed FITS competes favorably with the state-of-the-art algorithms. Additionally, an experimental comparison between FITS and MA under an extended time limit demonstrates that further improvements in terms of the solution quality can be achieved with MA in most cases. We also analyze several essential components of the proposed algorithms to understand their importance to the success of these approaches. (C) 2018 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据