iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s11590-023-02013-9
A two-phase multi-objective metaheuristic for a green UAV grid routing problem | Optimization Letters Skip to main content
Springer Nature Link
Log in

A two-phase multi-objective metaheuristic for a green UAV grid routing problem

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

This paper deals with Unmanned Aerial Vehicle (UAV) routing in dynamic grid scenarios with limited battery autonomy and multiple charging stations. Inspired by a multi-criteria view of real systems, we consider different objective functions, while respecting the navigation over forbidden areas and also a real-time flight autonomy. A multi-objective variant of Variable Neighborhood Search is considered for finding sets of non-dominated solutions. Twelve neighborhood structures were developed in order to explore the solution space, including learning techniques. The latter stores known routes in order to speed up the search. A case of study was developed where UAVs have to serve clients spread throughout a grid, representing a map. Each UAV starts in a given grid point with a given battery charge, where the grid is composed by four different kinds of points: a regular one and three special (prohibited, recharge and client). Any update can happen on the routes on real-time, so the metaheuristic should handle real-time information and update the plan and graphics user interface accordingly. Any sequence of valid adjacent points forms a route, but since this yields a huge number of combinations, a preprocessing technique is proposed to pre-compute distances in a given dynamic scenario. Computational results demonstrate the performance of different variants of the proposed algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Data Availability Statement

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

Notes

  1. The G-MOVND and G-VND code can be currently accessed at https://github.com/eliaslawrence/uvrp-vnd.

  2. BRKGA implementation is available at https://github.com/eliaslawrence/uvrp-vnd.

References

  1. Adabo, G.J.: Long range unmanned aircraft system for power line inspection of Brazilian electrical system. J. Energy Power Eng. 8, 2 (2014)

    Google Scholar 

  2. Agatz, N., Bouman, P., Schmidt, M.: Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52(4), 965–981 (2018)

    Article  Google Scholar 

  3. Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6(2), 154–160 (1994)

    Article  MATH  Google Scholar 

  4. Coelho, B.N., Coelho, V.N., Coelho, I.M., Ochi, L.S., Zuidema, D., Lima, M.S., da Costa, A.R., et al.: A multi-objective green uav routing problem. Comput. Oper. Res. 88, 306–315 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  5. Coelho, V.N., Grasas, A., Ramalhinho, H., Coelho, I.M., Souza, M.J., Cruz, R.C.: An ils-based algorithm to solve a large-scale real heterogeneous fleet vrp with multi-trips and docking constraints. Eur. J. Oper. Res. 250(2), 367–376 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  6. Deng, C., Wang, S., Huang, Z., Tan, Z., Liu, J.: Unmanned aerial vehicles for power line inspection: a cooperative way in platforms and communications. J. Commun. 9(9), 687–692 (2014)

    Article  Google Scholar 

  7. Deza, M.M., Deza, E.: Encyclopedia of distances. In: Encyclopedia of distances, pp. 1–583. Springer (2009)

  8. Duarte, A., Pantrigo, J.J., Pardo, E.G., Mladenovic, N.: Multi-objective variable neighborhood search: an application to combinatorial optimization problems. J. Global Optim. 63(3), 515–536 (2015). https://doi.org/10.1007/s10898-014-0213-z

    Article  MathSciNet  MATH  Google Scholar 

  9. Everything you need to know about iiot|ge digital. https://www.ge.com/digital/blog/what-industrial-internet-things-iiot

  10. Fonseca, C.M., Paquete, L., López-Ibánez, M.: An improved dimension-sweep algorithm for the hypervolume indicator. In: 2006 IEEE International Conference on Evolutionary Computation, pp. 1157–1163. IEEE (2006)

  11. Girshick, R., Donahue, J., Darrell, T., Malik, J.: Rich feature hierarchies for accurate object detection and semantic segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 580–587 (2014)

  12. Gonçalves, J.F., Resende, M.G.: Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17(5), 487–525 (2011)

    Article  Google Scholar 

  13. Haala, N., Cramer, M., Weimer, F., Trittler, M.: Performance test on uav-based photogrammetric data collection. Proc. Int. Arch. Photogram. Remote Sens. Spat. Inf. Sci. 38(1/C22), 7–12 (2011)

    Google Scholar 

  14. Harris, A., Sluss, J.J., Refai, H.H., LoPresti, P.G.: Alignment and tracking of a free-space optical communications link to a uav. In: The 24th Digital Avionics Systems Conference, DASC 2005, vol. 1, pp. 1–C. IEEE (2005)

  15. Irizarry, J., Gheisari, M., Walker, B.N.: Usability assessment of drone technology as safety inspection tools. J. Inf. Technol. Construct. (ITcon) 17(12), 194–212 (2012)

    Google Scholar 

  16. Li, L., Ota, K., Dong, M.: Deep learning for smart industry: efficient manufacture inspection system with fog computing. IEEE Trans. Ind. Inf. 14(10), 4665–4673 (2018)

    Article  Google Scholar 

  17. Lust, T., Teghem, J.: Two-phase pareto local search for the biobjective traveling salesman problem. J. Heuristics 16(3), 475–510 (2010)

    Article  MATH  Google Scholar 

  18. Máthé, K., Buşoniu, L.: Vision and control for uavs: a survey of general methods and of inexpensive platforms for infrastructure inspection. Sensors 15(7), 14887–14916 (2015)

    Article  Google Scholar 

  19. Metni, N., Hamel, T.: A uav for bridge inspection: visual servoing control law with orientation limits. Autom. Constr. 17(1), 3–10 (2007)

    Article  Google Scholar 

  20. Michie, D., Spiegelhalter, D.J., Taylor, C., et al.: Neural and statistical classification. Mach. Learn. 13(1994), 1–298 (1994)

    MATH  Google Scholar 

  21. Nigam, N., Kroo, I.: Persistent surveillance using multiple unmanned air vehicles. In: Aerospace Conference, 2008 IEEE, pp. 1–14. IEEE (2008)

  22. Palossi, D., Loquercio, A., Conti, F., Flamand, E., Scaramuzza, D., Benini, L.: A 64-mw dnn-based visual navigation engine for autonomous nano-drones. IEEE Internet Things J. 6(5), 8357–8371 (2019)

    Article  Google Scholar 

  23. Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem: an experimental study. In: Metaheuristics for Multiobjective Optimisation, pp. 177–199. Springer (2004)

  24. Plastiras, G., Terzi, M., Kyrkou, C., Theocharidcs, T.: Edge intelligence: challenges and opportunities of near-sensor machine learning applications. In: 2018 IEEE 29th International Conference on Application-Specific Systems, Architectures and Processors (asap), pp. 1–7. IEEE (2018)

  25. Resende, M.G., Ribeiro, C.C.: Grasp: greedy randomized adaptive search procedures. In: Search Methodologies, pp. 287–312. Springer (2014)

  26. Schermer, D., Moeini, M., Wendt, O.: A Variable Neighborhood Search Algorithm for Solving the Vehicle Routing Problem with Drones. Technical Report Technische Universität Kaiserslautern, Technical report (2018)

  27. Talbi, E.G.: Metaheuristics: From Design to Implementation, vol. 74. Wiley, New York (2009)

    Book  MATH  Google Scholar 

  28. Wang, X., Poikonen, S., Golden, B.: The vehicle routing problem with drones: several worst-case results. Optim. Lett. 11(4), 679–697 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  29. Wu, H., Lyu, F., Zhou, C., Chen, J., Wang, L., Shen, X.: Optimal uav caching and trajectory in aerial-assisted vehicular networks: a learning-based approach. IEEE J. Sel. Areas Commun. 38(12), 2783–2797 (2020)

    Article  Google Scholar 

  30. Zeng, L., Li, E., Zhou, Z., Chen, X.: Boomerang: on-demand cooperative deep neural network inference for edge intelligence on the industrial internet of things. IEEE Netw. 33(5), 96–103 (2019)

    Article  Google Scholar 

  31. Zhang, J., Letaief, K.B.: Mobile edge intelligence and computing for the internet of vehicles. Proc. IEEE 108(2), 246–261 (2019)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computer Science, Universidade Federal Fluminense, Niterói, Brazil

    Elias L. Marques Jr., Igor M. Coelho & Luiz Satoru Ochi

  2. OptBlocks, Av. João Pinheiro, 274 Room 201, Belo Horizonte, MG, 30130-186, Brazil

    Vitor N. Coelho

  3. Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

    Nelson Maculan

  4. Khalifa University, Abu Dhabi, UAE

    Nenad Mladenović

  5. REDEMAT, Universidade Federal de São João del-Rei, São João del-Rei, Brazil

    Bruno N. Coelho

Authors
  1. Elias L. Marques Jr.
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vitor N. Coelho
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Igor M. Coelho
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Luiz Satoru Ochi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Nelson Maculan
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Nenad Mladenović
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Bruno N. Coelho
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Elias L. Marques Jr..

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Nenad Mladenović: in memoriam

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Marques, E.L., Coelho, V.N., Coelho, I.M. et al. A two-phase multi-objective metaheuristic for a green UAV grid routing problem. Optim Lett 17, 2233–2256 (2023). https://doi.org/10.1007/s11590-023-02013-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-023-02013-9

Keywords

Search

Navigation