巡回セールスマン問題のための分解能の調節可能な整数線形計画定式化に関する検討

カテゴリ: 部門大会

論文No: TC9-4

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

発行日: 2018/09/05

タイトル(英語): Study on Integer Linear Programming Formulation having Adjustable Resolving Power for Traveling Salesman Problems

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

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

キーワード: 巡回セールスマン問題|整数線形計画法|貪欲法|運搬経路問題|traveling salesman problem|integer linear programming|greedy algorithm|vehicle routing problem

要約(日本語): 本稿では，巡回セールスマン問題 (TSP) の整数線形計画 (ILP) 問題としての定式化に関する研究について報告することを目的とする。報告する定式化では，都市が配置された2次元空間がセルの集まりへと分割され，同一のセルに含まれる都市間の接続関係は所与のヒューリスティクスにより固定されるとする。このセルの小ささ（多さ）をモデルの分解能と呼称したとき，分解能が低いモデルでは1つのセル内に多くの都市が配置され，多くの都市間の接続関係が固定されるため，最適性は低くなるものの計算時間は短くなると予想される。また，低分解能モデルの解の近傍に高分解能モデルの解を探索するという近似解法を期待できる。計算例では，このような予想や期待の妥当性を TSPLIB のいくつかの例題について調査した結果を示す。

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