日本船舶海洋工学会講演会論文集 （この行は学会にて記入します）

タッチアンドクロス法を利用した配管自動ルーティング
学生会員

安藤悠人*

正 会 員木村元**

Automatic Pipe-routing system using Touch and Cross method
byYuto Ando, Student Member

Hajime Kimura, Member

Key Words: Pipe arrangement, Automatic design, Optimization, Routing order, Touch and Cross method

1. 緒言

船舶を建造するにあたり，配管艤装設計には膨大な作業時間が必要であるとされている．その主な原因として配管設計問題の複雑さが挙げられる．配管経路およびバルブなどの周辺機器配置を検討する場合，各機器の配置は作業性を満足しつつも，最短経路の配管で接続されていることが理想的である．すなわち配管設計問題を解決するためには，機器を最適な場所に配置しつつ，複数の配管を最適な経路で結ぶという多目的最適化問題を解かなければならい．ゆえに実際の設計現場では，ベテラン設計者の長年の経験に頼ることでこの問題の解決を図っている．しかし，昨今ではこのようなベテラン設計者の減少が年々続いており，若手技術者への技術伝承問題等も発生している．よってベテラン技術者と同等の設計作業を行う，もしくは設計者の作業を支援することができるシステムの必要性は日増しに高まっていると考えられる．そこで本研究では，配管設計作業の自動化を目指し，複数の配管経路が存在する設計現場を想定した新しい配管経路探索アルゴリズムの提案を行う．
配管設計問題は上記のように二つの最適化問題を含んでいると考えられる．一つ目の問題とは，バルブなどを含む周辺機器の理想的な配置を検討する「機器配置問題」である．この問題を解決するために，木村 1)は作業者の消費カロリーを基準にした作業性を評価パラメータにする手法の提案を行っている．この提案手法により，複数の設計案における機器配置を比較することが可能となり，最適な機器の配置を探索することができる．二つ目の問
題とは，機器同士を結ぶ配管経路を探索する「配管経路探索問題」である．配管経路を評価するパラメータとしては経路の総長やエルボの個数が挙げられる．先行研究
2)では，迷路アルゴリズムの一つであるダイクストラ法を利用することで，最適な配管経路の探索を行っている．
また，自動的に生成される経路をより実用的なものとするために，経路探索途中に通路空間やパイプラック空間の存在，鳥居配管または溜りとよばれる U 字状になった配管の影響についても考慮している．本研究では先行研
究 2)に引き続き，経路探索問題に焦点を当てている．ただ
し本論文では，設計対象空間内に配管経路が複数ある場
合における経路探索に関して，新しい手法の提案を行っている．

*九州大学大学院工学府海洋システム工学専攻**九州大学大学院工学研究院海洋システム工学部門
原稿受付 (学会にて記入します)
春季講演会において講演 (学会にて記入します)©日本船舶海洋工学会

2. 経路探索システム
2. 1 設計対象となる配管および空間
本研究で使用する経路探索システムでは，始点・終点を有し，経路途中で分岐や直径の変化がない配管経路を探索対象としている．通常，船舶内に存在する配管経路
では，多くの分岐点などが存在しているが，本研究では先行研究 1, 2)と同様に，これらをすべて機器とみなしている．これにより経路探索問題に対して，より単純な探索アルゴリズムの利用が可能となっている．
使用される経路探索システムでは以下に記す 3 つのパイプピースを探索途中で考慮している．
【直管】真直ぐに伸びているパイプピース．本研究では直管は XYZ の 3 軸方向に沿ってのみ配置される．Fig.1
左図参照．
【エルボ】90 度に曲がっているパイプピース．曲率半径によって大きさが異なるため，経路探索を行う前に，エルボに関連するパラメータをあらかじめ入力する必要がある．Fig.1 中央図参照．
【ベンド】空間を局所的に斜めに通過するパイプピース．
経路中のわずかなずれを吸収するため位に使用される．
エルボ同様に曲率半径等のデータをあらかじめ入力する必要がある． Fig.1 右図参照．

Fig. 1 Three types of pipe-pieces
またシステム内では以下の空間が考慮されている．
【通路空間】作業者が通ることが想定されている空間．
配管が通路空間に干渉した状態で配置された設計案は，通行や作業に支障をきたす恐れがある．よって配管が通過，干渉することが望ましくない空間である． 経路探索
システム内では直方体の空間として取り扱われる．
【パイプラック空間】あらかじめ配管が通ることが想定されている空間．壁際や天井付近などに設置されるケースが多く，設計対象の配管経路はこの空間を通過することが望ましい．直方体の空間として取り扱う．
【障害物】船舶の構造物や配管周りの機器などが設置されているスペース．経路探索を行う際，配管は障害物と干渉することが許されない．直方体，もしくは三角形の面を複数組み合わせることで取り扱う．

2. 2 経路探索システムの流れ
Fig.2 は経路探索システムの探索手順を示したものである．まず設計対象となる空間を格子状に分割し，次に，各格子点における座標と配管の向きを状態量とした重み付グラフを作成する．この際，グラフの各ノードを接続するエッジに重みを付加する．ここでエッジの重みを表現するものとして，直管，エルボ，ベンドなどの各パイプピースに相当するコストが使用される．また，通路空間やパイプラック空間に経路が干渉している場合や，鳥居配管と呼ばれる U 字経路に対するコストに関しても，パイプピースの場合と同様にエッジの重みとして換算される．このようにして作成された重み付グラフに対して，迷路探索アルゴリズムの一種であるダイクストラ法を使用することで，始点・終点間のグラフ上の最短経路を獲得する．最後に，獲得されたグラフ上の最短経路を設計空間内の配管経路に変換することで，最終的な配管経路案を獲得する．以上の処理を行うことで，パイプ長や曲りの数，通路空間やパイプラックとの干渉，鳥居配管の存在などを考慮しながら，最適な配管経路の探索を行うことが可能となっている．より詳細な手順は先行研究 2)に記載されている．

3. 2 探索順序による設計案への影響
艤装設計の現場では一般的に，高価値な配管から経路を決定していくのが好ましいとされている．すなわち配管の材質が同じ場合は太い配管から順に設計が進められていく．現在の経路探索システムでも同様の手法を取り入れているが，パイプの直径が同じである場合，システム内で探索される配管の順番を無作為に決定している．
この結果，同じパイプ直径が複数存在するテスト問題では，システムによる探索を行うたびに異なる設計案が獲得されてしまうことがシミュレーション実験により確認されてきた． Fig.3 は配管経路の設計順序により最終的な設計案が変化している例を示している．

Fig. 3 Influence of routing orderFig. 2 Process of pipe-routing
配管が複数本ある場合，上記の処理を繰り返して行い，1 本ずつ順に経路探索を順次行う．この際，現在探索している経路が，既に配管が設置されている空間と干渉した場合，配管との干渉コストを加える．複数本の配管がある場合の詳細を次章で述べる．

3. 3 最適解の選択による設計案への影響
経路探索を行う場合，設計空間内の障害物の配置などによっては，最適な配管経路が複数存在する場合がある．
例えば Fig.4 に示しているのは，2 次元での経路探索イメージである．パイプ B の経路探索時には，図で示されているように，エルボの位置により複数の最適経路が考えられる．しかし，次にパイプ A の経路探索を行うと，既に獲得されている配管経路の影響により設計案が大きく変化していることが分かる．Fig.4 の上図では最適な経路で 2 本の配管が結ばれているが，下図ではパイプ A が大きく迂回した経路となっている．よってこの例で示されているように，経路探索を行う段階では最適であった配管経路が，その後の経路探索に対してマイナスの影響をもたらしてしまうことが考えられる．

3. 複数経路への対応
3. 1 複数経路の探索における 2 つの問題点
通常，船舶内には複数の配管経路が複雑に絡み合って存在している．このように複数の配管経路が存在する場
合，現在使用している経路探索システムでは 2 章で示した探索手順に従いながら配管経路を 1 本ずつ順次探索することで最終的な設計案を生成している．各配管経路を順次設計していく手順は， 実際の設計者も使用している方法であり，妥当な手法であると考えられる．しかしこの手法には，経路設計を行う配管の順番によって最終的に得られる解が大きく変化するという問題が発生している．この問題について 3.2 節で詳しく述べる．また，経路探索システムに存在するもう一つの問題点として，最適な配管経路が複数ある場合における解の選択という問題がある．これに関する詳細を 3.3 節に記載する．

Fig. 4 Influence of optimal routing selection

3. 3 タッチアンドクロス法を利用した経路探索
3.2 節および 3.3 節で述べた 2 つの問題点を解決するため，本論文ではタッチアンドクロス法を組み込んだ経路探索手法を提案する．タッチアンドクロス法とは，集積回路の配線問題を解決するために，松岡ら 3)によって提案された手法であり，複数経路の探索を行うことが想定されている手法である．
まずタッチアンドクロス法の概要について説明する．
タッチアンドクロス法の主な特徴は，タッチ（配線同士の接触）とクロス（配線同士の交差）という二つの制約違反状態をコストとして表し，配線処理が終了するまではそれらを許しているという点である．さらに，全体の経路探索を反復して行い，設定された制約違反コストの値を徐々に上昇させることで，最終的に配線同士が干渉していない解を獲得する．この手法を適用することで，単純に最適解を 1 本 1 本探索するだけでは得ることのできない経路案を獲得することが可能となる．
次に本研究で使用される配管経路探索システムに対してタッチアンドクロス法を適用したアルゴリズムについて述べる．まずタッチアンドクロス法同様に，配管同士の干渉に対してコストを設定する．ここで設定されたコストは，パイプピースや通路空間のコストのように重み付グラフにおけるエッジの重みとして計算される．式(1)はタッチアンドクロス法を利用した場合の探索コストを示している．探索システムではここで示している探索コストが最小となる配管経路が獲得される．

CTotal  CPipe  RSpace CInterference(1)

ここで探索対象となる配管経路の探索コストを CTotal，パイプピースの使用コストを CPipe 通路空間およびパイプラック空間との接触による割引率および割増率を RSpace，そして他の経路との干渉コストを CInterference とする．
次に提案手法では， CInterference を徐々に大きな値にしながら経路探索を複数回反復して行う．ここで，どの順番で配管経路の探索を繰り返し行えば，妥当な設計案が生成されるのかという問題が発生するが，これについては4.4 節において考察を行う．
Fig.5 として提案手法による探索を 2 次元でイメージ化したものを示す．図で示されているように，経路探索の序盤では絡み合っていた配管経路が，探索終盤になり干渉コストが増大するにつれて互いに干渉しなくなり，最終的に妥当な設計案を獲得することができる．

Fig. 5 Process of Touch and Cross method

3. 4 焼きなまし法を利用した設計案の比較
複数回の経路探索を行っている場合，既に獲得されている設計案と新しく獲得された設計案とを比較する必要がある．タッチアンドクロス法では二つの設計案を比較する場合，全体の探索コストが低い設計案を獲得する．
しかし本手法では，確率的にコストが高い設計案を獲得する場合がある．この処理の目的は，配管同士が互いに干渉せず，尚且つ妥当な配管経路で結ばれている設計案を発見することである．
集積回路の配線問題の場合，回路のサイズや配線のコスト等の観点から，すべての配線処理を互いに干渉せずに行えるかどうかが重要となってくる．一方で配管経路
では材料や施工コスト，メンテナンス性能などの影響により，すべての配管が干渉せずに配置されているだけでは不十分であると考えられる．よって最適な配管設計案を獲得するために，あえてコストの高い経路案を探索途中で考慮し，より多様な設計案を探索することが必要となる．このため提案手法では，二つの設計案を比較する際に焼きなまし法に基づく手法を用いる．
焼きなまし法とは局所解にとらわれず，大域的な解候補を探索するための最適化手法である．探索中に温度関数を定義し，温度および解候補の評価値に関する遷移確率を計算する．そして計算された遷移確率に従って解の改善と改悪を繰り返していくことで，最適解を探索する手法である．よって本システムでも温度関数を定義することで，経路案を比較するときに遷移確率を計算している．式(2)では提案手法で用いられている温度関数と経路の干渉コストとの関係性，式(3)では温度関数と経路の探索コストより計算される遷移確率をそれぞれ示す．

CInterference  exp(1/ T )(2)

P  exp(C / T )(3)

ただし，温度パラメータを T，遷移確率を P，新しく獲得された探索コストと以前の探索コストとの差を ΔC とする．また温度パラメータを下降させる場合は，現在の温度に冷却度 γ を掛ける．
提案手法では，3.2 節で説明されたタッチアンドクロス法を利用した探索手順に加えて，式(3)で示された遷移確率に従いながら獲得された設計案を入れ替えていくことで，経路同士の干渉がなく，尚且つ妥当な配管経路を獲得することが可能となっている．パイプが N 本ある場合における提案手法の探索プロセスを Fig,6 として示す．

Fig. 6 Process of the routing system

4. シミュレーション実験
4. 1 実験設定
提案したシステムの動作を確認するためにシミュレーション実験を行った．設計対象空間は X, Y, Z 方向に 6[m]の立方体であり，障害物 3 つ，通路空間 3 つ，パイプラック空間 2 つを設定する．また，経路探索を行う経路は合計で 13 本であり，それぞれ パイプ直径が 0.8[m]のものが 1 本，0.6 [m]のものが 2 本，0.4 [m]のものが 4 本，0.3 [m]のものが 6 本である．また温度パラメータ T の初期値を 100，最終値を 0. 1，冷却度 γ を 0.985 とした．
4. 2 実験結果
計算環境は，OS に Windows7 を使用，CPU には Intel Corei7 3.4Ghz，メモリーは 8.00GB，プログラム言語は Java 1.7を使用した．Fig.7 として本実験で得られた最終設計案を示す．図で示されている設計案を獲得するために要した計算時間はおよそおよそ 20 時間であった．また Fig.8 として各温度の値における設計案の様子を示した．なお図中の n は探索回数を示している．探索が繰り返され，温度が下がるにつれて配管同士の干渉が少なくなっていく様子が確認できる．

4. 3 シミュレーション実験についての考察
本システムでは設計対象空間内に複数の配管経路が存在する場合において，配管の設計順序や最適解の選択などに依存しない設計案の獲得を目標としている．そこで今回行われたシミュレーション実験を 5 回繰り返して最終設計案の比較を行ったところ，すべての実験において，Fig.7 で示されているような，最適解に近く妥当であろうと判断される解が得られた．しかし，冷却度を 0.8 に設定し実験を行ったところ，最終的に得られた解に改善の余地が残されており，探索結果が不十分となる場合があることが確認された．
焼きなまし法では，冷却度を 1 に近い値にするほど探索結果は良好となるが，それに伴い探索時間が増大する．
また本システムでは冷却度はコストの上昇幅にも大きく影響を与えている．よって今後は，最適解を精度よく，しかも可能な限り短時間で探索するシステムを構築するためにも，設計問題に見合った妥当な冷却度を定める必要があると考えられる．
4. 4 反復過程における設計順序
本システムでは 3 章に示したように，複数本の経路探索を反復して行っている．この反復過程の中で，どの順序で経路探索を行えばよいかという問題が発生する．すなわち，実際の設計者と同様に太いもの順で設計を繰り返すのか，ランダムで探索を繰り返すのか，もしくは細いもの順で探索を反復させるのかといった問題である．
そこで本研究では，細い順，太い順，ランダムな順でそれぞれ探索を繰り返す予備実験を行い，定性的な比較を行った．この結果，細い順で探索を繰り返す手法が最も精度よく妥当な解を発見できることが確認された．これは細い配管を先に探索することによって，後の経路探索において最適解の選択幅が減少するからであろうと考えられる． 今後，この手法が有効であるかを確認するために，さらなるシミュレーション実験が必要である．

5. 結言
Fig. 7 Final design of the simulation

本論文では，配管設計作業の自動化を目的として，配管経路が設計空間内に複数存在する場合を想定した自動経路探索手法の提案を行った．提案した手法では，探索途中における探索順序や，最適経路の選択の影響を受けにくい妥当な設計案を探索可能である．また，提案手法を Java プログラムで実装することでシミュレーション実験を行い，その設計能力について検証を行った．

謝辞

本研究は，日本学術振興会科学研究費補助金基盤研究(B) 課題番号 23360388 より補助を受けた．

参 考 文 献1)

2)

3)
Fig. 8 Results of the simulation

木村元：機器配置およびパイプの分岐を扱う配管自動設計システム, 日本船舶海洋工学会論文集, 第 14号, 2011, pp.165-173.
安藤悠人，木村元：溜りの影響を考慮した自動配管設計, 日本船舶海洋工学会講演論文集, 第 16 号, 2013
pp.179-182.
松 岡 英 俊 ， 新 田 泉 ： 大 規 模 配 線 シ ス テ ム ： GRP,
FUJITSU, 50, 6, 1999 pp.372-377.