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

Unmanned Aerial Vehicle Information Collection Missions with Uncertain Characteristics

Author

Listed:
  • Michael D. Moskal

    (Department of Industrial and Systems Engineering, University at Buffalo (SUNY), Buffalo, New York 14260)

  • Erdi Dasdemir

    (Department of Industrial Engineering, Hacettepe University, 06800 Ankara, Turkey)

  • Rajan Batta

    (Department of Industrial and Systems Engineering, University at Buffalo (SUNY), Buffalo, New York 14260)

Abstract

We study the unmanned aerial vehicle (UAV) route planning problem for information collection missions performed in terrains with stochastic attributes. Uncertainty is associated with the availability of information, the effectiveness of the search and collection sensors the UAV carries, and the flight time required to travel between target regions in the mission terrain. Additionally, uncertainties in flight duration vary the detection threat exposed in missions performed in nonfriendly terrains. We develop a mixed integer programming model to maximize the expected information collection while limiting the risks of not completing the mission on time and of being detected and restricting the variance imposed on flight duration. The model allows multiple path alternatives between target pairs and revisits to the same target regions. Computational experiments are performed on randomly generated instances to investigate the impact of problem parameters and mission restrictions. We also develop a case study with a military and a civilian application, each of which with different specifications. In addition, we validate that the actual performance of the optimal solution of the model is close to the result reported by the solver via a simulation study. We conclude that the developed model is robust and can be used for practical-sized missions, and the failure rate of its optimal routes in actual missions is negligibly small.

Suggested Citation

  • Michael D. Moskal & Erdi Dasdemir & Rajan Batta, 2023. "Unmanned Aerial Vehicle Information Collection Missions with Uncertain Characteristics," INFORMS Journal on Computing, INFORMS, vol. 35(1), pages 120-137, January.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:1:p:120-137
    DOI: 10.1287/ijoc.2022.1245
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2022.1245
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2022.1245?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. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, November.
    2. Raj A. Sivakumar & Rajan Batta, 1994. "The Variance-Constrained Shortest Path Problem," Transportation Science, INFORMS, vol. 28(4), pages 309-316, November.
    3. Stefan Poikonen & Bruce Golden, 2020. "The Mothership and Drone Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 249-262, April.
    4. Bruce L. Golden & Larry Levy & Rakesh Vohra, 1987. "The orienteering problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 34(3), pages 307-318, June.
    5. John Gunnar Carlsson & Siyuan Song, 2018. "Coordinated Logistics with a Truck and a Drone," Management Science, INFORMS, vol. 64(9), pages 4052-4069, September.
    6. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    7. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    8. Diclehan Tezcaner & Murat Köksalan, 2011. "An Interactive Algorithm for Multi-objective Route Planning," Journal of Optimization Theory and Applications, Springer, vol. 150(2), pages 379-394, August.
    9. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    10. Qinxiao Yu & Yossiri Adulyasak & Louis-Martin Rousseau & Ning Zhu & Shoufeng Ma, 2022. "Team Orienteering with Time-Varying Profit," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 262-280, January.
    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. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    2. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    3. Freeman, Nickolas K. & Keskin, Burcu B. & Çapar, İbrahim, 2018. "Attractive orienteering problem with proximity and timing interactions," European Journal of Operational Research, Elsevier, vol. 266(1), pages 354-370.
    4. Álvarez-Miranda, Eduardo & Luipersbeck, Martin & Sinnl, Markus, 2018. "Gotta (efficiently) catch them all: Pokémon GO meets Orienteering Problems," European Journal of Operational Research, Elsevier, vol. 265(2), pages 779-794.
    5. Wei Zhang & Kai Wang & Shuaian Wang & Gilbert Laporte, 2020. "Clustered coverage orienteering problem of unmanned surface vehicles for water sampling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(5), pages 353-367, August.
    6. Pamela J. Palomo-Martínez & M. Angélica Salazar-Aguilar & Víctor M. Albornoz, 2017. "Formulations for the orienteering problem with additional constraints," Annals of Operations Research, Springer, vol. 258(2), pages 503-545, November.
    7. Shih-Wei Lin & Sirui Guo & Wen-Jie Wu, 2024. "Applying the Simulated Annealing Algorithm to the Set Orienteering Problem with Mandatory Visits," Mathematics, MDPI, vol. 12(19), pages 1-24, October.
    8. Eva Barrena & David Canca & Leandro C. Coelho & Gilbert Laporte, 2023. "Analysis of the selective traveling salesman problem with time-dependent profits," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 31(1), pages 165-193, April.
    9. Bian, Zheyong & Liu, Xiang, 2018. "A real-time adjustment strategy for the operational level stochastic orienteering problem: A simulation-aided optimization approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 246-266.
    10. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    11. Pěnička, Robert & Faigl, Jan & Saska, Martin, 2019. "Variable Neighborhood Search for the Set Orienteering Problem and its application to other Orienteering Problem variants," European Journal of Operational Research, Elsevier, vol. 276(3), pages 816-825.
    12. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    13. Sun, Peng & Veelenturf, Lucas P. & Hewitt, Mike & Van Woensel, Tom, 2018. "The time-dependent pickup and delivery problem with time windows," Transportation Research Part B: Methodological, Elsevier, vol. 116(C), pages 1-24.
    14. Shiri, Davood & Akbari, Vahid & Hassanzadeh, Ali, 2024. "The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy," Transportation Research Part B: Methodological, Elsevier, vol. 185(C).
    15. Balcik, Burcu, 2017. "Site selection and vehicle routing for post-disaster rapid needs assessment," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 101(C), pages 30-58.
    16. Stavropoulou, F. & Repoussis, P.P. & Tarantilis, C.D., 2019. "The Vehicle Routing Problem with Profits and consistency constraints," European Journal of Operational Research, Elsevier, vol. 274(1), pages 340-356.
    17. Qinxiao Yu & Yossiri Adulyasak & Louis-Martin Rousseau & Ning Zhu & Shoufeng Ma, 2022. "Team Orienteering with Time-Varying Profit," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 262-280, January.
    18. Gunawan, Aldy & Lau, Hoong Chuin & Vansteenwegen, Pieter, 2016. "Orienteering Problem: A survey of recent variants, solution approaches and applications," European Journal of Operational Research, Elsevier, vol. 255(2), pages 315-332.
    19. Sun, Peng & Veelenturf, Lucas P. & Dabia, Said & Van Woensel, Tom, 2018. "The time-dependent capacitated profitable tour problem with time windows and precedence constraints," European Journal of Operational Research, Elsevier, vol. 264(3), pages 1058-1073.
    20. Ahmadi-Javid, Amir & Amiri, Elahe & Meskar, Mahla, 2018. "A Profit-Maximization Location-Routing-Pricing Problem: A Branch-and-Price Algorithm," European Journal of Operational Research, Elsevier, vol. 271(3), pages 866-881.

    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:35:y:2023:i:1:p:120-137. 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.