Efficient algorithms to find optimal paths in a public transportation network

This paper, studies problems related to public transportation routing in Singapore. Given a start point S and a destination D, the transportation routing problem is to find rides (using public transportation, namely bus/train) with the minimum cost, the minimum travelling time, or the minimum number of transfers (1) from S to D. The paper models the domain succinctly using directed acyclic graphs and provide efficient algorithms to solve the above problems. In addition, it shows that the problem of finding the best ride with a combination of cost, time and transfers in NP-hard and provide an effective algorithm for the problem.