The Drone-Assisted Traveling Salesman Problem with Robot Stations

Abstract

In this paper, we study the Drone-Assisted Traveling Salesman Problem with Robot Stations (TSP-D-RS). Specifically, we assume that there is a single truck that is equipped with a drone, and one or more potential sites of stations that might accommodate some robots. The TSP-D-RS asks for a valid route of the truck as well as feasible utilization of the drone and robots, such that all customers are served and minimal delivery time (makespan) or cost is accomplished. We provide a Mixed Integer Linear Programming formulation of the problem and perform a detailed numerical study. Through our numerical results, it is revealed that our formulation can be effectively addressed by a state-of-the-art solver. In addition, we demonstrate that optimizing the makespan coincides with reduced costs. In contrast, optimizing the operational costs might increase the makespan significantly. Furthermore, depending on the objective function, the operational utilization of the vehicles differs.