The adaptable Pareto set problem for facility location: A video game approach[Formula presented]

Mariano Vargas-Santiago, Raúl Monroy, Chi Zhang, José E. Ramirez-Marquez, Diana A. León-Velasco

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish
Article number115682
JournalExpert Systems with Applications
Volume186
DOIs
StatePublished - 30 Dec 2021

Keywords

  • Crowdsourcing
  • Facility location problem
  • Heuristics
  • Multi-objective optimization problems
  • Pareto set
  • Serious video games

Fingerprint

Dive into the research topics of 'The adaptable Pareto set problem for facility location: A video game approach[Formula presented]'. Together they form a unique fingerprint.

Cite this