Planar Maximal Covering Location Problem with Inclined Ellipses

Abstract:

aximum coverage location problem is considered in this study. Extension of this problem is investigated for situations that coverage areas are elliptical; these ellipses can locate anywhere on the plane with any angle. Mixed integer nonlinear programming (MINLP) is applied for formulation. This problem can be used in many practical situations such as locating wireless transmitter towers. A heuristic algorithm named MCLPEA for solving this problem was designed. This algorithm can produce very good results in efficient running time. Finally, the comparison of the results for this study was carried done.

• Periodical: Applied Mechanics and Materials (Volumes 110-116)
• Pages: 4861-4866
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.110-116.4861
• Online since: October 2011
• Authors: Hadi Charkhgard, Mohammad R. Akbari Jokar
• Keywords: Elliptical Coverage, Heuristic Algorithm , Inclined Ellipses, Maximal Covering Location Problem, Mixed Integer Nonlinear Programming

References

[1] Aguado-Agelet, F., Varela, A. M., Alvarez-Vazquez, L. J., Hernando, J. M., & Formella, A. (2002). Optimization methods for optimal transmitter Locations in a mobile Wireless system. IEEE Transactions and Vehicular Technology, 51(6), 1316-1321.

DOI: 10.1109/tvt.2002.804844

[2] Canbolat, M., S., & Massow, M., V. (2009). Plannar maximal covering with ellipses. Journal of Computers & Industrial Engineering, 57, 201-208.

DOI: 10.1016/j.cie.2008.11.015

[3] Church, R. (1984). The planar maximal covering location problem. Journal of Regional Science, 24, 185-201.

[4] Church, R., & ReVelle, C. (1974). The maximal covering location problem. Papers of the regional Science Assosiation, 6(32), 101-118.

DOI: 10.1007/bf01942293

[5] Current, J. R., & O'Kelly, M.E. (1992). Locating emergency warning sirens. Decision Siences, 23, 221-234.

DOI: 10.1111/j.1540-5915.1992.tb00385.x

[6] Drezner. Z., & Wesolowsky, G. O. (1997). On the best location of signal detectors. IIE Transactions, 29, 1007-1015.

DOI: 10.1080/07408179708966419

[7] Mehrez, A., & Stulman, A. (1982).

[1] [25] [2] 3. 53.

[6] 0. 3798271.

[1] [4] [2] [1] [50] [7] 8. 53.

[10] 0. 76485728.

[3] [10] 5. 2.

[1] 100.

[12] 14. 6.

[17] 2. 4324.

[3] [17] 12. 2.

[2] [25] [3] 6. 43.

[10] 0. 57296625 1, 2.

[10] 4. 8.

[2] [50] [12] 14. 6.

[19] 1. 847339 1, 3.

[19] 12. 2.

[2] 100.

[23] 27. 1.

[31] 7. 12436 1, 3.

[31] 24. 2 TABLE VI. S. Canbolat, Michael von Massow[2] k n # of points covered Selected facility(ies) Average runnig times(s) Optimality Worst Average Best.

[1] [25] [2] 2. 5.

[3] [1] 1. 6 Optimal.

[1] [50] [6] 7. 9.

[9] [3] 1. 92 optimal.

[1] 100.

[12] 15. 8.

[17] [3] 2. 76 optimal.

[2] [25] [6] 7. 3.

[9] 1, 2 2. 41 optimal.

[2] [50] [12] 14. 7.

[15] 1, 3 4. 12 Best integer solution.

[2] 100.

[23] 26. 2.

[28] 2, 3 7. 28 Best integer solution.