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

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%\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\%$$\end{document}. 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.