Grasp and delivery for moving objects on broken lines

作     者：Asahiro, Yuichi Miyano, Eiji Shimoirisa, Shinichi 

作者机构：Kyushu Sango Univ Dept Social Informat Syst Fukuoka 8138503 Japan Kyushu Inst Technol Dept Syst Innovat & Informat Fukuoka 8208502 Japan 

出 版 物：《THEORY OF COMPUTING SYSTEMS》 

年 卷 期：2008年第42卷第3期

页      面：289-305页

核心收录：

学科分类：07[理学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 070101[理学-基础数学] 

主　　题：moving objects grasp and delivery approximation algorithm MAXSNP-hardness 

摘      要：This paper studies the following variant of the Vehicle Routing Problem that we call the Grasp and Delivery for Moving Objects (GDMO) 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 one product and then delivers it to the depot. 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 GDMO is MAXSNP-hard, and (ii) it can be approximated with ratio 2. However, (iii) if we impose the straight line without bend restriction on the motion of every product, then the GDMO becomes tractable.