A FARE CALCULATION ALGORITHM FOR RAILWAY NETWORKS : A CASE STUDY INVOLVING 510 JR STATIONS WITHIN THE SUICA/PASMO SYSTEM

DOI Web Site Web Site 15 References

Bibliographic Information

Other Title
  • 鉄道運賃計算アルゴリズム : Suica/PASMO利用可能範囲のJR東日本510駅の運賃を対象とした場合
  • テツドウ ウンチン ケイサン アルゴリズム : Suica/PASMO リヨウ カノウ ハンイ ノ JR ヒガシニホン 510エキ ノ ウンチン オ タイショウ ト シタ バアイ

Search this article

Abstract

A railway fare for a specific path is usually determined by the distance, i.e. the longer the distance, the higher the fare. The fare rate, however, is sometimes different by area even within the same railway company. In addition, many of companies have additional rules to be used in the fare calculation, e.g. discounts for specific paths. In order to calculate the fare between a given pair of stations, we have to find the minimum cost path, but the shortest path (in the physical sense) is not always the minimum cost path for the reasons mentioned above. In the past, most of the efforts have been focused on an 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. This approach has inevitably led to a problem of a very large computational time. In this paper, we propose a much more efficient algorithm which basically uses the Dijkstra's algorithm with a modification which reflects the existence of a set of subnetworks which have their own fare rates. Our algorithm dramatically reduces the computational time, because the algorithm need not enumerate a large number of paths for every pair of stations.

Journal

References(15)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top