A facility location problem for extracurricular workshop planning: bi-level model and metaheuristics

This paper presents a facility location problem with capacitated multiservice facilities in which the allocation of the users is based on their preferences. The problem arises from an educational program, where a government agency or a nongovernmental organization (NGO) offers extracurricular workshops to elementary school students. These workshops promote the development of academic, social, or cultural skills of the students. This problem is formulated as a bi-level program. The government/NGO is associated with the upper level, which aims to minimize the costs for opening workshops in different schools and the costs of allocating students to each workshop. The lower level is related to the students and seeks to optimize their global preferences for the offered workshops. To solve this problem, we propose a single-level reformulation and two metaheuristics (a path-relinking metaheuristic (PRM) and an iterated local search (ILS) procedure). The best performing method is the PRM that generates saturated initial random solutions following a drop heuristic approach. After different phases of improvement (with drop and exchange heuristics), the solutions undergo a path-relinking procedure. The trajectory between the initial solution and the best solution found so far is explored using a randomized backward path-relinking strategy that thoroughly explores the neighborhood of the best solution. Computational experimentation indicates that the proposed PRM metaheuristic is effective and efficient. The results obtained provide better upper bounds in shorter running times than the ones obtained by the single-level reformulation or the ILS procedure. Finally, the application to a realistic case study of Apodaca municipality in Nuevo Leon, Mexico, shows that large-scale instances can be solved efficiently using the proposed metaheuristic.