In this study, we consider a variant of the Bilevel Uncapacitated Facility Location Problem (BLUFLP), in which the clients choose suppliers based on their own preferences. We propose and compare three metaheuristic approaches for solving this problem: Particle Swarm Optimization (PSO), Simulated Annealing (SA), and a combination of Reduced and Basic Variable Neighborhood Search Method (VNS). We used the representation of solutions and objective function calculation that are adequate for all three proposed methods. Additional strategy is implemented in order to provide significant time savings when evaluating small changes of solution's code in improvement parts. Constructive elements of each of the proposed algorithms are adapted to the problem under consideration. The results of broad computational tests on modified problem instances from the literature show good performance of all three proposed methods, even on large problem dimensions. However, the obtained results indicate that the proposed VNS-based has significantly better performance compared to SA and PSO approaches, especially when solving large-scale problem instances. Computational experiments on large scale benchmarks demonstrate that the VNS-based method is fast, competitive, and able to find high-quality solutions, even for large-scale problem instances with up to 2000 clients and 2000 potential facilities within reasonable CPU times.