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

• Type: Article in International Conference Proceedings Book
• Date: 2020

Authors

Matos, T (Author) Other; Oliveira, O (Author) Other; Gamboa, D (Author) Other

Conference proceedings International

Title: LEARNING AND INTELLIGENT OPTIMIZATION, LION

Pages: 240-252

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

Chania, GREECE, MAY 27-31, 2019

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13