WEKO3
アイテム
Routing of Carrier-vehicle Systems with Dedicated Last-stretch Delivery Vehicle and Fixed Carrier Route
https://ipsj.ixsq.nii.ac.jp/records/183005
https://ipsj.ixsq.nii.ac.jp/records/183005ee1f1254-bac9-4de2-b360-d2a77d97769f
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5808019.pdf (1.1 MB)
|
Copyright (c) 2017 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2017-08-15 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Routing of Carrier-vehicle Systems with Dedicated Last-stretch Delivery Vehicle and Fixed Carrier Route | |||||||||||||
| タイトル | ||||||||||||||
| 言語 | en | |||||||||||||
| タイトル | Routing of Carrier-vehicle Systems with Dedicated Last-stretch Delivery Vehicle and Fixed Carrier Route | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | [特集：離散と計算の幾何・グラフ・ゲーム] vehicle routing, NP-hardness, approximation algorithm, polynomial time algorithm | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| 著者所属 | ||||||||||||||
| Department of Applied Mathematics and Physics, Kyoto University／Technical University of Malaysia Malacca | ||||||||||||||
| 著者所属 | ||||||||||||||
| Department of Applied Mathematics and Physics, Kyoto University | ||||||||||||||
| 著者所属 | ||||||||||||||
| Faculty of Mechanical Engineering, Kyoto Institute of Technology | ||||||||||||||
| 著者所属 | ||||||||||||||
| Department of Applied Mathematics and Physics, Kyoto University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Department of Applied Mathematics and Physics, Kyoto University / Technical University of Malaysia Malacca | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Department of Applied Mathematics and Physics, Kyoto University | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Faculty of Mechanical Engineering, Kyoto Institute of Technology | ||||||||||||||
| 著者所属(英) | ||||||||||||||
| en | ||||||||||||||
| Department of Applied Mathematics and Physics, Kyoto University | ||||||||||||||
| 著者名 |
Mohd, Shahrizan bin Othman
× Mohd, Shahrizan bin Othman
× Aleksandar, Shurbevski
× Yoshiyuki, Karuno
× Hiroshi, Nagamochi
|
|||||||||||||
| 著者名(英) |
Mohd, Shahrizan bin Othman
× Mohd, Shahrizan bin Othman
× Aleksandar, Shurbevski
× Yoshiyuki, Karuno
× Hiroshi, Nagamochi
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | We examine a routing problem that arises when an unmanned aerial vehicle (UAV), or drone, is used in the last-stretch of parcel delivery to end customers. In the scenario that we study, a delivery truck is dispatched carrying a shipment of parcels to be delivered to customers. While the truck is following a predetermined route, a drone is charged with making the last-stretch delivery of a parcel from the truck to a customer's doorstep. Given a set of customers to be served and a set of rendezvous points where the drone can meet with the truck to pick up a parcel, we ask what the quickest way is of delivering all parcels to the end customers. We model this problem as a problem of finding a special type of a path in a graph of a special structure, and show that the graph problem is NP-hard even when all edge weights are restricted to be 1 or 2. Furthermore, we identify a special instance type that can be solved optimally in polynomial time. Finally, we propose a polynomial-time approximation algorithm for the graph problem in metric graphs, and show that its approximation ratio is bounded above by 2 in restricted metric graphs. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.25(2017) (online) DOI http://dx.doi.org/10.2197/ipsjjip.25.655 ------------------------------ |
|||||||||||||
| 論文抄録(英) | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | We examine a routing problem that arises when an unmanned aerial vehicle (UAV), or drone, is used in the last-stretch of parcel delivery to end customers. In the scenario that we study, a delivery truck is dispatched carrying a shipment of parcels to be delivered to customers. While the truck is following a predetermined route, a drone is charged with making the last-stretch delivery of a parcel from the truck to a customer's doorstep. Given a set of customers to be served and a set of rendezvous points where the drone can meet with the truck to pick up a parcel, we ask what the quickest way is of delivering all parcels to the end customers. We model this problem as a problem of finding a special type of a path in a graph of a special structure, and show that the graph problem is NP-hard even when all edge weights are restricted to be 1 or 2. Furthermore, we identify a special instance type that can be solved optimally in polynomial time. Finally, we propose a polynomial-time approximation algorithm for the graph problem in metric graphs, and show that its approximation ratio is bounded above by 2 in restricted metric graphs. ------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.25(2017) (online) DOI http://dx.doi.org/10.2197/ipsjjip.25.655 ------------------------------ |
|||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN00116647 | |||||||||||||
| 書誌情報 |
情報処理学会論文誌 巻 58, 号 8, 発行日 2017-08-15 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 1882-7764 | |||||||||||||
