日本財団 図書館


遺伝的アルゴリズムを用いた不定期船の配船計画作成に関する研究
正員 松倉 洋史*   正員 渋谷 理*
正員 勝原 光治郎*  正員 大和 裕幸**
 
* (独)海上技術安全研究所
** 東京大学・新領域創成科学研究科
原稿受理 平成17年10月14日
 
Study on Tramper Allocation Planning Using Genetic Algorithm
 
by Hiroshi Matsukura, Member
Osamu Shibuya, Member
Mitujirou Katuhara, Member
Hiroyuki Yamato, Member
 
Summary
 Tramper allocation is important and difficult work operation because it affects heavily on transport efficiency and stability although a lot of factors must be considered carefully and properly. Some information technologies are partially used in data collection, display and editing, but planning itself is done by human resources. Provided that high performance tramper allocation plan be generated automatically by using computer program, it is very useful not only for labor saving but also for seeking further enterprise-level efficiency and rationalization through various analysis. Notwithstanding above benefits, transport system dealt with real business is so complicated and large in scale that it is highly difficult to replace tramper allocation operation with computer algorithm and solve it within the time suitable for practical use.
 In this paper authors tries to mitigate above difficulties by using Genetic Algorithm (GA), one of heuristic methods, and by using logistics simulator to evaluate each chromosome's score (fitness) precisely. First, we develop allocation algorithm and analysis system, secondly we apply it for a small model to observe its attribution, and lastly apply it to transport system modeled with real ship operator and assess the feasibility of our approach. We could conclude that our approach is applicable, and introducing heuristic database is useful and sometimes indispensable.
 
1. 緒言
 不定期船輸送における配船計画は、輸送の効率性・安定性等(以下、輸送性能と記述)に大きく影響する上、考慮すべき要素の多い、非常に重要かつ困難な作業である。しかし、データ収集・表示・編集等で一部IT技術が用いられているものの、配船案の考案自体はほとんどが人手により行われている。
 仮に、コンピュータを利用して優れた配船計画を自動で作成することができれば、作成作業の効率化が図れるだけではなく、配船の自動生成システムの性能を向上させることでランニングコストの抑制、使用船舶数の削減等の輸送効率化が可能である。また、多くの想定事例に対して速やかに配船案を得られることから、供給安定性の向上・輸送関連設備投資計画の評価・地震等災害時対策の立案等、様々な検討を精度よく効率的に行うことが現実的となる。しかし、実務で対象とする輸送システムは非常に複雑かつ大規模であるため、全国規模の配船作業をコンピュータ上のアルゴリズムに置き換え、期的時間内に解くことは非常に困難である。
 上記の配船問題は、いわゆる在庫を考慮したルート決定問題の1つである。在庫を考慮したルート決定問題は、国内外で多くの研究が行われているが例えば1)など、海外における研究はほとんどがトラック等の非船舶を対象としたものであり、不定期船を対象としたものは少ない2)3)。また、国内における研究は、今までのところ著者らによる取り組み4)〜8)による他はあまり行われておらず、これらも混載・複数港荷役等への対応に関して十分とはいえない。
 本報告では前述の困難を解決するため、遺伝的アルゴリズムの枠組みを用いると共に、各染色体の評価にシミュレータを用いることとした。配船アルゴリズム及びそれを実現するためのシステム開発の後、小規模な輸送モデルを対象に配船を自動生成して特性を把握した後、実船社を対象とした輸送モデルを用いて配船計画を自動作成し、本手法の有効性を検討する。
 
2. 不定期船の配船
2.1 概要
 多くの不定期船社では、陸上タンクの在庫、荷主の要求やタンカーの位置・状態、港湾情報等の輸送関連情報を集約・分析する配船センターを設け、同種の荷物を扱うタンカーに関して配船計画を一元的に作成している(ただし、港湾内等の至近距離輸送に用いる小型の平水船などを除く)。
 配船センターから各タンカーに届く指示は、荷役月日、港、製品種類、荷役量、荷役種類等の輸送に必要な基本情報のみであり、各タンカーはそれをもとに航行経路、沖待ちの要不要、入出港時刻、荷役開始/終了時刻等、配船指示が可能となるよう現場の状況に応じた詳細な計画を立てて実際の輸送活動を行う。
 なお、配船計画を作成する期間は1月間分程度が多く、計画作成後に変更が生じた場合は、残りの期間における配船計画を実情にあわせて修正することとなる。
 
2.2 輸送形態の分類
 不定期船による輸送は、大きく以下の2種類に分かれる。ただし、実際の輸送では両者が混在したものも多い。
(1)オーダー式
 荷主が船社に対して荷役月日・港・製品種類・荷役量等の輸送の指示(オーダー)を出すものである。船社側はオーダーを受けて各輸送指示に対して船舶の割り当てを行う。船社は、主にどの船をどの輸送に割り当てるかという自由度しか持たないが、荷役月日については交渉により多少前後に動かすことが可能である。
(2)タンクバランス式
 船社が陸上のタンクの在庫(タンクバランス)を管理している場合である。トラック等の陸上輸送におけるVMI(Vender Managed Inventory)方式に相当するものである。すなわち、荷主からはタンクをオーバーフローあるいはドライアウトさせないということのみを依頼され、どのような輸送を行うかについては一任されている場合である。船社が荷主と一体となって輸送を行っている場合の他、荷主が自社船隊を有して輸送を行っている場合もこれにあたる。
 (1)と(2)を比較すると(2)の方が輸送の自由度が高い。すなわち、輸送の探索空間が広いため、通常は輸送性能が高い配船を作成することが可能である。トラック等による陸上輸送で輸送効率化の有力な手段としてVMI方式が普及しつつある現状を鑑みれば、海運分野でも更なる輸送性能の向上が可能であるとして、(2)方式の割合が高くなっていくことが期待される。その場合、両者が混在した状況に対応する必要があるが、探索空間が狭い(1)の手法を(2)へ拡張することよりも(2)に制約条件を付けて(1)に対処する方が、開発の見通しが良いと考えられる。
 以上により、本報告では(2)のタンクバランス式の輸送形態を取り上げることとする。
 
2.3 自動配船の困難性
 計算機による不定期船の配船自動化を困難にしているのは、主として次の理由である。
(1)輸送単位が数百〜数千トンと大きい上に、使用する船の隻数も限られるため、個々の輸送遅延の影響が大きく、各輸送の正確な取り扱いが必要(例えば、入港時間に間に合わなければ翌日以降の入港・荷役となる等)。
(2)船舶、港湾、貯蔵施設、工場、需要家、航路状況等、考慮すべき条件が複雑かつ多岐にわたる上、配船アルゴリズム上でのそれらの統一的な取り扱いが難しい。
(3)混載、複数港積み、複数港揚げ、帰り荷の考慮等、輸送形態が多様であり、また、入出港、積み揚げ、沖待ち等の時刻等、活動の状態を変化させるタイミングが無段階である(どの時刻で切り替えても良い)ため、組合せ爆発が起きやすい。
 上記困難に対処するため、幾つかのヒューリスティック手法の中から遺伝的アルゴリズムの枠組みを用いると共に各染色体の評価にシミュレータを利用することで、実用的な工数及び計算時間内で輸送を実施可能な解を求めることを試みる。
 
3. 遺伝的アルゴリズム
3.1 遺伝的アルゴリズムの概要
 遺伝的アルゴリズムは複数の実行可能解を保持しつつ、その解を進化のアナロジーを用いて改善していく方法の総称である9)
 最も基本的な遺伝的アルゴリズムは次のように表現できる。ただし、P(t)は第t世代の集団、交叉及び突然変異を行う関数をgenerate()、選択を行う関数をselect()とする。
 
1 t=0
2 P(0) = executable initial chromosome pool
3 while termination criteria ≠ yes
4 p'(t+1) := generate(P(t))
5 p(t+1) := select(P'(t+ 1))
6 t:=t+1
7 return best answer in P(i),i=0,..., t
 
 上記の基本的な枠組みは踏襲しつつも、解こうとしている課題に適合するよう、染色体生成法、性能評価法、評価関数の構成、各種パラメータの調整等を研究・開発することとなる。
 なお、解析対象及び遺伝的アルゴリズムの構成方法によっては、適切に解くことが困難となる場合もある。
 
3.2 自動配船の実現に向けたアプローチ
 本稿では染色体の輸送性能の評価を、多項式からなる評価関数等により静的に行うのではなく、物流シミュレータ上で動的に行うこととした。即ち染色体に配船計画案を記述し、検討対象となる輸送システムを出来るだけ忠実に再現したシミュレータ上で実行して輸送結果のパラメータを収集することで、どの程度の輸送性能が期待できる配船案であるのか評価する。
 シミュレータを用いることで、輸送性能の評価で時間がかかるデメリットはあるものの、次のようなメリットを享受可能である。
(1)入出港制限時間帯や船舶の仕様等、輸送システムの条件が変化しても、ほぼ同一の配船アルゴリズムで対応することが可能である。同様に、シミュレータの設定ファイルや染色体の生成用のデータベースを編集することで、多様な企業に対してもかなりの程度対応可能である等、汎用性が高い。
(2)解析対象の複雑さの増加は主としてシミュレータ部分が担うため、アルゴリズムが単純となる。なお、シミュレータの作成においては、オブジェクト指向プログラミング技術及び関連技術を適切に用いることで、現実世界の持つ複雑さを実用的な工数内で取り扱うことが可能と考える。
 ただし、遺伝的アルゴリズムの理論的解明は完全には行われてはおらず、適切な集団数・交叉率等、調整すべきパラメータが多数あるにも関わらず、その調整は試行錯誤で行う必要があるという欠点がある10)11)
 
3.3 構成
 
Fig. 1 Structure for Tramper Allocation Algorithm
 
 上記を実現するための自動配船システムの構成をFig. 1とした。
 まず、進化機構側で初期染色体プールを生成し、次に各染色体を物流シミュレータに送って輸送性能を評価する。その際、シミュレータは染色体を読み込み、解析対象に近似するよう設定された輸送環境下で航行計画を仮想的に実行し、輸送性能関係のパラメータを収集する。シミュレーション終了後、それらを用いて評価値の計算を行う。全染色体の評価値を計算した後、優秀な成績を残した染色体の特性が残りやすくなるよう次の世代の染色体を生成する。
 次世代の染色体生成においては、まず、成績の良い染色体が確率的に多く残るよう選択を行い、続いて、選択された個体を対象に交叉及び突然変異を行う。それらにより形成された染色体プールを再びシミュレータで評価する。以上を終了条件を満たすまで繰り返す。
3.3.1 染色体の初期発生
 染色体は2.1で述べた様な、港名・積み/揚げ・品目等の荷役の最も基本的な情報(荷役情報)を単位とする遺伝子列を隻数分順に並べたものである。以下の2種類のデータベースから乱数で生成される。
(1)遺伝子データベース(Gene Data Base: G-DB)
 上記の荷役基本情報を網羅的に登録したものである。例えば、A港において品目Bの消費側タンクがある場合は“港名:A、品目:B、荷役種類:揚げ”という遺伝子が登録される。
(2)ヒューリスティクスデータベース(Heuristics Data Base: H-DB)
 あらかじめ有効と思われる上記遺伝子の組合せを登録した知識データベースであり、以下の3種類から構成される。
(1)実務従事者の知見:実務従事者の経験及び過去の配船事例から収集して登録したもの。
(2)解析者の判断:解析者が輸送構造を分析して、必要、あるいは優れていると判断した組合せを作成して登録したもの。なお、将来的にはコンピュータプログラムの支援等により、当該エントリーを作成することも可能と考えている
(3)過去に生成した事例:過去の自動生成の試みにより、優れていると思われる組合せを登録したもの。
 ヒューリスティクスデータベースのエントリーには荷役ホールド数が記述してあるが、遺伝子データベースのエントリーには記述されていない。荷役ホールド数は、染色体に組み込む段階で乱数によって決定される。また染色体には荷役すべき日時の記載はなく、シミュレーション実行時にシミュレータ上の船舶が周囲の状況を判断しながら可及的速やかに輸送計画を遂行することとなる。
3.3.2 評価
 各染色体の適合度の評価値Fは、FtimeとFinventoryの積により算出される値とし、小さい方が優れているように構成した。
 
F=Ftime×Finventory
 
(1)輸送持続時間をもとにした評価値(Ftime
 輸送が持続した時間、すなわち配船案を実行して、陸上側の全てのタンクがオーバーフローもしくはドライアウトしなかった時間(以下、輸送持続時間)tをもとに、以下により算出される値である。なおCtは任意の定数(ただしCt>1)、Tnecessaryは必要な輸送持続1時間(例えば33日間の輸送計画を立てるならば33×24=792時間)である。Ftimeは小さい方が望ましい。
 
Ftime=Ct-t/Tnecessary
 
(2)タンク残量をもとにした評価値(Finventory
 輸送を持続できなくなったとき(いずれかのタンクがオーバーフロー/ドライアウトしたとき)、もしくは持続時間がTnecessaryに達したときの各タンク残量をもとに、以下により算出される値である。なお、Ciを任意の定数(ただし輸送持続時間の影響を在庫の影響より大きくするためCi>Ctとする)、icurrentをシミュレーション終了時の在庫量、itargetを在庫の目標値(ここではタンク容量の50%)、Vをタンク容量とする。Finventoryは小さい方が望ましい。
 
 
 進化過程の前半では輸送持続時間が短い(オーバーフローもしくはドライアウトにより短時間で輸送に失敗する)ことから、Ftimeが支配的である。しかし、全体の評価値FをFtimeとFinventoryの積とすることで、同一の輸送持続時間でもタンク残量のバランスが改善されれば評価関数値Fは向上する。これにより、同一持続時間の配船案同士における探索能力を確保できるようにした。
 また、Ftimeはひとたび必要輸送持続期間に達した後は一定値となり、後は必要輸送持続期間終了時のタンク在庫量の改善が行われる。
3.3.3 選択
 成績の良い上位から一定数の染色体は、無条件に次世代に残し、優秀な染色体の消滅及び破壊を防ぐこととした。
 また、選択はトーナメントにより行い、進化過程後半で各染色体の評価値が接近しても進化時の淘汰圧が下がらないようにし、局所探索能力を出来るだけ確保するよう配慮した。
3.3.4 交叉
 ランダムに選んだ染色体に対し2点交叉を行う。探索範囲が広くなるよう、同一染色体が複数回の交叉を受けることも可能とした。
3.3.5 突然変異
 乱数により輸送内容の一部を遺伝子データベースの組合せもしくはヒューリスティクスデータベースの内容と入れ替える。探索範囲が広くなるよう、同一染色体の複数回の突然変異も可能とした。
 
4. 自動配船システムの開発
 Fig. 1に従い、コンピュータ上に自動配船システムを実装した。ただし、物流シミュレータの開発・管理を容易にし、汎用性を上げるため、また、将来は並列分散計算に対応出来るようにするため、進化機構と物流シミュレータは完全に分離し、別プログラムとした。なお、進化機構とシミュレータ間のデータのやりとりは、汎用性を上げるため、インターネット及びイントラネットの汎用的な通信規格であるTCP/IP(Transmission Control Protocol/Internet Protocol)を用い、LANを介して行えるようにした。
 また、物流シミュレータとしては、物流システムを構成する要素のうち、物流計画部門を除いた生産・輸送・販売の現場活動に相当する機能を担当する部分をコンピュータ上に再現した。Fig. 2に開発したシミュレータの画面表示例を示す。
 
Fig. 2 Simulator Snap Shot
 
 シミュレータの各要素はマルチエージェントとしてプログラムされ、各エージェントは配船センターの基本的な輸送指示(配船案)に従って情報収集・判断を行い、詳細な行動計画を作成して自律的に活動を行う。
 タンカーは、地図上に設定したノード・パスの中からダイクストラ法により最短時間となる経路を探索して移動する。


前ページ 目次へ 次ページ





日本財団図書館は、日本財団が運営しています。

  • 日本財団 THE NIPPON FOUNDATION