RT Journal Article
T1 A comparative study of two hybrid grouping evolutionary techniques for the capacitated P-median problem
A1 Landa-Torres, I.
A1 Del Ser, J.
A1 Salcedo-Sanz, S.
A1 Gil-Lopez, S.
A1 Portilla-Figueras, J. A.
A1 Alonso-Garrido, O.
AB This paper addresses the application of two different grouping-based algorithms to the so-called capacitated P-median problem (CPMP). The CPMP is an NP-complete problem, well-known in the operations research field, arising from a wide spectrum of applications in diverse fields such as telecommunications, manufacturing and industrial engineering. The CPMP problem has been previously tackled by using distinct algorithmic approaches, among which we focus on evolutionary computation techniques. The work presented herein elaborates on these evolutionary computation algorithms when applied to the CPMP, by evaluating the performance of a novel grouping genetic algorithm (GGA) and a novel grouping harmony search approach (GHS). Both GGA and GHS are hybridized with a specially tailored local search procedure for enhancing the overall performance of the algorithm in the particular CPMP scenario under consideration. This manuscript delves into the main characteristics of the proposed GGA and GHS schemes by thoroughly describing the grouping encoding procedure, the evolutionary operators (GGA) and the improvisation process (GHS), the aforementioned local search procedure and a repairing technique that accounts for the feasibility of the solutions iteratively provided by both algorithms. The performance of the proposed algorithms is compared with that of several existing evolutionary-based algorithms for CPMP instances of varying size, based on which it is concluded that GGA and GHS dominate any other approaches published so far in the literature, specially when the size of the CPMP increases. The experimental section of the paper tries to evaluate the goodness of the grouping encoding, and also the differences in behavior between the GGA and GHS due to the meta-heuristic algorithm used.
SN 0305-0548
YR 2012
FD 2012-09
LK https://hdl.handle.net/11556/2918
UL https://hdl.handle.net/11556/2918
LA eng
NO Landa-Torres , I , Del Ser , J , Salcedo-Sanz , S , Gil-Lopez , S , Portilla-Figueras , J A & Alonso-Garrido , O 2012 , ' A comparative study of two hybrid grouping evolutionary techniques for the capacitated P-median problem ' , Computers and Operations Research , vol. 39 , no. 9 , pp. 2214-2222 . https://doi.org/10.1016/j.cor.2011.11.004
NO This work has been partially supported by Spanish Ministry of Science and Innovation, under a project number ECO2010-22065-C03-02, by Comunidad de Madrid and Universidad de Alcalá, through project number CCG10-UAH/TIC-5955, and by Spanish Ministry of Science and Innovation through the CONSOLIDER-INGENIO 2010 (CSD200800010).
DS TECNALIA Publications
RD 28 jul 2024