敗者復活型分岐限定法による首都圏電車網第 k 最低料金経路探索システム

• Item type: SIG Technical Reports(1)
• 公開日: 1987-07-15
• タイトル: 敗者復活型分岐限定法による首都圏電車網第 k 最低料金経路探索システム
• タイトル / 言語: en
• タイトル: The k - th Minimal Fare Route Search System for the Metropolitan Railway Networks through "The Revival - type Branch and Bound Method"
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 上智大学理工学部電気・電子工学科
• 著者所属: 上智大学理工学部電気・電子工学科
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Sophia University
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Sophia University
• 著者名: 加藤誠巳; 吉野, 美喜男
• 著者名(英): Masami, Kato; Mikio, Yoshino
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 首都圏の電車網は近年極めて複雑化し、出発駅と目的駅の間に多数の経路が考えられるようになった。更に運賃については、JRと他の私鉄・地下鉄との格差が広がり、利用者が距離的に短い経路を選択しても、その経路が必ずしも安い経路であるとは限らない状態になっている。このため短時間、低料金かつ少ない乗り換え回数で目的駅に行くことができる経路を探索することが望まれる。本稿では、最適経路の一つとして考慮すべきである第k最低料金経路の探索手法と、これを実際に首都圏電車網に適用した結果について御報告する。既に御報告した手法では最低(k=1)料金経路のみの探索であったが、これを改良した”敗者復活型分岐限定法”と名付けた手法によって第k番目まで最低料金経路の探索を可能としている。敗者復活型分岐限定法は、枝刈りを使用した分岐限定法の拡張であり、枝刈りの利点を生かしたまま第k番目までの最適解を探索する手法である。本手法は効率の良い枝刈り・枝止めにより枝が爆発的に増大することを回避できるので、料金経路探索だけでなく、他の第k番目までの最適解を求めたい応用用途にも適用可能であると考えられる。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently the railway networks around Tokyo area have become so complicated that a casual passenger cannot find the optimum route from his station of origin to that of destination. The authors have already proposed a system for finding the minimal fare route in such networks. That system, however, cannot give the second best one. In this paper, a system for searching the k-th minimal fare route is proposed, which advantageously employs a method designated as "the revival-type branch and bound method". Several minimal fare routes are demonstrated as example.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11253943
• 書誌情報: 情報処理学会研究報告情報システムと社会環境（IS）; 巻 1987, 号 49(1987-IS-015), p. 1-10, 発行日 1987-07-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会