Finding routes in a public transport network. A case study

摘要

There is a need for reliable and trustworthy public transport planner services. Mass transits are trying to solve problems as traffic jams or increasing pollution in densely populated city agglomerations. Passengers are looking for travel information on-line and companies providing public transport solutions often struggle with providing modern trip planner platforms. We address this problem by providing simple and easy to implement solution for shortest paths computation in public transport network of any size. In first part of the paper we present our approach to building time-expanded graph model of public transportation network. We use a structure with multiple vertices within one stop identified by triple (stop, time, line) and edges with constant travel times. Second part introduces k-shortest paths algorithm for created graph. We provide step by step explanation along with code samples. Average algorithm response time is around 1.5s for a public transport network of the size over 2800 stops. This is accepted query time for a web application. None additional speed-up techniques has been used to keep implementation and explanations simple and leaving room for further improvements. Algorithm has been successfully tested in Upper Silesian Industrial District (GOP) in cooperation with main public transport provider in the area (KZK GOP). This real instance is the biggest one in Poland and contains 370 lines and over 2800 stops.