The adaptable Pareto set problem for facility location: A video game approach. (30th December 2021)

• Record Type: Journal Article
• Authors: Vargas-Santiago, Mariano; Monroy, Raúl; Zhang, Chi; Ramirez-Marquez, José E.; León-Velasco, Diana A.
• Is Part Of: Expert systems with applications. Volume 186(2021)
• Publication Date: 2021-12-30
• Subjects: Facility location problem -- Multi-objective optimization problems -- Pareto set -- Heuristics -- Serious video games -- Crowdsourcing; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115682
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: Facility Location is a multi-objective optimization problem, where, given a set of demand centers, D, one is to determine how many facilities to open, in such a way that we satisfy the overall demand, while minimizing the sum of two types of costs: one associated to opening a facility, and the other to the distance from each demand center to the nearest facility that has been opened. There exist various techniques to solve it, including methods that are complete, and others that find a good solution, though not necessarily the optimal one. Current techniques, however, do not contemplate that there already is an initial configuration of the problem or that changes have occurred in the environment and so the existing solution must be adjusted to meet new requirements: they reformulate the optimization problem each time, starting from scratch. To fill in this gap, we introduce the adaptable Pareto set of the Facility Location Problem. In particular, we introduce a method that may apply either of two heuristics, namely: the incremental and the decremental heuristics, which deal with the case where it is necessary to increase (respectively, decrease) the number of facilities opened. To complete these heuristics, we provide a video game for crowdsourcing solutions to the adaptable Pareto set for the facility location problem; we have considered both cases, one where some facilities need to be added, and the other, where some facilities need to be removed. We have tested our two methods using the Swain dataset. Our experimental results show that our heuristics are competitive, when compared against both the optimal solution found through a complete method, and that approximated via a genetic algorithm. Further, our results show that video game players may obtain better solutions than those found heuristically, and that these solutions sometimes are similar to those found using a brute force algorithm. Highlights: A novel method for solving the Pareto set; an adaptable way to find the Pareto set. Solutions are found after an initial configuration. Two new heuristics (incremental/decremental) and their corresponding algorithms. Using crowdsourcing humans can solve complicated problems. Efficient method for solving NP-hard problems.