Document Type : Article

**Authors**

Department of Industrial Engineering, Faculty of engineering, University of Kurdistan, Sanandaj, Iran

**Abstract**

Facility location of two producers with preference of customers is discussed in this paper. Because of differences between two producers in terms of their influence on the market, the problem is formulated as a bi-level integer mathematical programming model with binary variables. It is considered that both leader and follower have some facilities at first and are going to open new facilities and this may lead to make changes in allocation of facilities and customers. To solve the problem, two metaheuristics algorithm based on genetic algorithm (GA) and hybrid of genetic algorithm and ant colony optimization (ACO) are proposed. In the first section of each algorithm, the location of facilities for two producers is determined and in the second section, each customer selects a facility. Upper bound of the competitive facility location problem is determined by solving the upper-level problem as an integer linear programming model without considering the follower’s decision. To evaluate the efficiency of proposed algorithms, enumeration technique is used to find optimal solution. Computational results show that all of the developed algorithms are capable of achieving optimal solution for small size problems and high-quality solution in reasonable computational time for medium and large-scale problems.

**Keywords**

- Bilevel programming
- competitive facility location
- Genetic Algorithm
- ant colony optimization algorithm

**Main Subjects**

References:

[1] Amirtaheri, O., Zandieh, M., and Dorri, B. “A bi-level programming model for decentralized manufacturer-distributer supply chain considering cooperative advertising”, Scientia Iranica, Transaction E: Indsutrial engineering., 25(2),pp.891-910 (2018).

[2] Pal, D., Sarkar, J. “Spatial competition among multi-store firms”, International Journal of Industrial Organization., 20(2), pp.163-190 (2002).

[3] Aboolian, R., Berman, O., Krass, D. “Competitive facility location model with concave demand”, European Journal of Operational Research., 181(2), pp.598-619 (2007).

[4] Beresnev, V L., “Upper bounds for objective functions of discrete competitive facility location problems”, Journal of Applied and Industrial Mathematics., 3, pp.419-432 (2009).

[5] Saidani, N., Chu, F., Chen, H. “Competitive facility location and design with reactions of competitors already in the market”, European Journal of Operational Research., 219(1), pp.9-17 (2012).

[6] Ashtiani, M G., Makui, A., and Ramezanian, R. “A robust model for a leader–follower competitive facility location problem in a discrete space”, Applied Mathematical Modelling., 37(1-2), pp.62-71 (2013).

[7] Beresnev,V. “Branch-and-bound algorithm for a competitive facility location problem”, Computers & Operations Research., 40(8), pp.2062-2070 (2013).

[8] Calvete, H I., Gale, C., and Iranzo, J A. “Planning of a decentrailized distribution network using bilevel optimization”, Omega., 49,pp.30-41 (2014).

[9] Rahmani, A., Mirhassani, SA . “Lagrangean relaxation-based algorithm for bi-level problems”, Optimization Methods and Software., 30(1),pp.1-14 (2015).

[10] Mirhassani, S A., Raeisi, S., and Rahmani, A. “Quantum binary particle swarm optimization-based algorithm for solving a class of bi-level competitive facility locatioVn problems”,Optimization Methods Software., 30(4), pp.756-768 (2015).

[11] Zhang, Y., Synder, LV., Ralphs, T K., and Zhaojie, X. “The competitive facility location problem under disruption risks”, Transportation Research Part E., 93, pp.453-473 (2016).

[12] Saranwong, S., Likasiri, C. “Bi-level programming model for solving distribution center problem: A case study in Northern Thailand’s sugarcane management”, Computers & Industrial Engineering., 103, pp.26-39 (2017).

[13] Qi, M., Xia, M., Zhang, Y., and Miao, L. “Competitive facility location problem with foresight considering service distance limitations”, Computers and Industrial Engineering., 112, pp.483-491 (2017).

[14] Kung, L-C., Liao, W-H. “An approximation algorithm for a competitive facility location problem with network effects”, European Journal of Operational Research., 267(1), pp.176-186 (2017).

[15] Nasiri, M.M., Mahmoodian, V., Rahbari, A., and Farahmand, S. “A modified genetic algorithm for the capacitated competitive facility location problem with the partial demand satisfaction”, Computers and Industrial Engineering.,124, pp.435-448 (2018).

[16] Beresnev, V., Melnikov, A. “Exact method for the capacitated competitive facility location problem”, Computers & Operation Research., 95, pp.73-82 (2018).

[17] Sadjadi, Sj., Gorji Ashtiani, M., Makui, A., and Ramezanian, R. “A mathematical model for competitive location problem with product selection”, Scientia Iranica, Transaction E: Industrial Engineering, DOI: 10.24200/sci.2018.51736.2337.

[18] Bilir, C., Ekici, S O., and Ulengin, F. “An integrated Multi-objective supply chain Network and Competitive Facility Location Model”, Computers and Industrial Engineering.,108,pp.136-148 (2017).

[19] Wang, S C., Chen, T C. “Multi objective competitive facility location problem with distance based attractiveness and its best non-dominated solution”, Applied Mathematical Modeling., 47, pp.785-795 (2017).

[20] Konak, A., Konak, S A., and Synder, L. “A multi objective approach to the competitive facility location problem”, Procedia Computers Science., 108, pp.1434-1442 (2017).

[21] Beresnev, V L., Mel’nikov, A A. “Approximate algorithms for the competitive facility location problem”, Journal of Applied and Industrial Mathematics., 5(2), pp.180-190 (2011).

[22] Beresnev, V L., Mel’nikov, A A. “The branch-and-bound algorithm for a competitive facility location problem with the prescribed choice of suppliers”, Journal of Applied and Industrial Mathematics., 8(2), pp.177-189 (2014).

[23] Wang, G., Ziyou, G., and Zhongping, W. “A global optimization algorithm for solving the bi-level linear fractional programming problem”, Computers & Industrial Engineering., 63(2), pp.428-432 (2012).

[24] Oduguwa, V., Roy, R. “Bi-level optimisation using genetic algorithm”, In: IEEE International Conference on Artiﬁcial Intelligence Systems Divnomorskoe, Russia., pp.322–327 (2002).

[25] Yin, Y. “Genetic-algorithms-based approach for bilevel programming models”, J. Transp. Eng., 126, pp.115–120 (2000).

[26] Hejazi, SR., Memariani, A., Jahanshahloo, G., and Sepehri, M M. “Linear bilevel programming solution by genetic algorithm”, Comput. Oper. Res., 29(13), pp.1913–1925 (2002).

[27] Wen, U P., Huang, A D. “A simple Tabu search method to solve the mixed-integer linear bilevel programming problem”, Europ. J. Oper. Res., 88(3), pp.563–571 (1996).

[28] Rajesh, J., Gupta, K., Kusumakar, H S., Jayaraman, V K., and Kulkarni, B D. “A Tabu search based approach for solving a class of bilevel programming problems in chemical engineering”, J. Heuristics., 9(4): pp.307–319 (2003).

[29] Wan, Z., Wang, G., and Sun, B. “A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems”, Swarm and Evolutionary Computation., 8, pp.26-32 (2013).

[30] Kou, R J., Lee, Y H., Zulvia, F E., and Tien, F C. “Solving bi-level linear programming problem through hybrid of immune genetic algorithm and particle swarm optimization algorithm”, Applied Mathematics and Computation.,266, pp.1013-1026 (2015).

[31] Talbi, E-G. “Metaheuristics for Bi-level Optimization”, Springer Publishing Company, Incorporated; (2013).

[32] Kress, D., Pesch, E. “Sequential competitive location on networks”, European Journal of Operational Research., 217(3), pp.483-499 (2012).

[33] Drezner, T. “A review of competitive facility location in the plane”, Logistics Research., 7, pp.1-12 (2014).

[34] Ahmadizar, F., Soltanpanah, H. “Reliability optimization of a series system with multiple-choice and budget constraints using an efﬁcient ant colony approach”, Expert Systems with Applications., 38(4). pp.3640-3646 (2011).

[35] Farughi, H., Yegane, B Y., and Fathian, M. “A new critical path method and a memetic algorithm for flexible job shop scheduling with overlapping operations”, Simulation: Transaction of the Society for Modeling and Simulation Interanational., 89(3), pp.264-277 (2012).

[36] Dorigo, M., Gambardella, L M . “Ant colony system: a cooperative learning approach to the traveling salesman problem”. IEEE Transactions on Evolutionary Computation., 1(1), pp.53-66 (1997).

[2] Pal, D., Sarkar, J. “Spatial competition among multi-store firms”, International Journal of Industrial Organization., 20(2), pp.163-190 (2002).

[3] Aboolian, R., Berman, O., Krass, D. “Competitive facility location model with concave demand”, European Journal of Operational Research., 181(2), pp.598-619 (2007).

[4] Beresnev, V L., “Upper bounds for objective functions of discrete competitive facility location problems”, Journal of Applied and Industrial Mathematics., 3, pp.419-432 (2009).

[5] Saidani, N., Chu, F., Chen, H. “Competitive facility location and design with reactions of competitors already in the market”, European Journal of Operational Research., 219(1), pp.9-17 (2012).

[6] Ashtiani, M G., Makui, A., and Ramezanian, R. “A robust model for a leader–follower competitive facility location problem in a discrete space”, Applied Mathematical Modelling., 37(1-2), pp.62-71 (2013).

[7] Beresnev,V. “Branch-and-bound algorithm for a competitive facility location problem”, Computers & Operations Research., 40(8), pp.2062-2070 (2013).

[8] Calvete, H I., Gale, C., and Iranzo, J A. “Planning of a decentrailized distribution network using bilevel optimization”, Omega., 49,pp.30-41 (2014).

[9] Rahmani, A., Mirhassani, SA . “Lagrangean relaxation-based algorithm for bi-level problems”, Optimization Methods and Software., 30(1),pp.1-14 (2015).

[10] Mirhassani, S A., Raeisi, S., and Rahmani, A. “Quantum binary particle swarm optimization-based algorithm for solving a class of bi-level competitive facility locatioVn problems”,Optimization Methods Software., 30(4), pp.756-768 (2015).

[11] Zhang, Y., Synder, LV., Ralphs, T K., and Zhaojie, X. “The competitive facility location problem under disruption risks”, Transportation Research Part E., 93, pp.453-473 (2016).

[12] Saranwong, S., Likasiri, C. “Bi-level programming model for solving distribution center problem: A case study in Northern Thailand’s sugarcane management”, Computers & Industrial Engineering., 103, pp.26-39 (2017).

[13] Qi, M., Xia, M., Zhang, Y., and Miao, L. “Competitive facility location problem with foresight considering service distance limitations”, Computers and Industrial Engineering., 112, pp.483-491 (2017).

[14] Kung, L-C., Liao, W-H. “An approximation algorithm for a competitive facility location problem with network effects”, European Journal of Operational Research., 267(1), pp.176-186 (2017).

[15] Nasiri, M.M., Mahmoodian, V., Rahbari, A., and Farahmand, S. “A modified genetic algorithm for the capacitated competitive facility location problem with the partial demand satisfaction”, Computers and Industrial Engineering.,124, pp.435-448 (2018).

[16] Beresnev, V., Melnikov, A. “Exact method for the capacitated competitive facility location problem”, Computers & Operation Research., 95, pp.73-82 (2018).

[17] Sadjadi, Sj., Gorji Ashtiani, M., Makui, A., and Ramezanian, R. “A mathematical model for competitive location problem with product selection”, Scientia Iranica, Transaction E: Industrial Engineering, DOI: 10.24200/sci.2018.51736.2337.

[18] Bilir, C., Ekici, S O., and Ulengin, F. “An integrated Multi-objective supply chain Network and Competitive Facility Location Model”, Computers and Industrial Engineering.,108,pp.136-148 (2017).

[19] Wang, S C., Chen, T C. “Multi objective competitive facility location problem with distance based attractiveness and its best non-dominated solution”, Applied Mathematical Modeling., 47, pp.785-795 (2017).

[20] Konak, A., Konak, S A., and Synder, L. “A multi objective approach to the competitive facility location problem”, Procedia Computers Science., 108, pp.1434-1442 (2017).

[21] Beresnev, V L., Mel’nikov, A A. “Approximate algorithms for the competitive facility location problem”, Journal of Applied and Industrial Mathematics., 5(2), pp.180-190 (2011).

[22] Beresnev, V L., Mel’nikov, A A. “The branch-and-bound algorithm for a competitive facility location problem with the prescribed choice of suppliers”, Journal of Applied and Industrial Mathematics., 8(2), pp.177-189 (2014).

[23] Wang, G., Ziyou, G., and Zhongping, W. “A global optimization algorithm for solving the bi-level linear fractional programming problem”, Computers & Industrial Engineering., 63(2), pp.428-432 (2012).

[24] Oduguwa, V., Roy, R. “Bi-level optimisation using genetic algorithm”, In: IEEE International Conference on Artiﬁcial Intelligence Systems Divnomorskoe, Russia., pp.322–327 (2002).

[25] Yin, Y. “Genetic-algorithms-based approach for bilevel programming models”, J. Transp. Eng., 126, pp.115–120 (2000).

[26] Hejazi, SR., Memariani, A., Jahanshahloo, G., and Sepehri, M M. “Linear bilevel programming solution by genetic algorithm”, Comput. Oper. Res., 29(13), pp.1913–1925 (2002).

[27] Wen, U P., Huang, A D. “A simple Tabu search method to solve the mixed-integer linear bilevel programming problem”, Europ. J. Oper. Res., 88(3), pp.563–571 (1996).

[28] Rajesh, J., Gupta, K., Kusumakar, H S., Jayaraman, V K., and Kulkarni, B D. “A Tabu search based approach for solving a class of bilevel programming problems in chemical engineering”, J. Heuristics., 9(4): pp.307–319 (2003).

[29] Wan, Z., Wang, G., and Sun, B. “A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems”, Swarm and Evolutionary Computation., 8, pp.26-32 (2013).

[30] Kou, R J., Lee, Y H., Zulvia, F E., and Tien, F C. “Solving bi-level linear programming problem through hybrid of immune genetic algorithm and particle swarm optimization algorithm”, Applied Mathematics and Computation.,266, pp.1013-1026 (2015).

[31] Talbi, E-G. “Metaheuristics for Bi-level Optimization”, Springer Publishing Company, Incorporated; (2013).

[32] Kress, D., Pesch, E. “Sequential competitive location on networks”, European Journal of Operational Research., 217(3), pp.483-499 (2012).

[33] Drezner, T. “A review of competitive facility location in the plane”, Logistics Research., 7, pp.1-12 (2014).

[34] Ahmadizar, F., Soltanpanah, H. “Reliability optimization of a series system with multiple-choice and budget constraints using an efﬁcient ant colony approach”, Expert Systems with Applications., 38(4). pp.3640-3646 (2011).

[35] Farughi, H., Yegane, B Y., and Fathian, M. “A new critical path method and a memetic algorithm for flexible job shop scheduling with overlapping operations”, Simulation: Transaction of the Society for Modeling and Simulation Interanational., 89(3), pp.264-277 (2012).

[36] Dorigo, M., Gambardella, L M . “Ant colony system: a cooperative learning approach to the traveling salesman problem”. IEEE Transactions on Evolutionary Computation., 1(1), pp.53-66 (1997).

Transactions on Industrial Engineering (E)

September and October 2020Pages 2539-2554