著者

HATOYAMA YUKIO

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.20, no.3, pp.164-181, 1977

被引用文献数

3

---

Discrete time Markov maintenance models are coupled with the theory of control of queues. Each system has an operating machine, spare machines and a repair facility. A decision maker has the option of opening or closing the repair shop when there are machines waiting for repair service, as well as the option of repairing or leaving an operating machine. A two-dimensional control limit policy is defined, and sufficient conditions for the optimality of a two-dimensional control limit policy are obtained for each model.

著者

根本 俊男 堀田 敬介

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.53, pp.90-113, 2010 (Released:2017-06-27)

参考文献数

15

被引用文献数

1

---

衆議院議員選挙の一部には小選挙区制が採用され,一票の重みの格差は2倍未満が基本と定められている.しかし,2002年再画定時の一票の重みの格差は2.054倍で,その基本は守られていない.この現状に対して批判は多く,議席数配分方式の見直しが提案されている.しかし,議席数配分だけではなく区割画定も格差に影響を与える.そのため,区割画定の影響把握が小選挙区を巡る議論では重要になる.その影響の計測法として坂口・和田(2000)により最適区割の概念が提案された.その後,実測で生じる技術面の困難が根本・堀田(2003)により克服され定量分析が実現された.その分析の結果,定数配分方式や議席数の改定では十分な格差縮小は難しく,区割線の引き方の変更にまで踏み込んだ検討が必要と現在では認識されるに至っている.そこで本論文では,区割線に関し市区郡行政界の変化と二つの県に跨る選挙区を許す県境緩和について定量的に分析し考察する.まず,市区郡行政界は平成の大合併を経て変化をした.その変化により,格差縮小の限界が2001年再画定検討時の1.977倍から5年後には2.153倍に拡大し,区割の環境は格差の観点から悪化していることを示す.次に,県境の緩和を許すことで2倍未満が達成可能であること,ただし,それには3県以上に適用する必要があることを明らかにする.さらに,道州制導入まで検討を進め,その効果の限界は1.940倍であることも提示する.これらの結果は,2011年に検討される区割再画定にて従来の区割方針に若干の見直しを加えたとしても格差2倍未満達成は不可能であることを強く示唆する.また,格差2倍未満にこだわることは,地域のつながりを崩す区割画定に直結せざるを得ない状況も示している.

著者

森田 隼史 池上 敦子 菊地 丞 山口 拓真 中山 利宏 大倉 元宏

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.54, pp.1-22, 2011 (Released:2017-06-27)

参考文献数

13

---

鉄道運賃は,基本的に乗車距離が長くなればなるほど高くなるように設定されているが,同じ距離でも,会社によって,さらには同じ会社内でも地域や路線によって異なる料金が設定されている.さらに,乗車区間によっては割引ルールや特定の運賃が設定されていることなどから,最短経路の運賃が最安になるわけではない.運賃計算では,利用者の乗車経路が明確でない場合,乗車可能経路の中から最も安い運賃となる経路を利用したとみなし,その運賃を採用するルールが設定されている.そのため,与えられた2駅間の正しい運賃を計算するためには,その2駅間の乗車可能経路の運賃を全て,もしくはその1部を列挙して判断する必要があると考えられてきた.これに対し,我々は2008年,複数の鉄道会社を含む鉄道ネットワークにおける最安運賃経路探索用ネットワークFarenetと探索アルゴリズムを提案し,これを利用した自動改札機用運賃計算エンジンの実用にいたった.本論文では,Farenet構築の基盤となった1会社内の運賃計算,具体的には,首都圏エリアで利用可能であるICカード乗車券Suica/PASMOの適用範囲に含まれるJR東日本510駅の全2駅間(129,795組)に対して行った運賃計算について報告する.4つの対キロ運賃表と複数の運賃計算ルールが存在するこの運賃計算において,異なる地域・路線を考慮した部分ネットワークとダイクストラ法を利用することにより,多くの経路を列挙する従来の運賃計算方法において数時間要していた計算を,約1秒で処理することに成功した.論文の最後では,アルゴリズムの効率を示すとともに,対象ネットワークが持つ運賃計算上の特徴についても報告する.

著者

西浦 博

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.52, pp.20-37, 2009 (Released:2017-06-27)

参考文献数

51

---

本稿は感染症の検疫期間の決定手法を提案するとともに,検疫による予防効果の考え方の理論的基礎を構築する.感染した可能性のある人に対して通常の生活から一定期間だけ分離あるいは生活行動制限をする検疫は,国内に常在しない感染症の侵入を防ぐボーダーコントロールに欠かせない感染症対策である.これまでに検疫時の医学的検査や法制度に関する議論が行なわれてきたが,具体的な検疫期間の決定手法や特定の検疫期間が与えられたときの流行拡大を防ぐ疫学的効果は詳しく検討されてこなかった.感染症流行の数理モデルを用いて,検疫が感染者侵入を防止する効果を理論的に明らかにする.まず,異なる疫学的指標によって様々な検疫の効果を検疫期間の関数として定義し,それぞれの効果の違いと必要な疫学的情報を明らかにする.これまでの検疫期間は潜伏期間のみを用いて議論されてきたが,感染しても症状を呈さない不顕性感染者を明示的に考慮することによって,より豊富な検疫期間の検討が可能なことを示す.また,様々な検疫の直接的効果を提示するだけでなく,感染者が検疫の網の目を潜り抜けて侵入した場合の流行動態も検疫期間の関数で考えることにより,検疫が侵入先に及ぼす疫学的効果を明らかにする.特に,侵入者によって流行が発生する確率と検疫による流行の遅れをモデル化する.具体的事例として新型インフルエンザを想定した数値計算例を提示し,本稿の手法が様々な感染症の検疫に関する意思決定に役立つことを示す.

著者

石井 秀昌 西野 成昭

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.64, pp.154-174, 2021 (Released:2021-09-28)

参考文献数

25

---

自己の利得最大化に反する行動を説明するモデルとして社会的選好の研究が進められてきたが,協調ゲームのように,元々好ましい状態がナッシュ均衡であるゲームに社会的選好が与える影響はわかっていない.本研究では,プレイヤが不平等回避選好を持つことで生じる協調ゲームのダイナミクスの変化を分析する.適応度として効用関数の値を用いるレプリケータダイナミクスを考え,その解析と数値計算を通して,不平等回避の強さがゲームの均衡にも,均衡に至る戦略分布のダイナミクスにも影響することを明らかにする.本研究を通して,協調ゲームでは不平等回避選好が協調状態の実現を阻害し得ること,また社会的選好がゲームに与える影響を理解する上で,ゲームの均衡だけでなくダイナミクスの分析も重要であることを示す.

著者

中桐 裕子 栗田 治

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.47, pp.83-105, 2004 (Released:2017-06-27)

参考文献数

12

被引用文献数

1 9

---

本研究では, ある商品やファッション, その他の嗜好が一瞬にして人々の間に広まり, その後短期間のうちに忘れ去られてしまうといった社会的なブームに着目し, この現象をモデル化して解析する.ある特定のブームに参加する顧客の状態を「ブーム前」, 「ブーム」, 「ブーム後」, 「定着」の4つに分割した上で, 状態を変化させる顧客の数が直前の状態にある顧客数に比例すると仮定して線形微分方程式モデルを作成し, ブーム前後の定着顧客数比やブームのピーク時刻など諸特性値を算出した.このモデルは, 我が国における「即席めん消費ブーム」, 「焼酎ブーム」や「サッカーブーム」時の実データを説明するのに有効であると結論付けられ, モデルによってブーム特性の地域差やブームによる定着顧客数の増加について定量的に説明することができた.本研究で提案したモデルは非常に簡便・単純であり, モデル拡張による適用範囲の拡大などが望める.

著者

木村 博道 秋山 英三

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.52, pp.56-81, 2009 (Released:2017-06-27)

参考文献数

16

被引用文献数

1

---

古典的な経済学では,通常,投資家は完全合理的な行動を行うと仮定する.そのような仮定をおいた理論では,市場均衡の存在を証明することが可能であるが,現実の投資家にとって重要な,スプレッド(アスクとビッドの差)やマーケットインパクト(注文に対して価格がどのぐらい変動するか)を説明することは難しい.その一方で,近年,投資家の合理性をまったく仮定せず,注文はポアソン到着に従って到着すると仮定する「ゼロインテリジェンスモデル」が提案されている(Smith et al. 2003).このモデルでは,スプレッドや価格の拡散係数を定量的に説明することが可能である(Farmer et al. 2005).しかしながら,ゼロインテリジェンスモデルでは,マーケットインパクトを表現する量の一種である,Kyleのλ(単位株数の注文に対して平均してどのぐらい価格が変動するか)を説明することはできなかった.本研究では,まず,東京証券取引所の実データを用いて,指値注文分布や直前の注文に依存して注文到着率がどのように変動するかなどの性質を調べた.次に,ゼロインテリジェンスモデルにそれらの性質を導入し,シミュレーションを行った.このモデルを「ローインテリジェンスモデル」と呼ぶことにする.その結果,ローインテリジェンスモデルでは,スプレッドや拡散係数に加えて,Kyleのλをも説明できることが分かった.このことは,金融市場の流動性を理解するには,注文と注文分布の相互作用,あるいは注文同士の相互作用が重要である可能性を示唆する.

著者

臼井 颯汰 栗野 盛光 大藤 剛宏 繁野 麻衣子

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.65, pp.1-21, 2022 (Released:2022-03-04)

参考文献数

26

---

臓器移植は,他の救命手段のない患者に,他者の健康な臓器と取り替えて機能を回復させる医療である.臓器移植は治療のための最終手段であり移植数を増やすことは重要な課題であるが,臓器を提供するドナーがいても医学的制約と社会的制約により移植不可能なことがある.社会的制約の克服方法の一つに交換移植(ドナー交換移植)があり,交換移植のシステムを導入している国も複数ある.交換移植のなかでも,レシピエントとドナーの2組の間でドナー交換をする循環型は非2部グラフ上のマッチングとして表現できる.移植数を増やすという目的に従うと,安定性の概念を大域的に拡張して要素数の多いマッチングを含むポピュラーマッチングによる交換が一つの方法となりえる.そこで,本研究では,交換移植のシステムとしてポピュラーマッチングのなかで要素数が最大のドミナントマッチングに着目し,ドミナントマッチングを求める発見的解法を示し,その方法を用いて肺移植を対象にシミュレーションをおこなう.

著者

池上 敦子 森田 隼史 山口 拓真 菊地 丞 中山 利宏 大倉 元宏

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.51, pp.1-24, 2008 (Released:2017-06-27)

参考文献数

41

被引用文献数

1 1

---

本研究では,運賃設定の異なる複数の鉄道会社を含む鉄道ネットワーク上の運賃計算を正確かつ高速に行えるネットワーク表現とアルゴリズムについて報告する.鉄道運賃は,利用者の乗車経路が明らかであるとき,多くの場合,その経路に含まれる各鉄道会社が定めた運賃を足し合わせることによって得られる.一方,利用者の乗車経路が明確でない場合,利用可能経路の中で最も安い経路を利用したとみなし,その運賃を採用することが一般的である.しかし,鉄道運賃は,基本的には「距離が長くなればなるほど高く」なるように設定されているものの,同じ距離でも,会社によって異なる料金が設定されていることや,乗車区間によって割引ルールや特別運賃が設定されていることなどから,物理的距離に基づくショーテストパスが最も安い経路になるわけではない.よって,与えられた2駅間の正しい運賃を計算するためには,その2駅間の可能経路の運賃をすべて,もしくは,その1部を列挙して比較判断する必要があることがこれまでにも報告されてきた.本研究では,物理的構造に基づくネットワーク上での経路探索を行う代わりに,ダイクストラ法が利用可能な運賃計算用ネットワークを構築し,ダイクストラ法と,少ないケースではあるがK-shortest paths問題用のアルゴリズムを利用することにより,複数社を含む鉄道ネットワーク運賃計算の大幅な高速化に成功した.

著者

泉 武志 小中 英嗣

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

TORSJ (ISSN:13498940)

巻号頁・発行日

vol.59, pp.21-37, 2016

被引用文献数

1

---

<p>本稿では2015年からJリーグが導入する2ステージ+ポストシーズン制度についてシミュレーションを行い,ポストシーズンが3,4,5チームで争われる確率がそれぞれ約62%, 35%, 3%(平均約3.4)であるとの結論を得た.</p><p>シミュレーションには対戦チームの平均得点および平均失点を反映させたモデルを使用した.平均得点および平均失点を得点に反映させるため,過去5シーズンの対戦データから回帰分析を用いてモデルを作成した.このモデルに基づき,10万シーズンのシミュレーションを計算機上で行い上記の結果を得た.</p><p>またこの結果から,新しいシステムはポストシーズン進出の条件設計が不適切であり,2ステージ制ではなく本質的には1ステージ制+ポストシーズンの制度であることを明らかにした.</p>

著者

西浦 博

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:04534514)

巻号頁・発行日

vol.52, pp.20-37, 2009

参考文献数

51

---

本稿は感染症の検疫期間の決定手法を提案するとともに,検疫による予防効果の考え方の理論的基礎を構築する.感染した可能性のある人に対して通常の生活から一定期間だけ分離あるいは生活行動制限をする検疫は,国内に常在しない感染症の侵入を防ぐボーダーコントロールに欠かせない感染症対策である.これまでに検疫時の医学的検査や法制度に関する議論が行なわれてきたが,具体的な検疫期間の決定手法や特定の検疫期間が与えられたときの流行拡大を防ぐ疫学的効果は詳しく検討されてこなかった.感染症流行の数理モデルを用いて,検疫が感染者侵入を防止する効果を理論的に明らかにする.まず,異なる疫学的指標によって様々な検疫の効果を検疫期間の関数として定義し,それぞれの効果の違いと必要な疫学的情報を明らかにする.これまでの検疫期間は潜伏期間のみを用いて議論されてきたが,感染しても症状を呈さない不顕性感染者を明示的に考慮することによって,より豊富な検疫期間の検討が可能なことを示す.また,様々な検疫の直接的効果を提示するだけでなく,感染者が検疫の網の目を潜り抜けて侵入した場合の流行動態も検疫期間の関数で考えることにより,検疫が侵入先に及ぼす疫学的効果を明らかにする.特に,侵入者によって流行が発生する確率と検疫による流行の遅れをモデル化する.具体的事例として新型インフルエンザを想定した数値計算例を提示し,本稿の手法が様々な感染症の検疫に関する意思決定に役立つことを示す.

著者

田中 克弘 山本 零

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.66, pp.1-22, 2023 (Released:2023-12-28)

参考文献数

33

---

本論文では,決定係数最大化ポートフォリオ(Maximal Predictability Portfolio: MPP) 構築問題に,離散変数を用いて記述できる銘柄数制約を加えたポートフォリオ最適化モデルを提案する.この問題は非凸型制約を含む混合整数二次計画問題として定式化されるため,良質な解を高速で得られる解法を提案する.提案解法は,既存解法の二次計画問題の求解を繰り返すアルゴリズムを応用した単純な二段階解法である.まず,銘柄数制約を加えていないMPP 構築問題から得られる解を初期解とし,次に,それを用いて銘柄数制約を加えたMPP 構築問題を求解する.更に,離散変数の削減も実施することで投資候補銘柄数が1500,シナリオ数が1000 の大規模なデータに対しても僅か数分で計算が終了することを示す.併せて,銘柄数制約を加えて構築するMPP は,銘柄数制約を加えずに構築するMPP よりも取引コストを抑制できることから,より良い投資成績となることを示す.

著者

田村 征洋 黒岩 祥太

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.52, pp.1-19, 2009 (Released:2017-06-27)

参考文献数

22

被引用文献数

1 1

---

2005年9月11日の衆議院総選挙における自民党圧勝の要因は何か.本論文では『人々にとって最も好ましい公共政策とは何か,その傾向はどのように有権者の政党支持や選挙に於ける投票に影響しているのか』を計量的に位置付けることを考え,政策に対する有権者意識に関する基礎的知見を得る為に,政策全般に対する有権者の選好傾向を調査・分析した.具体的には,政策全般へのコンジョイント分析を用いる.従来の5段階評価などは政党(全体)評価と個々の政策(個別)評価の関係を定量化することが困難であり,「軽い負担で手厚いサービス」という安直な結果に陥りやすい.現実は各政策を個別に評価(投票)するのではなく政党単位(政策の組合せ)で評価する.従って,全体評価から部分(要因)価値を定量化するコンジョイント分析は有効な手法であろう.結果は野党が掲げる理想的な政策(公共事業費の大幅な削減や消費税の現状維持,年金の一元化など)の効用値は高くなるものの政党単位で見た場合(各党の掲げる政策に近い水準を当てはめた場合)では有権者の政策に対する選好傾向にバラツキが生じ,今回の選挙結果を裏付ける有効な知見を得た.

著者

大田 靖 水谷 直樹

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.64, pp.22-45, 2021 (Released:2021-08-20)

参考文献数

26

被引用文献数

3

---

本研究では,ファッションや映画、食品などの人間社会的流行に対して,先行研究で提案された数理モデルを基に,疫学的流行を記述する数理モデルの基礎となったSIRモデル,及びマーケティングにおけるイノベータ理論を考慮し,新しい形の流行モデルを提案した.また,一過性で終わるような流行(以下,一過性タイプの流行),及び再び盛り上がりをみせるような流行(以下,再起タイプの流行)の実データを用いて,ベイズ推定のアプローチによる提案モデルのパラメータ推定を行い,さらに,実データへのフィッティングを行った.本研究で提案されたモデルによって,再起や微細な振動を表現することが可能となり,先行研究で提案された数理モデルに比べて実データへのフィッティングにおいて,その精度を大幅に高めることができた.特に,再起タイプの流行であるKitKatや本麒麟のSNSへの投稿データにおいては,多少のずれはみられるものの,明らかに先行研究のモデルでは表現できていなかった再起や微細な振動が再現された.これらの結果から,提案モデルは人間社会的流行の変遷を説明するための便利なツールであることが結論づけられた.

著者

竹原 均

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.45, no.4, pp.507-528, 2002 (Released:2017-06-27)

参考文献数

19

---

本研究ではダウンサイドリスクモデルのもとでの新たなマネージャー構造最適化モデルを提案する.論文ではまずWaring,Whitney,Pirone,Castilleにより提案されたモデルでの,収益率の正規性,マネージャー間の相関構造などの仮定が,実務上は不適切であることを株式投資信託の収益率を分析することにより示す.その上で既存のモデルでの問題点を解決するために,政策ポートフォリオからのショートフォールを考慮した最適化モデルと,リスク調整をダウンサイドリスクにより行う新しいパフォーマンス評価尺度を提案する.

著者

川名 純平 諏訪 竜也 関 庸一

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.61, pp.23-44, 2018 (Released:2018-12-27)

参考文献数

12

---

本研究では,経営主体横断的に収集されたスーパーマーケットの大規模ID付きPOSデータの分析法を提案する.これにより,店舗や顧客の販売や購買の類型をとらえ,顧客行動とその遷移傾向を明らかにする.まず,月次の商品カテゴリ上での販売額・購買額分布に注目して,これに自己組織化マップ(SOM)を適用することで,店舗販売類型,顧客行動類型を抽出する.この際,カテゴリごとの金額が桁違いであるので,Box-Cox変換を利用した.次に,店舗グループごとに,顧客の購買行動類型の構成比,月間の類型間遷移の頻度,新規顧客の加入数などに注目し,その特徴を明らかにした.その結果,顧客のロイヤリティや年齢層が異なる店舗グループの間では,米,精肉,鮮魚といった商品購買行動の傾向や遷移が異なることが明らかになった.提案法は,店舗間の顧客層の差異を発見するために有効であると考えられる.

著者

川上 幹男 楠田 浩二

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.64, pp.175-203, 2021 (Released:2021-09-28)

参考文献数

23

---

宿泊・飲食サービス業の就業者数の重回帰予測モデルを,予測高精度,速報性,説得力,政策決定支援力のEBPMに資する4要件を満たすモデルとして構築する.四半期毎に2四半期先までの就業者数を予測する平常時モデルに加え,今般の緊急事態宣言のような不測の事態の影響を織り込める非常時モデルを重回帰モデルの説明変数予測にVARモデルのインパルス応答分析を利用して構築する.非常時モデルは就業者数が世界金融危機時以来の低水準にまで低下することを予測しており,当該業界向けの支援策が喫緊の課題であることを示している.

著者

池田 欽一 時永 祥三

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.42, no.1, pp.18-31, 1999 (Released:2017-06-27)

参考文献数

11

被引用文献数

1 2

---

本論文では, まずフラクタル性をもつ時系列のインパルス応答関数をスケール関数により近似的に展開した場合に, 時間軸方向にインパルス応答を伸長することにより予測が行える原理について説明し, 予測誤差などについて整理する. 次に, フラクタル性をもつ時系列について, フラクタル次元が未知である場合に, 時系列をウェーブレット変換係数から計算できる方法を整理する. これらを現実の株価時系列へと適用して, 株価予測誤差の検討, フラクタル性, その次元推定について述べる. 具体的な応用例として株価のオプション取引のシミュレーションをとりあげ, 本論文の予測手法とこれに基づくオプション戦略の有効性について示している.

著者

大槻 知史 愛須 英之 田中 俊明

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.53, pp.30-55, 2010 (Released:2017-06-27)

参考文献数

13

被引用文献数

2 2

---

現在多くの鉄道事業者では,経験豊富な熟練者が膨大な時間を割いて一定期間の車両運用の基本計画を作成し,またダイヤ乱れが発生する度に計画修正している.本稿ではこの車両運用計画作成の自動化を目的とする制約充足解法を提案し,実問題に基づく評価では汎用ソルバーCPLEXよりも高速に求解できることを確認した.また提案解法は基本計画作成・修正計画作成のいずれにも利用可能であり,かつ評価関数の設計の自由度が高いため,多くの鉄道事業者に対し適用可能な汎用解法となる可能性がある.

著者

藤重 悟

出版者

公益社団法人 日本オペレーションズ・リサーチ学会

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.21, no.2, pp.189-204, 1978

被引用文献数

1 30

---

G(V、A^*;V_1、V_2)を、点集合V、枝集合A^*、および、"入口"V_1(⊆V)、"出口"V_2(⊆7)をもつグラフとする。簡単のためV_1∩V_2:φとしておく。グラフGの各枝αには、その容量c(α)と単位流量当りの費用γ(a)とが付与されているとする。さらに、人ロV_1と出口V_2上に、それぞれ、ホリマトロイドP_1(V_1、ρ_1)、P_2(V_2、ρ_2)が定義されているとする。以上の諸量の定義されたグラフをネットワークNと呼ぶことにする。N上の"独立流れ"とは、各枝の容量条件を満たす入口V_1から出口V_2へのG上の流れであり、かつ、V_1への流入ベクトルがP_1の、V_2からの流出ベクトルがP_2の、それぞれ、独立ベクトルであるようなものである。ただし、V_1への流入ベクトルとは、各v^εV_1にvへの流入量を対応づけるベクトルである(流出ベクトルについても同様)。"独立流れ問題"とは、(1)N上の最大独立流れ(すなわち、V_1からV_2への最大流量をもつN上の独立流れ)を見出す問題、および、(2)N上の最大独立流れのうちで費用が最小であるものを見出す問題、のことである。本論文では、与えられた独立流れに関連して定義される補助ネットワークを用いて独立流れ問題を解く算法を提示する。プライマル・デュアルな形の算法は概略つぎのようである。N上のある独立流れから出発して、補助ネットワーク上の最短路を見出し、それに基づいて流れを変更し、流量が増加した新たな独立流れ(問題(2)の場合は同じ流量をもつ独立流れのうちで最小費用の独立流れ)を得る。さらに、得られた独立流れに関連する補助ネットワ-クを構成し、以上の手続きを繰返す。問題(2)に対しては、プライマルな形の算法も提示してある。これらの算法を導出する過程において、最大独立流れや最小費用の最大独立流れを特徴づけるいくつかの命題が、構成的に証明される。複数個の(ポリ)マトロイドが関係するような、今までに提起されている問題のうちの多くは、独立流れ問題として"自然な形で定式化される。ネットワーク流れ問題としての定式化が多くの組合せ的問題に対して有効であったのと同様に、独立流れ問題としての定式化が(ポリ)マトロイド的な組合せ的問題に対して有効である。なお、パラメタc(a)(a^εA*)、ρi(A)(A⊆V i;i=1、2)が可約な場合、本論文で提示した算法は有限回の操作の後に終了し解を与える。一般の独立流れ問題に対し本論文で提示した算法が有限回の操作の後に終了するか否かの問題、有限回で終了するとすればその手間の評価の問題、などは今後に残された課題である。