配送計画問題に対する近似アルゴリズムの実際的性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2000-03-21
• タイトル: 配送計画問題に対する近似アルゴリズムの実際的性能評価
• タイトル / 言語: en
• タイトル: Practical Evaluation of Approximation Algorithms for the Vehicle Routing Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 中央大学大学院理工学研究科情報工学
• 著者所属: 中央大学大学院理工学研究科情報工学
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者所属(英): en
• 著者所属(英): Department of Information and System Engineering, Chuo University
• 著者名: 山下, 慶子; 浅野, 孝夫
• 著者名(英): Yoshiko, Yamashita; Takao, Asano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 配送計画問題は近年活発に研究されている問題で，経済活動のさまざまな状況でおこる．この問題には幾つかの種類があり，容量kの巡回路被覆問題，容量kの配送巡回路問題，電話予約送迎問題などがその代表例である．本稿では最も一般的な枠組での配送計画問題である容量kの配送巡回路問題の代表的なアルゴリズムを実装し，その実際的性能を評価する．さらに，複数デポーの配送計画問題に対する近似アルゴリズムを提案する．このとき従来の目的である配送に要する総距離最小という指標から少し離れ，現実的に乗組員の仕事量均等化を考慮に入れることも試みる．そして配達時間帯指定の配送計画問題にも取り組み，ベンチマークデータを用いて計算機実験を行い，提案するアルゴリズムの実際的性能評価を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The vehicle routing problem has received much attention in recent year and occurs in many practical settings. There are several variants of this problem: the k-tour cover problem, the k-delivery TSP and the dial-a-ride problem or stacker crane problem. In this paper, we try to evaluate the practical performances of representative algorithms for the k-delivery TSP. Furthermore, we propose approximation algorithms for the multi-depot vehicle routing problem and the vehicle routing problem with time windows and evaluate their practical performances through the computational experiments based on bench-mark data.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2000, 号 31(1999-AL-072), p. 33-40, 発行日 2000-03-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会