Solution-based tabu search for the capacitated dispersion problem

被引:14
作者
Lu, Zhi [1 ]
Martinez-Gavara, Anna [2 ]
Hao, Jin-Kao [3 ]
Lai, Xiangjing [4 ]
机构
[1] Univ Shanghai Sci & Technol, Business Sch, 516 Jungong Rd, Shanghai 200093, Peoples R China
[2] Univ Valencia, Dept Estadist & Invest Operat, C Doctor Moliner 50, Valencia 46100, Spain
[3] Univ Angers, LERIA, 2 Blvd Lavoisier, F-49045 Angers, France
[4] Nanjing Univ Posts & Telecommun, Inst Adv Technol, Nanjing 210023, Peoples R China
基金
中国国家自然科学基金;
关键词
Combinatorial optimization; Diversity maximization; Dispersion; Metaheuristics; Tabu search; FACILITY DISPERSION; DIVERSITY; ALGORITHM; INTENSIFICATION; OPTIMIZATION;
D O I
10.1016/j.eswa.2023.119856
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Given a weighted graph with a capacity associated to each node (element), the capacitated dispersion problem (CDP) consists in selecting a subset of elements satisfying a capacity constraint, in such a way that the minimum distance among them is maximized. The purpose of this work is to tackle this NP-hard problem, by developing an effective and parameter-free heuristic algorithm based on the solution-based tabu search. Specifically, we propose a fast greedy construction heuristic to obtain high-quality initial solutions. To ensure a high search efficiency, our algorithm exploits the combination of three neighborhoods, including a new neighborhood based on the constrained swap strategy, and uses hash functions to identify eligible candidate solutions. Extensive computational experiments on benchmark instances in the literature are performed to demonstrate the high performance of our algorithm and get insights into the influences of the algorithmic components. The application of our algorithm to a realistic location problem further shows the usefulness of our approach for practical problems.
引用
收藏
页数:15
相关论文
共 44 条
  • [1] [Anonymous], 2010, Experimental Methods for the Analysis of Optimization Algorithms, DOI DOI 10.1007/978-3-642
  • [2] [Anonymous], 2011, NETWORK DISCRETE LOC
  • [3] A note on hashing functions and tabu search algorithms
    Carlton, WB
    Barnes, JW
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 95 (01) : 237 - 239
  • [4] A hybrid metaheuristic approach for the capacitated arc routing problem
    Chen, Yuning
    Hao, Jin-Kao
    Glover, Fred
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2016, 253 (01) : 25 - 39
  • [5] Benchmarking optimization software with performance profiles
    Dolan, ED
    Moré, JJ
    [J]. MATHEMATICAL PROGRAMMING, 2002, 91 (02) : 201 - 213
  • [6] Tabu search and GRASP for the maximum diversity problem
    Duarte, Abraham
    Marti, Rafael
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 178 (01) : 71 - 84
  • [7] Hybrid evolutionary algorithms for graph coloring
    Galinier, P
    Hao, JK
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 1999, 3 (04) : 379 - 397
  • [8] Hybrid heuristics for the maximum diversity problem
    Gallego, Micael
    Duarte, Abraham
    Laguna, Manuel
    Marti, Rafael
    [J]. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2009, 44 (03) : 411 - 426
  • [9] Glover F., 1998, Handbook of Combinatorial Optimization, DOI [10.1007/978-1-4613-0303-9_33, DOI 10.1007/978-1-4613-0303-9_33, DOI 10.1007/978-1-4613-0303-933, 10.1007/978-1- 4613-0303-9_33]
  • [10] KUBY MJ, 1987, GEOGR ANAL, V19, P315