A 2-phase approach for planning of hazardous waste collection using an unmanned aerial vehicle

Jihene Kaabi (), Youssef Harrath (), Amine Mahjoub (), Nabil Hewahi () and Khadija Abdulsattar ()
Additional contact information
Jihene Kaabi: University of Bahrain
Youssef Harrath: University of Bahrain
Amine Mahjoub: University of Bahrain
Nabil Hewahi: University of Bahrain
Khadija Abdulsattar: University of Bahrain

4OR, 2023, vol. 21, issue 4, No 2, 585-608

Abstract: Abstract In this paper, a new Vehicle Routing Problem is studied. An unmanned aerial vehicle (UAV) is considered to handle the process of collecting hazardous waste from different sites. New constraints related to flying and weight capacities of the UAV are set. The goal is to collect the waste from the different sites within the shortest time. This paper includes four main contributions: (i) A proof of the strongly NP-hardness of the problem. (ii) A new linear program to optimally solve the problem for small-sized instances. (iii) An efficient 2-phase approach, called Maximum Waste in a Minimum Time during each Trip (MWMTT). (iv) A new tight lower bound to validate MWMTT. Phase 1 of MWMTT generates trips with maximum collected waste within the shortest time. Phase 2 uses a linear program to assign the trips generated in phase 1 into different groups in a way that the trips of the same group are performed by the UAV without the need to recharge it. An exhaustive experimental study was conducted using three randomly generated data sets for each of two experiments. In the first experiment, 16 small scale instances with number of sites varying from 10 to 40 are used. Whereas in the second experiment, 48 medium and large scale instances of 41 to 981 sites are considered. The results obtained by MWMTT in the small scale instances experiment are compared with the lower bound and the linear program. On the other hand, the results obtained by MWMTT in medium and large scale instances experiment are compared with only the lower bound. The obtained results show that MWMTT has a very promising performance. For small instances the average of the optimality gap between the result of the approach and the optimal solution (linear program) is less than 10 $$\%$$ % . For the medium and large instances, the gap moves almost in a steady state for every data set and the behavior of MWMTT is similar to the behavior of the lower bound.

Keywords: UAVs; Shortest path; Waste management; Heuristic; Lower bound; Linear programming; 90–08 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-022-00526-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:21:y:2023:i:4:d:10.1007_s10288-022-00526-0

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-022-00526-0

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().