Dynamic programming approaches for the traveling salesman problem with drone

Bouman, P., Agatz, N., & Schmidt, M. · 2018

full-text

Separate from the same authors’ heuristic paper, this one attacks the TSP-D exactly with dynamic programming. The pair is what people cite when they discuss how large an instance can be solved exactly. The algorithm was not re-implemented.

It presents exact dynamic-programming methods and reports that they solved larger problems than the mathematical-programming approaches then in the literature. Restricting how many locations the truck may visit while the drone is away is reported to cut solution time substantially, with a relatively small effect on solution quality.

“Larger” is relative to exact methods of that time, not to the size of a daily operational VRP. Adding the restriction generally gives up a guarantee of optimality. Read that point as the paper’s experimental observation.