C#コミュの配管定尺割りアルゴリズム

様々な長さの配管材があり、それらを5.5mの定尺に割付を行い5.5mの配管材を
手配するのに最も余り材を少なくするようなアルゴリズムってあるんですかね？

配管長さは1mm単位で任意とし、5.5mを分割する場合は切り代として10mmを見込みます。
例えば
15.00m、12.70m、11.45m、10.25m、7.00m、6.85m、5.35m、4.25m、3.33m、2.10m、1.22m、0.57mの12本の配管がありそれを5.5mの定尺に割付して最も効率よく(余材と手配材を最小にする)方法なんです。
どこかにそんな最適化のアルゴリズムある気がするのですがなかなか見つからず。

個人的には、以下のような方法かなと考えていますがなにか他に案などあれば
ご教示ください。

(案)
1.5.5m以上の配管から、5.5mを切り出す。

　(例)15mの配管なら
　　　15/5.5　=　2(本)＋4m(余)

2.1の余り材と5.5m以下の配管材から最長のものA(m)を選択

3.5.5mから2で選んだ配管材長さ＋切り代10mmを引きその余りの
　長さ以下で残っている配管長さの最短のものを当てはめる。

　　5.5-A-0.01=B(m)

4.B以下で余り材から最短のものC(m)を探す。

　　B-C-0.01=D(m)

5.これを繰り返し当てはまるものがなくなれば、2に戻る。

6.すべての配管材が割り当てられれば最適化終了

といった具合です。
なにかよいアドバイスをお願いします。

　　

コメント(11)

最初
全て
最新の40件

[2] mixiユーザー 12月11日 08:25

単純に考えれば長い方から取っていく方法と、短い方から取っていく方法があるかと思います。
継ぎ手(と言って良いか判りませんが)の長さはどの程度見る必要がありますか？

[3] mixiユーザー 12月11日 09:37

皆様、説明不足で申し訳ありません。

まず手配材についてですが、配管を発注する場合は基本的に5.5m単位でしか
購入できません。
ありえないことですが、1cmの配管がほしいとしても5.5m1本手配と考えます。

一般には配管は現場の状況に合わせてmm単位で様々な長さに切ったり、溶接
したりする必要があります。

たとえば、5.5mと3mと2mの配管材が必要な場合、相当"あれ”な方だと
5.5mを3本手配し、2.5mと3.5mの余材を発生させてしまいます。
その場合の数え方として、手配材3本で余材が2.5m+3.5m-切り代=約6mとなります。

管割の最適化を行うとすれば、5.5m2本を手配し、1本はそのまま使用。
残りの1本から3mと2mを切り出し、切り代10mmを含め約0.5mの余材が出ることになります。
つまり手配材2本と余材約0.5mです。

基本的に余材を最小にするように考えていけば、手配材も最少本数になるはず
なので余材最小が優先になります。

また、配管接続部分についてですが3DCADより継ぎ手部をすでに考慮した実長
を取得します。5.5m以上の配管も継ぎ手部は溶接継ぎ手となるため考慮の必要は
ありません。

あと1点注意していただきたいのは、余り材をつぎはぎすることはできません。
5.5mから3mと2mの配管を切り出して、残りの0.48m(切り代考慮)以下の配管部品
がない場合はそれは廃棄となります。
1mの配管をもう1本手配する必要があった場合、先ほどのあまり0.48mとどこかの余りの0.52mを見つけてきて合わせて1mというわけにはいかないのがややこしいところです。

長文失礼しました。

[4] mixiユーザー 12月11日 12:22

線形計画法なんかを使えばいいんじゃないでしょうか。

[6] mixiユーザー 12月11日 23:59

たけをさん

線形計画法ですか。
あまりなじみはないので調べて見ます。
ありがとうございます。

はむちゃんさん

まあそういったところです。

[8] mixiユーザー 12月12日 01:54

紙に書いてちょっと思いついただけなので、ベストかどうかの検証までは行ってませんが、こんな方法はどうでしょうか。あくまで参考にということで。
簡単に考える為に数字を置き換えて考えてます。

基準値を 1.0として、以下の数字を対象とする。(ランダムな数字をソート済み)

0.1 0.1 0.2 0.2 0.3 0.3 0.4 0.7 0.8 0.9

この数字から一番大きい数字、0.9を a に格納し、
小さい数字から順にアタックして、
足して基準値と同じまたは近い数字になる候補を探す。
候補がなくなるか基準値と同じになった時点で合計値にプラスしていく。
候補があって、足しても基準値以下の場合は次回に繰り越していく。
すべての候補がなくなるまでループさせる。
それを数字の動きで見ていくと、

合計 0 : 0.1 0.1 0.2 0.2 0.3 0.3 0.4 0.7 0.8 0.9 …必要な部材の長さを列挙
合計 1 : 0.1 0.2 0.2 0.3 0.3 0.4 0.7 0.8 … 0.9 + 0.1 が消えて合計に加算
合計 2 : 0.1 0.2 0.3 0.3 0.4 0.7 … 0.8 + 0.2 が消えて合計に加算
合計 3 : 0.1 0.2 0.3 0.4 … 0.7 + 0.3 が消えて合計に加算
合計 4 : 0.1 0.2 0.7 … 0.4 + 0.3 = 0.7では基準値以下で候補があるので繰越
合計 4 : 0.1 0.9 … 0.2 + 0.7 = 0.9 で、候補があるので繰越
合計 5 … 0.1 + 0.9 = 1.0で合計に加算。候補がすべてなくなり計5本

という流れになり、最終的に必要な本数は5本。
わかりやすくする為に簡単な数字におきかえてやってみた方法ですが。
こんな感じの考え方ではどうでしょうか。
数字が単純な為にうまくいってるだけかもしれませんので、あくまで参考程度に。

長文で失礼しました。

[10] mixiユーザー 12月14日 23:22

これってNP完全問題ですよね。

計算対象の配管の本数は何本ぐらいなのですか？

[11] mixiユーザー 12月15日 23:54

Kazukさん、ありがとうございます。
余材については、最適化計算後余材を配管種別に追加登録し発注後のデータを
別途管理するようになっています。
また、3dモデルは設計進捗により更新されるためそのたびに以前のデータと
余り材、発注済み本数を計算し最適な発注本数を計算させるという仕様になっています。設計進捗により本数も増えたり減ったり・・・。
長い材料から取っていくと短い配管が残った場合余り材の長さが長くなってしまうこともあるので、結局長いほうから取っていった場合と、長いものを取ってきて、余材を短い方から埋めていくという2種類で最適な方を選択するように考えています。

はらこさん
1プラント分ですから、配管総延長100Km程度になるかと思います。
また、その配管種類も膨大で配管径毎に種類分けもする必要があります。

みなさまのたくさんのご意見たいへん参考になりました。
これを機にもう少しアルゴリズムを勉強してみたいと思います。

ログインすると、みんなのコメントがもっと見れるよ