Optimal route computation for circular public transport routes with differential fare structure

In many public transport information systems, route searching for pre-trip journey planning is an essential and important function. While different types of route query and path finding algorithms have been proposed to solve the problem of optimum route or path searching, there remains no single answer to the best solution for all public transportation networks in the world. As a result, customization of the optimum route computation is needed. In this paper, a structural analysis of public transport routes in terms of fare and operation patterns has been conducted. An enhanced route computation algorithm has been proposed in order to provide more reasonable and logical results for different structures. The development and implementation of the programming logic, together with the validation of the enhanced algorithm are also presented. It is found that the traditional approach of selecting closest stops to origin, destination or interchange stops may not satisfy all patterns, especially for cities with a very dense network of public transport stops and for circular routes. To cater for a lot of these special cases, the new approach of stop selection adopts a comparison of the stop sequence within a route with a threshold of commuting behaviour. Real cases from a governmental public transportation enquiry system in Hong Kong are extracted for implementation and evaluation; results from which have been proved satisfactory to both system planners and users.