RVND Heuristics for the Traveling Salesman Problem with Locating Drone Launch Stations

This article addresses the Traveling Salesman Problem with Drone Launch Station Location (PCV–LELD), in which n customers are served by a truck or drones launched from strategically placed stations. The problem consists of locating the stations, defining the customers served by drones, and planning the route of the truck, which departs from the warehouse, visits open stations and remaining customers, and returns to the starting point. The goal is to minimize the total cost that considers truck movements, drones and the opening of stations. The following are evaluated: (i) a Mixed Integer Linear Programming (PLIM) model, which combines the Miller–Tucker–Zemlin formulation with a facility location model; (ii) a constructive heuristic based on DBSCAN; and (iii) an RVND-based local search. Computational experiments in TSPLIB instances analyze the quality of the solutions and the computational performance of the proposed methods.