Effective metaheuristic algorithms for the minimum differential dispersion problem

Yang Wang, Qinghua Wu and Fred Glover

European Journal of Operational Research, 2017, vol. 258, issue 3, 829-843

Abstract: This paper presents tabu search and memetic search algorithms for solving the minimum differential dispersion problem. The tabu search algorithm employs a neighborhood decomposition candidate list strategy and a rarely used solution-based tabu memory. Unlike the typical attribute-based tabu list, the solution-based tabu strategy leads to a more highly focused intensification process and avoids tuning the tabu tenure, while employing coordinated hash functions that accelerate the determination of tabu status. The memetic search algorithm incorporates the tabu search procedure within it and makes use of a crossover operator that generates solution assignments by an evaluation mechanism that includes both quality and distance criteria. Experimental results on a benchmark testbed of 250 problems reveal that our tabu search algorithm is capable of discovering better solutions for 179 (71.6%) of the problem instances, while our memetic search algorithm finds better solutions for 157 (62.8%) of the instances, collectively yielding better solutions for 181 (72.4%) of the test problems than recently reported state-of-the-art algorithms.

Keywords: Metaheuristics; Combinatorial optimization; Dispersion problems; Tabu search; Memetic search (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716308694
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:3:p:829-843

DOI: 10.1016/j.ejor.2016.10.035

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().