動的ネットワーク表現に基づく列車・航空便の最適乗継系列探索の手法とその実際への応用

情報処理学会 Web Site 被引用文献3件 参考文献12件

書誌事項

タイトル別名
  • ドウテキ ネットワーク ヒョウゲン ニ モトズク レッシャ コウクウビン ノ
  • 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
  • 応用

この論文をさがす

抄録

近年，公共交通網の発達にともない，時刻表を考慮に入れて任意の出発地から任意の目的地に至る最適な経路を見い出すこと，すなわち動的最適経路問題を人手で解くことは困難になりつつある．このような動的最適経路問題を解くため，従来からネットワークに時間の概念を導入する手法および近似解を与える方法がいくつか提案されてきている．しかし，厳密な最適解を効率良く求める手法はいまだ与えられていなかった．本論文の目的はこのような問題を解決するべく空間と時間を一体化してコンパクトに表現する動的ネットワークと名付けた新しい概念を提案することにある．これによりネットワーク規模は縮小され，したがって使用するメモリ量ひいては計算所要時間を減少させることができる．最適解の探索は，本文中で定義する出発地出発時刻を逐次継承した動的ネットワークを生成した後，継承した出発地出発時刻を活用して条件を満たす最適乗継系列を分岐限定法を用いて後方向探索することにより実行される．さらに，ここで提案した探索手法を用いて，日本全国の私鉄を含む9，015の駅ならび空港のいずれかを出発地あるいは目的地として指定したとき，航空機，新幹線特急，JR在来線特急の時刻表を考慮に入れて，最適乗継系列を実際に探索するシステムをパーソナルコンピュータを用いて試作した例について述べ，ここで提案した探索手法の有効性を示している．

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.

収録刊行物

被引用文献 (3)*注記

もっと見る

参考文献 (12)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ