折線上を移動する物体に対する回収問題の困難性 Hardness of Pickup and Delivery for Moving Objects on Broken Lines

本稿では, 次のような車両配送計画問題の一種である移動物体回収問題(Pickup and Delivery for Moving Objects, PDMO問題)を考える.問題の入力として, n個の移動荷物および一度に荷物を1個のみ回収可能なロボット・アームが与えられる.移動荷物はあらかじめ決められた移動軌跡上を一定の速さで移動する.ロボット・アームは原点を出発し, 1個の荷物を掴み, それを原点へと回収する.本問題の目的は, できるだけ多くの移動荷物を決められた場所まで回収するような移動経路の集合を求めることである.本稿では次の結果を示す.(i)すべての荷物が少なくとも1度折れ曲がるような折線上を移動する場合には, PDMO問題はMAXSNP困難であり, (ii)PDMO問題に対する2近似アルゴリズムが存在する.しかし, (iii)すべての荷物がそれぞれ直線上を移動する場合には, PDMO問題に対する多項式時間アルゴリズムが存在する.

We consider the following variant of the Vehicle Routing Problem that we call the Pickup and Delivery for Moving Objects (PDMO) problem, motivated by robot navigation: The input to the problem consists of n products, each of which moves on a predefined path with a fixed constant speed, and a robot arm of capacity one. In each round, the robot arm grasps and delivers one product to its original position. The goal of the problem is to find a collection of tours such that the robot arm grasps and delivers as many products as possible. In this paper we prove the following results: (i) If the products move on broken lines with at least one bend, then the PDMO is MAXSNP-hard, and (ii) it can be approximated with ratio two. However, (iii) if we impose the "straight line without bend" restriction on every motion of the product, then the PDMO becomes tractable.