TY - JOUR
T1 - 3-D dynamic UAV base station location problem
AU - Cicek, Cihan Tugrul
AU - Shen, Zuo Jun Max
AU - Gultekin, Hakan
AU - Tavli, Bulent
N1 - Funding Information:
History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms and Applications. Funding: C. Tugrul Cicek acknowledges the support of Fulbright Commission Turkey under the Visiting Researcher Scholarship Program [Grant VSR2018].
Publisher Copyright:
Copyright: © 2021 INFORMS
PY - 2021/6
Y1 - 2021/6
N2 - We address a dynamic covering location problem of an unmanned aerial vehicle base station (UAV-BS), in which the location sequence of a single UAV-BS in a wireless communication network is determined to satisfy data demand arising from ground users. This problem is especially relevant in the context of smart grid and disaster relief. The vertical movement ability of the UAV-BS and nonconvex covering functions in wireless communication restrict utilizing classical planar covering location approaches. Therefore, we develop new formulations to this emerging problem for a finite time horizon to maximize the total coverage. In particular, we develop a mixed-integer nonlinear programming formulation that is nonconvex in nature and propose a Lagrangean decomposition algorithm (LDA) to solve this formulation. Because of the high complexity of the problem, the LDA is still unable to find good local solutions to large-scale problems. Therefore, we develop a continuum approximation (CA) model and show that CA would be a promising approach in terms of both computational time and solution accuracy. Our numerical study also shows that the CA model can be a remedy to build efficient initial solutions for exact solution algorithms. Summary of Contribution: This paper addresses a facet of mixed integer nonlinear programming formulations. Dynamic facility location problems (DFLPs) arise in a wide range of applications. However, classical DFLPs typically focus on the two-dimensional spaces. Emerging technologies in wireless communication and some other promising application areas, such as smart grids, have brought new location problems that cannot be solved with classical approaches. For practical reasons, many research attempts to solve this new problem, especially by researchers whose primary research area is not OR, have seemed far from analyzing the characteristics of the formulations. Rather, solution-oriented greedy heuristics have been proposed. This paper has two main objectives: (i) to close the gap between practical and theoretical sides of this new problem with the help of current knowledge that OR possesses to solve facility location problems and (ii) to support the findings with an exhaustive computational study to show how these findings can be applied to practice.
AB - We address a dynamic covering location problem of an unmanned aerial vehicle base station (UAV-BS), in which the location sequence of a single UAV-BS in a wireless communication network is determined to satisfy data demand arising from ground users. This problem is especially relevant in the context of smart grid and disaster relief. The vertical movement ability of the UAV-BS and nonconvex covering functions in wireless communication restrict utilizing classical planar covering location approaches. Therefore, we develop new formulations to this emerging problem for a finite time horizon to maximize the total coverage. In particular, we develop a mixed-integer nonlinear programming formulation that is nonconvex in nature and propose a Lagrangean decomposition algorithm (LDA) to solve this formulation. Because of the high complexity of the problem, the LDA is still unable to find good local solutions to large-scale problems. Therefore, we develop a continuum approximation (CA) model and show that CA would be a promising approach in terms of both computational time and solution accuracy. Our numerical study also shows that the CA model can be a remedy to build efficient initial solutions for exact solution algorithms. Summary of Contribution: This paper addresses a facet of mixed integer nonlinear programming formulations. Dynamic facility location problems (DFLPs) arise in a wide range of applications. However, classical DFLPs typically focus on the two-dimensional spaces. Emerging technologies in wireless communication and some other promising application areas, such as smart grids, have brought new location problems that cannot be solved with classical approaches. For practical reasons, many research attempts to solve this new problem, especially by researchers whose primary research area is not OR, have seemed far from analyzing the characteristics of the formulations. Rather, solution-oriented greedy heuristics have been proposed. This paper has two main objectives: (i) to close the gap between practical and theoretical sides of this new problem with the help of current knowledge that OR possesses to solve facility location problems and (ii) to support the findings with an exhaustive computational study to show how these findings can be applied to practice.
KW - Continuum approximation
KW - Dynamic location
KW - Lagrangean decomposition
KW - Nonlinear optimization
KW - UAV base station
UR - http://www.scopus.com/inward/record.url?scp=85112797408&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85112797408&partnerID=8YFLogxK
U2 - 10.1287/ijoc.2020.1034
DO - 10.1287/ijoc.2020.1034
M3 - Article
AN - SCOPUS:85112797408
SN - 1091-9856
VL - 33
SP - 839
EP - 860
JO - INFORMS Journal on Computing
JF - INFORMS Journal on Computing
IS - 3
ER -