社団法人 日本オペレーションズ・リサーチ学会
ENGLISH
入会申込み お問合わせ
HOME オペレーションズ・リサーチ学会とは 研究活動案内 OR事典Wiki 機関誌 論文誌 会員の方へ
活動概要
会長挨拶
支部紹介
 
HOME  > 論文誌 > 論文誌目次 
TORSJ 54 和文概要とキーワード
 
1. 鉄道運賃計算アルゴリズム― Suica/PASMO利用可能範囲のJR東日本510駅の運賃を対象とした場合―
森田 隼史(日本信号(株)), 池上 敦子(成蹊大学)
菊地 丞, 山口 拓真中山 利宏(日本信号(株)), 大倉 元宏(成蹊大学)
概要
鉄道運賃は,基本的に乗車距離が長くなればなるほど高くなるように設定されているが,同じ距離でも,会社によって,さらには同じ会社内でも地域や路線によって異なる料金が設定されている.さらに,乗車区間によっては割引ルールや特定の運賃が設定されていることなどから,最短経路の運賃が最安になるわけではない.運賃計算では,利用者の乗車経路が明確でない場合,乗車可能経路の中から最も安い運賃となる経路を利用したとみなし,その運賃を採用するルールが設定されている.そのため,与えられた2駅間の正しい運賃を計算するためには,その2駅間の乗車可能経路の運賃を全て,もしくはその1 部を列挙して判断する必要があると考えられてきた.これに対し,我々は2008 年,複数の鉄道会社を含む鉄道ネットワークにおける最安運賃経路探索用ネットワークFarenet と探索アルゴリズムを提案し,これを利用した自動改札機用運賃計算エンジンの実用にいたった.本論文では,Farenet 構築の基盤となった1 会社内の運賃計算,具体的には,首都圏エリアで利用可能であるIC カード乗車券Suica/PASMO の適用範囲に含まれるJR 東日本510 駅の全2駅間(129,795 組)に対して行った運賃計算について報告する.4つの対キロ運賃表と複数の運賃計算ルールが存在するこの運賃計算において,異なる地域・路線を考慮した部分ネットワークとダイクストラ法を利用することにより,多くの経路を列挙する従来の運賃計算方法において数時間要していた計算を,約1秒で処理することに成功した.論文の最後では,アルゴリズムの効率を示すとともに,対象ネットワークが持つ運賃計算上の特徴についても報告する.
キーワード
交通、鉄道ネットワーク、運賃計算、最短経路問題
ページトップへ戻る
2. 企業価値変動モデルとCVaRを用いた与信ポートフォリオ最適化問題とその効率的解法
後藤 順哉(中央大学), 高野 祐一(東京工業大学), 山本 芳嗣(筑波大学), 和田 保乃(みずほ第一FT(株)
概要
本論文では,東証業種別株価指数の推移データに因子分析を施した結果を用いて企業価値変動モデルを構築し,それに基づいてデフォルトのシナリオを発生させ,リスク尺度としてConditional Value-at-Riskを用いて与信の最適化を行った.これにより経済動向を示す共通因子の影響を,「共通因子の個数」と「共通因子と個別因子の影響の比を決めるパラメータ」の両者を変化させて観察した.解くべき最適化問題の規模はシナリオの個数に影響を受けるため,多数のシナリオを用いて問題を解くことは易しくないが,問題の構造を利用して,簡単な前処理と解法の工夫によって10万シナリオの問題を7秒程度で,50万シナリオの問題を35秒程度で解くことに成功した.
キーワード
線形計画、リスク管理、与信ポートフォリオ、Conditional Value-at-Risk,  企業価値変動モデル
ページトップへ戻る
3. 間引きシステム入力待ち行列の解析
藤原 飛一、 紀 一誠(神奈川大学)
概要
本論文では,Poisson過程で到着する客をある2つの窓口AとBに振り分ける問題について考える.このとき,負荷が均等になるように振り分けたとしても,振り分け方の相違により,到着時間間隔分布が異なるため,待ち時間は異なってくる.本稿ではこの問題を($m$-$n$)間引き入力待ち行列モデルとして考察をおこない,特に(2-2)間引き振り分け規則の場合における待ち時間への影響を調べる.この入力過程における客の到着時間間隔は互いに独立な確率変数列とはならない.解析に際しては古典的な位相法,母関数法,Rouch$\acute{\mathrm{e}}$の定理およびSturmの定理を用いることにより,系内客数分布および待ち時間の期待値等に関する厳密解を導く.
キーワード
待ち行列,マルコフ過程,G/M/1,位相法,母関数法,Rouch$\acute{\mathrm{e}}$ の定理
ページトップへ戻る

4. 大規模最短路問題に対するダイクストラ法の高速化
安井雄一郎、藤澤克樹、笹島啓史 (中央大学),
後藤和茂(マイクロソフト)

概要
最短路問題はネットワーク上の経路探索などの多くの応用を持ち,また他の最適化問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.最短路問題に対する解法としてはダイクストラ法などの安定的かつ効率的な高速アルゴリズムが存在するが,実問題は非常に大規模になるためさらなる高速化が不可欠である.そこで本論文では大規模最短路問題に対し,計算機のメモリ階層構造を考慮しつつ汎用的かつ効率的に高速化を行うための実装方法を示す.さらに論文中では計算機のメモリ階層構造における律速箇所の特定を行うための汎用的な解析方法を示し,高速化の有用性を検証していく.本手法により実装されたバイナリ・ヒープを適用したダイクストラ法は,実行性能,安定性,メモリ要求量などを他の実装と比較すると総合的に最も優れているといえる.また本実装を用いた大規模最短路問題に対するオンライン・ソルバーについても説明を行う.
キーワード
アルゴリズム,グラフ理論,計算機,最適化,情報技術,ネットワークフロー
ページトップへ戻る
HOMEに戻る
イベントカレンダー
2017年度第3回ORセミナー
日程:
2017年10月7日(土)
場所:
㈱構造計画研究所

2017年度第4回ORセミナー
日程:
2018年1月20日(土)
場所:
南山大学
シンポジウム
2018年春季シンポジウム
日程:
2018年3月14日(水)
場所:
東海大学

2018年秋季シンポジウム
日程:
2018年9月5日(水)(予定)
場所:
名古屋市立大学
研究発表会
2018年春季研究発表会
日程:
2018年3月15日(木)-16日(金)
場所:
東海大学

2018年秋季研究発表会
日程:
2018年9月6日(木)-7日(金)(予定)
場所:
名古屋市立大学