A Simple Dual-RAMP Algorithm for the Capacitated Facility Location Problem

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2020

Autores

Matos, T (Autor) Outra; Oliveira, O (Autor) Outra; Gamboa, D (Autor) Outra

Ata de Conferência Internacional

Título: LEARNING AND INTELLIGENT OPTIMIZATION, LION

Páginas: 240-252

13th International Conference on Learning and Intelligent Optimization (LION)

Chania, GREECE, MAY 27-31, 2019

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00R-KEJ

DOI: 10.1007/978-3-030-38629-0_20

Abstract (EN): Facility Location embodies a class of problems concerned with locating a set of facilities to serve a geographically distributed population of customers at minimum cost. We address the classical Capacitated Facility Location Problem (CFLP) in which the assignment of facilities to customers must ensure enough facility capacity and all the customers must be served. This is a well-known NP-hard problem in combinatorial optimization that has been extensively studied in the literature. Due to the difficulty of the problem, significant research efforts have been devoted to developing advanced heuristic methods aimed at finding high-quality solutions in reasonable computational times. We propose a Relaxation AdaptiveMemory Programming (RAMP) approach for the CFLP. Our method combines lagrangean subgradient search with an improvement method to explore primal-dual relationships to create advanced memory structures that integrate information from both primal and dual solution spaces. The algorithm was tested on the standard ORLIB dataset and on other very large-scale instances for the CFLP. Our approach efficiently found the optimal solution for all ORLIB instances and very competitive results for the large-scale ones. Comparisons with current best-performing algorithms for the CFLP show that our RAMP algorithm exhibits excellent results.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13