On the Min-cost Traveling Salesman Problem with Drone

By Quang Minh Ha, Yves Deville, Quang Dung Pham, Minh Hoàng Hà. arXiv.org, 2015

575 citations recorded by the source corpus.

Abstract 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.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/f14823aa5e4f7cfe0ac279c553ce96b7b6dc41f8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Industrial and Manufacturing Engineering

Citations in the corpus

Applications and Research avenues for drone-based models in logistics: A classification and review (2021, methodology): “In a similar study by Wang et al. (2019), the FSTSP is considered with both cost minimization and tour time minimization objectives.”
The vehicle routing problem with drones: Extended models and connections (2017, background): “, see [1, 10]) propose computational approaches to address special cases of the VRPD.”
Coordinated Logistics with a Truck and a Drone (2018, background): “The recent papers [5, 22, 35] all describe mixed integer programming formulations and heuristic algorithms for solving several optimization problems in 3”
An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones (2019, background): “Another problem for the parcel delivery with UAVs is considered in Ha et al. (2018).”
Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey (2018, methodology): “[106] formulate the TSP with a drone, or a flying sidekick TSP.”
The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones (2020, background): “Ponza (2016), Ha et al. (2018), Freitas and Penna (2018), Daknama and Kraus (2017), and Schermer et al. (2018) explored neighborhood search based heuristics, while Bouman et al. (2018) present a dynamic programming approach for obtaining optimal solutions.”