On the Min-cost Traveling Salesman Problem with Drone
  Over the past few years, unmanned aerial vehicles (UAV), also known as
drones, have been adopted as part of a new logistic method in the commercial
sector called "last-mile delivery". In this novel approach, they are deployed
alongside trucks to deliver goods to customers to improve the quality of
service and reduce the transportation cost. This approach gives rise to a new
variant of the traveling salesman problem (TSP), called TSP with drone (TSP-D).
A variant of this problem that aims to minimize the time at which truck and
drone finish the service (or, in other words, to maximize the quality of
service) was studied in the work of Murray and Chu (2015). In contrast, this
paper considers a new variant of TSP-D in which the objective is to minimize
operational costs including total transportation cost and one created by waste
time a vehicle has to wait for the other. The problem is first formulated
mathematically. Then, two algorithms are proposed for the solution. The first
algorithm (TSP-LS) was adapted from the approach proposed by Murray and Chu
(2015), in which an optimal TSP solution is converted to a feasible TSP-D
solution by local searches. The second algorithm, a Greedy Randomized Adaptive
Search Procedure (GRASP), is based on a new split procedure that optimally
splits any TSP tour into a TSP-D solution. After a TSP-D solution has been
generated, it is then improved through local search operators. Numerical
results obtained on various instances of both objective functions with
different sizes and characteristics are presented. The results show that GRASP
outperforms TSP-LS in terms of solution quality under an acceptable running
time.
