{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:14:42Z","timestamp":1760145282288,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T00:00:00Z","timestamp":1719532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Unmanned aerial vehicles (UAVs, drones) are not just a technological achievement based on modern ideas of artificial intelligence; they also provide a sustainable solution for green technologies in logistics, transport, and material handling. In particular, using battery-powered UAVs to transport products can significantly decrease energy and fuel expenses, reduce environmental pollution, and improve the efficiency of clean technologies through improved energy-saving efficiency. We consider the problem of maximizing the average environmental benefit of a fleet of drones given a periodic schedule of tasks performed by the fleet of vehicles. To solve the problem efficiently, we formulate it as an optimization problem on an infinite periodic graph and reduce it to a special type of parametric assignment problem. We exactly solve the problem under consideration in O(n3) time, where n is the number of flights performed by UAVs.<\/jats:p>","DOI":"10.3390\/a17070283","type":"journal-article","created":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T08:17:29Z","timestamp":1719821849000},"page":"283","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximizing the Average Environmental Benefit of a Fleet of Drones under a Periodic Schedule of Tasks"],"prefix":"10.3390","volume":"17","author":[{"given":"Vladimir","family":"Kats","sequence":"first","affiliation":[{"name":"Institute for Industrial Mathematics, Ben Gurion University, Beer-Sheva 8424902, Israel"}]},{"given":"Eugene","family":"Levner","sequence":"additional","affiliation":[{"name":"School of Computer Science, Holon Institute of Technology, Holon 5810201, Israel"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Engesser, V., Rombaut, E., Vanhaverbeke, L., and Lebeau, P. (2023). Autonomous Delivery Solutions for Last-Mile Logistics Operations: A Literature Review and Research Agenda. Sustainability, 15.","DOI":"10.3390\/su15032774"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1080\/13675567.2021.1981273","article-title":"Drones for supply chain management and logistics: A review and research agenda","volume":"26","author":"Rejeb","year":"2021","journal-title":"Int. J. Logist. Res. Appl."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1080\/00207543.2021.1840148","article-title":"Ripple effect and supply chain disruption management: New trends and research directions","volume":"59","author":"Dolgui","year":"2021","journal-title":"Int. J. Prod. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1080\/00207543.2021.2002969","article-title":"5G in digital supply chain and operations management: Fostering flexibility, end-to-end connectivity and real-time visibility through internet-of-everything","volume":"60","author":"Dolgui","year":"2021","journal-title":"Int. J. Prod. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"48572","DOI":"10.1109\/ACCESS.2019.2909530","article-title":"Unmanned Aerial Vehicles (UAVs): A Survey on Civil Applications and Key Research Challenges","volume":"7","author":"Shakhatreh","year":"2019","journal-title":"IEEE Access"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Manfreda, S., McCabe, M.F., Miller, P.E., Lucas, R., Madrigal, V.P., Mallinis, G., Ben Dor, E., Helman, D., Estes, L., and Ciraolo, G. (2018). On the Use of Unmanned Aerial Systems for Environmental Monitoring. Remote Sens., 10.","DOI":"10.20944\/preprints201803.0097.v1"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"102998","DOI":"10.1016\/j.futures.2022.102998","article-title":"Agriculture 4.0: A systematic literature review on the paradigm, technologies and benefits","volume":"142","author":"Maffezzoli","year":"2022","journal-title":"Futures"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Garey, M., Graham, R., and Johnson, D. (1976, January 3\u20135). Some NP-complete geometric problems. Proceedings of the 8th Annual ACM Symposium on Theory of Computing, Hershey, PA, USA.","DOI":"10.1145\/800113.803626"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/net.21628","article-title":"Dynamic vehicle routing problems: Three decades and counting","volume":"67","author":"Psaraftis","year":"2015","journal-title":"Networks"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/j.ejor.2022.10.015","article-title":"Drone location and vehicle fleet planning with trucks and aerial drones","volume":"308","author":"Rave","year":"2023","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1016\/j.trc.2018.05.011","article-title":"Dynamic operations and pricing of electric unmanned aerial vehicle systems and power networks","volume":"92","author":"Zhang","year":"2018","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1109\/MITS.2019.2919500","article-title":"Demand Estimation for Aerial Vehicles in Urban Settings","volume":"11","author":"Balac","year":"2019","journal-title":"IEEE Intell. Transp. Syst. Mag."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/net.21818","article-title":"Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey","volume":"72","author":"Otto","year":"2018","journal-title":"Networks"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"123476","DOI":"10.1109\/ACCESS.2023.3329195","article-title":"Drone-Based Delivery Systems: A Survey on Route Planning","volume":"11","author":"Attenni","year":"2023","journal-title":"IEEE Access"},{"key":"ref_15","unstructured":"She, R.F. (2023). Design of Freight Logistics Services in the Era of Autonomous Transportation. [Doctoral Dissertation, University of Illinois at Urbana-Champaign]."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/nav.3800010309","article-title":"Minimizing the number of tankers to meet a fixed schedule","volume":"1","author":"Dantzig","year":"1954","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ford, L.R., and Fulkerson, D.R. (1962). Flows in Networks, Princeton University Press.","DOI":"10.1515\/9781400875184"},{"key":"ref_18","first-page":"538","article-title":"Minimal quantity of operators for serving a homogeneous linear technological process","volume":"39","author":"Karzanov","year":"1978","journal-title":"Autom. Remote Control"},{"key":"ref_19","first-page":"538","article-title":"An exact optimal cyclic scheduling algorithm for multi-operator service of a production line","volume":"43","author":"Kats","year":"1982","journal-title":"Autom. Remote Control"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1287\/opre.30.4.760","article-title":"Minimizing the Number of Vehicles to Meet a Fixed Periodic Schedule: An Application of Periodic Posets","volume":"30","author":"Orlin","year":"1982","journal-title":"Oper. Res."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1023\/A:1018980928352","article-title":"Minimizing the number of robots to meet a given cyclic schedule","volume":"69","author":"Kats","year":"1997","journal-title":"Ann. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0377-2217(97)00339-1","article-title":"Minimizing the number of vehicles in periodic scheduling: The non-Euclidean case","volume":"107","author":"Kats","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/moor.9.2.190","article-title":"Minimum Convex Cost Dynamic Network Flows","volume":"9","author":"Orlin","year":"1984","journal-title":"Math. Oper. Res."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1016\/j.ejor.2003.09.036","article-title":"Vehicle minimization for periodic deliveries","volume":"165","author":"Campbell","year":"2005","journal-title":"Eur. J. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s00291-003-0153-3","article-title":"A unified modeling and solution framework for combinatorial optimization problems","volume":"26","author":"Kochenberger","year":"2004","journal-title":"OR Spectr."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1016\/j.orl.2007.12.001","article-title":"A strongly polynomial simplex method for the linear fractional assignment problem","volume":"36","author":"Kabadi","year":"2008","journal-title":"Oper. Res. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/moor.4.4.414","article-title":"Combinatorial Optimization with Rational Objective Functions","volume":"4","author":"Megiddo","year":"1979","journal-title":"Math. Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1137\/0218003","article-title":"A Fast Parametric Maximum Flow Algorithm and Applications","volume":"18","author":"Gallo","year":"1989","journal-title":"SIAM J. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0166-218X(93)00094-G","article-title":"An algorithm for fractional assignment problems","volume":"56","author":"Shigeno","year":"1995","journal-title":"Discret. Appl. Math."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Radzik, T. (1992, January 24\u201327). Newton\u2019s method for fractional combinatorial optimization. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, PA, USA.","DOI":"10.1109\/SFCS.1992.267785"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/net.20288","article-title":"A fast parametric assignment algorithm with applications in max-algebra","volume":"55","author":"Gassner","year":"2009","journal-title":"Networks"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0166-218X(81)90026-3","article-title":"Parametric shortest path algorithms with an application to cyclic staffing","volume":"3","author":"Karp","year":"1981","journal-title":"Discret. Appl. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/net.3230210206","article-title":"Faster parametric shortest path and minimum-balance algorithms","volume":"21","author":"Young","year":"1991","journal-title":"Networks"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/7\/283\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:07:17Z","timestamp":1760108837000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/7\/283"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,28]]},"references-count":33,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2024,7]]}},"alternative-id":["a17070283"],"URL":"https:\/\/doi.org\/10.3390\/a17070283","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2024,6,28]]}}}