WEKO3
アイテム
動的ネットワーク表現に基づく列車・航空便の最適乗継系列探索の手法とその実際への応用
https://ipsj.ixsq.nii.ac.jp/records/13440
https://ipsj.ixsq.nii.ac.jp/records/134400ebcaf93-7e3d-46fc-bcad-6fe75db076ee
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 1997 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | Journal(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 1997-04-15 | |||||||
タイトル | ||||||||
タイトル | 動的ネットワーク表現に基づく列車・航空便の最適乗継系列探索の手法とその実際への応用 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | A Method for Finding the Optimal Transfer Sequences of Trains and Airplanes Based on the Dynamic Network Representation and Its Application to a Practical Problem | |||||||
言語 | ||||||||
言語 | jpn | |||||||
キーワード | ||||||||
主題Scheme | Other | |||||||
主題 | 論文 | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
資源タイプ | journal article | |||||||
その他タイトル | ||||||||
その他のタイトル | 応用 | |||||||
著者所属 | ||||||||
上智大学理工学部電気電子工学科 | ||||||||
著者所属 | ||||||||
日本電気株式会社情報メディア研究所 | ||||||||
著者所属 | ||||||||
上智大学理工学部電気電子工学科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Electrical and Electronics Engineering, Sophia University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Information Technology Research Laboratories, NEC Corporation | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Department of Electrical and Electronics Engineering, Sophia University | ||||||||
著者名 |
菊池, 新
× 菊池, 新
|
|||||||
著者名(英) |
Shin, Kikuchi
× Shin, Kikuchi
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 近年,公共交通網の発達にともない,時刻表を考慮に入れて任意の出発地から任意の目的地に至る最適な経路を見い出すこと,すなわち動的最適経路問題を人手で解くことは困難になりつつある.このような動的最適経路問題を解くため,従来からネットワークに時間の概念を導入する手法および近似解を与える方法がいくつか提案されてきている.しかし,厳密な最適解を効率良く求める手法はいまだ与えられていなかった.本論文の目的はこのような問題を解決するべく空間と時間を一体化してコンパクトに表現する動的ネットワークと名付けた新しい概念を提案することにある.これによりネットワーク規模は縮小され,したがって使用するメモリ量ひいては計算所要時間を減少させることができる.最適解の探索は,本文中で定義する出発地出発時刻を逐次継承した動的ネットワークを生成した後,継承した出発地出発時刻を活用して条件を満たす最適乗継系列を分岐限定法を用いて後方向探索することにより実行される.さらに,ここで提案した探索手法を用いて,日本全国の私鉄を含む9,015の駅ならび空港のいずれかを出発地あるいは目的地として指定したとき,航空機,新幹線特急,JR在来線特急の時刻表を考慮に入れて,最適乗継系列を実際に探索するシステムをパーソナルコンピュータを用いて試作した例について述べ,ここで提案した探索手法の有効性を示している. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | In recent years,the public transportation networks have made remarkable progress,so that one cannot easily find the optimal transfer sequence from his origin to his destination.While several methods for introducing the concept of time into networks and for giving suboptimal solutions have been proposed,they are not necessarily satisfactory.The authors have been engaged in developing a method and a system which provides the optimal transfer sequences of the trains and the airplanes with the timetables taken into account.In this paper,we introduce a novel concept of the dynamic network which compactly represents the spatial factor and the temporal factor together.Using this dynamic network representation,the authors give a novel and efficient algorithm for finding the strictly optimal solutions which employs the forward deduction using the timetable constraint and the backward induction using a branch and bound method.Furthermore,an optimal transfer sequence searching system for the airplanes and the limited expresses of the Sinkansen and the JR local lines has been developed using a personal computer,in which any one of 9,015 stations and airports can be chosen as an origin or a destination.The memory capacity and the CPU time required to obtaion the optimal transfer sequences is quite reasonable,which reveals that the algorithm and the system is of practical use. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN00116647 | |||||||
書誌情報 |
情報処理学会論文誌 巻 38, 号 4, p. 915-926, 発行日 1997-04-15 |
|||||||
ISSN | ||||||||
収録物識別子タイプ | ISSN | |||||||
収録物識別子 | 1882-7764 |