FINDING THE MINIMUM COST PATH FOR A RAILWAY FARE CALCULATION : A CASE STUDY INVOLVING MORE THAN ONE RAILWAY COMPANY

Ikegami Atsuko, Morita Shunji, Yamaguchi Takuma, Kikuchi Jo, Nakayama Toshihiro, Ohkura Motohiro

doi:10.15807/torsj.51.1

Bibliographic Information

Other Title

鉄道運賃計算のための最安運賃経路探索 : 複数の鉄道会社を含む場合
テツドウウンチンケイサンノタメノサイアンウンチンケイロタンサクフクスウノテツドウガイシャオフクムバアイ

Search this article

Description

When calculating the fare between a given pair of stations, the minimum cost path from among the many feasible paths between the stations must be determined. The railway fare for a specific path is usually calculated by distance, i.e. the longer the distance, the higher the fare. The fare rate, however, differs between railway companies and there are additional rules to be used in the fare calculation, e.g. discounts for specific paths. Therefore, the shortest-distance path is not always the minimum cost path. Most previous research efforts have focused on the enumeration of feasible paths between a pair of stations and a comparison of their resulting fares in order to choose the minimum fare for the pair. Using this approach, computational time is inevitably long. In this paper, we propose some network representations for the fare calculation of a railway network and use an efficient algorithm based on Dijkstra's algorithm to calculate fares between all pairs of 1638 stations in the area where IC-ticket (Suica/Pasmo) is usable. Our algorithm reduces the computational time because the algorithm need not enumerate a large number of paths for every pair of stations.

Journal

Transactions of the Operations Research Society of Japan

Transactions of the Operations Research Society of Japan 51 (0), 1-24, 2008

The Operations Research Society of Japan

Keywords

Details 詳細情報について

Export

Report a problem