An Efficient Greedy Randomized Heuristic for the Maximum Coverage Facility Location Problem with Drones in Healthcare
Source abstract
Abstract
Recently, drones, have been utilized in many real-life applications including healthcare services. For example, providing medical supplies, blood samples, and vaccines to people in remote areas or during emergencies. In this study, the maximum coverage facility location problem with drones (MCFLPD) was studied. The problem is the application of drones in the context of the facility location and routing. It involves selecting the locations of drone launching centers, which maximizes patient service coverage within certain drone range constraints. In this study, a heuristic named the maximum coverage greedy randomized heuristic (MCGRH) is developed. The idea of the algorithm is to first choose some facilities to open at random from among those that can handle the most weight of the patient demands. After that, patients are assigned to the closest opened facility with the capacity to serve them. Finally, drones are assigned to patients based on the least amount of battery consumed between the patient and the facility. Extensive testing of MCGRH indicated that it ranks efficiently alongside other methods in the literature that tried to solve the MCFLPD. It was able to achieve a high coverage of patients (more than 80% on average) within a very fast processing time (less than 1 s on average).
Source: crossref · Quality: baseline
Research context
OpenAlex topics: UAV Applications and Optimization · Facility Location and Emergency Management · Vehicle Routing Optimization Methods
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
College of Computer and Information Sciences, King Saud University, Riyadh 11543, Saudi Arabia
References (33)
Show source-provided references
1. (2021, December 29). 2021 North American Wildfire Season-Center for Disaster Philanthropy. Available online: https://disasterphilanthropy.org/disaster/2021-north-american-wildfire-season/.
2. (2021, December 29). 2021 Haiti Earthquake and Tropical Storm Grace-Center for Disaster Philanthropy. Available online: https://disasterphilanthropy.org/disaster/2021-haiti-earthquake-and-tropical-storm-grace/.
3. (2021, December 29). 2021 Atlantic Hurricane Season Fast Facts-CNN. Available online: https://edition.cnn.com/2021/04/13/weather/2021-atlantic-hurricane-season-fast-facts/index.html.
4. (2020, March 23). Coronavirus Disease 2019. Available online: https://www.who.int/emergencies/diseases/novel-coronavirus-2019.
5. (2020, March 23). Australia Fires: A Visual Guide to the Bushfire Crisis-BBC News. Available online: https://www.bbc.com/news/world-australia-50951043.
6. Radu, S. (2020, September 05). 5 of the Deadliest Natural Disasters in 2019 | Best Countries | US News. Available online: https://www.usnews.com/news/best-countries/slideshows/5-of-the-deadliest-natural-disasters-in-2019.
7. (2020, March 23). 2018 Indonesia Quakes and Tsunamis: Facts, FAQs, and How to Help | World Vision. Available online: https://www.worldvision.org/disaster-relief-news-stories/2018-indonesia-earthquake-facts.
8. Improvement of rural access roads in developing countries with initiative for self-reliance of communities10.1016/j.sandf.2013.12.003 ↗
9. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey10.1002/net.21818 ↗
10. Last-mile delivery concepts: A survey from an operational research perspective10.1007/s00291-020-00607-8 ↗
11. Liu, Y. (2020, March 23). China Adapts Surveying, Mapping, Delivery Drones to Enforce World’s Biggest Quarantine and Contain COVID-19 Outbreak | The Star Online. Available online: https://www.thestar.com.my/tech/tech-news/2020/03/05/china-adapts-surveying-mapping-delivery-drones-to-enforce-worlds-biggest-quarantine-and-contain-covid-19-outbreak.
12. Raptopoulos, A. (2019, April 20). No Roads? There’s a Drone for That. Available online: https://amandacoxdesign.wordpress.com/2013/12/02/tedtalk-andreas-raptopoulosno-roads-theres-a-drone-for-that/.
13. (2020, March 25). DHL | Press Release | English. Available online: https://www.dhl.com/en/press/releases/releases_2016/all/parcel_ecommerce/successful_trial_integration_dhl_parcelcopter_logistics_chain.html.
14. Tilley, A. (2021, December 29). UPS Experiments with Drone Delivery in Partnership with Zipline. Available online: https://www.forbes.com/sites/aarontilley/2016/05/09/ups-experiments-with-drone-delivery-in-partnership-with-zipline/?sh=609b416b45a4.
15. Dragolea, N. (2020, March 25). 9 Drones That Will Revolutionise Healthcare-Doctorpreneurs. Available online: http://www.doctorpreneurs.com/9-drones-that-will-revolutionise-healthcare/.
16. (2021, December 29). Drone First Aid Kit Stock Illustration 192927128. Available online: https://www.shutterstock.com/image-illustration/drone-first-aid-kit-192927128.
17. UAVs path planning architecture for effective medical emergency response in future networks10.1016/j.phycom.2021.101337 ↗
18. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions10.1016/j.cor.2020.105004 ↗
19. Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles10.1016/j.trc.2019.11.002 ↗
20. Maximum coverage capacitated facility location problem with range constrained drones10.1016/j.trc.2018.12.001 ↗
21. Adeleke, O.J., and Olukanni, D.O. (2020). Facility Location Problems: Models, Techniques, and Applications in Waste Management. Recycling, 5.10.3390/recycling5020010 ↗
22. El-Ghazali, T. (2009). Metaheuristics: From Design to Implementation, John Wiley & Sons. [2nd ed.].
23. (2021, December 29). Mixed-Integer Programming (MIP)-A Primer on the Basics-Gurobi. Available online: https://www.gurobi.com/resource/mip-basics/.
24. Ilkhanizadeh, S., Golabi, M., Hesami, S., and Rjoub, H. (2020). The Potential Use of Drones for Tourism in Crises: A Facility Location Analysis Perspective. J. Risk Financ. Manag., 13.10.3390/jrfm13100246 ↗
25. Udroiu, R., Deaconu, A.M., and Nanau, C.Ş. (2021). Data Delivery in a Disaster or Quarantined Area Divided into Triangles Using DTN-Based Algorithms for Unmanned Aerial Vehicles. Sensors, 21.10.3390/s21113572 ↗
26. Deaconu, A.M., Udroiu, R., and Nanau, C.Ş. (2021). Algorithms for Delivery of Data by Drones in an Isolated Area Divided into Squares. Sensors, 21.10.3390/s21165472 ↗
27. Design of Hospital Delivery Networks Using Unmanned Aerial Vehicles10.1177/0361198120915891 ↗
28. Lynskey, J., Thar, K., Oo, T., and Hong, C. (2019). Facility Location Problem Approach for Distributed Drones. Symmetry, 11.10.3390/sym11010118 ↗
29. Application of hierarchical facility location problem for optimization of a drone delivery system: A case study of Amazon prime air in the city of San Francisco10.1007/s00170-017-1363-1 ↗
30. Stochastic facility location model for drones considering uncertain flight distance10.1007/s10479-018-3114-6 ↗
31. Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO2e emissions10.1016/j.trd.2017.09.011 ↗
32. The capacitated maximal covering location problem with backup service10.1007/BF02097800 ↗
33. (2021, December 29). SPSS Statistics-Saudi Arabia | IBM. Available online: https://www.ibm.com/sa-en/products/spss-statistics.