観光客巡回問題と旅程の随時計画法
Optimal Tourist Problem and Anytime Planning of Trip Itineraries
限られた時間で複数の観光地を巡り情報収集するロボットの経路と滞在時間を最適化する2つのNP困難問題に対し、混合整数計画に基づく随時アルゴリズムを提案し、イスタンブールの観光旅程計画で有効性を示した。
著者: Jingjin Yu, Javed Aslam, Sertac Karaman, Daniela Rus
分類: cs.RO
原文アブストラクト
We introduce and study the problem in which a mobile sensing robot (our tourist) is tasked to travel among and gather intelligence at a set of spatially distributed point-of-interests (POIs). The quality of the information collected at each POI is characterized by some non-decreasing reward function over the time spent at the POI. With limited time budget, the robot must balance between spending time traveling to POIs and spending time at POIs for information collection (sensing) so as to maximize the total reward. Alternatively, the robot may be required to acquire a minimum mount of reward and hopes to do so with the least amount of time. We propose a mixed integer programming (MIP) based anytime algorithm for solving these two NP-hard optimization problems to arbitrary precision. The effectiveness of our algorithm is demonstrated using an extensive set of computational experiments including the planning of a realistic itinerary for a first-time tourist in Istanbul.
