文献

J-GLOBAL ID：202002260463812506   整理番号：20A2053095

線形順序付け問題に対するタブー探索法に基づくアルゴリズムの提案

A heuristic algorithm based on tabu search for the linear ordering problem

著者 (2件)： 坂部将大 (名古屋大) ,  柳浦睦憲 (名古屋大)
資料名： スケジューリング・シンポジウム講演論文集  (Proceedings of the Scheduling Symposium)
巻： 2020  ページ： 79-84  発行年： 2020年09月17日 
JST資料番号： L8301A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： n個の頂点,m個のエッジ,およびエッジのコストを含む有向グラフが与えられた場合,線形順序付け問題(LOP)は,逆エッジの総コストが最小になるように頂点の順列を見つけることで構成される。NP困難問題として知られるLOPには,多くの実世界のアプリケーションがある。近傍で最良解を効率的に検索するために提案されたTREEと呼ばれるアルゴリズムを一般化して,新しいアルゴリズムが近傍で非タブー最良解を効率的に検索し,タブー探索アルゴリズムに組み込むことができるようにする。また,著者らのアルゴリズムは,タブー保有期間の自動調整メカニズムも備える。最後に,提案したアルゴリズムの実験結果を既存の反復局所探索アルゴリズム(ILS)と比較した。提案したアルゴリズムは,多くの事例でILSより良い結果を得た。(翻訳著者抄録)

シソーラス用語： *順序づけ問題 ,  *アルゴリズム ,  有向グラフ ,  NP困難 ,  応用プログラム ,  近傍探索法 ,  *タブー探索アルゴリズム
準シソーラス用語： NP困難問題 ,  アプリケーション ,  局所探索

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  人工知能  (JE08000Z)

引用文献 (5件)：

• R. Battiti, G. Tecchiolli, The reactive tabu search, ORSA Journal on Computing, Vol. 6, pp. 126-140 (1994)
• H.B. Chencery, T. Watanabe, International comparisons of the structure of production, Econometrica, Vol. 26, pp. 487-521 (1958)
• C.S. Sakuraba, D.P. Ronconi, E.G. Birgin, M. Yagiura, Metaheuristics for large-scale instances of the linear ordering problem, Expert Systems with Applications, Vol. 42, pp. 4432-4442 (2015)
• C.S. Sakuraba, M. Yagiura, Efficient local search algorithms for the linear ordering problem, International Transactions in Operational Research, Vol. 17, pp. 711-737 (2010)
• T. Schiavinotto, T. Stützle, Linear ordering problem: Instances, search space analysis and algorithms, Journal of Mathematical Modelling and Algorithms, Vol. 3, pp. 367-402 (2004)

タイトルに関連する用語 (6件)： 線形 ,  順序付け問題 ,  タブー ,  探索法 ,  アルゴリズム ,  提案