巡回セールスマン問題のための整数線形計画法における2-opt制約の融合

カテゴリ: 部門大会

論文No: TC10-2

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

発行日: 2021/09/08

タイトル(英語): Merging 2-opt Constraints in Integer Linear Programming Formulations for Traveling Salesman Problems

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

著者名(英語): Tsutomu Inamoto (Ehime University),Yoshinobu Higami (Ehime University)

キーワード: 巡回セールスマン問題|整数線形計画法|妥当不等式|2-opt法|traveling salesman problem|integer linear programming|valid inequality|2-opt method

要約(日本語): 本稿では，巡回セールスマン問題 (TSP) の（近似）解の整数線形計画法による求解時間を削減することを目的とし，2-opt法に基づく制約式を融合する技法を提案する．著者らはこれまでに，都市の座標が所与である TSP への整数線形計画法の適用にあたって，交差する辺が同時に選択されることはないという2-opt法に基づく制約式の利用を提案した．ここで，複数の2-opt制約を取り上げ，それらに関係する辺がすべて交差するなら，それらの制約式を1つへと融合できる．この融合により，解空間の削減と計算コストの増加の抑制を両立できると期待する．計算例では，TSP の小さなベンチマーク問題を対象として，提案技法により作成される制約式の数や提案技法が求解時間に与える影響などを示す．

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