Dynamic programming approaches for the traveling salesman problem with drone

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

full-text

同じ著者グループのヒューリスティック論文とは別に、TSP-Dの厳密解を動的計画で攻めた論文です。どこまで厳密に解けるかを言うときに対になります。解法の再実装はしていません。

動的計画に基づく厳密解法を示し、それ以前の数理計画より大きい問題を解けた、と述べています。無人機が離れている間にトラックが訪れてよい地点数を制限すると、計算時間が大きく減り、解の質への影響は比較的小さい、という実験上の観察です。

「大きい」は当時の厳密解法との比較です。実務の日次VRPの大きさではありません。制限を入れると最適性は一般に保証されなくなります。その点は論文の実験観察として読んでください。