A decomposition-based iterative optimization algorithm for traveling salesman problem with drone

Yurek, E. E., & Ozmutlu, H. C. · 2018

citation-level

TSP-Dを、トラック経路と担当の決定と、無人機経路の最適化に分解する反復法として引用されます。厳密寄りの分解を探すときの参照です。全文の再実装確認はしていません。

第一段階でトラック経路と無人機担当を決め、第二段階ではそれを固定して無人機側を混合整数計画で最適化します。著者らは、均一な事例について、顧客12件程度までを平均的に短い時間で解けた、と報告しています。より大きい問題には最適化ベースのヒューリスティックを提案しています。

解けた大きさは、彼らの事例の型での話です。数百顧客の日次計画にそのまま載るアルゴリズムだとは読めません。エネルギー詳細や飛行禁止は主目的ではありません。