Modelling and Solving the Location Problem of Fire Launching Sites

Document Type : Original Article

Authors

Abstract

Using the mathematical and optimization models has significant impact in military strategic decision making problems such as finding location of domestic fire launching site of hard and soft kill. In this paper, an integer linear programming model is developed for location problem of fire launching sites with goal of maximizing the expected value of the target accessibility and protection of strategic realms. Also, two     metaheuristic algorithms based on genetic algorithm and particle swarm optimization algorithm have been designed to solve the problem. The computational results of these methods have been compared to exact answers from modeling. It is revealed that with time limit of 60 seconds, the developed genetic algorithm and particle swarm optimization have 0.16% and 0.07% average deviation from optimal solutions,          indicating they perform efficiently.  
 

Keywords


A. Turan, “algorithms for the weapon-target allocation problem,” PhD dissertation, Middle East Technical University, 2012.
[1]
R. Farahani and M. Hekmatfar, “Facility location: concepts, models, algorithms and case studies. 2009,”                   Physica-Verlag, Heidelberg, 2009.
[2]
L. Cooper, “Location-allocation problems,” Operations research, vol. 11, no. 3, pp. 331-343, 1963.
[3]
S. L. Hakimi, “Optimum distribution of switching centers in a communication network and some related graph theoretic problems,” Operations Research, vol. 13, no. 3, pp. 462-475, 1965.
[4]
R. E. Kuenne and R. M. Soland, “Exact and approximate solutions to the multisource Weber problem,” Mathematical Programming, vol. 3, no. 1, pp. 193-209, 1972.
[5]
A. T. Murray and R. L. Church, “Applying simulated annealing to location-planning models,” Journal of Heuristics, vol. 2, no. 1, pp. 31-53, 1996.
[6]
J. Brimberg and N. Mladenovic, “Solving the continuous location-allocation problem with tabu search,” Studies in Locational Analysis, vol. 8, no. 23-32, p. 41, 1996.
[7]
R. K. Ahuja, A. Kumar, K. C. Jha, and J. B. Orlin, “Exact and heuristic algorithms for the weapon-target assignment problem,” Operations Research, vol. 55, no. 6, pp.           1136–1146, 2007.
[8]
S. P. Lioyd and H. S. Witsenhausen, “Weapon allocation is NP-Complete,” IEEE Summer Simulation Conference, Reno, Nevada, 1986.
[9]
P. A. Hosein, J. T. Walton, and M. Athans, “Dynamic       weapon-target assignment problems with vulnerable C2 nodes,” Massachusetts inst of tech cambridge lab for information and decision systems, pp. 1-10, 1988.
[10]
C. Huaiping, J. Liu, Y. Chen, and H. Wang, “Survey of the research on dynamic weapon-target assignment problem,” Journal of Systems Engineering and Electronics, vol. 17, no. 3, pp. 559-565, 2006.
[11]
G. G. denBroeder Jr, R. E. Ellison, and L. Emerling, “On optimum target assignments,” Operation Research, vol. 7, pp. 322–326, 1958.
[12]
J. D. Katter, “A solution of the multi-weapon, multi-target assignment problem,” WP-26597, The MITRE Co., Bedford, MA, 1986.
[13]
S. C. Chang, R. M. James, and J. J. Shaw, “Assignment algorithm for kinetic energy weapons in boost defense,” Proceedings IEEE 26th Conference of Decision and Control, Los Angeles, CA, pp. 1678–1683, 1987.
[14]
D. Orlin, “Optimal weapons allocation against layered defenses,” Naval Research Logist, vol. 34, pp. 605–616, 1987.
[15]
D. A. Castanon, “Advanced weapon-target assignment algorithm,” Quarterly report #TR-337, Alpha Tech., Inc, Burlington, MA, 1987.
[16]
E. Wacholder, “A neural network-based optimization algorithm for the static weapon-target assignment problem, ORSA Journal Comput., vol. 4, pp. 232–246, 1989.
[17]
D. J. Green, J. T. Moore, and J. J. Borsi, “An integer solution heuristic for the arsenal exchange model (AEM),” Military Operation Research Society, vol. 3, no. 2, pp.           5–16, 1997.
[18]
Z. J. Lee, S. F. Su, and C. Y. Lee, “An immunity-based ant colony optimization algorithm for solving weapon–target assignment problem, Applied Soft Computing,” vol. 2, pp. 39–47, 2002.
[19]
Z. J. Lee and W. L. Lee, “A hybrid search algorithm of ant colony optimization and genetic algorithm applied to Weapon-Target Assignment Problems,” Intelligent Data Engineering and Automated Learning, Springer Berlin Heidelberg, pp. 278-285, 2003.
[20]
L. Zhen, S. Jain-gue, and G. Xiao-guang, “Compact genetic algorithm and its application in WTA problem,” Computer Engineering and Application, vol. 44, no. 3, pp. 229-231, 2008.
[21]
G. Cho, “Hybrid Nested Partitions method with Intelligent Greedy Search for solving Weapon-Target Assignment Problem,” Graduate Theses and Dissertations, Paper 10757, 2009.
[22]
D. P. Lötter, I. Nieuwoudt, and J. H. Van Vuuren, “A multiobjective approach towards weapon assignment in a ground-based air defence environment,” ORiON: The Journal of ORSSA, vol. 29, no. 1, pp. 31-54, 2013.
[23]
J. M. Rosenberger, H. S. Hwang, and R. P. Pallerla, “The Generalized Weapon Target Assignment Problem,” 10th International Command and Control Research and Technology Symposium, McLean, VA, 2005.
[24]
A. A Miri and M. Lotfi, “A Dynamic Model for Doing of an Integrated Naval Defence Network Based on Independency Of Sites,” 1st national conference of science and technology of naval combat systems, Mashhad, Iran, 2011. (In Percian)
[25]
M. Peymankar, “Local Searches and Tabu Search Algorithms for Concurrent Location and Weapons Assignment Problems of Warships,” M. Sc dissertation, Ferdowsi university of Mashhad, 2013. (In Persian)
[26]
M. Ranjbar and M. Peymankar, “Weapon assignment and time scheduling of fire stations,” Technical Report, Ferdowsi University of Mashhad, Mashhad, 2016. (In Persian)
[27]
J. H. Holland, “Adaptation in natural and artificial systems,” An introductory analysis with applications to biology, control, and artificial intelligence: U Michigan Press, 1975.
[28]
J. Kennedy, “Particle swarm optimization,” in Encyclopedia of machine learning, ed: Springer, pp.        760-766, 2011.
[29]
J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation, 1997 IEEE International Conference on, pp. 4104-4108, 1997.
[30]