自動経路探索システムにおける複数本配管への対応

学正員

安 藤 悠 人*

正会員

元**

木 村

Automatic Routing System for Multiple Pipe-lines
byYuto Ando、 Student Member

Hajime Kimura、 Member

Summary
During the ship design, designers have to deal with all pipe-routes in order to generate practical piping layouts composed by
the minimum cost value (i.e. interference with obstacles, the length of each pipe-parts, etc.). However, the routing task requires huge
work hours because there are many regulations and functional design rules in the field. In this paper, we propose an automatic
routing system for multiple pipe-routes. The proposed system aims to solve the complicated multiple routing problems and to
improve the design work efficiency. In the routing problem for pipes, there are two major factors having the significant influence tofinal routing designs: the order of routing search and the selection from candidates of pipe-routes. The routing system is capable ofhandling these two factors by adopting Touch and Cross method and simulated annealing method. Touch and Cross method isrouting algorithm to find candidates including no interference with each path. Simulated annealing method is one of the
optimization methods to find a global optimum of a given function in a large search space. By combining these two methods, therouting system can reduce the influence of the search order and the selection problem. Therefore, it is able to find suitablepipe-routes automatically though there are no guarantees to find the best layouts. The routing system also uses Dijkstra's method asa routing method to find the optimal route efficiently. The performance of the system is demonstrated through several simulations.

テムの必要性は日増しに高まっていると考えられる．
1.

緒

言

そこで本研究では，配管設計における経路設定作業の自動化を目指し，設計者の作業の支援を行うシステムを検討して船舶の建造過程において，配管艤装の設計には膨大な作業いる．とくに本論文では，配管経路が複数本存在する場合を時間が必要である．近年では情報処理技術を利用することで想定した探索手法の提案を行う．本手法では設計者が作業中作業の省力化に努めているが，未だに設計作業を自動化できに配慮している項目（障害物との干渉，配管長，曲りの数なていないというのが配管設計の現状である．この主な原因とど）をコストとして定式化し，獲得される経路の実用性を向して設計問題の複雑さが挙げられる． 配管艤装を設計する上させている．また，本手法の特徴として経路の干渉回避方

場合，設計対象となる空間内に存在する各機器の配置，およ法の一つであるタッチアンドクロス法に焼きなまし法を組びそれらを接続する妥当な配管経路を検討しなければならみ合わせていることが挙げられる．これにより獲得される解ない．すなわち配管設計問題は，各機器の最適な配置の決定，は最適である保証はないが，膨大に存在する解候補の中からおよび最適な配管経路の設定等を含む多目的最適化問題でコストの低い妥当な解を効率的に獲得することができる．

あると考えられる．現在では熟練技術者の豊富な経験に頼ることで設計作業の解決を図っている．しかし近年，熟練作業

2.

配管設計問題者の減少が続いており，若手技術者への技術伝承問題等も発生している．よって配管設計作業を自動的に解決するシス

配管設計問題を取り扱う場合，すでに述べたように二つの最適化問題を取り扱う必要がある．設計者は初めに，設計対＊＊＊

九州大学大学院工学府海洋システム工学専攻

象空間内に存在するバルブやレデューサといった移動可能

九州大学大学院工学研究院海洋システム工学部門

な機器の配置を検討しなければならない．この際，機器の配原稿受理

平成 23 年 9 月 15 日

置場所はメンテナンス性や作業性が考慮されている必要がある．本論文ではこの問題を「機器配置問題」と呼称する．

案手法では，探索アルゴリズムとして GA が使用されている．

この問題を解決するために木村 1)は，作業性を評価基準とす

筆者らによる先行研究 6)では，空間を局所的に斜めに通過る手法の提案を行っている．この提案手法では，船舶の操船するベンドや，配管が可能な限り通過してほしいパイプラッを行う作業者の消費カロリーを基準にすることで作業性をク空間を考慮した経路探索手法を提案している．この手法で評価している．また提案手法の特徴として，配置される機器

は，空間を分割するメッシュの幅がパイプ径に依存せず，まとしてバルブやレデューサといった一般的なものだけでなた場所によってメッシュ幅は可変であることが特徴である．

く，配管の分岐点も考慮している点が挙げられる．このアプ

さらに先行研究 7)では，パイプが高さ方向に U 字となってローチにより，配管経路は始点・終点を一つずつ含んだ単純いる「鳥居配管」についても考慮されている．鳥居配管ではな経路となる．その結果，配管一本の経路探索に対して，ダ内部の流体や気体が管内に溜まってしまうため，通常の設計

イクストラ法などの最適解の獲得が保証されているアルゴ

現場では可能な限り避けるべきものと考えられている．そのリズムを使用することができる．木村 1)の提案手法では，機ため提案手法ではこのような鳥居配管をできるだけ避けた器の配置を決定する方法として遺伝的アルゴリズム(GA)を実用的な配管経路が自動的に獲得可能となっている．しかし，使用することで問題の解決を図っている．しかし経路探索ア

この手法では，設計対象となる配管が 1 本の場合は最適なルゴリズムとしては，経路中に含まれるエルボが 3 個まで経路を確実に獲得することが可能であったが，設計対象の配という制約条件のもとで直管を組み合わせるという手法を管が複数本になった場合において，好ましくない配管経路案取り入れており，複雑な経路を探索できない場合が発生してが獲得されてしまうケースが存在していた．

いた．そこで本論文では，この機器配置システムと組み合わ

船内には通常，複数の配管経路が複雑に配置されている．

せて使用することが想定された，迷路探索アルゴリズムを適

これらの複数の経路案を設計する場合，既に設定された配管用した新たな経路探索システムを提案する．詳細については経路を障害物とみなしつつ，1 本ずつ順次経路探索を進めて後述する．

いくことで最終的な設計案を作成するのが一般的である．既

また，機器配置問題を考慮しているその他のシステムとしに記した配管経路の自動探索における先行研究でもこのアて，Burdorf ら 2)が提案している CAPD が挙げられる．こプローチが採用されている．しかし，このように順次経路探のシステムでは機器配置を行うために，各機器に対して 3

索を行う場合，どの配管経路から経路探索を行うかによって段階に分類された配置条件を与えている．システムでは事前最終的な経路案が大きく変化する．経路探索を行う順序によに設定された配置条件を可能な限り満足するような配置案

る影響を考慮している先行研究である Paulo ら 5)は，設計順を自動的に生成することができる．また，この手法では熟練

序による影響への対処手段として，すべての順序において経作業員の知識や経験を配置条件として事前に入力すること

路探索を行う手法を提案している．しかし，狭い区画だけでも可能となっている．

も数十本以上存在している配管経路を全順序で経路探索す

機器配置問題を考慮した後に検討しなければならないのることは組合せ爆発を引き起こし，現実的ではない．

が「配管経路探索問題」である．これは配置された機器同士

また経路探索を 1 本ずつ進めていく場合， 獲得される妥を結ぶ最適な配管経路を探索する問題である．ここで探索さ当な経路として複数の解候補が出現する場合がある．すなわ

れる配管経路には，可能な限り総延長が短いことや，曲りのち経路中のエルボの個数は同じだが，その位置などが異なる

数が少ないことが求められる．Asmara ら 3)は，配管設計問

設計案が複数存在するケースである．そのような複数の解が題を解決するシステムとして Delft-Pipe を提案している．

発生している場合においても，どの解候補を選択するかによ

このシステムでは空間をメッシュ状に分割し，作成された各って，後の経路探索の結果に大きな影響を与える．しかし配セルに対して異なるコストを設定する．これにより，自動的

管設計に関する先行研究では，解候補の選択による最終設計に獲得される配管経路が通路空間と干渉することを防いだ

案の影響は未だ考慮されていない．

り，配管経路を壁際にまとめたりすることが可能となっていそこで本論文では配管経路探索問題の解決を目指し，複数る．ただし，メッシュの分割幅がパイプ径に大きく依存して本の配管を経路探索することを目的とした新しい経路探索

しまうという問題がシステム内には存在していた．また，経手法を提案する．本手法では膨大なパターンが存在する経路

路探索手法としては迷路探索アルゴリズムを使用している．

の設計案の中から，妥当な設計案を自動的かつ効率的に発見

さらに配管経路探索問題を取り扱っているその他の先行研することが可能である．本システムで獲得される設計案は最究として，伊藤ら 4)，Paulo ら 5)の研究も挙げられる．これ

適である保証はないが，設計者が現場で配慮している項目をらの研究でも，経路探索が行われる空間をメッシュ状に分割コストとして考慮することにより，その実用性を高めている．

することで，探索領域を限定している．ただし，これらの提3.

配管経路探索問題のモデル化

本論文で提案する手法では，先行研究 6)に引き続き配管経

4.

4. 1

配管経路探索アルゴリズム

1 本の配管経路に対する経路探索アルゴリズム

路探索問題をネットワーク上における始点・終点間の経路探

ここでは設計対象となる配管経路が 1 本の場合，どのよ

索問題とみなしている．探索対象となる配管経路では以下のうにして経路探索を行うかについて述べる．本手法では配管項目を前提条件としている．

経路探索問題を重み付きグラフ（ネットワーク）上の経路探【探索対象となる配管】始点・終点を一つずつ有しており，

索問題とみなすことで問題の解決を図っており，経路探索の

経路途中で分岐がなく，直径の変化もない配管経路．通常，手法としては先行研究 6)に引き続き，迷路探索アルゴリズム

船舶内の配管経路では数多くの分岐点が存在しているが，第の一種であるダイクストラ法を使用している．なお経路探索

2 章でも述べたように，本手法では分岐点を機器の一種としのための前提条件は，第 3 章で記載されたものである．

てみなしている．このアプローチにより経路探索を行うシス

Fig.1 として配管経路が 1 本の場合における経路探索の簡

テムでは経路途中の分岐点を考慮する必要がなく，単純な探易的な手順を示す．まず経路探索システムでは，設計対象空

索アルゴリズムの使用が可能になっている．

間の分割を行う．この際，メッシュ幅を細かく設定すること

また，自動的に探索される配管経路の形状として以下の 3

で，より正確に最適な経路を探索することができる．また，

つのものがある．

システム内では図に示されているような均等なメッシュだ【直管】真直ぐに伸びているパイプピース．

けでなく，不均一なメッシュ幅にも対応可能である．障害物【エルボ】90 度に曲がっているパイプピース．曲率半径にや始点・終点の周りにより細かなメッシュを配置することで，よって大きさが異なるため，経路探索を行う前にエルボに関計算時間の増加を抑えつつ，妥当な配管経路が獲得可能となするパラメータを設定する必要がある．

っている．

【ベンド】空間を局所的に斜めに通過するパイプピース．経路中の微小なずれを吸収するために使用される．曲率半径等の値によって大きさが異なるため，事前にパラメータを設定しておく必要がある．
さらに配管以外にも，経路探索を行う前提条件として以下の項目を仮定する．
【設計対象空間】経路探索が行われる空間．サイズが予め設定されているものとする．本研究では設計対象空間の形状を直方体に限定している．
【配管経路の配置可能な方向】配管経路は，局所的に使用されているベンドの部分をのぞいて，設計対象空間の各辺に平行な方向にのみ配置されるものとする．
【障害物】設計対象空間内に存在する構造部材や機器などがFig.1 Process of routing for a pipe-route

配置されている空間．探索される配管経路がこれらの空間に干渉することは許容されない．形状としては，三角形平面お空間の分割が終了すると，各格子点における配管経路の座よび直方体に限定されている．

標と向きを状態量とした重み付きグラフが作成される．グラ【通路空間】船舶の乗組員が通行することが想定されている

フ内の各ノードを接続するリンクにおける重みは，直管，エ空間．この領域内を配管経路が通過することは，機器の操作

ルボ，ベンドといったパイプ径に応じたパイプピースの使用性に悪影響を及ぼすと考えられる．よって配管経路の通過がコストに，通路空間やパイプラック空間を通過した場合のコ

極力避けなければならない空間である．形状は直方体であり，スト変化量が考慮されたものとなっている．すなわち経路の位置とサイズが予め設定されているものとする．

評価値となる総コストの値は，パイプラック空間を通過すれ【パイプラック空間】予め配管経路の通過が想定されている

ば割引され，それとは逆に通路空間に干渉すれば割増される．

空間．探索される配管経路は極度の迂回経路とならない限り，また筆者らは先行研究 7)で配管における溜りに着目していこの空間内に設置されることが望ましい．なお，この空間のる．溜りとは配管経路が高さ方向に U 形状になっている箇

形状は直方体であり，位置とサイズおよび配管経路が通過し所のことであり，内部流体の流れに対して悪影響を有していてほしい方向が事前に設定されているものとする．

るパイプ形状である．よって溜りの生成を可能な限り避ける

ために，提案手法では高さ方向へ経路探索を進める場合，そ4. 2 複数本の経路探索における二つの問題点

れらのノード間を結ぶリンクの重みにはコストの割増値が船内では通常，複数の配管経路が複雑に絡み合って存在し設定されている．これにより探索される経路は水平移動を優ている．すなわち，配管経路探索システムには，複数本の配先したものとなる．ゆえに最終的に獲得される配管経路では，管経路を探索しつつ，尚且つ妥当な設計案を生成する能力が極端な迂回経路となる場合を除いて，経路中に鳥居配管は生必要となる．しかし複数本の経路探索を考慮する場合，第 2

成されない．このように，ネットワークの各リンクには空間章にて記したように， 最終的に獲得される経路案が以下のや配管形状を考慮した重み関数が設定されている．

二つの原因によって大きく変化する．

ネットワークの作成が終了すると，始点・終点間を結ぶ最

まず一つ目の原因として，最終的に生成される経路案が，適な経路の探索が行われる．ここで最適な経路とはコストが配管経路の探索順序に大きく依存している点が挙げられる．

最小となるものを意味している．すなわち始点から終点まで

この問題に関する詳細を 4.3 節にて述べる．さらに，もう一を結ぶリンクの重みをすべて足し合わせたものが最小となつの原因として，1 本の配管経路中に複数の最適解が存在しる経路が探索される．このような最適経路を探索するために，た場合，その中からどの解を選択するかによって最終的に得本システムではダイクストラ法が使用されている．ダイクスられる経路案が大きく変化してしまうといった問題がある．

トラ法とはネットワーク上の任意の 2 点間を結ぶ最短経路

これに関する詳細は 4.4 節で述べる．

を効率よく且つ確実に探索することができる手法である．
ダイクストラ法によるネットワーク上の最適経路の探索

4. 3 探索順序による設計案への影響が終了すると，獲得された経路を設計対象空間内の配管経路

配管設計の現場では一般的に，高価値な配管経路から設計へ変換する．以上の探索処理を経ることで，本システムでは作業が進められている．すなわち管の材料が等価な場合，径最適な 1 本の配管経路を獲得することが可能となっている．

の大きな配管から経路設計が行われる．既存の経路探索シス

なお，獲得される経路は以下の 6 つの条件を満たしたもの

テムでも同様の手順で経路設計が行われていたが，径が同じとなっており，実用性の高い配管経路となっている．

配管が複数存在する場合は，その中からランダムに探索順序

1) パイプ長が短いこと．

を決定していた．すなわち既存のシステムを，実際の配管設

2) エルボおよびベンドの数が少ないこと．

計のように同じ径の配管が数多く存在する問題へ適用する

3) 通路空間を極力回避すること．

と，経路探索を行うたびに異なる探索順序で探索が実行され4) パイプラック空間を可能な限り通過すること．

ることとなる．しかし，この探索手法では既に配置された配

5) 高さ方向へ極力移動しないこと．

管経路を障害物とみなしているため，探索順序の変化によっ

6) その他の配管経路と可干渉しないこと．

て最終的な経路案が大きく影響を受けると考えられる．

（ただし探索のステージに応じて干渉を許す．）

CParts  CParts X ,Y  CParts Z  RZ

(1)

ここで，式(1)として高さ方向への移動と各パイプピースの使用コストの関係性を示す．ただし X もしくは Y 方向に設置されているパイプピースの使用コストを CParts X, Y とし，
Z 方向に伸びているパイプピースを CParts Z とする．そしてZ 方向への遷移によるコストの変化率を RZ とする．

CPipe  CParts  RSpace  CInterference(2)

また式(2)として 6 つの条件が考慮された探索コストの計算式を示す．1 本の配管経路の探索コストを CPipe，通路空間等との干渉によるコストの変化率を RSpace，パイプとの干Fig.2 Influence of routing search order

渉コストを CInterference として示す．CInterference は経路探索中に変化する値となり，その詳細は 4.5, 4.6 節で述べる．

Fig.2 は探索順序によって最終的に獲得される配管経路がシステム内では最適な経路案として CPipe が最小となる経

異なっている例を示している．ここでは径の等しい 2 本の路が獲得される．また，CPipe の値が等しい経路案が複数あ

配管経路（パイプ A，パイプ B）の経路探索を行う場合を想る場合はその中からランダムで一つが選択される．

定している．ただし図中では例を分かりやすいものとするた

めに，2 次元平面内での経路探索を示している．この場合，

路探索の順序同様に，最終設計案に対して大きな影響力を有

既存のシステムの手順に従うなら，2 本のパイプの径は等ししている要素であると考えられる．

いため，Fig.2 の上のようにパイプ A から探索を始める場合と，下のようにパイプ B から探索する場合の 2 通りの順序

4.5 タッチアンドクロス法を利用した探索アルゴリズムが考えられる．しかし図中で示されているように，最終的に4.3 節および 4.4 節で述べた，複数本の配管経路探索にお獲得される経路案は，探索順序が異なると全く違うものになける二つの問題点を解決するために，本論文ではタッチアンっていることが分かる．よって探索順序とは，最終設計案にドクロス法と焼きなまし法を組み合わせた新たな経路探索

対して非常に大きな影響力を有している要素である．

手法の提案を行う．ここではタッチアンドクロス法の適用法について述べる．

4.4 解の選択による設計案への影響

タッチアンドクロス法とは，集積回路の配線問題を解決す

1 本の配管経路探索を行う場合，設計対象空間内にある障るために，松岡ら 8)によって提案された経路探索手法であり，害物の配置によっては，経路の最適解として複数の解が存在ペナルティ関数法における外点法の一種である．ペナルティ

する場合が考えられる．特に障害物が少なく，設計空間に余関数法とは，制約条件を満たしていない状態をペナルティ値

裕がある場合，エルボやベンドといった曲りの位置が少しだとして評価し，その値を加えた目的関数（拡張目的関数）をけ異なる経路案が複数存在するが，それらの経路すべてが最探索することで，制約条件を満たした最適解を探索する手法

適解の候補となってしまうことがある．そのような場合，経である．また外点法とは，加えられるペナルティ値を探索の

路探索システムでは複数個存在する最適な経路候補の中か過程で徐々に大きくすることで，制約条件を満たした状態にらランダムで一つの解を選択している．しかし，既存のシスおける拡張目的関数の最小値を探索する手法である 9)．

テムのように経路探索を複数回繰り返さない場合では，どのタッチアンドクロス法では，タッチ（配線同士の接触）と経路を選択するかによって，最終的に得られる経路案が大き

クロス（配線同士の交差）という二つの制約違反状態をペナ

く変わってしまう場合がある．解の選択によって最終設計案

ルティ値として表現し，目的関数にその値を加えている．さが異なっている例として Fig.3 を示す．

らに，経路探索処理を複数回反復して行いつつ，設定された制約違反コストの値を徐々に上昇させることで，最終的に経路同士が干渉していない解を獲得する．また，反復して行われる経路探索の過程では，複数ある経路の中から 1 本を選び再度経路を探索し，その経路が設定されると，他の経路を選択し同様の経路探索処理を行う．このように複数本の経路探索過程では，すべての経路を同時に探索するのではなく，
経路 1 本ずつに焦点を当てているので，既存のダイクスト
ラ法を利用した経路探索手法と容易に組み合わせることができる．
次にタッチアンドクロス法を適用した配管経路探索シス

Fig.3 Influence of optimal routing selection

テムについて述べる．上記のように，タッチアンドクロス法
では経路同士の干渉にコストを設定している．よって配管経

Fig.3 では径の大きなパイプ B と径の小さなパイプ A の路探索問題でも，配管同士の経路干渉を意味する制約違反コ

経路探索を 2 次元平面で行う場合を示している．ここで，スト（ペナルティ値）を設定する．式(3)として経路探索シ

パイプ B の最適な経路候補としては図中の上のような経路

ステム内での経路干渉コストを記す．

と，下のような経路が考えられる．しかし，Fig.3 下図ではCInterference  VPipe  RInterference

パイプ B の経路の影響によって，後に経路探索されるパイ(3)プ A が大きく迂回してしまっていることが確認できる．こただし，経路同士の干渉コストを CInterferecne，干渉しているのように経路探索の序盤では設計対象空間内に障害物とな部分の配管が外接する直方体の体積を VPipe，コストの割増るものが少ないため，より多くの経路案が発生してしまう．

率を RInterference とする．式(3)のように設定された干渉コス

しかし，エルボの設置場所等が少しだけ異なる経路案の中か

トは，パイプピースの使用コストのように，経路探索過程でらどの経路を選ぶかによって，後の探索結果が大きく変化し作成されるネットワークにおけるリンクの重みとして換算ていることが分かる．ゆえに経路中における解の選択は，経される．

また，複数の配管経路を含んだ設計案を評価するパラメー

値を比較することで，x から x’ へ遷移するかどうかを確率タとしては式(2)で示された各経路の探索コストをすべて足的に選択する．探索過程では温度関数を定義し，温度関数おし合わせたものを使用している．式(4)として N 本の配管経よび解候補の評価値より遷移確率を計算する．そして計算さ路を含んだ設計案の評価パラメータを示し，これがペナルテれた遷移確率に従い，解の改善と改悪を確率的に繰り返すこィ関数法における拡張目的関数を意味する．ただし設計案のとで探索を進めていく．なお温度関数は探索が繰り返される

評価パラメータを総コスト CTotal として示す．

につれて徐々に小さな値となり，解の変動幅もそれに伴い収CTotal  i 1 C Pipe, iN

束していく．
(4)

タッチアンドクロス法を組み合わせた経路探索システム
では，経路探索を複数回繰り返しながら行う．それに伴い徐々に配管同士の干渉コストを増加させることで，次第に干渉のない配管経路案を獲得することが可能になっている．
Fig.4 として提案手法による経路探索を 2 次元でイメージ化したものを示す．この図で示されているように，経路探索の序盤では干渉コストが小さい値なため，経路同士が干渉を無視した単純な最短経路となっていることが確認できる．しかし，探索回数がすすむにつれて干渉コストが増大していき，徐々に経路同士の干渉が少なくなり，最終的に経路干渉のない妥当な設計案が獲得されていることが分かる．

Fig.5 Process of routing by the proposed method
次に提案手法における焼きなまし法の導入方法について述べる．まず Fig.5 として配管経路が N 本ある場合での，本手法による経路探索プロセスを示す．図中に示されている
ように，提案手法では全パイプに対する経路探索を 1 本ず
つ繰り返し行い，以前に獲得された経路との比較・選択を焼きなまし法に従い行っていく．
また，設計案の比較・選択の過程で解の遷移確率を計算するために，温度関数を設定する必要がある．本手法で設定された温度関数を式(5)として示す．

Fig.4 Process of routing with Touch and Cross method

Tk 1  Tk  1/ k (5)

ここでは探索 k 回目の温度を Tk として表す．また，パラメ
4.6 タッチアンドクロス法における焼きなまし法の導入

ータ β は冷却率をコントロールするパラメータであり，本シ

前節で示したように，タッチアンドクロス法では経路を一ステムでは 0.01 を代入している．さらに，獲得解の改善，本ずつ順次引き直して改善を繰り返すことで探索を進めて改悪を決定する遷移確率は式(6)で計算される．
遷移確率を P，

いく．しかし，常に改善を繰り返すだけでは，最適解へ到達

新しく探索された解の総コストと以前に探索された解の総するまえに探索が行き詰ってしまうケースが考えられる．こコストとの差を ΔC とする．

のように最終設計案が局所解へ陥ってしまうことを防ぐた
めに，本研究ではタッチアンドクロス法のプロセス中に，焼P = exp(ΔC / Tk )(6)

きなまし法を導入する．これにより，最終的に獲得される設

また，提案手法では焼きなまし法をタッチアンドクロス法

計案が局所解に陥ることを防ぎ，より実用的な経路案の獲得と組み合わせて使用しているため，温度関数の値が遷移確率が可能となる．

だけでなく，経路の干渉コストにも影響を与える．このアプ

焼きなまし法とは局所解にとらわれず，大域的な解候補をローチにより，探索が繰り返されるたびに温度関数の値を低探索するための最適化手法である．この手法では，現在の解下させ，それと同時に干渉コストを上昇させることが可能と候補 x の近傍 x’ を生成し，それぞれの評価値，f(x), f(x’) のなっている．式(7)として干渉コストに影響を与えるコスト

の割増率と温度関数の関係性を示す．なお T0 は温度関数の2.6 本であったが，本システムでは溜り 1.0 個，パイプラッ

初期値を示している．

クを通過する配管も 4.0 本となり，溜りの発生を抑え，パイ

RInterference  T0 / Tk

(7)

プラックを可能な限り通過させる設計案の生成に成功している．よって，タッチアンドクロス法と焼きなまし法を適用提案手法では，式(1) ~ (7)で示されている関係性を考慮すした提案手法は，配管経路が複数本ある場合でも，妥当な設ることで，タッチアンドクロス法および焼きなまし法を経路計案を高確率で獲得することが可能であることが確認され探索に組み込んでいる．このアプローチによって配管経路がた．ただし，提案手法では経路探索を繰り返し行っているこ

複数本ある場合でも，最終的に生成される設計案が 4.3 節，とから，繰り返し探索を行っていない先行研究のシステムと4.4 節で述べたような影響を受けにくいものとなっている．

比べて探索時間は大幅に増加している．探索時間に関する考以上のような比較・選択過程を取り入れることで，獲得さ察は次章で行う．

れる解が局所解に留まることを避けることができる．また，
経路探索を行う順序が妥当な設計案を発見する探索時間や探索精度に対して重要な要素となっている．これに関する考察は 6.1 節で行う．

5.

計算機シミュレーション実験

5. 1 シミュレーション実験 1
提案手法の動作を確認するために二つのシミュレーショ
ン実験を行った．実験 1 ではバラストポンプルームを想定した各辺 6[m]の直方体を用意し，その中に障害物 3 個，通路空間 3 個，パイプラック空間 2 個を設定した．また，経路探索を行う配管 13 本あり，パイプ径 0.8[m]が 1 本，0.6[m]Fig.6 Final result of the simulation1が 2 本，0.4[m]が 4 本，0.3[m]が 6 本となっている．また
温度関数の初期値を 100，最終値を 1 とし，RZ の値は 2.0とした．その他の各パラメータの数値を Appendix に示す．
計算環境は，OS に Windows7 を使用し，CPU は Intel Core i7
3.4Ghz，メモリーは 8.00GB，プログラム言語は Java version
1.7 を用いた．
5. 2 実験結果 1
Fig.6 に本実験で最終的に獲得された経路案を示す．最終的な設計案を獲得するために要した時間は約 18 時間であった．各経路は干渉なく接続されており，尚且つ可能な限りパイプラック空間を通過し，通路空間を避けたものとなっている．また鳥居配管についても可能な限り避けたものとなっている．同様の実験条件で 10 回シミュレーションを繰り返したところ，すべての実験結果で Fig.6 で示された経路案が獲得された．さらに同様の実験条件の下で，先行研究のシステ
ムを動作させたところ，実験を繰り返すたびに異なる設計案が獲得されることが確認されている．本実験を 10 回行い獲得された総コスト CTotal の平均値を比較すると，先行研究のシステムでは平均で 40.2，本システムでは平均で 38.6 となっている．また以前のシステムでは設計案に平均で 1.4 個の溜りが確認され，パイプラックを通過する配管の数も平均

Fig.7 Obtained pipe-routes during the simulation1

また Fig.7 として探索途中で獲得された経路を示す．なお，

は 4 本あり，パイプ径 0.9[m], 0.7[m], 0.5[m], 0.3[m]がそれ図中の k が探索回数，T がその時点での温度関数の値をそれ

ぞれ 1 本ずつである．温度関数の初期値を 100，最終値を 1

ぞれ示している．ここでの探索回数では，すべての配管につとし， RZ の値は 4.0 とした．その他のパラメータの値はいて経路探索を行うことを一単位としている．さらに表示さAppendix で示す．計算環境は実験 1 と同様である．

れている経路案の総コストを CTotal として示す．探索回数が小さい時点では温度関数の値が高く，干渉コストの値が小さ

5. 4 実験結果 2

いため，獲得された設計案は経路同士を無視した単純な最短Fig.9 として最終的に生成された経路案を示す．本実験で経路群になっていることがわかる．しかし探索回数が増加すの探索時間はおよそ 18 時間であり，最終経路案として妥当

るにつれて温度関数の値は小さくなり，それに伴って干渉コな設計案を獲得することができた．各配管経路は探索序盤でストが増大していくことで経路同士の干渉が徐々に少なくは干渉していたが，探索が繰り返されるにつれて徐々に変化なっていく．最終的には図中下段で示されているような干渉していき，最終的に図で示すような経路案が獲得された．

のない妥当な設計案が獲得されていることが確認できる．また，Fig.6 での経路は配管同士が複雑に絡み合った経路が確認できる．実際の施工現場では設計された経路を管割によって分断して施工するため，ある程度複雑な経路でも実現可能である．ただし本システムでは施工性を一切考慮に入れておらず，その取扱いは今後必要になってくると考えられる．よって施工性の考察について次章にて記す．

Fig.9 Final result of the simulation2

Fig.8 Total results of the simulation1
Fig.8 として横軸に探索回数 k，縦軸に総コスト CTotal を表したグラフを示す．このグラフでは本システムを同じ実験条件で 10 回繰り返した後に得られた総コストの平均値を表示している．Fig.8 から探索回数が増加するにつれて総コストが徐々に増加していることが分かる．これは干渉コストが探索回数に伴い徐々に増加するという提案手法の特徴によるものである．また本実験では探索回数が約 22 回前後で妥
当な解に収束していた．ここで，解が収束するときに総コストの下降が確認できるが，これは妥当な設計案では配管同士の干渉が無くなることやパイプラックの通過による影響であると考えられる．

5. 3 シミュレーション実験 2
実験 2 では船舶のデッキ裏の空間を想定した細長い直方体を用意した．設計対象空間のサイズは X, Y, Z 方向にそれ
ぞれ 8[m], 12[m], 4[m]となっている．経路探索を行う配管

Fig.10 Obtained pipe-routes during the simulation2

Fig.10 として探索過程で獲得されている経路案をそれぞれ

適解の選択幅が減少するためであると考えられる．よって第示す．本実験でも温度関数の値が減少するにつれて干渉コス

6 章で示したシミュレーション実験では，距離が短い配管経トが増大し，その結果として徐々に干渉の無い経路が獲得さ路から探索を繰り返している．今後，この手法がどれほど有れている．先行研究でのシステムと比較すると，総コストは効であるかどうかを確認するためには，さらなるシミュレー

44.7 から 43.3 へ変化しており，改善が確認できた．またション実験および検討が必要である．

Fig.11 として横軸に探索回数 k，縦軸に総コスト CTotal を表したグラフを示す．このグラフで示されている総コストは，6.2 探索時間に関する考察

本実験を 3 回繰り返した平均値である．グラフより総コス

第 6 章で示した実験では最終的な解を獲得するための計

トは探索回数が増加するにつれて徐々に増大し，探索回数が算時間としてそれぞれ 18 時間を要している．これは実験設

およそ 30 回で妥当な最終設計案を生成していることが分か定で記した計算機を使用した場合の探索時間であるが，今後る．ただし本実験ではパイプ同士が絡み合ったまま探索が終

さらに計算時間を短縮する必要があると考えられる．

了してしまうケースが確認された．これは始点・終点付近に提案手法では，設計対象空間のサイズ，空間を分割するメ

エルボが集中してしまう場合に発生しており，今後，干渉コ

ッシュの数，そして探索される配管の数，焼きなまし法におストや温度関数をさらに検討する必要がある．

ける温度関数の冷却速度などによって計算時間が変化する．
特に船舶の機関室へ本システムを導入し，正確な配管経路を自動設計する場合を考えると，メッシュの数はある程度細かく設定する必要があり，尚且つ探索が必要な配管経路は数百本に及ぶ．よってそのような場合，探索時間が爆発的に増加することが考えられる．そこで探索時間を短縮するためには，複数の計算機を同時に使用することが必要となってくる．ただし提案手法では，1 本ずつの経路探索を複数回繰り返していることから，探索中の経路が設定されないと次の配管の経路探索を行うことができない．よって複数の計算機を単純に並列使用するだけでは，探索時間を短縮する有効な手段とは

Fig.11 Total results of the simulation2

ならない．そこで本研究では今後の方針として，始点・終点を結ぶ解として最適経路が複数ある場合に，すべての経路パ

6. 考察

ターンをそれぞれの計算機で事前に獲得しておき，後にそれらをパズルのように組み合わせる手法を検討している．

6.1 反復過程における経路探索順序の影響提案手法では第 4 章で述べたように，複数本の配管の中6.3 施工性，安全性の評価手法の組み込み

から 1 本ずつ配管を選択し経路探索行っている．さらにこ提案手法では，獲得される配管経路の評価基準として，経の処理をすべての配管経路について繰り返すことにより，設路の総延長や曲りの数等を考慮した総コストを使用してい計案の生成を行っている．この反復される経路探索過程の中る．しかし実際の配管設計の現場では，設計している配管経で，どの順序で経路を選んでいけばよいかという問題が発生

路の施工性や安全性等の検討も行っており，これらは配管設する．すなわち，実際の設計者と同様に径の大きな配管から計において重要な問題であると考えられる．本論文の提案手順で設計を繰り返すべきなのか，ランダムで探索を繰り返す

法では施工性や安全性の評価問題は取り扱っていないが，このか，もしくはその他の順序なのかといった問題である．それらの問題を考慮した配管自動設計システムの構築が将来

こで本研究では，径の大きいもの順，小さいもの順，ランダ

的に必要となってくると考えられる．安全性をシステム内でムな順序，そして始点・終点距離の短いもの順，長いもの順

評価する手法として，電装機器周辺に通路空間や既に探索さの 5 つのパターンでそれぞれ探索を繰り返す予備実験を行れた配管経路の上の空間のような配管経路の通過が望ましい，定性的な比較を行った．その結果，始点・終点距離の短くない空間をコストが割り増される空間として自動的に設いもの順で経路探索を反復させることが最も効率的に妥当置することが考えられる．一方で施工性の評価については，な設計案を獲得できることが確認された．これは始点・終点

配管のフランジ割問題も含んでいることから，設計者の意見距離が短い経路は，経路中に最適解のパターンが少なく，そを今後さらに収集し，新しい手法を検討する必要があると考れらを先に配置させておくことで，後の経路探索における最えられる．

proceedings of the 5th International Conference on Computer

7. 結言

and IT Application(COMPIT), Mar. Ind. 2006. Leiden.
本論文では配管設計作業の自動化へ向けて，配管経路が設

4)伊藤 照明, 福田 収一: 遺伝的アルゴリズムを用いた計空間内に複数本存在する場合を想定した自動経路探索手

配管経路探索法の検討, 人工知能学会誌, Vol.13, No.5,法の提案を行った．提案手法では，経路探索手法としてダイ

pp.791-802 (1998 年)

クストラ法を使用し，複数本の経路探索を効率よく行うため

5)

T. M. Paulo, and V. J. A. S Lobo: A Tool for Automaticにタッチアンドクロス法と焼きなまし法を組み合わせていRouting of Auxiliary Circuits in Ships, Proceedings of 14th

る．これにより，複数本の経路探索を行う際に問題となってPortuguese Conference on Artificial Intelligence (EPIA

いた経路探索の順序や，経路探索中における解の選択による2009), Aveiro ( Oct. 2009)

影響を緩和することが可能となる．よって複数の配管経路を

6)

安藤 悠人，木村 元：エルボおよびベンドを考慮した配探索する場合でも，提案した経路探索システムでは妥当な設

管設計アルゴリズム，日本船舶海洋工学会論文集，第計案を自動的に生成することができる．また本論文では，提15 号, 2012, pp.219 - 226.

案手法を java プログラムに実装し，実際の設計現場を想定

7)

安藤 悠人，木村 元：溜りの影響を考慮した自動配管設

した問題でのシミュレーション実験を行うことで，その設計

計，日本船舶海洋工学会講演論文集，第 16 号，2013,

能力に関する検証を行った．

pp.179 - 182.
8)

謝

英俊，新田

泉：大規模配線システム：GRP,

FUJITSU, 50, 6, 1999, pp.372 - 377.

辞9)

本研究は，日本学術振興会科学研究費補助金基盤研究 (B)

松岡

今野

浩，山下

浩：非線形計画法，日科技連出版社,

1978.

課題番号 23360388 より一部補助を受けた．
Appendix
参 考 文 献実験 1，2 で使用された各パラメータの値．
1)

木村

元：機器配置およびパイプの分岐を扱う配管自動設計システム，日本船舶海洋工学会論文集，第 14 号，2011, pp.165 - 173.
2)

A. Burdorf, B. Kampczyk, M. Lederhose, H. Shmidt-Traub:
CAPD – computer-aided plant design, Computers andChemical Engineering 28, 2004, pp.73 – 81.

3)

A. Asmara, U. Nienhuis: Automatic piping system in ship,