Multi-Level Uncapacitated Facility Location Problem with Clients' Preferences

Abstract

This paper introduces the multi-level uncapacitated facility location problem with clients’ preferences (MLUFLP-CP), which represents a generalization of the well-known multi-level uncapacitated facility location problem (MLUFLP). The MLUFLP-CP is first modeled as a bi-level mathematical program, and then reformulated to four integer linear programs. Due to the NP-hardness of the MLUFLP-CP, the problem instances of real-world dimensions are unsloved to optimality by CPLEX solver. Therefore, we have designed a general variable neighborhood search (GVNS) metaheuristic as an efficient solution approach to the MLUFLP-CP. The GVNS concept and its parameters are adapted to the multi-level nature of problem, and a novel VND variant, denoted as multi-level VND, is used as a local search improvement procedure. Computational experiments on MLUFLP-CP instances show that the proposed GVNS quickly reaches all known optimal solutions, improves upper bounds obtained by CPLEX and efficiently provides solutions for large-scale instances that were out of reach for CPLEX.