Metaheuristic approaches to solving large-scale Bilevel Uncapacitated Facility Location Problem with clients' preferences
DOI:
https://doi.org/10.2298/YJOR130702032MKeywords:
location problems, discrete optimization, particle swarm optimization, simulated annealing, variable neighborhood searchAbstract
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.References
Alekseeva, E.V., and Kochetov, Y.A., “Genetic Local Search for the p-Median Problem with Clients’ Preferences”, Diskret. Anal. Issled. Oper., 14 (2007) 3–31.
Beasley, J.E., “Obtaining Test Problems via Internet”, Journal of Global Optimization, 8 (1996) 429–433.
Brimberg, J., Mladenović, N., Urošević, D., and Ngai, E., “Variable Neighborhood Search for the Heaviest k-Subgraph”, Computers and Operations Research, 36 (2009) 2885–2891.
Cánovas, L., García, S., Labbé, M., and Marín, A., “A Strengthened Formulation for the Simple Plant Location Problem with Order”, Operations Research Letters, 35 (2007) 141–150.
Cornuejols, G., Nemhauser, G.L., and Wolsey, L.A., “The Uncapacitated Facility Location Problem”, In: Mirchandani, P.B., and Francis, R.L. (eds.), Discrete Location Theory, New York: Wiley Interscience, 1990, 119–171.
Dekkers, A., and Aarts, E., “Global Optimization and Simulated Annealing”, Mathematical Programming, 50 (1991) 367–393.
Dempe, S., Foundations of Bilevel Programming, Dordrecht: Kluwer Academic Publishers, 2002.
Eglese, R.W., “Simulated Annealing: A Tool for Operational Research”, European Journal of Operational Research, 46 (1990) 271–281.
García-López, F., Melián-Batista, B., Moreno-Pérez, J.A., and Moreno-Vega, J.M., “The Parallel Variable Neighborhood Search for the p-Median Problem”, Journal of Heuristics, 8 (2002) 375–388.
Gorbachevskaya, L.E., Polynomially Solvable and NP-Hard Bilevel Standardization Problems, PhD Thesis, Sobolev Institute of Mathematics, Novosibirsk, (in Russian), 1998.
Hanjoul, P., and Peeters, D., “A Facility Location Problem with Clients’ Preference Ordering”, Regional Science and Urban Economics, 17 (1987) 451–473.
Hansen, P., and Mladenović, N., “Variable Neighborhood Search for the p-Median”, Location Science, 5 (1997) 207–226.
Hansen, P., and Mladenović, N., “An Introduction to Variable Neighborhood Search”, In: Voss S., Martello, S., Osman, I.H., and Roucairol, C. (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers, 1999, 433–458.
Hansen, P., and Mladenović, N., “Variable Neighborhood Search: Principles and Applications”, European Journal of Operational Research, 130 (2001) 449–467.
Hansen, H., Kochetov, Y.A., and Mladenović, N., “Lower Bounds for the Uncapacitated Facility Location Problem with User Preferences”, Preprint G 2004 24, GERAD-HEC, Montreal, 2004.
Henderson, D., Sheldon, H., Jacobson, H., and Johnson, A.W., “The Theory and Practice of Simulated Annealing”, In: Glover F., and Kochenberger, G.A., (eds.), Handbook of Metaheuristics, New York, Boston, Dordrecht, London, Moscow: Kluwer Academic Publishers, 2003, 287–321.
Kennedy, J., and Eberhart, R.C., “Particle Swarm Optimization”, Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, 1995, 1942–1948.
Kennedy, J., and Eberhart, R.C., “A Discrete Binary Version of the Particle Swarm Algorithm”, Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, 1997, 4104–4108.
Kennedy, J., and Eberhart, R.C., Swarm Intelligence, San Francisco, CA: Morgan-Kaufmann, 2001.
Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., “Optimization by Simulated Annealing”, Science, 220 (1983) 671–680.
Koulamas, C., Anthony, S.R., and Jaen, R., “A Survey of Simulated Annealing Application to Operations-Research Problems”, OMEGA International Journal of Management, 22 (1994) 41–56.
Liang, Y.C., Lo, M.H., and Chen, Y.C., “Variable Neighborhood Search for Redundancy Allocation Problems”, IMA Journal of Management Mathematics, 18 (2007) 135–155.
Marić, M., “An Efficient Genetic Algorithm for Solving the Multi-Level Uncapacitated Facility Location Problem”, Computing and Informatics, 29 (2010) 183–201.
Marić, M., Stanimirović, Z., and Stanojević, P., “An Efficient Memetic Algorithm for the Uncapacitated Single Allocation Hub Location Problem”, Soft Computing, 17 (2013) 445–466.
Marić, M., Stanimirović, Z., and Milenković, N., “Metaheuristic Methods for Solving the Bilevel Uncapacitated Facility Location Problem with Clients Preferences”, Electronic Notes in Discrete Mathematics, 39 (2012) 43–50.
Mladenović, N., Tododijević, R., and Urošević, D., “An Efficient General Variable Neighborhood Search for Large Travelling Salesman Problem with Time Windows”, The Yugoslav Journal of Operations Research, 23 (2013), DOI: 102298YJOR120530015M.
Pérez Pérez, M., Almeida Rodríguez, F., and Moreno-Vega, J.M., “A Hybrid VNS–Path Relinking for the p-Hub Median Problem”, IMA Journal of Management Mathematics, 18 (2007) 157–171.
Pulido, G.T., Coello, C.A.C., and Lechuga, M.S., “Handling Multiple Objectives with Particle Swarm Optimization”, IEEE Transactions on Evolutionary Computation, 8 (2004) 256–279.
Raidl, G.R., and Gottlieb, J., “Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack Problem”, Evolutionary Computation, 13 (2005) 441–475.
Resende, M.G.C., and Werneck, R.F., “A Fast Swap-Based Local Search Procedure for Location Problems”, Annals of Operations Research, 150 (2007) 205–230.
Reyes-Sierra, C., and Coello, C.A.C., “Multi-Objective Particle Swarm Optimizers: A Survey of the State-of-the-Art”, International Journal of Computational Intelligence Research, 2 (2006) 287–308.
Schwengerer, M., Pirkwieser, S., and Raidl, G., “A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem”, Evolutionary Computation in Combinatorial Optimization, 2012, 13–24.
Suman, B., and Kumar, P., “A Survey of Simulated Annealing as a Tool for Single and Multi-Objective Optimization”, Journal of the Operational Research Society, 57 (2006) 1143–1160.
Vasilev, I.L., and Klimentova, K.B., “The Branch and Cut Method for the Facility Location Problem with Clients’ Preferences”, Journal of Applied and Industrial Mathematics, 4 (2010) 441–454.
Vasilev, I.L., Klimentova, K.B., and Kochetov, Y.A., “New Lower Bounds for the Facility Location Problem with Clients’ Preferences”, Computational Mathematics and Mathematical Physics, 49 (2009) 1010–1020.
Downloads
Published
Issue
Section
License
Copyright (c) 2015 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
