An Exploration of Evolutionary Algorithms for a Bi-objective Competitive Facility Location Problem in Congested Systems

Zarrinpoor, Naeme

doi:10.22034/2018.3.6

An Exploration of Evolutionary Algorithms for a Bi-objective Competitive Facility Location Problem in Congested Systems

Document Type : Research Paper

Author

Naeme Zarrinpoor

Department of Industrial Engineering, Shiraz University of Technology, Shiraz, Iran

10.22034/2018.3.6

Abstract

This paper presents a bi-objective competitive facility location model for congested systems in which entering facilities will compete with the competitors’ facilities for capturing the market share. In the proposed model, customers can chose which facility to patronize based on the gravity function that depends on both the quality of service provider and the travel time to facilities. The proposed model attempts to simultaneously maximize the captured demand by each facility and minimize the total waiting times at the system. To solve the model, two multi-objective evolutionary algorithms, involving a multi-objective harmony search algorithm (MOHS) and a non-dominated sorting genetic algorithm-II (NSGA-II), are proposed. The performance of solution procedures are compared in terms of different performance metrics including generational distance, spacing metric, diversification metric, and number of non-dominated solution. Computational results based on different problem sizes show that in general MOHS outperforms NSGA-II.

Keywords

Main Subjects

optimization in supply chain management

References

Aboolian, R., Berman, O. and Krass, D. (2007). Competitive facility location and design problem. European Journal of Operational Research, Vol. 182, pp. 40–62.

Ahmadi-Javid, A., Seyedi, P. and Syam, S.S. (2017). A survey of healthcare facility location. Computers & Operations Research, Vol.79, pp. 223–263.

Benati S. (1999). The maximum capture problem with heterogeneous customers. Computers &Operations Research, Vol. 26, pp.1351–1367.

Benati, S. and Hansen, P. (2002). The maximum capture problem with random utilities: Problem formulation and algorithms. European Journal of Operational Research, Vol.143, pp. 518–530.

Boffey, B., Galvao, R. and Espejo, L. (2007). A review of congestion models in the location of facilities with immobile servers. European Journal of Operational Research, Vol. 178, pp. 643–662.

Boonmee, C., Arimura, M. and Asada, T. (2017). Facility location optimization model for emergency humanitarian logistics. International Journal of Disaster Risk Reduction, Vol. 24, pp. 485–498.

Brandeau, M. and Chiu, S. (1994). Location of competing facilities in a user optimizing environment with market externalities. Transportation Science, Vol. 28, pp. 125–140.

Brandeau, M., Chiu, S., Kumar, S. and Grossman, T. (1995). Location with market externalities. In: Drezner Z. Facility location: A survey of applications and methods. Springer Verlag, New York.

Beresnev, V. and Melnikov, A. (2018). Exact method for the capacitated competitive facility location problem. Computers & Operations Research, Vol. 95, pp.73-82.

Coello, C.A.C. and Christiansen, A.D. (2000). Multi-objective optimization of trusses using genetic algorithms. Computers & Structures, Vol. 75, pp. 647–660.

Coello, C.A.C., Van Veldhuizen, D.A. and Lamont, G.B. (2002). Evolutionary algorithms for solving multi-objective problems. Kluwer Academic Publishers, New York.

Colome, R. and Serra, D. (2001). Consumer choice and competitive location models: Formulations and heuristics. Papers in Regional Science, Vol. 80, pp. 425–438.

Current, J.R., Daskin, M. and Schilling, D.A. (2002). Discrete network location models, in: Z. Drezner, H.W. Hamacher (Eds.), Facility Location: Applications and Theory, Springer, Heidelberg.

Deb, K. and Agrawal, R. B. (1995).Simulated binary crossover for continuous search space. Complex Systems, Vol. 9, pp. 115–148.

Deb, K. and Goyal, M. (1996). A combined genetic adaptive search (GeneAS) for engineering design. Computer Science and Informatics, Vol. 26, pp.30–45.

Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: NSGA-II”. IEEE Transactions on Evolutionary Computation, Vol. 6, pp. 182–197.

DePalma, A., Ginsburgh, V., Labbe, M. and Thisse, J. (1989). Competitive location with random utilities. Transportation Science, Vol. 23, pp. 244–252.

Drezner, Z. (1982). Competitive location strategies for two facilities. Regional Science and Urban Economics, Vol. 12, pp. 485–493.

Drezner, T., Drezner, Z. and Kalczynski, P. (2015). A leader-follower model for discrete competitive facility location. Computers & Operations Research, Vol. 64, pp. 51–59.

Drezner, T., Drezner, Z. and Salhi, S. (2002). Solving the multiple competitive facilities location problem. European Journal of Operational Research, Vol. 142, pp. 138–151.

Drezner, T., Drezner, Z. and Zerom, D. (2018). Competitive facility location with random attractiveness. Operations Research Letters, Vol. 46, pp. 312-317.

Eiselt, H. and Laporte, G. (1989). Competitive spatial models. European Journal of Operational Research, Vol. 39(3), pp. 231–242.

Eiselt, H., Laporte, G. and Thisse, J. (1993). Competitive location models: A framework and bibliography. Transportation Science, Vol. 27, pp. 44–54.

Fernandez, J., Toth, B.G., Redondo, J.L., Ortigosa, P.M. and Arrondo, A.G. (2017). A planar single-facility competitive location and design problem under the multi-deterministic choice rule. Computers & Operations Research, Vol. 78, pp. 305-315.

Farahani, R.Z., Hekmatfar, M., Fahimnia, B. and Kazemzadeh, N. (2014). Hierarchical facility location problem: Models, classifications, techniques, and applications. Computers & Industrial Engineering, Vol. 68, pp.104–117.

Geem, Z.W., Kim, J.H. and Loganathan, G.V. (2001). A new heuristic optimization algorithm: harmony search. Simulation, Vol. 76, pp. 60–68.

Ghaffarinasab, N., Motallebzadeh^,A., Jabarzadeh^,Y. and Kara, B.Y. (2018). Efficient simulated annealing based solution approaches to the competitive single and multiple allocation hub location problems. Computers & Operations Research, Vol. 90, pp.173-192.

Gross, D. and Harris, C.M., Fundamental of queuing theory, (3rd ed), New York, NY: Wiley Interscience, 1998.

Hakimi, S.L. (1983). On locating new facilities in a competitive environment. European Journal of Operation Research, Vol.12, pp.29–35.

Hotelling, H. (1929). Stability in competition. The Economic Journal, Vol. 39, pp. 41–57.

Huff, D.L. (1964). Defining and estimating a trade area. Journal of Marketing, Vol. 28, pp. 34–38.

Huff, D.L. (1966). A programmed solution for approximating an optimum retail location. Land Economics, Vol. 42, pp.293–303.

Khalili-Damghani, K., Abtahi, A.R. and Tavana, M. (2013). A new multi-objective particle swarm optimization method for solving reliability redundancy allocation problems. Reliability Engineering and System Safety, Vol. 111, pp. 58–75.

Kung, L.C. and Liao, W.H. (2018). An approximation algorithm for a competitive facility location problem with network effects. European Journal of Operational Research, Vol. 267, pp.176–186.

Ljubic, I. and Moreno, E. (2018). Outer approximation and submodular cuts for maximum capture facility location problems with random utilities. European Journal of Operational Research, Vol. 266, pp. 46–56.

Marianov, V., Rı´os, M. and Icaza, M.J. (2008). Facility location for market capture when users rank facilities by shorter travel and waiting times. European Journal of Operational Research, Vol. 191, pp.32–44.

McGarveya, R.G. and Cavalier, T.M. (2005). Constrained location of competitive facilities in the plane. Computers & Operations Research, Vol. 32, pp. 359–378.

Nakanishi, M. and Cooper, L.G. (1974). Parameter estimate for multiplicative interactive choice model: least squares approach. Journal of Marketing Research, Vol.11, pp. 303–311.

Nariman-Zadeh, N., Atashkari, K., Jamali, A., Pilechi, A. and Yao, X. (2005). Inverse modelling of multi-objective thermodynamically optimized turbojet engine using GMDH-type neural networks and evolutionary algorithms. Engineering Optimization, Vol. 37, pp.437–462.

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

Redondo, J.L., Fernández, J., Arrondo, A.G., Garcı´a, A. and Ortigosa, P.M. (2012). Fixed or variable demand? Does it matter when locating a facility?. Omega, Vol.40, pp. 9–20.

Redondo, J.L., Fernández, J., Hervás, J.D.A., Arrondo, A.G. and Ortigosa, P.M. (2015). Approximating the Pareto-front of a planar bi-objective competitive facility location and design problem. Computers & Operations Research, Vol. 62, pp. 337–349.

ReVelle, C. (1986). The Maximum capture or “sphere of influence” location problem: Hotelling revisited on a network. Journal of Regional Science, Vol. 26, pp. 343–357.

Shiode, S. and Drezner, Z. (2003). A competitive facility location problem on a tree network with stochastic weights. European Journal of Operation Research, Vol. 149, pp.47–52.

Sivasubramani, S. and Swarup, K.S. (2011). Multi-objective harmony search algorithm for optimal power flow problem. Electrical Power and Energy Systems, Vol. 33, pp. 745–752.

Taleizadeh, A.A., Niaki, S.T.A. and Nikousokhan, R. (2011). Constraint multiproduct joint-replenishment inventory control problem using uncertain programming. Applied Soft Computing, Vol. 11, pp. 5143–5154.

Ortiz-Astorquiza, C., Contreras, I. and Laporte^, G. (2018). Multi-level facility location problems. European Journal of Operational Research, Vol. 267, pp. 791-805.

Qi, M., Xia, M., Zhang, Y. and Miao, L. (2017). Competitive facility location problem with foresight considering service distance limitations. Computers & Industrial Engineering, Vol.112, pp. 483–491.

Veldhuizen, D.V. (1999). Multi-objective evolutionary algorithms: Classifications, analyses, and new innovations. Ph.D. Thesis. Dayton, OH: Air Force Institute of Technology Report No. AFIT/DS/ENG/99-01, 1999.

Wang, S.C., Lin, C.C., Chen, T.C. and Hsiao, H.C.W. (2018). Multi-objective competitive location problem with distance-based attractiveness for two facilities. Computers & Electrical Engineering, Vol. 71, pp.237-250.

Weber, Uber den Standort der Industrian, University of Chicago Press, 1909, translated as (in 1929): Alfred Weber’s Theory of the Location of Industries.

Wu, T.H. and Lin, J.N. (2003). Solving the competitive discretionary service facility location problem. European Journal of Operational Research, Vol.144, pp. 366–378.

Zarrinpoor, N., Fallahnezhad, MS. and Pishvaee, MS. (2018).The design of a reliable and robust hierarchical health service network using an accelerated Benders decomposition algorithm. European Journal of Operational Research, Vol.265, pp. 1013 –1032.

Zarrinpoor, N., Fallahnezhad, MS. and Pishvaee, MS. (2017). Design of a reliable hierarchical location-allocation model under disruptions for health service networks: A two-stage robust approach. Computers & Industrial Engineering, Vol.109, pp.130–150

Zarrinpoor, N. and Seifbarghy, M. (2011). A competitive location model to obtain a specific market share while ranking facilities by shorter travel time. International Journal of Advanced Manufacturing Technology, Vol. 55, 807–816.

Zhang, Y., Snyder, L.V., Ralphs, T.K. and Xue, Z. (2016). The competitive facility location problem under disruption risks. Transportation Research Part E, Vol.93, pp. 453–473.