学位論文 銀行間支払い順序決定アルゴリズムに関する研究

立花, 慎也  ,  タチバナ, シンヤ

pp.1 - 31 , 2015-03-25 , The University of Electro-Communications
内容記述
本論文は、銀行間の支払い順序を決定するためのアルゴリズムを検討する。ノードを銀行、重み付きエッジをある銀行から別の銀行への債務とすると、銀行間の支払い順序問題は有向グラフで表される。ここで、各銀行は債務を履行するために一定の自己資金を用意する必要があるが、他の銀行からの支払いを考慮することで、その自己資金は与えられた支払額よりも小さくできることがある。しかし、その債務の決済がどのような順番で行われるかにより、用意しなければならない自己資金の額は変化する。また、銀行が自己資金を調達するにはコストがかかるため、その資金量は少ないほうが望ましいが、そのための最適化アルゴリズムに関する検討はこれまでされていなかった。そこで本論文では、銀行全体の資金量を最小化する決済の順番と決済に必要な資金投入額の最小値を求める問題を定義し、まず動的計画法により決済の順番とその最小資金量を同時に求めるアルゴリズムを検討した。しかし、決済順序が同じ銀行を二回以上通らなければならないとき、動的計画法では正しい解を求めることができなかった。このため、決済順序の列挙と決済資金量の計算を別の問題として扱うことを考え、動的計画法により可能な決済順序を列挙した上で、それぞれの決済順序に対して必要な資金量を線形計画法で計算し、その中から最小となる資金量と対応する決済順序を求めるアルゴリズムを検討した。その結果、必要な資金投入額の最小値を効率的に求めることができた。

このアイテムのアクセス数:  回

その他の情報