MEALS: A multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem

Herminia I. Calvete, Carmen Galé and José A. Iranzo

European Journal of Operational Research, 2016, vol. 250, issue 2, 377-388

Abstract: In this paper we develop a hybrid metaheuristic for approaching the Pareto front of the bi-objective ring star problem. This problem consists of finding a simple cycle (ring) through a subset of nodes of a network. The aim is to minimize both the cost of connecting the nodes in the ring and the cost of allocating the nodes not in the ring to nodes in the ring. The algorithm preserves the general characteristics of a multiobjective evolutionary algorithm and embeds a local search procedure which deals with multiple objectives. The encoding scheme utilized leads to solving a Traveling Salesman Problem in order to compute the ring associated with the chromosome. This allows the algorithm to implicitly discard feasible solutions which are not efficient. The algorithm also includes an ad-hoc initial population construction which contributes to diversification. Extensive computational experiments using benchmark problems show the performance of the algorithm and reveal the noteworthy contribution of the local search procedure.

Keywords: Ring star problem; Hybrid evolutionary algorithm; Bi-objective optimization; Local search; Metaheuristics (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715008863
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:250:y:2016:i:2:p:377-388

DOI: 10.1016/j.ejor.2015.09.044

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 ().