給油施設操業スケジュ ーリング
阿瀬始，茨木俊秀
Il川棚州珊州珊m皿…lllltttllllllttl冊…＝‖脚…l………ll州Il…削川刑胴川t……1t…‖＝‖‖‖＝………l川Illl…………………………＝l川Ill川Il…川l……………lllll州l…‖‖‖‖‖＝m‖＝‖‖‖‖‖‖ ‖＝‖川‖

1．はじめに2。給油施設操業スケジューリング問題

本論文の対象とする給油施設とは，タンカーで運ば

2．1給油施設の概要れてきた油（単一種）をバースから揚油し，施設内の給油施設は図1に示すように，タンカーが到着してタンクに貯蔵後，パイプラインを通して供給先へ送油接岸できるための肯基のバース，陸揚げした油を貯蔵するための設備である．給油施設における操業スケジするための〟群のタンク群，油を供給先へ送るためューリングでは，供給先からの送油要求と，送油要求のエ系統のパイプラインからなる．各タンク群は一般に対して決められた配船計画にもとづき，タンクの受に同じ容量の複数のタンクを有している．さらに，泊入れ／払出し順序の約1週間から1カ月の計画を作成をバースから陸揚げする設備や供給先へ油を送り出すすることが求められる．

ためのポンプ，バースとタンク，タンクとパイプライ

図1はこの給油施設の構成を示したものである．タンを結ぶ施設内配管や経路切換えのためのバルブ等をンカーで運ばれてきた油を揚油して施設内のタンクに有する．各バースは揚油配管系統によりどのタンク群貯蔵するためには，タンカーを複数あるうちの適当なにも接続可能である．本論文では．打≦」材として議論をバースに着船させ，揚油配管上のいくつかのバルブを進めるが，∬＞〟の場／合への一般化も可能である．受切り換えて，揚油配管を通してバースと目的のタンクけ入れるべきタンクを切り換えるとき，切換え先のタ群とを接続しなければならない。あるバースとタンクンクが元のタンクと同一タンク寮内であれば，その切群を接続するためには，そのバースとタンク群の対応換えは短時間でできるので操業上は支障をきたさない。

関係を実現するバルブを開くだけでなく，そのバースそれに反して，それらが異なるタンク群に属するとき

あるいはタンク群がそれぞれすでに別のタンク群あるは，バースとタンク群を結ぶ施設内配管のいくつものいはバースにつながっていた場合にはそれらの対応関バルブを切り換えることが必要となり，非常に時間が係を実現していたバルブを閉じなければならない．そかかる．特にこの切換えが揚油中に発生すると，タンの結果，これらのバルブの設定にはかなりの手間がかカーの出航を遅らせることになる．

かるのが実情である．したがって，いったんある設定

また，バースは着桟可能なタンカーの積載量によっで運用を始めると，その日はできるだけ設定変更はしてJ個のグループに分けられる．各バースの揚油速度たくないという強い要求がある。そこで，各日のスケは等しいとする．

ジュールにおいて，バースとタンク群の対応関係の変2．2 タンクの運用方法更回数を最小とすることが要請される．

本研究はこの目的を達成するタンク繰りスケジューリングシステムの開発を目指したものである．

各タンクはいったん受入れを始めたら，途中で受入れを中断することなく，満になるまで抽を受け入れ続ける．ただし，満になる前に揚油が終了した場合は，あせ はじめ NKK制御技術部

まだ満になっていないが受入れ終了（中断）になる．

〒230′8611横浜市鶴見区末広町2−1

満になって定められた静置時間（24時間）以上経過す

いばらき としひで

ると払出しが可能となる．払出しは空になるまで行い，京都大学大学院 情報学研究科 数理工学専攻

その後再び定められた静置時間（3時間）以上経過す〒606−8501京都市左京区吉田本町

ると受入れ可能となる．各タンクにおける受入れある1998年11月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（15）603

、． ‥ ．‥‖‥・．∴・！．し こ 、パイプライン1

パイプラインエ
バース．打園］し 給油施設

いは払出しの作業がそれぞれ満あるいは空になる前に置を経てタンクは払出し可能となるから，ある日の払中断した場合は，そのタンクの次の作業は中断した作

出しスケジューリングは，当日の送油要求と前日のタ業の継続となり，再開時の静置は必要でない

ンク状態と在庫量を入力として実行される。送油に際してのタンク群選択には特に考慮する点はなく，先入3。聞題の記述

れ先出しの原則に従って受け入れた順に払い出すタン

給油施設における操業スケジューリング［1］とは，クを選択するだけである。＋−一方，受入れについては，供給先からの送油要求と，送油要求に対してあらかじ

受け入れるべきタンクを受入れ可能なタンクの中からめ決められた配船計画を入力として9 タンクの受入

巨∃由に選ぶことができる。各タンクは送油によって空れ／払出し順序の1週間〜1カ月間の計画を作成するになったあとは3時間の静置で受入れ可能になるので，ことである。

その日の途中から受入れ可能となるタンクがあり得る。

もう少し細かく見ると9 図2に示すように9 このス

すなわち9 受入れスケジューリングは，配船計画にもケジューリングは払出しスケジューリングと受入れス
ュ山リングとからなる。受入れ後2那寺間以上の静とづくその臼に到着するタンカーの到着時刻，揚油時ケジ間帯，揚油量と，前日のタンク状態と在庫量9 および送油要求
タンク状態と在庫量

図2 給油施設操業スケジュー】ノング6関砲（且6）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレ」ションズ。リサーチ

当日新たに受入れ可能になるタンク情報を入力としてンク群∽が時刻五で量γを受け入れることになったと実行される．この受入れスケジューリングが操業スケする．このとき，更新後のタンク群受入れ可能量をジューリングの中心であるので，単に操業スケジューリングというと受入れスケジューリングを指すことが多く，本論文でもそのように扱う．
今説明したように，前日までのスケジューリング結果が既知であるとすると，その日のスケジュールに必要なデータはすべて決まってしまう．したがって，1Ⅴ，∽（わ）とすると；乃≦オ≦ⅣⅤ，れ）＝（ min（lん（り，lん（f乃）−γ）；1≦才≦乃−1lん（Jど）−γとなる．なお，スケジューリング開始時のlん（≠）を帆（f）と表す．
揚油グループ筏，ノ＝1，．．．，′は，揚油を揚油量の大き週間から1カ月間のスケジュールを，全体をまとめてさでグループ化したときの大きい方からノ番目のグル解かなくても，1日単位で前から順番に作成していくー70である．このグループ化は着桟可能なタンカーのことにすれば，最適値の保証はできないが，実用上有大きさによりバースがグループ化されることに対応し効な結果を得ることができると期待される．ている．

1日あたりのスケジューリングは，各揚油へのバー

β乃は揚油乃の割当て可能バース集ノ合を表し，揚油乃ス割当てとタンク群割当てとからなる．バース割当て（のタンカー）が着桟可能なバースで，かつ揚油乃ととは各揚油にそのタンカーが着桟可能なバースを1つ時間がオーバーラップしている揚油に割当て済みでなずつ割り当てることである．揚油中にバースを替えるいバースからなる．この集合もスケジューリングの進ことはしないので，割り当てられるバースは1つずっ行とともに次のように更新される．スケジューリング

である．タンク群割当ては各揚油にタンク群を割り当のある段階で，揚油乃がバース如こ割り当てられたとて，そのタンク群の受入れ可能量の範囲内でその揚油するとき，更新後の揚油才の割当て可能バース集ノ合は，の揚油量の全部または一部を受け入れさせることであβ才一（々）；揚油オと乃の時間がオーバーラップ

β ∫＝る．このとき，揚油を介して（バース，タンク群）の組（βゴ ；そうでない合せができるが，1日の中でこの組合せを途中で変更となる．なお，βfの初期値はオ∈」珠のとき，グループする回数が最小となるスケジュールを作成することが

筏の揚油が着桟できるすべてのバースの集合である．

目的である．

グラフG＝（朽，旦タ）はノ番目までのグループ且，月ら，‥り既に属する揚油を節点とし，2つの揚油が時間4．解 法

的にオーバーラップするとき対応する節点間を枝で結3．で述べた組合せ最適化問題は，整数群の分割問題んでできるグラフである．グラフGにおいて，そのであるPARTITIONを特別な場合として含んでいる中の任意の2節点が枝で接続されているようなγ個のので，明らかにNP困難であり［3］，常に厳密解を効

節点からなるクリーク［4］をγ一クリークという．

率よく求める解法は期待できない．したがって，実用以上の記号と概念を使って，アルゴリズムは次のよ性のある近似解法が求められ，文献［2］で筆者らは問うに記述できる．

題の特徴を活かしたアルゴリズムを提案した．以下に

車型

そのアルゴリズムを示す．

1）揚油乃＝1，…，Ⅳ，タンク群∽＝1，…，〟に対し，まず，アルゴリズムで用いる記号と概念を述べる．
揚油に開始時刻の小さい順に番号1，…，Ⅳをつけ，んzを揚油乃の開始時刻とする．1ん（才）はタンク群∽の時刻gにおける受入れ可能量を表し，タンク群∽に属する受入れ可能タンクの空容量の和のその日の時刻J以後のすべての時刻における最小値である．その日の途中から受入れ可能となるタンクがあるので，スケジューリタンク群の受入れ可能量I‰（′乃）を求める．
2）揚油乃＝1，…，Ⅳを揚油量の大きい順にグルー70〟1，月去，…，既に分ける．
3）揚油乃＝1，…，Ⅳの割当て可能バース集合β乃を求める．

4）ノ：＝1とする．

St印2 グラフGの作成と極大クリークの抽出

ング開始時の1ん（才）は単調非減少な階段関数である．

グラフGを作成し，Gの極大クリークCl，‥．，Cざをアルゴリズムの中では時刻チ乃における値があれば十分すべて求める．グラフGに節点が存在しなければであり，この値はアルゴリズムの進行に伴い次のようStep6に行く．に更新される．揚油乃へのタンク群割当ての結果，タ
1998年11月号

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

（17）605

クリークCl，…クCぶの中から，③結果のタンク群受入れ可能量陥（才乃）が最小となる①血nl彪乃トγ（Cざ）が最小のクリークCgを選ぶ心 こ

タンク群を選ぶひ，ごlt ＼各ル、け一−−−ルでタンク群受入れ可能量が負にならないタ

こに，γ（Cざ）はクリークC5の節点数であるの②条件①を満たすクリークが複数あるときは9ンク群を選ぶことが原則であるが，それしか選択の可能性がない場合は，負の量が最小になるタンク群を選lβ乃弓が最小のクリークC5を選ぶ。

（∋条件②を満たすクリークが複数あるときは，∑・∴し ヽ択する隕 バー】−スの割籾ては，選ばれたタンク群がバー】彪乃Eが最ノJ、のクリい・クCsを選ぶ働 これが複数ある

スとの対応がすでについている場合はそのバースを割ときは，どれか1つを自由に選ぶ。ただし，条件り当てる点 そうでない場合は，割当て可能バース集合（説②，③における評価対象となる揚油漑は，バ、−mの中のバーー〝スのうちタンク群との対応がまだついていスを割当て済みでない揚油とする巾

ないバ、爪−−−−スを任意に選んで割り当てる。

姐旦 揚油の選択

なお，このアルゴリズムは基本的に（バース選ばれたクリ・劃クCsの中のバースを割当て済みでク群）の組∴合せの変更回数が0の解を求めようとする

ない揚油の中か玩 巨銑lの最小の揚油裾を選ぶ㊤ 同ものであり9 場合によってはタンク群の受入れ可能量

じ条件の揚油が複数あるときは番号が擬人の揚瀾悌を超えて揚油を受け入れることがあるw もちろんそのを選ぶ￠

ような解はタンクのオー【バーーフローという事態になる，タンため実行l昭詣ではないから9 芙行可能な解にするため

些至里選ばれた揚油偶に，後述するバース◎タンク群割当の修正が必要となる巾 この修正アルゴリズムについててルールに従いバースとタンク群を割り当てる。そはここでは述べないので，文献［2］を参照されたい。

して，タンク群受入れ可能量，割当て可能バース集

毎軋 揚油には揚油量の大きな揚油から′J、さい量の合を更新する帥 このクリークの中にバー叫スを割当て揚油まであり，′受入れ側のタンク群にも受入れ可能量済みでない揚油が残っていればstep4に戻る。残の大きなものから小さいものがある。もし，揚油量のっていなければstep2に戻る。

小さな揚油から順にタンク群に割り当てていくとする

墾狙旦と9 割当て−が進んでいくにしたがって各タンク群の受Step2へ戻る。

入れ可能童は小さくなっていくから9 揚油量の大きなアルゴリズムのS臨p5で用いたバー¶スとタンク群揚油に割当てるときに9 各タンク群の受入れ可能量の割当てルールを以下に示すけ

中にこの揚油量以上のものが残っていない恐れがある。

（1）割当て候補タンク群集合アを求める。rはヲ 割

揚油量がタンク群の受入れ可能量を止二回っている場合当て可能バース集合の中のバースとすでに対応済

は9 揚油途牒でタンク群切換えが必要となるので，こみのタンク群ヲ およびバースとの対応がまだついれは極力避けたい事態である。

本アルゴリズムは9 給油施設操業スケジューリングていないタンク群からなるの（2）集合アの中から，次のルhル（卦〜③に従いタンク群を割り当てた結果の影響が最小のタンク群を問題の特性を踏まえてこのような状況を避けることをねらいとしたものであり，次のような特徴をもつ。
1）揚油鼠の大きな揚油から順に割り当てる。

選ぶ￠①揚油グループ邸ブの揚油がまだ残っている場合はヲ

2）バ、−ス選択の制限の厳しい揚油から先に割り当結果としての頂ん（才乃）から構成される集合（Ⅴ椚（㍍）：タ据∈γ），（ym（㍍一1）：プ鶴∈ア），。。。，（‰（fl）∴椚∈γ）をこの順番に調

東風 パーースに着桟可能なタンカーグループ（1）K＝M＝4の給油施設（2）K＝M＝6の給油施設

べていき，その値が既を定義する最大揚油量以上である要素の個数の変化が最も遅く現れるようなタンク群を選ぶ。

②結果としての数列−ん（㍍），陥（f乃▼1），【い。。
陥（￡1），椚∈アほ仁血走かどこかで値が減少する。この値の減少が最も早く現れるタンク群を選ぶ。
6随6（18）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ。】jサーチ

表2 タンク群の容量（1）K＝M＝4の給油施設（2）K＝M＝6の給油施設

タンク群 タンクの容量 タンク数 タンク群の容量

タンク群 タンクの容量 タンク数 タンク群の容量

3000［KL］ 39000［KL］
9000［KL］ 2 18000［KL］
3000［KL］ 39000［KL］
9000［KL］ 2 18000［KL］

1234 423000［KL］ 33000［KL］ 339000［KL］ 2 18000［KL］

145 563000［KL］ 33000［KL］ 39000［KL］ 29000［KL］
9000［KL］
9000［ⅩL］
9000［KL］

18000［KL］

条件がゆるくなるので問題としてはやさしくなる．まてる．

3）割り当てた結果のタンク群受入れ可能量をチェ

た，揚油条件は番号が大きいほど問題としては難しくックすることにより，残りの揚油のタンク群割当なる．図3における升目の中の番号才は，1≦ノ≦才なるての可能性が大きくなるようなタンク群を選ぶ．

すべての揚油条件ノに対しバース・タンク群対応の変更
回数0の最適解が得られたことを示す．

5．実証結果と評価

また，他の手法との性能を比較するため，他に2つ本アルゴリズムの有効性を検証するため，4バーの手法（これを他手法1，他手法2と呼ぶ）でも同じス・4タンク群，すなわち斤＝〟＝4の給油施設と6バ問題を解いた．他手法1と2は，揚油の大きさ順に進ース・6タンク群，すなわち宵＝〟＝6の給油施設に本める本アルゴリズムとは異なり，揚油の時刻順に割当アルゴリズムを適用した．これらの給油施設の設備諸てを進めるもので発想としては自然である．また，各元のうち，バースに着桟可能なタンカーグループを表

揚油にタンク群を割り当てるとき，他手法1は余裕の1に，タンク群の容量を表2に示す．この2つの施設大きなタンク群から優先的に割り当てる考え方であり，に対し，それぞれ表3に示す4つの揚油条件とタンク受入れ可能量が最大のタンク群を選ぶ．他手法2は本群受入れ可能量の条件アルゴリズムの考え方を一部取り入れ，その揚油の属．り ①最初の揚油開始時の初期値：∑帆（′1）

する揚油グルー70番号をノとすれば，候補となるタン

ノ〃＝l

斤＝〟＝4の場合二15000，18000，21000，24000［KL］

ク群のうち受入れ可能量がノ番目の大きさのタンク群

g＝〝＝6の場合：18000，21000，24000，27000［KL］を選ぶ。候補となるタンク群がノ個より少なければ受．1J②当日新たに受入れ可能となる量：∑（取（れ）−入れ可能量が最小のタンク群を選ぶ．各手法を適用し〝J＝l仇（才1））た結果を揚油条件ごとに示したのが図4である．図4

宵＝〟＝4の場合：24000，27000，30000［KL］

における縦軸，横軸は図3と同じである．図4におけ斤＝〟＝6の場合：33000，36000，39000［KL］

る升目の中の番号は変更回数0の最適解が得られたアのもとで，最適スケジュールを計算した．計算には揚ルゴリズムを示しており，油条件において各揚油の揚油開始時刻と揚油量，タン1……本アルゴリズムのみ

ク群受入れ可能量条件において∽＝1，．‥，〟，乃＝1，…，2……本アルゴリズムと他手法2Ⅳに対する帆（才乃）というさらに詳細なデータが必要

3……

であるが，紙面の都合で省略した．結果は図3に示す

3つのアルゴリズムすべてである．升目の中の番号0はどのアルゴリズムでも変通りである．図3において横軸は最初の揚油開始時のタンク群総受入れ可能量，縦軸は当日新たに受入れ可γ（1）∬＝」快4（2）斤＝脾61518 2124

18 21 24 27能となる量である．右方向あるいは上方向に行くほど
表3 揚油条件（1）K＝M＝4（2）K＝M＝6

揚油条 揚油数 総揚油

揚油条 揚油数 総 揚油

件番号 N

件番号 N1234［KL］

25000
28000
93200010 35000
7182

1998年11月号

34［KL］

10111213

33443000
7000
4000
7000

ズ＝最初の揚油開始時のタンク群総受入れ可能量［1000KL］

ァ＝当日新たに受入れ可能となる量［1000KL］

図3 本アルゴリズムの求解性能© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（19）607（り∬＝ル整＝4の場合

1518 2124 1518 2124

1518 2124 1518 2124
（2）」灯＝ル㌢＝6の場合

18 2B 24 27 18 21 24 27
B8 21 24 27 18 21 24 27戌∵ニ最初の揚油開始時のタンク群総受入れ可能量［1000KL］
アニ当田新たに受入れ可能となる畳［1000KL］
圏梯 他手法との比較

更回数0の最適解を得ることができなかったことを示ゴリズムが開発できた。本アルゴリズムは，問題の条している。図4から，甜＝ガ＝4の小さい方の給油施件がかなり厳しいときにも変更回数0の最適解を見つ

設では揚油条件とタンク群条件が厳しくなければ他手けてくれる可能性が高いが，実際の給油施設では設備法2でも最適解を見つけているが，揚油条件とタンクをできるだけ有効に使おうとするほど厳しい条件のも群条件が厳しくなると本アルゴリズムでなければ変更とでの運用になるので，本アルゴリズムの有効性はよ

回数0の最通解が得られないことがわかる冊 この傾向り高いと考えられる。

は∬＝ノ膵＝6の大きい方の給油施設の場合により顕著

参考文献である。単純なヒューリスティックにもとづく他手法
1では，問題の条件がかなりゆるくない限り最適解が［1］湊，掛谷，根津：給油施設の能力評価と操業スケジ

ュ」リング；NK．K捜報，No．153，pp．106−113（1991）

得られないようである。）［2］阿瀬，茨木：給油施設操業スケジューリング；シス

テム制御情報学会論文誌，Vol．11，No．5，pp．223−−．・ニー−こ−．

232（1998）

給油施設の操業スケジューリング問題はNP困難［3］M．訴∴Garey and D．S．Johnson：Con砂ute7S andな組合せ最適化問題であり，制約の厳しい場合も含め，J‥／‥・∫．イ＼ご′こ ．∴．リ∴ い／∴ ●J、／．・．・＝．ミ・り−、、

常に厳密解を効率良く求めることは期待できないが，

Pleteness，W−H．Freeman（1979）

問題の特徴をうまく利用することにより，良い解（多［4］Fmarary：Gプてゆh 77zeo77，Addison−Wesley

くの場合貴通解）の得られるヒューリスティックアル（1969）、ご‡照準強沖虔嘩策」二、・十・、
5月22日（金）理事会において9 会員の増強策として以下の臨時措置が決定された。
（1）学生会届から正会員に移行した会員の初年度の会費は半額とする（具体的には，12，000円の正会員会費が初年度6，000円となる）￠（2）他学会からの会員勧誘策として，他学会会貝は入会金なし，会費は1年間に限り半額とする。
（3）当学会が主催するシンポジウム，セミナー等に出席した八で9 当学会に入会を希望する人は

6田8（20）

入会金なし，初年度会費は半額とする。
ただしヲ（2）および（3）の措置は今後2年間限りとする。これらの促進策は財政検討委貝会の第8次報告に基づく措置で，厳しい財政状況の中で，会員増強の有力な特典として決定されたものであります。
ぜひ，皆様の周囲でご入会を希望される人がいれば，これらの特典をご説明の上，ご勧誘いただければと思います（なお，この臨時措置は5月25日以降の入会希望者に適用されます）。

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

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