Truck-and-drone routing problems have become an important topic of research in the last decade due to their applications for last-mile deliveries. Despite the large number of publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact is true even for one of the simplest variants involving one truck and one drone whose routes must synchronize at customers’ locations: the Basic Traveling Salesman Problem with a Drone (TSP-D). In this article, we devise a new algorithm for the TSP-D that is able to solve every benchmark instance with up to 59 customers, and it scales up to 99 customers when the drone is much faster than the truck. The core of our method is a dynamic programming algorithm that is applied for column generation and variable fixing within tailored decremental state-space relaxation strategies.