総完了時間最小化を目的とした複数拠点・複数トリップ車両ルーティング
Multi-Depot Multi-Trip Vehicle Routing with Total Completion Time Minimization
災害救助のためのUAV群の経路計画を、総完了時間を最小化する複数拠点・複数トリップ車両ルーティング問題として定式化し、MILPとマトヒューリスティックを提案した。
著者: Tiziana Calamoneri, Federico Corò, Simona Mancini
分類: math.OC, cs.RO
原文アブストラクト
Unmanned aerial vehicles (UAVs) are aircraft whose flights can be fully autonomous without any provision for human intervention. One of the most useful and promising domains where UAVs can be employed is natural disaster management. In this paper, we focus on an emergency scenario and propose the use of a fleet of UAVs that help rescue teams to individuate people needing help inside an affected area. We model this situation as an original graph theoretical problem called Multi-Depot Multi-Trip Vehicle Routing Problem with Total Completion Times minimization (MDMT-VRP-TCT); we go through some problems already studied in the literature that appear somehow similar to it and highlight the differences, propose a mathematical formulation for our problem as a MILP, design a matheuristic framework to quickly solve large instances, and experimentally test its performance. Beyond the proposed application, our solution works in any case in which a multi-depot multi-trip vehicle routing problem must be solved.
