×

Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint. (English) Zbl 1458.90452

Summary: This paper models the problem of providing an unmanned aerial vehicle (UAV)-based wireless network in a disaster area as a set covering problem that takes into consideration the operational constraints and benefits of UAVs. The research presents a branch-and-price algorithm and two approximation models of the quadratic coverage radius constraint in a simple discretization and a linear pairwise-conflict constraint based on Jung’s theorem. In computational experiments, we found that the exact branch-and-price algorithm and two approximation models are applicable for realistic-scaled problems with up to 100 demand points and 2,000 m of coverage radius.

MSC:

90B80 Discrete location and assignment
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

OR-Library; QUAD01
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ahmadi-Javid, A.; Seyedi, P.; Syam, S. S., A survey of healthcare facility location, Comput. Oper. Res., 79, 223-263 (2017) · Zbl 1391.90365
[2] Aida, S.; Shindo, Y.; Utiyama, M., Rescue activity for the great east japan earthquake based on a website that extracts rescue requests from the net, Proceedings of the Workshop on Language Processing and Crisis Information 2013, 19-25 (2013), Asian Federation of Natural Language Processing
[3] Aringhieri, R.; Bruni, M.; Khodaparasti, S.; van Essen, J., Emergency medical services and beyond: addressing new challenges through a wide literature review, Comput. Oper. Res., 78, 349-368 (2017) · Zbl 1391.90366
[4] Beasley, J. E., OR-library: distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 11, 1069-1072 (1990)
[5] Bélanger, V.; Ruiz, A.; Soriano, P., Recent optimization models and trends in location, relocation, and dispatching of emergency medical vehicles, Eur. J. Oper. Res., 272, 1, 1-23 (2019) · Zbl 1403.90469
[6] Boonmee, C.; Arimura, M.; Asada, T., Facility location optimization model for emergency humanitarian logistics, Int. J. Disaster Risk Reduct., 24, 485-498 (2017)
[7] Borndörfer, R.; Weismantel, R., Set packing relaxations of some integer programs, Math. Program., 88, 3, 425-450 (2000) · Zbl 1018.90028
[8] Brotcorne, L.; Laporte, G.; Semet, F., Ambulance location and relocation models, Eur. J. Oper. Res., 147, 3, 451-463 (2003) · Zbl 1037.90554
[9] Brunkard, J.; Namulanda, G.; Ratard, R., Hurricane Katrina deaths, Louisiana, 2005, Disaster Med. Public Health Prep., 2, 4, 215-223 (2008)
[10] Calik, H.; Labbé, M.; Yaman, H., p-center problems, (Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location Science (2015), Springer), 79-92
[11] Capoyleas, V.; Rote, G.; Woeginger, G., Geometric clusterings, J. Algorithms, 12, 2, 341-356 (1991) · Zbl 0734.68092
[12] Chand, G. S.L. K.; Lee, M.; Shin, S. Y., Drone based wireless mesh network for disaster/military environment, J. Comput. Commun., 6, 4, 44-52 (2018)
[13] Chandrashekar, K.; Dekhordi, M. R.; Baras, J. S., Providing full connectivity in large ad-hoc networks by dynamic placement of aerial platforms, IEEE MILCOM 2004. Military Communications Conference, 2004., 1429-1436 (2004), IEEE
[14] Chowdhury, S.; Emelogu, A.; Marufuzzaman, M.; Nurre, S. G.; Bian, L., Drones for disaster response and relief operations: a continuous approximation model, Int. J. Prod. Econ., 188, 167-184 (2017)
[15] Comley, W. J., The location of ambivalent facilities: use of a quadratic zero-one programming algorithm, Appl. Math. Model., 19, 1, 26-29 (1995) · Zbl 0828.90070
[16] Daskin, M. S.; Maass, K. L., The p-median problem, (Laporte, G.; Nickel, S.; Saldanha da Gama, F., Location Science (2015), Springer), 21-45
[17] Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column Generation (2006), Springer
[18] Drezner, Z.; Klamroth, K.; Schöbel, A.; O. Wesolowsky, G., The weber problem, (Drezner, Z.; Hamacher, H. W., Facility Location: Applications and Theory (2001), Springer), 1-36 · Zbl 1041.90023
[19] Elzinga, J.; Hearn, D.; Randolph, W. D., Minimax multifacility location with euclidean distances, Transp. Sci., 10, 4, 321-336 (1976)
[20] Gendreau, M.; Manerba, D.; Mansini, R., The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: a branch-and-price approach, Eur. J. Oper. Res., 248, 1, 59-71 (2016) · Zbl 1346.90112
[21] Grötschel, M.; Wakabayashi, Y., A cutting plane algorithm for a clustering problem, Math. Program., 45, 1, 59-96 (1989) · Zbl 0675.90072
[22] Gu, Y.; Zhou, M.; Fu, S.; Wan, Y., Airborne WiFi networks through directional antennae: an experimental study, 2015 IEEE Wireless Communications and Networking Conference (WCNC), 1314-1319 (2015), IEEE
[23] Heinzelman, J.; Waters, C., Crowdsourcing crisis information in disaster-affected Haiti, Technical Report (2010), United States Institute of Peace
[24] Ho, D.-T.; Grøtli, E. I.; Sujit, P. B.; Johansen, T. A.; Sousa, J. B., Optimization of wireless sensor network and UAV data acquisition, J. Intell. Robot. Syst., 78, 1, 159-179 (2015)
[25] Hoffman, K. L.; Padberg, M., Solving airline crew scheduling problems by branch-and-cut, Manag. Sci., 39, 6, 657-682 (1993) · Zbl 0783.90051
[26] Holley, P., 2017. Water is swallowing us up: In Houston, desperate flood victims turn to social media for survival, The Washington Post. (accessed 9 September 2019). https://wapo.st/2vw1F4X?.
[27] Ji, X.; Mitchell, J. E., Finding optimal realignments in sports leagues using a branch-and-cut-and-price approach, Int. J. Oper. Res., 1, 1-2, 101-122 (2005) · Zbl 1100.90053
[28] Ji, X.; Mitchell, J. E., Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, Discrete Optim., 4, 1, 87-102 (2007) · Zbl 1169.90469
[29] Johnson, E. L.; Mehrotra, A.; Nemhauser, G. L., Min-cut clustering, Math. Program., 62, 1, 133-151 (1993) · Zbl 0807.90117
[30] Jonkman, S. N.; Maaskant, B.; Boyd, E.; Levitan, M. L., Loss of life caused by the flooding of new orleans after hurricane Katrina: analysis of the relationship between flood characteristics and mortality, Risk Anal., 29, 5, 676-698 (2009)
[31] Jung, H., Ueber die kleinste Kugel, die eine räumliche Figur einschliesst., J. Reine Angew. Math., 123, 241-257 (1901) · JFM 32.0296.05
[32] Kim, D.; Lee, K.; Moon, I., Stochastic facility location model for drones considering uncertain flight distance, Ann. Oper. Res., 1-20 (2018)
[33] Kim, S.; Moon, I., Traveling salesman problem with a drone station, IEEE Trans. Syst. Man. Cybern., 49, 1, 42-52 (2019)
[34] Maaskant, B.; Jonkman, S. N.; Boyd, E., Fatalities due to hurricane Katrina (2005), Technical Report (2018), TU Delft
[35] Manerba, D.; Mansini, R., The nurse routing problem with workload constraints and incompatible services, IFAC-PapersOnLine, 49, 12, 1192-1197 (2016)
[36] Mehrotra, A.; Trick, M. A., Cliques and clustering: a combinatorial approach, Oper. Res. Lett., 22, 1, 1-12 (1998) · Zbl 0911.90337
[37] Mozaffari, M.; Saad, W.; Bennis, M.; Debbah, M., Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage, IEEE Commun. Lett., 20, 8, 1647-1650 (2016)
[38] Mozaffari, M.; Saad, W.; Bennis, M.; Debbah, M., Unmanned aerial vehicle with underlaid device-to-device communications: performance and tradeoffs, IEEE Trans. Wirel. Commun., 15, 6, 3949-3963 (2016)
[39] Osman, I. H.; Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search, Int. Trans. Oper. Res., 1, 3, 317-336 (1994) · Zbl 0857.90107
[40] Periyasamy, S.; Khara, S.; Thangavelu, S., Balanced cluster head selection based on modified k-means in a distributed wireless sensor network, Int. J. Distrib. Sens. Netw., 12, 3, 1-11 (2016)
[41] Plastria, F., Continuous covering location problems, (Drezner, Z.; Hamacher, H. W., Facility Location: Applications and Theory (2001)), 37-79 · Zbl 1013.90089
[42] Ryan, D. M.; Foster, B. A., An integer programming approach to scheduling, (Wren, A., Computer Scheduling of Public Transport: Urban Passenger Vehicle and Crew Scheduling (1981), North-Holland), 269-280
[43] Sadykov, R.; Vanderbeck, F., Bin packing with conflicts: a generic branch-and-Pprice algorithm, INFORMS J. Comput., 25, 2, 244-255 (2012)
[44] Sasikumar, P.; Khara, S., K-means clustering in wireless sensor networks, 2012 Fourth International Conference on Computational Intelligence and Communication Networks, 140-144 (2012), IEEE
[45] Simchi-Levi, D.; Chen, X.; Bramel, J., The Logic of Logistics: Theory, Algorithms, and Applications for Logistics and Supply Chain Management (2005), Springer · Zbl 1178.90046
[46] Toregas, C.; Swain, R.; ReVelle, C.; Bergman, L., The location of emergency service facilities, Oper. Res., 19, 6, 1363-1373 (1971) · Zbl 0224.90048
[47] Vance, P. H., Branch-and-price algorithms for the one-dimensional cutting stock problem, Comput. Optim. Appl., 9, 3, 211-228 (1998) · Zbl 0897.90161
[48] Vance, P. H.; Barnhart, C.; Johnson, E. L.; Nemhauser, G. L., Solving binary cutting stock problems by column generation and branch-and-bound, Comput. Optim. Appl., 3, 2, 111-130 (1994) · Zbl 0801.90080
[49] Vanderbeck, F.; Wolsey, L. A., Reformulation and decomposition of integer programs, (Jünger, M.; Liebling, T. M.; Naddef, D.; Nemhauser, G. L.; Pulleyblank, W. R.; Reinelt, G.; Rinaldi, G.; Wolsey, L. A., 50 Years of Integer Programming 1958-2008 (2010), Springer), 431-502 · Zbl 1187.90207
[50] Wallop, H., 2011. Japan earthquake: how Twitter and Facebook helped, The Telegraph. (accessed 9 September 2019). https://www.telegraph.co.uk/technology/twitter/8379101/Japan-earthquake-how-Twitter-and-Facebook-helped.html.
[51] Welzl, E., Smallest enclosing disks (balls and ellipsoids), (Maurer, H., New Results and New Trends in Computer Science (1991), Springer), 359-370
[52] Wu, Q.; Zeng, Y.; Zhang, R., Joint trajectory and communication design for multi-UAV enabled wireless networks, IEEE Trans. Wirel. Commun., 17, 3, 2109-2121 (2018)
[53] Zeng, Y.; Xu, X.; Zhang, R., Trajectory design for completion time minimization in UAV-enabled multicasting, IEEE Trans. Wirel. Commun., 17, 4, 2233-2246 (2018)
[54] Zeng, Y.; Zhang, R.; Lim, T. J., Throughput maximization for UAV-enabled mobile relaying systems, IEEE Trans. Commun., 64, 12, 4983-4996 (2016)
[55] Zhan, C.; Zeng, Y.; Zhang, R., Energy-efficient data collection in UAV enabled wireless sensor network, IEEE Wirel. Commun. Lett., 7, 3, 328-331 (2018)
[56] Zorbas, D.; Di Puglia Pugliese, L.; Razafindralambo, T.; Guerriero, F., Optimal drone placement and cost-efficient target coverage, J. Netw. Comput. Appl., 75, 16-31 (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.