Approximation Algorithms for the Traveling Salesman with a Drone

• Item type: SIG Technical Reports(1)
• 公開日: 2017-09-12
• タイトル: Approximation Algorithms for the Traveling Salesman with a Drone
• タイトル / 言語: en
• タイトル: Approximation Algorithms for the Traveling Salesman with a Drone
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Applied Mathematics and Physics, Kyoto University／Technical University of Malaysia Malacca
• 著者所属: Department of Applied Mathematics and Physics, Kyoto University
• 著者所属: 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
• 著者所属(英): Department of Applied Mathematics and Physics, Kyoto University
• 著者名: Mohd, Shahrizan Bin Othman; Aleksandar, Shurbevski; Hiroshi, Nagamochi
• 著者名(英): Mohd, Shahrizan Bin Othman; Aleksandar, Shurbevski; Hiroshi, Nagamochi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We examine a routing problem arising when an unmanned aerial vehicle (UAV), or drone, is used in a combination with a truck for the last-stretch of parcel deliveries to end customers. Agatz et al. (ERIM Report Series, Reference No. ERS-2015-011-LIS (2015)) proposed a (2 + α) - approximation algorithm for the Traveling Salesman Problem with Drone (TSP-D), with the minimum spanning tree heuristic for the TSP and with no drone deliveries. With this work, we propose an improved, min {3/2 + α, 1 +√n} - approximation algorithm for the TSP-D where n is the number of customers that need to be served.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We examine a routing problem arising when an unmanned aerial vehicle (UAV), or drone, is used in a combination with a truck for the last-stretch of parcel deliveries to end customers. Agatz et al. (ERIM Report Series, Reference No. ERS-2015-011-LIS (2015)) proposed a (2 + α) - approximation algorithm for the Traveling Salesman Problem with Drone (TSP-D), with the minimum spanning tree heuristic for the TSP and with no drone deliveries. With this work, we propose an improved, min {3/2 + α, 1 +√n} - approximation algorithm for the TSP-D where n is the number of customers that need to be served.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-164, 号 1, p. 1-6, 発行日 2017-09-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会