Exact methods for the traveling salesman problem with multiple drones

Cavani, S., Iori, M., & Roberti, R. · 2021

full-text

無人機を一台から複数へ増やすと、厳密解のモデルが別の難しさを持つ、という事実を残す論文である。機数の増加を、都市規模の解決だと読む誤りを止める。

一台の通常車両と複数の無人機が顧客を分担する TSP-MD を、コンパクトな混合整数計画、妥当不等式、分解と分枝切断で扱った、と要旨は述べる。その厳密手法は二十四人の顧客までを最適に解け、同種の問題で十人程度であった既存の厳密解を改善した、と書いている。

二十四は、彼らのテスト・インスタンスの人数である。需要の予測ではない。エネルギーが荷物と風で変わること、ポートの枠、規制は、この到達点の外側に残る。一台で三十九人まで届いた Roberti と Ruthmair の結果と、人数を競わせない。