巡回セールスマン問題のクラスタ間の接続に着目した整数線形計画問題としての定式化

カテゴリ: 部門大会

論文No: TC2-1

グループ名: 【C】2019年電気学会電子・情報・システム部門大会プログラム

発行日: 2019/08/28

タイトル(英語): Grid-Clustering Integer Linear Programming Formulation focusing on Inter-Cluster Bridges for Traveling Salesman Problem

著者名: 稲元 勉(愛媛大学),樋上 喜信(愛媛大学)

著者名(英語): Tsutomu Inamoto|Yoshinobu Higami

キーワード: 巡回セールスマン問題|整数線形計画法|クラスタ分割クラスタ分割|traveling salesman problem|integer linear programming|clustering

要約(日本語): 本稿は，運搬経路問題への整数線形計画法に基づく求解アプローチの展開を目指し，巡回セールスマン問題 (TSP) のための整数線形計画法としての定式化を開発することを目的とする。開発中の定式化では，都市平面をグリッドへと分割し，異なるグリッド間を接続できる都市数を制限する。そのような都市をブリッジと呼称したとき，ブリッジ数が少なくなるよう制約することで，多くの都市はその近傍である同じグリッド内の都市としか接続できなくなり，最適性の劣化と引き換えに計算時間を短縮できると期待できる。以上の期待から，TSP の代表的ベンチマークセットである TSPLIB を対象とし，TSPLIB 内で扱いやすい例題へ開発中の定式化を応用することにより，素朴な定式化よりも短時間で最適解あるいは準最適解を求められると示すことを，本稿の目標とする。

PDFファイルサイズ: 367 Kバイト