| 講演名 | 2002/11/22 木構造ネットワーク上の配送・回収車両計画問題 加藤 直樹, 矢野 太平, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 単一デポが指定された木構造ネットワークにおいて、二種類の需要がある容量制約付き車両配送計画問題について考察し、総走行距離最小化基準の下で2-近似アルゴリズムを提案した。需要点には、荷物の配送と積込み(回収)の二種類の需要があり、需要の分割が許されるものとする。 |
| 抄録(英) | This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. There are two types of demands, pickup demand and delivery demand. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery. Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., the sum of goods to be delivered and those picked up should satisfy the vehicle capacity. We propose a 2-approximation algorithm for the problem. |
| キーワード(和) | 車両配送計画問題 / 近似アルゴリズム / 木構造ネットワーク |
| キーワード(英) | Vehicle routing problem / approximation algorithm / tree-shaped network |
| 資料番号 | COMP2002-50 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2002/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 木構造ネットワーク上の配送・回収車両計画問題 |
| サブタイトル（和） | |
| タイトル（英） | 2-Approximation Algorithm for Vehicle Routing Problems on Trees with Two Types of Demands |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 車両配送計画問題 / Vehicle routing problem |
| キーワード(2)（和/英） | 近似アルゴリズム / approximation algorithm |
| キーワード(3)（和/英） | 木構造ネットワーク / tree-shaped network |
| 第 1 著者 氏名（和/英） | 加藤 直樹 / Naoki KATOH |
| 第 1 著者 所属（和/英） | 京都大学工学研究科 Faculty of Engineering, Kyoto University |
| 第 2 著者 氏名（和/英） | 矢野 太平 / Taihei YANO |
| 第 2 著者 所属（和/英） | 理化学研究所 計算科学技術推進室 Computational Science Division, The Institue of Physical and Chemical Research |
| 発表年月日 | 2002/11/22 |
| 資料番号 | COMP2002-50 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 490 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |