文献

J-GLOBAL ID：201502207797065165   整理番号：15A1085098

大都市近郊区間の経路の効率的な列挙と検索

著者 (2件)： 堀山貴史 (埼玉大) ,  羽室行信 (関西学院大)
資料名： オペレーションズ・リサーチ
巻： 60  号： 10  ページ： 600-607  発行年： 2015年10月01日 
JST資料番号： F0251A  ISSN： 0030-3674  CODEN： OPREA  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： JR各社が定める「大都市近郊区間」内では,出発駅・到着駅の間の最短距離によって運賃が決められ,乗車経路は同じ駅を2度通らなければ自由に選択できる。たとえば,東京駅から隣の有楽町駅までには4,152,859通りの経路がある。乗客は,そうした膨大な経路の中から,各自の好みに合わせて経路を選択している。本稿では,ZDD(Zero-suppressed Binary Decision Diagram;ゼロサプレス型二分決定グラフ)を利用して,与えられたグラフ中の経路を効率的に列挙する方法を紹介する。また,列挙された経路を実行可能解として,異なる目的関数ごとに最小化問題や最大化問題を何度も簡単に解き直す方法について述べる。そして,東京近郊区間の例を中心に,経由する単線区間が最多となる経路などを紹介する。(著者抄録)

シソーラス用語： 近郊鉄道 ,  東京都 ,  *都市郊外 ,  *経路探索 ,  組合せ ,  *二分決定グラフ ,  索引作成 ,  組合せ問題 ,  グラフ理論 ,  部分集合 ,  順路問題 ,  有向グラフ ,  閉路
準シソーラス用語： ZDD ,  経路問題 ,  *都市近郊

分類 (2件)： 輸送と業務  (TC01030N) ,  グラフ理論基礎  (IA02020S)

引用文献 (6件)：

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Combinatorial Algorithms: Part 1, Addison-Wesley Professional, 2011.
• J. Kawahara, T. Inoue, H. Iwashita and S. Minato, ”Frontier-based search for enumerating all constrained subgraphs with compressed representation,” Technical Report TCS-TR-A-14-76, Division of Computer Science, Hokkaido University 2014.
• 湊真一ら, 特集 BDD/ZDDを用いた新しい列挙索引化技法(フロンティア法)とその応用, オペレーションズ・リサーチ: 経営の科学, 57, pp.596-628, 2012.
• 湊真一(編), 『ERATO 湊離散構造処理系プロジェクト,超高速グラフ列挙アルゴリズム-〈フカシギの数え方〉が拓く,組合せ問題への新アプローチ-』, 森北出版, 2015.
• JR時刻表, 2014年1月号, 交通新聞社, 2014.

タイトルに関連する用語 (3件)： 都市近郊 ,  経路 ,  検索