Departmental Bulletin Paper 階層構造をもつ配置問題のための解法アルゴリズムと探索手順に関する実験的検討
An Experimental Study of Solving Algorithms and Search Procedures for Layout Problem in Multi Floor Structures

鈴木, 淳

(5)  , pp.5 - 12 , 2016-02 , 獨協大学情報学研究所
本稿では, 階層構造をもつ配置問題のための解法アルゴリズムと探索手順について研究されている。この配置問題は, 多数の配置ユニットを階層構造内にある配置セルへ割り当てる決定問題であり, ユニット間のフローコストと隣接選好が考慮されている。この問題を解くために, シミュレーテッドアニーリング法に基づく解法アルゴリズムを開発した。最適解の探索効果やパラメータ設定, 近傍探索手順の採用などの検討を行うために, 数値実験を実施した。実験の結果から, 次のようなことがわかった。120ユニットで最適値が5000~9000の例題において, エポックをユニット数の2乗として40~60の初期温度を設定した場合に探索効果が高いことがわかった。近傍探索手順として単純2点交換法と動的2点交換法を比較したが, 結果に大きな相違は認められなかった。初期解を違えた実験の結果からは初期解依存性はないとみられる。階層数の違いよりも, 階層間コスト係数の違いの方が, 問題の最適解を見出すことを難しくする。開発されたアルゴリズムの探索効果は概ね確認できた。今後の課題として, 階層間コスト係数が高い配置問題のために, 探索手順やパラメー夕設定に更なる検討が必要である。
In this Paper, algorithms and search procedures are studied for solving the multi floor layout problem. The layout problem is a decision of assignment of units into cells in a multi floor structure considering the flow cost and adjacent prefernce between units. To solve this Ploblem, an algorithm based on the simulated annealing method and neighborhood search procedures were developed in this study. For consideration of optimizations, setting of parameter, values and neighborhood search procedures, numerical experiments were executed. From the results of experiments, it was found to be as follow: for the problems with 120 units in the range of the optimum of 5000-9000 by using the algorithm set the square of the number of units into the epoch, the search effectiveness is excellent the case of initial temperature of 40-60. It was compared a simple 2-opt exchange method and a dynamic 2-opt exchange method as neighborhood search procedures, however the large difference in the results was not observed. From comparison of the results of computation with different two initial solutions, the initial solution dependence was not recognized. The differece in the cost factor, between floors makes it difficult to find the oputimum than the difference in the number of floors. Effectiveness of the developed algorithm has been demonstrated by numerical experiments. As a future research, it is required more research on the search procedure and the parameter settings for problems give higher flow cost factor between floors.

Number of accesses :  

Other information