TRAVELING SALESMAN PROBLEM WITH LOCATING DRONE LAUNCH STATIONS

This paper addresses the Traveling Salesman Problem with Drone Launching Stations, in which a set of \(n\) customers is served either by a truck or by drones launched from open stations. The problem consists of locating/opening stations, defining the truck route that starts at the depot, visits the open stations and customers not served by drones, and returns to the depot. For each open station, the set of customers to be served by drones must be determined. The objective is to minimize the costs associated with transportation and the opening of stations while ensuring that all customers are served. A Mixed-Integer Linear Programming model is proposed to solve the problem, based on the Miller-Tucker-Zemlin formulation and a facility location model. The model’s efficiency was evaluated using 30 instances generated under different scenarios, varying the number and capacity of drone batteries, and analyzing the GAP obtained within a time limit for execution