動的な車両ルーティングにおけるタスク待ち時間の最適化
Optimizing Task Waiting Times in Dynamic Vehicle Routing
移動ロボット群が時間と場所をランダムに到着するタスクを処理する動的車両ルーティング問題において、待ち時間のpノルムをコスト関数に用いる新方策を提案し、中負荷シナリオでの平均・95パーセンタイル待ち時間を改善した。
著者: Alexander Botros, Barry Gilhuly, Nils Wilde, Armin Sadeghi, Javier Alonso-Mora, Stephen L. Smith
分類: cs.RO, cs.SY, eess.SY
原文アブストラクト
We study the problem of deploying a fleet of mobile robots to service tasks that arrive stochastically over time and at random locations in an environment. This is known as the Dynamic Vehicle Routing Problem (DVRP) and requires robots to allocate incoming tasks among themselves and find an optimal sequence for each robot. State-of-the-art approaches only consider average wait times and focus on high-load scenarios where the arrival rate of tasks approaches the limit of what can be handled by the robots while keeping the queue of unserviced tasks bounded, i.e., stable. To ensure stability, these approaches repeatedly compute minimum distance tours over a set of newly arrived tasks. This paper is aimed at addressing the missing policies for moderate-load scenarios, where quality of service can be improved by prioritizing long-waiting tasks. We introduce a novel DVRP policy based on a cost function that takes the $p$-norm over accumulated wait times and show it guarantees stability even in high-load scenarios. We demonstrate that the proposed policy outperforms the state-of-the-art in both mean and $95^{th}$ percentile wait times in moderate-load scenarios through simulation experiments in the Euclidean plane as well as using real-world data for city scale service requests.
