瞳醸騨融機騒麟鰯闘機騒翻繍機機構冨盟副面開プロジェクト計画の最適化システム
石堂一成。1II1I1II，"IIIIIIIIIUIllIOIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
川11111111
川
刷"肌111
H
川
川
11H
川
川1111
H
川111
川
川
H
刷111
H
川
聞11111
川
川1111
H
川1111111111
川
川
H
肌川
H
11川
川川
11川
11H
剛
1111
削11
川
川
H
肌H
11111
肌1111
川
刷111
11
刷川
川
11111111
刷
肌111
H
川
川
H
111111
川
川
111
111
川
川
11川
11111
川
川
11111
川
川"肌111
11
川刷刷
川H川H
H
川
川111
川111
川
川11H
川川
川
川
11H
聞
肌H
川111
H
附
川11111
H川川
川
11H
聞1111川111
川
聞H
川
H
11附
刷川
H
11附1111111
刷1111
川"刷川川
H
11川
川
111
川111
H
川聞川
H
川111
H川
川1111111
H川川11剛
11H附1111
川11111111
川川
聞H
川
11川
11H
川
1111
川川"聞
附1111
H
附削11111l

工種は，大区分・中区分・小区分に区分し，小区1. まえがき

分段階では約 400 工種となる.

大規模で、長期にわたるプロジェグトの増加にと(2) 工種別工事量山積み: 数理計画法で扱もなって合理的な計画手法の必要性が強くなってう部分には，各単位時間ごとに消化すべき工事量きたのに応えるべく，筆者らはプロジェグトの種を工種別に求めた工種別工事量山積みが与えられ類・計画手法の適用目的に合わせていくつかのプる.単位時聞は通常，月を用い，単位工事量は工ロジェグト・マネジメント・システムを開発・実種ごとに適切な単位を用いる.ただ，どの工種で用化してきた[ 3J.

も 1 時間当りの平均工事量で各月の工事量が与え本稿では，これらのうちから数理計画法による最適化実施の典型的な一例を選られる.これは，休日・天候・土質条件などのサび報告する.具体的には，非常に大規模で離激的イト特有の条件を考慮して計算されている.

な数理計画問題を実際的な観点からいかにして実(の建機種・建機グラス: 建設機械は，プ用的に解き成果をあげているかについて報告す

ルドーザ・ダンプトラックというような種類に分る.

けられる.この種類を建機種と呼ぶ.対象建機種

次章以下，問題の概要・解法・実用化結果について述べる.の数は約 100 種である.建機グラスは， 10 トン型ブルドーザ・ 86 トン型プルドーザというような工事能力の異なる建設機械を区別するための分類で2. 問題の概要ある.建機グラスの数は，建機種ごとに異なるが各種のプロジェクトのうち，フルターンキー・ベースのプラント建設プロジェグトではエンジニ

最大 10 グラス程度である.

(4) 建機種組合せケース: 工種によってはアリングおよびコンストラグションの両面からの各種の工事機能をもっ建機種の異なる組合せによ

プロジェクト・マネジメントが重要で、あり，総合って遂行され得る場合がある.たとえば普通土掘的なプロジェクト・マネジメント・システムを開削・積込・運搬・捨土という l つの工種は表 1 に発し実用化している.ここでは，そのうちの建設示す(a)- (f)のような建機種組合せケースによって機械計画サブシステムで数理計画法を適用してい遂行され得る.建機種組合せケースの数は工種ごる部分の問題の概要を示す.とに異なるが，最大 10 ケース/工種程度である.

(1) 工種区分: 工事の種類を工種と呼ぶ.

(5) 工事機能: 表 1 の例のように工種を構成する各種の要素的な機能を工事機能と呼ぶ.こいしどう

かずしげ三菱重工業

1982 年 6 月号のf7U-では4 つの工事機能によって工種が構成さ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(33) 339表 1

建設機械の分担する工事機能の例

Lt 到建機種[掘ぷl品土|プルドーザの遂行に同時に複数の建機種組合せケースを採用することを可能とする.以上の結果，利点として数式化が比較的筒明になる.

[o[ ム [0[0(2) 初期モテやルの評価関数[o[ [[
一両二 -~~-----r(b)日r-----[-[‑‑‑‑‑‑
r‑‑‑
T
6‑r
6ン九ヲム

[o[ [[KL+.
E .E {CLιk， loMax
k=ll=lte{1 ， 2 ド， ...T)1

一一一歩 mln.

N t ,J,1:, k ,L,m
建機ランニング・コスト係数(円/月・台) .

[o[o[ [一一CI建機イニシャル・コスト係数(円/月) .

N

建機台数.

t

時間に関する添字.T が全体の工期.

j

工種に関する添字 .J が工種の総数.

i

建機種組合せケースに関する添字 . 1 が工ヨベル

r‑‑‑‑‑
T‑‑‑‑‑
T
6‑r
6ーックノξ ッグホー[o[o[ [ダ γλ ヲム

r-----[------r6-r 厄|モータスクレーパ [o[ ム [0[0れている.同ーの工事機能をもっ複数の建機種が種ごとの建機種組合せケースの総数.
k

建機種に関する添字 .K が建機種の総数.

l

建機クラスに関する添字 .L が建機種ごとの建機グラスの総数.

存在する一方，同ーの建機種でも工種あるいは建機種組合せケースによって担当する工事機能が異m

購入済み分と新規購入分とを区分する添字
m=1 …購入済み分 . m=2 …新規購入分.

なる場合がある.

(6) 最適化評価基準(3) 初期モデルの制約式: 建機費用を評価基準とし，購入済み建設機械も考慮に入れ，与えられfor Vt ε{1 ， 2 ，… ， T}， VjE {1, 2,… , J} ;1

計画・運用計画を求めることになる.

最適化の困難性: 最適化を困難にするP

各工事機能に対する各建機種組合せケース

ごとの各建機種・各建機グラスごとの時間当り平均工事処理能力(工事量/h ・台)
Q

各工事機能の各月ごとの時間当りの平均工台数の整数性等が存在し，結局，この問題は大規模で離散的な最適化問題となる.

事量(工事量/h).

forVtE{1, 2,… , T }, VkE{! , 2,… , K} ,VlE{! , 2,… , L} ;解法

J1512LN山川 I~NULk ， 13.
1 初期モデル(1) 初期モデルの要点

Li=1/C=
11=1 隅 =1

要因として，工種の多さ・工事機能の組合せの複雑さ・建機種および建機グラスの多さ・建設機械

K.
E.
E.
E.
E(Pj.t ム 1 0 Nt ， i ， i ，lc ， l ，情 )"~Qt ， i

た工事量山積みを消化するような建設機械の購入

3.

J

(.
E .E=1Nム1 ，川j ム
j=1;

CR

(ムは実質的には不要)(ηL-;-;:-~--;-:~--~ ------[------|る [--6(d)

(f)

K

1J

よみム正 r-----l-6T----r

(c)

(e)

T51 五五五五五 (CR川村・ Nt ，J， ""k ， t ，机): 全体を 1 つの最適

NUL

各建機種・各建機グラスごとの購入済み化問題にモテゃル化する.具体的には，総建機費用建機台数.

を最小化するように各月・各工種ごとに新規購入(4) 初期モデルの実用性: 初期モテールは容分と購入済み分を区別して用途別に建機種・建機易に整数線形計画問題に変換できるから，実用的グラスごとの投入建機台数を求める.に解けるかどうかは問題の大きさに依存する.変

340 (34)

1 つの工種© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

部分問題 (t， j , i) を適切な順序で生成して繰換後の変数および制約式の個数は次のとおり.変数の個数 =2 ・ T ・ J ・ I ・ K ・ L+K ・ L，の個数 =2 ・ T.K ・ L+T.J;

制約式

T=60 , J=400 ,返し解き，全体の解を得るが，その概略フローは
図 1 のとおりである.図 1 中の記号の意味は次の1=10, K=100 , L= lO であるから，変数 =480，とおり.

001 ， 000個，制約式 =144， 000個となる.若干，問j"

題を変形し，かつ取り扱える範囲を限定するとし

j会ても ，tj"

T=30 , J= lO, 1=6, K=25 , L=5 程度

建設機械計画未決定の工種の添字.

:{j"}のなかの最も重要な工種.
工種 j の工事量が与えられている月のうち，建設機械計画未決定の月の添字.にしかできないから，変数 =450， 125個，制約式=
このように大きな問題は，整数t女:{ti"} のうちの最も重要な月の添字.

性を無視するとしても実用的に解くことは困難で

i"欣:工種 j交の建機種組合せケースのうちそ7 ， 800 個となる.のケースを採用するとした場合の建設機ある.

械計画の試算を未実施であるケースに関そこで，初期モデルの基本的な考え方をできるする添字.

だけいかしながら，実用的に解けるようなモデルを検討した.その結果，実用上のコスト・パフォ

Ut ， J ム 1: 月 t に工種 j に投入し得るイニシャルコーマンスも考慮して，最終的には次に示すモデル

スト加算不要の建機種 k ，を採用することになった.の総建機台数.ただし{j"}= {1, 2,… , J} の場合，

3.
2 最終モデル(1) 最終モテ咽ルの要点

建機クラス 1

Ut ， J ム I=NULk ， 1: 問題の特性を活用して部分的な最適化問題に分割し，それらを全部解いて全体の最適解を求める.具体的には，総建機費用をほぼ最小化するように各月・各工種ごとに新規購入分と購入済み分を区別して用途別に建(の部分問題 (t， j , i) の評価関数・制約式:
KL

Z Z Z1(CRj ム k ， l. Nt , iK L+kL:L: (Clk ,l . Nt ， i ムム 1 ， 2) ー→ min.
=11=1
Nt ， i ， t ， k ， l ， 隅

機種・建機クラスごとの投入建機台数を求める.

工種を十分細分化すればつの工事の遂行に同時に複数の建機種組合せケースを採用する必要性をなくせるから，比較して l つを採用する.ただし，月単位で採用するものが異なってもよい.複ただし，KL

L:L:L: (Pi ， i ι l • Nt ，J， i ， k ， t ，前)ミ Qt ， j=
11=
1m=l

1;

forVkE{1, 2,… , K }, vlε{1 ， 2 ，… ， L} ;Nt ， J ， i ， k ， l ， l::三 Ut ， i ， 州

数工種に投入できる建機種は，重要な工種から投この問題は整数線形計画問題であり，大きさも入する.以上の結果，計算時聞が短くなる反面，変数三三 200個，制約式三三 101 個となって十分実用的解法が複雑になる.に解ける.

(の最終モデルの解法: 最終モデルでは，(4) アルゴリズム: 部分問題 (t， j , i) を解多数の部分問題を解いて全体の解を得る.部分問

くためのアルゴリズムは図 2 に概略フローを示し

題の最小単位を問題 (t， j , i)と表記するが，これているような分校限定法のアルゴリズムである.

は月 t において工種 j で建機種組合せケース t を[FJ は，もとの問題から整数性条件を除去したも採用した場合の最適化問題を意味する.この部分のであり，改訂シンプレックス法を用いて解く.

問題を解くと，新規購入分とイニシャルコスト加分校によって生成された部分問題を解く段階では算不要分に区分した建機種・建機グラスごとの投双対シンプレックス法を用いる.活性節点の選択

入建機台数および建機費用が求められる.

では最新の活性節点を選択する方法をとり，分校

1982 年 6 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(35)341

NO 島平なし
YE 日

最適解あり

活性節点を 1 つ j~ び，
分校により部分問題をつくる

NO

暫定解との比較・更整数解か

事守定解の評価\\|羽数より良いかNO

新.活性節点の整理.

NOlt" j,') 二二世

NONO

図 1

部分問題は 2 っとも検討済みか

最終モデルの解法の概略フロー

NO

解なし

変数の摘出では評価関数式で最大係数をもつものを選ぶ方法をとっている.

4. 実用化結果大規模で離散的な最適化問題を数理計

図 2

分校限定法の概略フロー画法によって実用的に解いた結果に関し，数理計画法の応用技術の側面および具体例の補う形となって全体として有効に機能し，実用化側面から述べる.

が可能となった.

(1) 数理計画法の応用技術にはそデリング・ト(2) 今回の応用技術上の課題としては，大規模ランスフォーメーション・アルゴリス、ムの 3 つの性・離散性・最適化の度合・計算時聞が主要なも要素がある.今回の実用化ではこれらの要素が相のであった.

342 (36)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

表 2最適化の度合の例

方法

建機費用例

ようになる.

(7) 計算時聞については，最適化の度合を犠牲にしなくても現状で十分実用的なものになっている.具体的には，数十億円の建機費用となる場合概略計算の計算時聞が IBM 3033 で CPU5 分程度となっている.

(8) 以上からもわかるように，数理計画法によ(3) 大規模性については，問題を小規模の部分問題に分割して解き，それらを合成することによる最適化の実用化によって十分満足のできる成果をおさめることがで、きた.

り解決できた.この分割・合成は，具体例として取り上げた問題の間有の特性を主としてモデリング段階で利用したものである.

具体例として説明したシステムの実用化は，社

内関係部門の積極的な協力によってはじめて可能(4) 離散性については，アルゴリズム段階で分校限定法を採用して解決できた.分校限定法では活性節点および分校変数の選択方法が問題であっになったことを付言しておく.なお，末筆ながら最適化の考え方についてご指導いただいた京都大学三根久教授に深謝の意を表します.

たが，活性節点は最新のものを選択する方法，分
校変数は評価関数式で最大係数をもつものを選ぶ方法を採用したところ，良好な結果が得られた.

(5) 最適化の度合についても，実用的に十分なものとなった.モデリング段階で問題の分割・合成を行なっているため，想定範囲外の特殊なデータを入力する場合には最適性が保証されない.しかし，通常の場合はほぼ最適と考えて支障ない.

(6) 具体的な最適化の度合は ， tことえば表 2 の参芳文献[1J Garfinkel , R.S. andNemhauser , G. L.:
IntegerProgramming.JohnWiley & Sons ,1972.
[2J 茨木俊秀:整数計画法.オベレーショシズ・リサーチ.

Vo 1. 15 , No.9-Vo 1. 16 , No.1(1970‑71)[3J 石堂一成ほか:不確定性をもっプロジェクトの計
画評価手法.三菱重工技報. Vo 1. 13 , No.6(1976)(2) 文献紹介・局間呼量へのカルマンフィルターの適用

阿部氏:武蔵野通信
その他スタインのパラドックスの話題もでた.

義務未来分析番勝
-第 1 回日時: 4 月 24 日(土)議参予測とその周辺課題縁
日時: 4 月 14 日(水)テム研 15F

議題

出席者

18:00‑21:00 場所早大シス8名

14:00‑17:00

場所:青山学院大学 8 号館第 5 会議室

出席者 13名

議題:日本の高齢化社会における医薬と福祉に関するシステム分析，高森寛氏.
未来分析のメソドロジーとして，本質的支配要因が何(1)文献輪読:予測モデルの選択について
小野氏:鉄道技研

各種の定量的予測モデルの選択につき述べている.

であるかを明らかにすることを当面の研究課題としたが今回はその第 1 歩として老人医療費の増加要因を社会システムの見地からとりあけ.たものであった.その要因とある 1 つのクラスのモデルが他よりも必ず良いというして，市場機能としての競争原理の欠如 L モラールハことはない.予測者はモデルの選釈において，コストやザードの 2 点がクローズアップされたのは，今後の研究モデルの敏感性等を考えて選ばねばならぬ.に示唆を与えるところが大きかった.

1982 年 6 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(37)343