IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i3p839-860.html
   My bibliography  Save this article

3-D Dynamic UAV Base Station Location Problem

Author

Listed:
  • Cihan Tugrul Cicek

    (Department of Industrial Engineering, Atilim University, 06830, Incek, Ankara, Turkey; Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720)

  • Zuo-Jun Max Shen

    (Department of Industrial Engineering and Operations Research, University of California, Berkeley, Berkeley, California 94720)

  • Hakan Gultekin

    (Department of Mechanical & Industrial Engineering, Sultan Qaboos University, AL-Khoud 123, Muscat, Oman; Department of Industrial Engineering, TOBB University of Economics and Technology, 06560, Cankaya, Ankara, Turkey)

  • Bulent Tavli

    (Department of Electrical and Electronics Engineering, TOBB University of Economics and Technology, 06560, Cankaya, Ankara, Turkey)

Abstract

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.

Suggested Citation

  • Cihan Tugrul Cicek & Zuo-Jun Max Shen & Hakan Gultekin & Bulent Tavli, 2021. "3-D Dynamic UAV Base Station Location Problem," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 839-860, July.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:3:p:839-860
    DOI: 10.1287/ijoc.2020.1034
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1034
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2020.1034?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Yanfeng Ouyang & Carlos F. Daganzo, 2006. "Discretization and Validation of the Continuum Approximation Scheme for Terminal System Design," Transportation Science, INFORMS, vol. 40(1), pages 89-98, February.
    2. G. F. Newell, 1971. "Dispatching Policies for a Transportation Route," Transportation Science, INFORMS, vol. 5(1), pages 91-105, February.
    3. Marshall L. Fisher, 2004. "The Lagrangian Relaxation Method for Solving Integer Programming Problems," Management Science, INFORMS, vol. 50(12_supple), pages 1861-1871, December.
    4. Brotcorne, Luce & Laporte, Gilbert & Semet, Frederic, 2003. "Ambulance location and relocation models," European Journal of Operational Research, Elsevier, vol. 147(3), pages 451-463, June.
    5. Tingting Cui & Yanfeng Ouyang & Zuo-Jun Max Shen, 2010. "Reliable Facility Location Design Under the Risk of Disruptions," Operations Research, INFORMS, vol. 58(4-part-1), pages 998-1011, August.
    6. Xin Wang & Michael K. Lim & Yanfeng Ouyang, 2017. "A Continuum Approximation Approach to the Dynamic Facility Location Problem in a Growing Market," Transportation Science, INFORMS, vol. 51(1), pages 343-357, February.
    7. Ansari, Sina & Başdere, Mehmet & Li, Xiaopeng & Ouyang, Yanfeng & Smilowitz, Karen, 2018. "Advancements in continuous approximation models for logistics and transportation systems: 1996–2016," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 229-252.
    8. Wang, Xin & Ouyang, Yanfeng, 2013. "A continuum approximation approach to competitive facility location design under facility disruption risks," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 90-103.
    9. R. Horst & N. V. Thoai, 1999. "DC Programming: Overview," Journal of Optimization Theory and Applications, Springer, vol. 103(1), pages 1-43, October.
    10. Cui, Tingting & Ouyang, Yanfeng & Shen, Zuo-Jun Max J, 2010. "Reliable Facility Location Design under the Risk of Disruptions," University of California Transportation Center, Working Papers qt5sh2c7pw, University of California Transportation Center.
    11. Dasci, Abdullah & Verter, Vedat, 2001. "A continuous model for production-distribution system design," European Journal of Operational Research, Elsevier, vol. 129(2), pages 287-298, March.
    12. Marshall L. Fisher, 2004. "Comments on ÜThe Lagrangian Relaxation Method for Solving Integer Programming ProblemsÝ," Management Science, INFORMS, vol. 50(12_supple), pages 1872-1874, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Ansari, Sina & Başdere, Mehmet & Li, Xiaopeng & Ouyang, Yanfeng & Smilowitz, Karen, 2018. "Advancements in continuous approximation models for logistics and transportation systems: 1996–2016," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 229-252.
    2. Fan, Hongqiang & Yun, Lifen & Li, Xiaopeng, 2022. "A linear-time crystal-growth algorithm for discretization of continuum approximation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 161(C).
    3. Yun, Lifen & Fan, Hongqiang & Li, Xiaopeng, 2019. "Reliable facility location design with round-trip transportation under imperfect information part II: A continuous model," Transportation Research Part B: Methodological, Elsevier, vol. 124(C), pages 44-59.
    4. Lei, Chao & Ouyang, Yanfeng, 2018. "Continuous approximation for demand balancing in solving large-scale one-commodity pickup and delivery problems," Transportation Research Part B: Methodological, Elsevier, vol. 109(C), pages 90-109.
    5. Ouyang, Yanfeng & Wang, Zhaodong & Yang, Hai, 2015. "Facility location design under continuous traffic equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 18-33.
    6. Wang, Yineng & Lin, Xi & He, Fang & Li, Meng, 2022. "Designing transit-oriented multi-modal transportation systems considering travelers’ choices," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 292-327.
    7. Jiguang Wang & Yucai Wu, 2019. "A Continuous Approximation Approach Based on Regular Hexagon Partition for the Facility Location Problem under Disruptions Risk," Complexity, Hindawi, vol. 2019, pages 1-12, February.
    8. An, Yu & Zhang, Yu & Zeng, Bo, 2015. "The reliable hub-and-spoke design problem: Models and algorithms," Transportation Research Part B: Methodological, Elsevier, vol. 77(C), pages 103-122.
    9. Jabbarzadeh, Armin & Fahimnia, Behnam & Sheu, Jiuh-Biing & Moghadam, Hani Shahmoradi, 2016. "Designing a supply chain resilient to major disruptions and supply/demand interruptions," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 121-149.
    10. Li, Xiaopeng & Ma, Jiaqi & Cui, Jianxun & Ghiasi, Amir & Zhou, Fang, 2016. "Design framework of large-scale one-way electric vehicle sharing systems: A continuum approximation model," Transportation Research Part B: Methodological, Elsevier, vol. 88(C), pages 21-45.
    11. Xiaopeng Li & Yanfeng Ouyang, 2012. "Reliable Traffic Sensor Deployment Under Probabilistic Disruptions and Generalized Surveillance Effectiveness Measures," Operations Research, INFORMS, vol. 60(5), pages 1183-1198, October.
    12. Xin Wang & Michael K. Lim & Yanfeng Ouyang, 2017. "A Continuum Approximation Approach to the Dynamic Facility Location Problem in a Growing Market," Transportation Science, INFORMS, vol. 51(1), pages 343-357, February.
    13. Michael K. Lim & Achal Bassamboo & Sunil Chopra & Mark S. Daskin, 2013. "Facility Location Decisions with Random Disruptions and Imperfect Estimation," Manufacturing & Service Operations Management, INFORMS, vol. 15(2), pages 239-249, May.
    14. Xie, Siyang & An, Kun & Ouyang, Yanfeng, 2019. "Planning facility location under generally correlated facility disruptions: Use of supporting stations and quasi-probabilities," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 115-139.
    15. Chen, Qi & Li, Xiaopeng & Ouyang, Yanfeng, 2011. "Joint inventory-location problem under the risk of probabilistic facility disruptions," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 991-1003, August.
    16. Yun Bai & Xiaopeng Li & Fan Peng & Xin Wang & Yanfeng Ouyang, 2015. "Effects of Disruption Risks on Biorefinery Location Design," Energies, MDPI, vol. 8(2), pages 1-19, February.
    17. Boyacı, Burak & Geroliminis, Nikolas, 2015. "Approximation methods for large-scale spatial queueing systems," Transportation Research Part B: Methodological, Elsevier, vol. 74(C), pages 151-181.
    18. Wang, Xin & Lim, Michael K. & Ouyang, Yanfeng, 2015. "Infrastructure deployment under uncertainties and competition: The biofuel industry case," Transportation Research Part B: Methodological, Elsevier, vol. 78(C), pages 1-15.
    19. Cui, Jianxun & Zhao, Meng & Li, Xiaopeng & Parsafard, Mohsen & An, Shi, 2016. "Reliable design of an integrated supply chain with expedited shipments under disruption risks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 143-163.
    20. Iloglu, Suzan & Albert, Laura A., 2018. "An integrated network design and scheduling problem for network recovery and emergency response," Operations Research Perspectives, Elsevier, vol. 5(C), pages 218-231.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:33:y:2021:i:3:p:839-860. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.