著者

小川 将史 井上 真郷

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告 = IEICE technical report : 信学技報 (ISSN:09135685)

巻号頁・発行日

vol.114, no.306, pp.321-328, 2014-11-17

---

本研究では,組み合わせ最適化問題である『複数巡回セールスマン問題』の厳密な最適解の探索を行う.この問題では,全ての都市を何れかのセールスマンが一度ずつ訪れて共通の出発地点に全員戻るのに要する時間を最小にしなければならない.ゼロサプレス型二分決定グラフ(ZDD)とsimpathアルゴリズムを応用することにより,条件を満たす解を全列挙し,最適解の効率的な探索が可能なアルゴリズムを提案する.