Multiple Traveling Salesperson Problem With Drones: General Variable Neighborhood Search Approach

Abstract

A key factor to consider in the development of new technologies in a number of fields is the use of unmanned aerial vehicles. This rapidly developing technology is used in military, communication, health, mapping, agriculture and transportation fields. The importance of cargo transportation has grown due to the growth of e-commerce. Currently, with advancing technology, and the effect of the pandemic, purchases are increasingly made over the internet. For cargo transporters, this situation leads to an increase in the number of destination points, in distances traveled, and in the delivery frequency, and a decrease in the package sizes. As a result, the planning of transportation has become increasingly complex. One solution is to make greater use of unmanned aerial vehicles in this sector, and to reduce reliance on trucks through appropriate planning. This involves two aspects: the unmanned aerial vehicle delivering to a point, while the cargo truck delivers to a separate point. In this study, we consider a multiple traveling salesperson problem simultaneously using multiple trucks and unmanned aerial vehicles for package delivery. We develop a general variable neighborhood search algorithm, and compare the results with the existing studies in the literature. Computational experiments show that our approach is able to find highly satisfactory solutions in reasonable time, and outperforms the existing methods in terms of best solution, average solution and solution time in majority of the instances.