Finding the minimum cost path for a railway fare calculation: a case study involving more than one railway company

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.