WEKO3
アイテム
Pickup and Delivery for Moving Objects on Broken Lines
http://hdl.handle.net/10228/0002000060
http://hdl.handle.net/10228/0002000060fdf8d699-b274-4467-9360-fa80f37c58a0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10347766.pdf (155 KB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-08-10 | |||||||||||||||||
| 資源タイプ | ||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||
| タイトル | ||||||||||||||||||
| タイトル | Pickup and Delivery for Moving Objects on Broken Lines | |||||||||||||||||
| 言語 | en | |||||||||||||||||
| 言語 | ||||||||||||||||||
| 言語 | eng | |||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× 宮野, 英次
WEKO
6037
× Shimoirisa, Shinichi
|
|||||||||||||||||
| 抄録 | ||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||
| 内容記述 | 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 the motion of every product, then the PDMO becomes tractable. | |||||||||||||||||
| 備考 | ||||||||||||||||||
| 内容記述タイプ | Other | |||||||||||||||||
| 内容記述 | 9th Italian Conference on Theoretical Computer Science, ICTCS 2005, Siena, Italy, October 12-14, 2005 | |||||||||||||||||
| 書誌情報 |
Lecture Notes in Computer Science 巻 3701, p. 36-50, 発行日 2005 |
|||||||||||||||||
| 出版社 | ||||||||||||||||||
| 出版者 | Springer | |||||||||||||||||
| DOI | ||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||
| 関連識別子 | https://doi.org/10.1007/11560586_5 | |||||||||||||||||
| ISBN | ||||||||||||||||||
| 識別子タイプ | ISBN | |||||||||||||||||
| 関連識別子 | 978-3-540-29106-0 | |||||||||||||||||
| ISBN | ||||||||||||||||||
| 識別子タイプ | ISBN | |||||||||||||||||
| 関連識別子 | 978-3-540-32024-1 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||
| 収録物識別子 | 0302-9743 | |||||||||||||||||
| ISSN | ||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||
| 収録物識別子 | 1611-3349 | |||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||
| 権利情報 | Copyright (c) 2005 Springer-Verlag Berlin Heidelberg | |||||||||||||||||
| 出版タイプ | ||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||
| 査読の有無 | ||||||||||||||||||
| 値 | yes | |||||||||||||||||
| 研究者情報 | ||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||
