著者
渡邊 浩和 小野 勉 松永 昭浩 金川 明弘 高橋 浩光
出版者
日本知能情報ファジィ学会
雑誌
日本ファジィ学会誌 (ISSN:0915647X)
巻号頁・発行日
vol.13, no.1, pp.119-126, 2001-02-15
被引用文献数
1

複数巡回セールスマン問題(MTSP)とは, 複数のセールスマンが与えられた都市を巡回訪問するとき, ある評価関数値を最小にするような各人の巡回経路を求める組合わせ最適化問題である.この経路を求めるにあたって, 各セールスマンの担当経路の輻輳は最大限避ける一方で, 各セールスマンの担当経路長はなるべく均等化することが望ましい.本論文では, MTSPの一つの近似解法を提案する.提案の解法は, ファジィクラスタリングにより, 各人の担当経路の中心部分のみを決定しておき, 残された都市の各クラスターへの挿入を通して担当経路長の均等化を計るアルゴリズムである.MTSPの一種であるN-TSPに関して, Fredericksonらのツアー分割アルゴリズムとの解の比較を行い, 提案法の有効性を示す.