On Defensive Location Problem and its Solution Using Heuristic Methods


  • Omid Kardani Department of Applied Mathematics, Khajeh Nasir Toosi University of Technology, Tehran, Iran
  • Navid Kardani School of Engineering, Islamic Azad University, Tehran, Iran


competitive facility location, defensive location problem, constraint global optimization, heuristic methods, improved electromagnetism-like mechanism


A new approach to the defensive location problem (DLP) is proposed which aims to generalize the problem into a global optimization problem, hence the name “generalized DLP†(GDLP). In DLP, a decision maker locates defensive facilities in a network in order to prevent their enemies from reaching an important site called a core. The fact that whether or not a defensive facility is located on a given vertex of the network leads to formulating DLP as a bi-level 0-1 programming problem. In GDLP, on the other hand, the defensive capacity allocated to vertices of the network can be any real number in a continuous interval. This gives rise to the formulation of GDLP as a global constraint optimization problem. Furthermore, simple but efficient heuristic solution method based on Improved Electromagnetism-like Mechanism tailored for GDLPs is proposed. The efficiency of the proposed solving methods is then shown by applying to some numerical examples of GDLP.



M. M. Ali and M. Golalikhani, “An electromagnetism-like method for nonlinearly constrained global optimization,†Computers & Mathematics with Applications, vol. 60, no. 8, pp. 2279–2285, 2010.

M. G. Alikhani, N. Javadian and R. Tavakkoli-Moghaddam, “A novel hybrid approach combining electromagnetism-like method with Solis and Wets local search for continuous optimization problems,†Journal of Global Optimization, vol. 44, no. 2, pp. 227–234, 2009.

Ş. İ. Birbil and S. C. Fang, “An Electromagnetism-like mechanism for global optimization,†Journal of Global Optimization, vol. 25, pp. 263–282, 2003.

J. F. Bard, Practical Bi-level Optimization: Algorithm and Applications, Dordrecht: Kluwer Academic Publishers, 1998.

O. Ben-Ayed, “Bilevel linear programming,†Computers and Operation Research, vol. 20, pp.485-501, 1993.

R. Chelouah and P. Siarry, “A continuous genetics algorithm designed for the global optimization of multimodal functions,†Journal of Heuristics, vol. 6, pp. 191–213, 2000.

T .H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms, MIT Press and McGraw Hill, USA, 2001.

S. Dempe and A. B. Zemkoho, “The bilevel programming problem: reformulations, constraint qualifications and optimality conditions,†Mathematical Programming , vol. 138, no. 1-2, pp. 447-473, 2013.

Z. Drezner and T. Drezner, “Modelling lost demand in competitive facility location,†Journal of Operational Research Society, vol. 63, pp. 201-206, 2012.

Z. Drezner and H. W. Hamacher, Facility location: application and theory, Springer, USA, 2004.

H. Küçükaydin, N. Aras and I. K. Altmel, “Competitive facility location problem with attractiveness adjustment of the follower: a bilevel programming model and its solution,†European Journal of Operational Research, vol. 208, no. 3, pp. 206–220, 2011.

H. Küçükaydin, N. Aras and I. K. Altmel, “A leader–follower game in competitive facility location,†Computers & Operations Research, vol. 39, no. 2, pp. 437–448, 2012.

Y. Levin and A. Ben-Israel, “A heuristic method for large-scale multi-facility location problems,†Computers and Operations Research, vol. 31, pp. 257–272, 2004.

D. G. Luenberger and Y. Ye, Linear and nonlinear programming, Springer, USA, 2008.

Z. Q. Luo, J. S. Pang and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge: Cambridge University Press, 1996.

N. Mladenović, M. Dražić, V. KovaÄevic-VujÄić and M. ÄŒangalović, “General variable neighborhood search for the continuous optimization,†European Journal of Operational Research, vol. 191, pp. 753–770, 2008.

A. M. A. C. Rocha and E. M. G. P. Fernandes, “Modified movement force vector in an electromagnetism-like mechanism for global optimization,†Optimization Methods and Software, vol. 24, no. 2, pp. 253-270, 2009.

R. Suárez-Vega, D. R. Santos-Peñate, P. Dorta-González and M. Rodríguez-Díaz, “A multi-criteria GIS based procedure to solve a network competitive location problem,†Applied Geography, vol. 31, no. 1, pp. 282–291, 2011.

T. Uno and H. Katagiri, “Single- and multi-objective defensive location problems on a network,†European Journal of Operational Research, vol. 188, pp. 76–84, 2008.

Uno, H. Katagiri and K. Kato, "A Competitive Facility Location Problem on a Network with Fuzzy Random Weights," Engineering Letters, vol. 19, no. 2, pp. 143-146, 2011.

T. Uno, H. Katagiri, K. Kato, “A Facility Location for Fuzzy Random Demands in a Competitive Environment,†IAENG International Journal of Applied Mathematics, vol. 40, no. 3, pp. 172-177, 2010.

T. Uno, H. Katagiri, K. Kato, “Competitive Facility Location with Fuzzy Random Demands,†IAENG Transactions on Engineering Technologies, vol. 5, pp. 99-108, America Institute of Physics, 2010.

T. Uno, H. Katagiri and K. Kato, “Competitive facility location with random demands,†IAENG Transactions on Engineering Technologies, vol. 3, pp. 83-93, America Institute of Physics, 2009.

T. Uno and K. Kato, “An interactive fuzzy satisficing method for multiobjective stochastic defensive location problems,†in Proc. of FUZZ-IEEE, pp. 879–883, 2011.

R. Zanjirani-Farahani, M. Steadie-Safi and N. Asgari, “Multiple criteria facility location problem: A survey,†Applied Mathematical Modelling, vol. 34, no. 7, pp. 1689-1709, 2010.

C. Zhang, X. Li, L. Gao and Q. Wu, “Improved electromagnetism-like mechanism algorithm for constrained optimization,†Expert Systems with Applications, In Press. Available: http://www.sciencedirect.com/science/article/pii/S0957417413002753




How to Cite

Kardani, O., & Kardani, N. (2013). On Defensive Location Problem and its Solution Using Heuristic Methods. Asian Journal of Applied Sciences, 1(2). Retrieved from https://ajouronline.com/index.php/AJAS/article/view/136