Exact methods for the traveling salesman problem with drone

Roberti, R., & Ruthmair, M. · 2021

full-text

Work that extended how far an exact method can push a tour of one truck and one drone. The sentence "solved up to thirty-nine customers" cannot be exchanged for "solved a city." The card is on the shelf to stop that exchange.

The published abstract says they carry dynamic-programming recursions into a branch-and-price method on a set-partitioning formulation, using an ng-route relaxation and three-level hierarchical branching. That branch-and-price, they write, solves instances of up to thirty-nine customers to optimality, more than doubling the size then considered manageable. Their scenarios also say that one drone, if fast enough, can significantly reduce a route's completion time.

Thirty-nine is a count of customers in an instance. Wind, prohibited airspace, battery aging, and regulatory permission are not the center of the exact method. "Significantly" is their word under their speed assumptions, not a minute-count for a named city. The full text was not re-derived for this card.