GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem. (February 2017)

• Record Type: Journal Article
• Authors: Rodriguez, Francisco J.; Glover, Fred; García-Martínez, Carlos; Martí, Rafael; Lozano, Manuel
• Is Part Of: Computers & operations research. Volume 78(2017)
• Page Start: 243
• Page End: 254
• Publication Date: 2017-02
• Subjects: Multidimensional two-way number partitioning problem -- GRASP -- Exterior path-relinking -- Restricted local search -- Binary combinatorial optimisation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.09.005
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the "exterior form" of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. Our computational experiments show the superiority of this approach compared with the previous best method for MDTWNP and with alternative methods for this problem that use other forms of PR. Abstract : Highlights: The MDTWNP problem is solved by a GRASP with Exterior Path Relinking (ePR) metaheuristic. We explore the exterior PR variant that remained virtually unexplored up to now. We propose a novel local search procedure for the MDTWNP problem, which provides a smoother descent and a faster performing. The experimental study carried out shows the benefits of the ePR variant and the new local search in the GRASP+ePR method. GRASP+ePR provides high-quality solutions with regards to the state-of-the-art algorithms, especially for large instances.