著者

梅田 博之 浅野 孝夫

雑誌

第80回全国大会講演論文集

巻号頁・発行日

vol.2018, no.1, pp.161-162, 2018-03-13

---

誰からも不満が出ないようにケーキを分けるにはどうすればよいか?ケーキは均一でなく、人の好み(評価関数)も様々である。これに挑むのがケーキ分割問題である。一般に(a)無羨望性=各人が他人の割当を羨まないことと(b)カット数の最小性が望まれるが、これらを同時に満たす分割を求める問題はPPAD完全である。そこでAlijaniら (AAAI,2017) は、ケーキが(ロールケーキ状の)閉区間の場合、各人の評価関数が単純(ある1つの部分区間にのみ正定数の効用を持つ)であれば、多項式時間可解と示した。本発表ではこの結果をホールケーキ版へ一般化し、多項式時間可解と示す。ここでホールケーキとは円形のケーキであり、閉区間の一般化とみなせる。

著者

B. コルテ J. フィーゲン著 シュプリンガー・ジャパン編 浅野孝夫 [ほか] 訳

出版者

丸善出版

巻号頁・発行日

2012

著者

山下 慶子 浅野 孝夫

出版者

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

雑誌

情報処理学会研究報告アルゴリズム(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.