著者

山下 慶子 浅野 孝夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2000, no.31, pp.33-40, 2000-03-21

被引用文献数

1

---

配送計画問題は近年活発に研究されている問題で,経済活動のさまざまな状況でおこる.この問題には幾つかの種類があり,容量kの巡回路被覆問題,容量kの配送巡回路問題,電話予約送迎問題などがその代表例である.本稿では最も一般的な枠組での配送計画問題である容量kの配送巡回路問題の代表的なアルゴリズムを実装し,その実際的性能を評価する.さらに,複数デポーの配送計画問題に対する近似アルゴリズムを提案する.このとき従来の目的である配送に要する総距離最小という指標から少し離れ,現実的に乗組員の仕事量均等化を考慮に入れることも試みる.そして配達時間帯指定の配送計画問題にも取り組み,ベンチマークデータを用いて計算機実験を行い,提案するアルゴリズムの実際的性能評価を行う.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.