Optimization approaches for the traveling salesman problem with drone

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

full-text

TSP with drone（TSP-D）という呼び名と、ルートを先に決めてから無人機担当を割り当てる発想を広く定着させた論文です。最悪近似比まで議論している点が、単なる数値実験と区別されます。全文の再読ではなく、書誌と標準的な主張のカードです。

トラックと無人機の協調を整数計画でモデル化し、局所探索と動的計画に基づくヒューリスティックを提案しています。小さい事例では最適解と比べ、大きい人工事例ではトラックだけの配送との差を見ています。彼らの実験設定では、協調により相当の節約があり得る、という主張です。

節約の大きさは、速度比や航続や顧客配置の仮定に依存します。論文が示した「あり得る」は、任意の都市で同じ割合が出るという意味ではありません。規制や複数無人機の運用は、この定式の範囲外です。